[FOM] Learnability

K. P. Hart k.p.hart at tudelft.nl
Fri Jan 18 04:02:17 EST 2019


My two cents:
https://hartkp.weblog.tudelft.nl/2019/01/11/more-on-machine-learning-and-ch/
and
https://arxiv.org/abs/1901.04773

KP
On 1/17/19 10:36 AM, Dennis Müller wrote:
> 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
>
>

-- 
E-MAIL: K.P.Hart at TUDelft.NL           PAPER: Faculty EEMCS
PHONE:  +31-15-2784572                       TU Delft
FAX:    +31-15-2787245                       Postbus 5031
URL:    http://fa.its.tudelft.nl/~hart       2600 GA  Delft
                                              the Netherlands



More information about the FOM mailing list