Archive for incompleteness theorem

undecidable learnability

Posted in Books, Statistics, Travel, University life with tags , , , , , , on February 15, 2019 by xi'an

“There is an unknown probability distribution P over some finite subset of the interval [0,1]. We get to see m i.i.d. samples from P for m of our choice. We then need to find a finite subset of [0,1] whose P-measure is at least 2/3. The theorem says that the standard axioms of mathematics cannot be used to prove that we can solve this problem, nor can they be used to prove that we cannot solve this problem.”

In the first issue of the (controversial) nature machine intelligence journal, Ben-David et al. wrote a paper they present a s the machine learning equivalent to Gödel’s incompleteness theorem. The result is somewhat surprising from my layman perspective and it seems to only relate to a formal representation of statistical problems. Formal as in the Vapnik-Chervonenkis (PAC) theory. It sounds like, given a finite learning dataset, there are always features that cannot be learned if the size of the population grows to infinity, but this is hardly exciting…

The above quote actually makes me think of the Robbins-Wasserman counter-example for censored data and Bayesian tail prediction, but I am unsure the connection is anything more than sheer fantasy..!
~

logicomix

Posted in Books with tags , , , , , , on December 11, 2010 by xi'an

Thanks to Judith Rousseau (who gave me the book to read), I have enjoyed very much Logicomix: An epic search for truth, which is written in the format of a comic book or a graphic novel (just like Nietzsche, even though it is drawn in an altogether different if pleasant and colourful style). This bestselling book is about Bertrand Russell‘s doomed quest for the logical foundations of mathematics and about the intense debates in the philosophical and mathematical communities at the turn of the  century, ending with Gödel’s incompleteness theorem and Wittgenstein’s Tractatus Philosophicus. (Which reminded me of another book, Wittgenstein’s poker, that I read ages ago.)

Continue reading