[FOM] Learnability

[Joe Shipman]

This can’t be right. All known mathematically definable problems of practical significance can be formulated in ways that are set-theoretically absolute and do not depend on CH. 

The paper is well-written and rigorous, but the kind of “function” it finds the “learnability of” to be “undecidable” involves “inputs” which contain an infinite amount of information (namely, a finite subset of the real number interval [0,1]) . The learning machine is then supposed to be able to produce an “output” which contains an infinite amount of information (another finite subset of [0,1]).

If the input were streamed, and the output were streamed, and “learning” was defined in terms of some limit property of the input and output functions, then we would have a realistic model, but it seems their proof would then not apply. In their model, all the input is needed to produce any of the output.

— JS

Sent from my iPhone

> On Jan 13, 2019, at 7:26 PM, Victor Marek <marek at cs.uky.edu> wrote:
> 
> 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