期刊
INTERNATIONAL JOURNAL OF APPROXIMATE REASONING
卷 163, 期 -, 页码 -出版社
ELSEVIER SCIENCE INC
DOI: 10.1016/j.ijar.2023.109057
关键词
Undecidability; Incomputability; PAC learning & VC-dimension; Online learning & Littlestone dimension; Teaching dimension
Currently, there is no general-purpose procedure to evaluate whether a machine learning model can successfully learn from data. Through computational proofs, we show that for certain learning problems, learnability is undecidable, both in terms of independence of axioms and computability. This implies that we cannot automate the process of assessing new learning models.
Machine learning researchers and practitioners steadily enlarge the multitude of successful learning models. They achieve this through in-depth theoretical analyses and experiential heuristics. However, there is no known general-purpose procedure for rigorously evaluating whether newly proposed models indeed successfully learn from data. We show that such a procedure cannot exist. For PAC binary classification, uniform and universal online learning, and exact learning through teacher-learner interactions, learnability is in general undecidable, both in the sense of independence of the axioms in a formal system and in the sense of uncomputability. Our proofs proceed via computable constructions that encode the consistency problem for formal systems and the halting problem for Turing machines into whether certain function classes are trivial/finite or highly complex, which we then relate to whether these classes are learnable via established characterizations of learnability through complexity measures. Our work shows that undecidability appears in the theoretical foundations of artificial intelligence: There is no one-size-fits-all algorithm for deciding whether a machine learning model can be successful. We cannot in general automatize the process of assessing new learning models.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据