From Undecidability of Non-Triviality and Finiteness to Undecidability of Learnability
This reveals a fundamental limitation in the theoretical foundations of AI, showing that automating the assessment of new learning models is impossible in general, which is a foundational problem for machine learning researchers and practitioners.
The paper proves that for several learning frameworks (PAC binary classification, uniform and universal online learning, and exact learning), there is no general procedure to decide whether a proposed model can successfully learn from data, establishing undecidability in both axiomatic and computational senses.
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.