论文标题
关于可计算学习者的可学习性表征
On characterizations of learnability with computable learners
论文作者
论文摘要
我们研究了Agarwal等人介绍的可计算PAC（CPAC）学习。 （2020）。首先，我们考虑了发现适当和不当CPAC学习的特征的主要开放问题。我们给出了强大CPAC学习密切相关的概念的特征，并为Agarwal等人提出的柯尔特开放问题提供了负面答案。 （2021）所有可决定的VC类是否都是不适当的CPAC。其次，我们考虑（可计算）PAC可学习性的不可证明。我们给出了一个简单的一般论点，可以表现出这种方法，并开始研究可学习性的算术复杂性。我们简要讨论了Ben-David等人的不可证明性结果的关系。 （2019年），这激发了Agarwal等人的工作。
We study computable PAC (CPAC) learning as introduced by Agarwal et al. (2020). First, we consider the main open question of finding characterizations of proper and improper CPAC learning. We give a characterization of a closely related notion of strong CPAC learning, and provide a negative answer to the COLT open problem posed by Agarwal et al. (2021) whether all decidably representable VC classes are improperly CPAC learnable. Second, we consider undecidability of (computable) PAC learnability. We give a simple general argument to exhibit such ndecidability, and initiate a study of the arithmetical complexity of learnability. We briefly discuss the relation to the undecidability result of Ben-David et al. (2019), that motivated the work of Agarwal et al.
