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 we provide a negative answer to the open problem posed by Agarwal et al. (2021) whether all decidable PAC learnable classes are improperly CPAC learnable. Second, we consider undecidability of (computable) PAC learnability. We give a simple and general argument to exhibit such undecidability, and we 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.
翻译:我们研究了Agarwal等人(2020年)提出的可比较的PAC(CPAC)学习(CPAC)学习(CPAC),我们研究了Agarwal等人(2020年)。首先,我们考虑了找到适当和不当的CPAC学习特征的主要未决问题。我们描述了一个密切相关的强烈CPAC学习概念的特征,并对Agarwal等人(2021年)提出的公开问题提供了否定的答案,即所有可分解的PAC可以学习的班级是否都无法正确学习CPAC。第二,我们考虑了(可比较的)PAC学习的不可更改性。我们给出了一个简单而笼统的论据,以展示这种不可确定性。我们发起了一项关于可计算性复杂性的研究。我们简要讨论了促使Agarwal等人(2019年)开展工作的Ben-David等人(2019年)的不可降解性结果之间的关系。