提出新维度刻画多分类可学习性，解决宽容0-1损失的理论问题。
Characterizing the Multiclass Learnability of Forgiving 0-1 Loss Functions
- 基于Natarajan维数构造新组合维度
- 该维度有限当且仅当模型可学习
- 适用于集合反馈、列表学习等场景
本文研究了在输出和标签空间有效有限的多分类设置下，宽容0-1损失函数的可学习性。为此，我们提出了一个基于Natarajan维数的新组合维度，并证明：在该设定中，假设类可学习当且仅当这一广义Natarajan维数为有限值。此外，我们展示了该维度还能刻画其他已知学习设定，例如大量集合值反馈的实例以及修改版的列表学习。
原文摘要 · Abstract (English)
In this paper we will give a characterization of the learnability of forgiving 0-1 loss functions in the multiclass setting with effectively finite cardinality of the output and label space. To do this, we create a new combinatorial dimension that is based off of the Natarajan Dimension and we show that a hypothesis class is learnable in our setting if and only if this Generalized Natarajan Dimension is finite. We also show how this dimension characterizes other known learning settings such as a vast amount of instantiations of learning with set-valued feedback and a modified version of list learning.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。