The problem of attempting to learn the mapping between data and labels is the crux of any machine learning task. It is, therefore, of interest to the machine learning community on practical as well as theoretical counts to consider the existence of a test or criterion for deciding the feasibility of attempting to learn. We investigate the existence of such a criterion in the setting of PAC-learning, basing the feasibility solely on whether the mapping to be learnt lends itself to approximation by a given class of hypothesis functions. We show that no such criterion exists, exposing a fundamental limitation in the decidability of learning. In other words, we prove that testing for PAC-learnability is undecidable in the Turing sense. We also briefly discuss some of the probable implications of this result to the current practice of machine learning.
翻译:试图了解数据和标签之间的绘图问题是任何机器学习任务的症结所在,因此,机器学习界在实际和理论方面都有兴趣考虑是否存在一种测试或标准来决定尝试学习的可行性,我们调查在PAC学习的设置中是否存在这种标准,仅仅根据所学的绘图是否适合以某一类假设功能进行近似的可行性,我们表明不存在这种标准,这暴露了学习的衰落性的根本限制。换句话说,我们证明在图灵意义上,测试PAC-可忽略性是无法确定的。我们还简要讨论了这一结果对目前机器学习做法可能产生的影响。