[FOM] Learnability

[Dennis Müller]

The following twitter thread by John Carlos Baez summarizes the issue in 
a rather concise manner:
https://twitter.com/johncarlosbaez/status/1083047483368890368

Basically: The question of whether a ML agent can generalize a 
classification scheme with a certain accuracy from a finite set of 
training data is reducible to finding a finite subset of [0,1] with a 
sufficiently large P-measure, where the measure P itself is unknown 
except for N iid samples. The latter is apparently possible iff there's 
at most finitely many uncountable cardinals < 2^aleph0.

> During a routine perusal of the site RealClearScience.com, I read the 
> piece
> about the article "Learnability can be undecidable", by S. Ben-David, 
> P. Hrubes
> et.al. The piece is published in the journal Nature Machine Intelligence.
> In that paper the authors appear to show that certain aspect of 
> machine learning
> (pretty practical task) is equivalent (in ZFC) to Continuum Hypothesis 
> which
> is (as we know since P.J. Cohen) undecidable in ZFC.
>
> I never did Machine Learning, and this appears to be absolutely 
> incredible.
> The piece in RealClearScience is a product of a science writer, not 
> necessarily
> knowing what s/he is talking about.
>
> Obviously, the matter is relevant to F.O.M. Could someone in the 
> community make
> this matter clearer for pedestrians such as I?
>
> Thanks,
>
> Victor Marek
> Victor W. Marek Department of Computer Science
> marek at cs.uky.edu University of Kentucky
> marek at cs.engr.uky.edu Lexington, KY 40506-0633
> 859-257-3496 (office) 859-257-3961 (Dept)
> http://www.cs.uky.edu/~marek 859-257-1505 (FAX)
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> https://cs.nyu.edu/mailman/listinfo/fom


-- 
Dennis M. Müller
logicalphalluses.net
"Mathematics is the music of reason. To do mathematics is to engage in an act of discovery and conjecture, intuition and inspiration; to be in a state of confusion— not because it makes no sense to you, but because you gave it sense and you still don’t understand what your creation is up to; to have a breakthrough idea; to be frustrated as an artist; to be awed and overwhelmed by an almost painful beauty; to be alive, damn it. Remove this from mathematics and you can have all the conferences you like; it won’t matter. Operate all you want, doctors: your patient is already dead."
  - Paul Lockhart (on mathematics in school)