Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning
David Kattermann, Lothar Sebastian Krapp
我们学习可计算可能大致正确(CPAC)学习,其中学习者必须是可计算功能。 以前观察到,统计学习的基本定理,其特征是Vapnik-Chervonenkis(VC-)尺寸的有限性,不再在这个框架中存在。 最近的作品在可计算设置中恢复了基本定理的类似物,例如引入了有效的VC-dimension。 以此为指导,我们研究了CPAC学习和递归可枚举可表示(RER)类之间的联系,这些类的成员可以算法列出。 我们的结果表明,有效的VC-dimensions可以将任意值高于传统值,即使是RER类,它为CPAC学习的各种概念创造了一个完整的(非)示例。 然而,这两个维度与满足CPAC学习足够强烈概念的课程相吻合。 然后,我们观察到CPAC可学习性也可以通过包含实现相同样本的RER类来表征。 此外,表明满足唯一识别属性的CPAC可学习类必然是RER。 最后,我们确定,通过考虑非统一CPAC学习的轻松概念,可以保证RER类的不可知论可学习性。
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 in...
