提出可计算多分类学习的判定标准，解决理论可学习性与实际计算能力的矛盾。
On the Computability of Multiclass PAC Learning
- 定义可计算版本的Natarajan维数，刻画有限标签下的可计算学习性。
- 证明可计算区分器维度能统一表征多种学习情形的可计算性。
- 揭示无限标签下经典DS维无法用区分器表达，凸显计算限制边界。
本文研究在Valiant（1984）提出的概率近似正确（PAC）学习框架下，多分类学习的可计算性问题。在Agarwal等（2020）提出的可计算PAC（CPAC）框架中，学习者及其输出函数均需为可计算函数。针对有限标签空间的情形，我们提出了可计算版的Natarajan维数，并证明其完全刻画了该设定下的CPAC可学习性。进一步，我们建立了一个关于可计算区分器维度的元特征刻画：区分器由Ben-David等（1992）定义，是标签空间的特定嵌入形式，每种嵌入对应一个维度；在非可计算设置中，这些维度的有限性等价于多分类PAC可学习性。我们证明，在可计算设置中，对应的可计算维度同样刻画了CPAC学习性。最后，我们证明：尽管在有限标签空间下，用于刻画无限标签空间下PAC可学习性的DS维，无法表示为任何区分器形式，从而揭示了计算限制的深层边界。
原文摘要 · Abstract (English)
We study the problem of computable multiclass learnability within the Probably Approximately Correct (PAC) learning framework of Valiant (1984). In the recently introduced computable PAC (CPAC) learning framework of Agarwal et al. (2020), both learners and the functions they output are required to be computable. We focus on the case of finite label space and start by proposing a computable version of the Natarajan dimension and showing that it characterizes CPAC learnability in this setting. We further generalize this result by establishing a meta-characterization of CPAC learnability for a certain family of dimensions: computable distinguishers. Distinguishers were defined by Ben-David et al. (1992) as a certain family of embeddings of the label space, with each embedding giving rise to a dimension. It was shown that the finiteness of each such dimension characterizes multiclass PAC learnability for finite label space in the non-computable setting. We show that the corresponding computable dimensions for distinguishers characterize CPAC learning. We conclude our analysis by proving that the DS dimension, which characterizes PAC learnability for infinite label space, cannot be expressed as a distinguisher (even in the case of finite label space).
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。