Learnability can be undecidable
The mathematical foundations of machine learning play a key role in the development of the field. They improve our understanding and provide tools for designing new learning paradigms. The advantages of mathematics, however, sometimes come with a cost. Gödel and Cohen showed, in a nutshell, that not everything is provable. Here we show that machine learning shares this fate. We describe simple scenarios where learnability cannot be proved nor refuted using the standard axioms of mathematics. Our proof is based on the fact the continuum hypothesis cannot be proved nor refuted. We show that, in some cases, a solution to the ‘estimating the maximum’ problem is equivalent to the continuum hypothesis. The main idea is to prove an equivalence between learnability and compression.
Code (0)
등록된 구현이 없습니다.
Tasks
BIG-bench Machine LearningPAC learningSimilar Papers 제목 키워드 기반
Learnability Can Be Independent of ZFC Axioms: Explanations and Implications
In Ben-David et al.'s "Learnability Can Be Undecidable," they prove an independence result in theoretical machine learning. In particular, they define a new type of learnability, called Estimating The Maximum (EMX) learn…
PAC-learning is Undecidable
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 …
BIG-bench Machine LearningPAC learningA Complete Characterization of Learnability for Stochastic Noisy Bandits
We study the stochastic noisy bandit problem with an unknown reward function $f^*$ in a known function class $\mathcal{F}$. Formally, a model $M$ maps arms $\pi$ to a probability distribution $M(\pi)$ of reward. A model …
From Undecidability of Non-Triviality and Finiteness to Undecidability of Learnability
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…
BIG-bench Machine LearningBinary ClassificationA Note on Quantum Markov Models
The study of Markov models is central to control theory and machine learning. A quantum analogue of partially observable Markov decision process was studied in (Barry, Barry, and Aaronson, Phys. Rev. A, 90, 2014). It was…