[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