Professor Shai Ben-David and his colleagues Pavel Hrubes, Shay Moran, Amir Shpilka and Amir Yehudayoff have shown that a simple machine learning problem — whether an algorithm can extract a pattern from limited data — is mathematically unsolvable because it is linked to inherent shortcomings of mathematics discovered by Austrian mathematician Kurt Gödel in the 1930s.
“Our results are the first-ever demonstration of a problem in concrete statistical machine learning that cannot be answered mathematically,” Professor Ben-David said.
Their work, titled “Learnability can be undecidable,” was published on January 7, 2019 in the first volume of a new Nature publication — Nature Machine Intelligence — as well as featured as a front-page news and views article on Nature’s website.
“Their work on the undecidability of a relatively natural problem in machine learning is a real surprise to machine learning researchers and mathematicians,” said Mark Giesbrecht, Professor and Director of the David R. Cheriton School of Computer Science. “It is a highly significant and almost troubling result that some things can’t be learned, and is certainly a major contribution to the theory of machine learning.”
To learn more about this research, please see Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff, Learnability can be undecidable, Nature Machine Intelligence Journal, vol. 1, January 2019, 44–48.