计算学习中，可计算的模型能识别递归可枚举类，但需重新定义学习理论。
Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning
- 用递归可枚举类表示学习类，构建可计算学习框架
- 有效VC维可无限大，即使在递归可枚举类中也成立
- 适合研究可计算学习理论的学者，特别是形式化学习者
我们研究可计算的大概率近似正确（CPAC）学习，其中学习器必须是可计算函数。先前发现经典统计学习基本定理——通过VC维有限性刻画PAC可学习性——在此框架下不再成立。近期工作通过引入有效VC维，在可计算设定中恢复了类似定理。本文基于此，探讨CPAC学习与递归可枚举可表示（RER）类之间的关系。结果显示，即使对于RER类，有效VC维也可取任意大于传统值的数值，从而生成一系列（非）例子用于不同形式的CPAC学习。然而，对于满足强条件的CPAC学习，两个维度一致。此外，我们发现CPAC学习性可通过包含实现相同样本的RER类来表征；若学习类具有唯一识别性，则必为RER类。最后，通过引入非均匀CPAC学习这一宽松概念，证明对RER类可保证抗噪声学习能力。
原文摘要 · Abstract (English)
We study computable probably approximately correct (CPAC) learning, where learners are required to be computable functions. It had been previously observed that the Fundamental Theorem of Statistical Learning, which characterizes PAC learnability by finiteness of the Vapnik-Chervonenkis (VC-)dimension, no longer holds in this framework. Recent works recovered analogs of the Fundamental Theorem in the computable setting, for instance by introducing an effective VC-dimension. Guided by this, we investigate the connection between CPAC learning and recursively enumerable representable (RER) classes, whose members can be algorithmically listed. Our results show that the effective VC-dimensions can take arbitrary values above the traditional one, even for RER classes, which creates a whole family of (non-)examples for various notions of CPAC learning. Yet the two dimensions coincide for classes satisfying sufficiently strong notions of CPAC learning. We then observe that CPAC learnability can also be characterized via containment of RER classes that realize the same samples. Furthermore, it is shown that CPAC learnable classes satisfying a unique identification property are necessarily RER. Finally, we establish that agnostic learnability can be guaranteed for RER classes, by considering the relaxed notion of nonuniform CPAC learning.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。