Learnability Can Be Undecidable. Ben-David, S., Hrubeš, P., Moran, S., Shpilka, A., & Yehudayoff, A. 1(1):44–48. ![Learnability Can Be Undecidable [link]](https://bibbase.org/img/filetypes/link.svg "link")
Paper doi abstract bibtex The mathematical foundations of machine learning play a key role in the development of the field. They improve our understanding and provide tools for designing new learning paradigms. The advantages of mathematics, however, sometimes come with a cost. Gödel and Cohen showed, in a nutshell, that not everything is provable. Here we show that machine learning shares this fate. We describe simple scenarios where learnability cannot be proved nor refuted using the standard axioms of mathematics. Our proof is based on the fact the continuum hypothesis cannot be proved nor refuted. We show that, in some cases, a solution to the 'estimating the maximum' problem is equivalent to the continuum hypothesis. The main idea is to prove an equivalence between learnability and compression.
@article{ben-davidLearnabilityCanBe2019,
title = {Learnability Can Be Undecidable},
author = {Ben-David, Shai and Hrubeš, Pavel and Moran, Shay and Shpilka, Amir and Yehudayoff, Amir},
date = {2019-01},
journaltitle = {Nature Machine Intelligence},
volume = {1},
pages = {44--48},
issn = {2522-5839},
doi = {10.1038/s42256-018-0002-3},
url = {https://doi.org/10.1038/s42256-018-0002-3},
abstract = {The mathematical foundations of machine learning play a key role in the development of the field. They improve our understanding and provide tools for designing new learning paradigms. The advantages of mathematics, however, sometimes come with a cost. Gödel and Cohen showed, in a nutshell, that not everything is provable. Here we show that machine learning shares this fate. We describe simple scenarios where learnability cannot be proved nor refuted using the standard axioms of mathematics. Our proof is based on the fact the continuum hypothesis cannot be proved nor refuted. We show that, in some cases, a solution to the 'estimating the maximum' problem is equivalent to the continuum hypothesis. The main idea is to prove an equivalence between learnability and compression.},
keywords = {*imported-from-citeulike-INRMM,~INRMM-MiD:c-14677845,artificial-intelligence,epistemology,limiting-factor,machine-learning,mathematics,modelling-uncertainty,software-uncertainty,unexpected-effect},
number = {1}
}
Downloads: 0
{"_id":"TMXFLo7DbZmpCEQTv","bibbaseid":"bendavid-hrube-moran-shpilka-yehudayoff-learnabilitycanbeundecidable","authorIDs":[],"author_short":["Ben-David, S.","Hrubeš, P.","Moran, S.","Shpilka, A.","Yehudayoff, A."],"bibdata":{"bibtype":"article","type":"article","title":"Learnability Can Be Undecidable","author":[{"propositions":[],"lastnames":["Ben-David"],"firstnames":["Shai"],"suffixes":[]},{"propositions":[],"lastnames":["Hrubeš"],"firstnames":["Pavel"],"suffixes":[]},{"propositions":[],"lastnames":["Moran"],"firstnames":["Shay"],"suffixes":[]},{"propositions":[],"lastnames":["Shpilka"],"firstnames":["Amir"],"suffixes":[]},{"propositions":[],"lastnames":["Yehudayoff"],"firstnames":["Amir"],"suffixes":[]}],"date":"2019-01","journaltitle":"Nature Machine Intelligence","volume":"1","pages":"44–48","issn":"2522-5839","doi":"10.1038/s42256-018-0002-3","url":"https://doi.org/10.1038/s42256-018-0002-3","abstract":"The mathematical foundations of machine learning play a key role in the development of the field. They improve our understanding and provide tools for designing new learning paradigms. The advantages of mathematics, however, sometimes come with a cost. Gödel and Cohen showed, in a nutshell, that not everything is provable. Here we show that machine learning shares this fate. We describe simple scenarios where learnability cannot be proved nor refuted using the standard axioms of mathematics. Our proof is based on the fact the continuum hypothesis cannot be proved nor refuted. We show that, in some cases, a solution to the 'estimating the maximum' problem is equivalent to the continuum hypothesis. The main idea is to prove an equivalence between learnability and compression.","keywords":"*imported-from-citeulike-INRMM,~INRMM-MiD:c-14677845,artificial-intelligence,epistemology,limiting-factor,machine-learning,mathematics,modelling-uncertainty,software-uncertainty,unexpected-effect","number":"1","bibtex":"@article{ben-davidLearnabilityCanBe2019,\n title = {Learnability Can Be Undecidable},\n author = {Ben-David, Shai and Hrubeš, Pavel and Moran, Shay and Shpilka, Amir and Yehudayoff, Amir},\n date = {2019-01},\n journaltitle = {Nature Machine Intelligence},\n volume = {1},\n pages = {44--48},\n issn = {2522-5839},\n doi = {10.1038/s42256-018-0002-3},\n url = {https://doi.org/10.1038/s42256-018-0002-3},\n abstract = {The mathematical foundations of machine learning play a key role in the development of the field. They improve our understanding and provide tools for designing new learning paradigms. The advantages of mathematics, however, sometimes come with a cost. Gödel and Cohen showed, in a nutshell, that not everything is provable. Here we show that machine learning shares this fate. We describe simple scenarios where learnability cannot be proved nor refuted using the standard axioms of mathematics. Our proof is based on the fact the continuum hypothesis cannot be proved nor refuted. We show that, in some cases, a solution to the 'estimating the maximum' problem is equivalent to the continuum hypothesis. The main idea is to prove an equivalence between learnability and compression.},\n keywords = {*imported-from-citeulike-INRMM,~INRMM-MiD:c-14677845,artificial-intelligence,epistemology,limiting-factor,machine-learning,mathematics,modelling-uncertainty,software-uncertainty,unexpected-effect},\n number = {1}\n}\n\n","author_short":["Ben-David, S.","Hrubeš, P.","Moran, S.","Shpilka, A.","Yehudayoff, A."],"key":"ben-davidLearnabilityCanBe2019","id":"ben-davidLearnabilityCanBe2019","bibbaseid":"bendavid-hrube-moran-shpilka-yehudayoff-learnabilitycanbeundecidable","role":"author","urls":{"Paper":"https://doi.org/10.1038/s42256-018-0002-3"},"keyword":["*imported-from-citeulike-INRMM","~INRMM-MiD:c-14677845","artificial-intelligence","epistemology","limiting-factor","machine-learning","mathematics","modelling-uncertainty","software-uncertainty","unexpected-effect"],"downloads":0},"bibtype":"article","biburl":"https://tmpfiles.org/dl/58794/INRMM.bib","creationDate":"2020-01-08T20:39:39.368Z","downloads":0,"keywords":["*imported-from-citeulike-inrmm","~inrmm-mid:c-14677845","artificial-intelligence","epistemology","limiting-factor","machine-learning","mathematics","modelling-uncertainty","software-uncertainty","unexpected-effect"],"search_terms":["learnability","undecidable","ben-david","hrubeš","moran","shpilka","yehudayoff"],"title":"Learnability Can Be Undecidable","year":null,"dataSources":["DXuKbcZTirdigFKPF"]}