Abstract
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) learnability.
They argue that this type of learnability fits in with other notions such as
PAC learnability, Vapnik's statistical learning setting, and other general
learning settings. However, using some set-theoretic techniques, they show that
some learning problems in the EMX setting are independent of ZFC. Specifically
they prove that ZFC cannot prove or disprove EMX learnability of the finite
subsets on the 0,1 interval. Moreover, the way they prove it shows that there
can be no characteristic dimension for EMX; and, hence, for general learning
settings. Here, I will explain their findings, discuss some limitations on
those findings, and offer some suggestions about how to excise that
undecidability. Parts 2-3 will explain the results of the paper, part 4-5 will
discuss some limitations and next steps, and I will conclude in part 6.
Description
[1909.08410] Learnability Can Be Independent of ZFC Axioms: Explanations and Implications
Links and resources
Tags