用星形多面体边界做二分类，可精确分析模型复杂度与优化特性。
How to Learn a Star: Binary Classification with Starshaped Polyhedral Sets
- 基于固定剖分的分段线性函数，决策边界为星形多面体
- 给出模型VC维上界，离散损失的解集对应超平面排列的胞腔
- 对数似然损失最优解唯一性条件明确，随参数变化几何结构清晰
我们研究一类受限于连续分段线性函数的二分类问题，其决策边界为（可能非凸）星形多面体集，定义在固定的多面体单纯扇上。本文分析该函数类的表达能力，刻画两种损失函数下的损失景观：0/1损失（离散损失）和对数似然损失。特别地，给出了该模型的VC维显式上界，并将离散损失的子水平集明确描述为超平面排列中的胞腔。对于对数似然损失，给出了最优解唯一的充分条件，并描述了在改变底层指数分布速率参数时最优解的几何结构变化。
原文摘要 · Abstract (English)
We consider binary classification restricted to a class of continuous piecewise linear functions whose decision boundaries are (possibly nonconvex) starshaped polyhedral sets, supported on a fixed polyhedral simplicial fan. We investigate the expressivity of these function classes and describe the combinatorial and geometric structure of the loss landscape, most prominently the sublevel sets, for two loss-functions: the 0/1-loss (discrete loss) and a log-likelihood loss function. In particular, we give explicit bounds on the VC dimension of this model, and concretely describe the sublevel sets of the discrete loss as chambers in a hyperplane arrangement. For the log-likelihood loss, we give sufficient conditions for the optimum to be unique, and describe the geometry of the optimum when varying the rate parameter of the underlying exponential probability distribution.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。