Professor Shai Ben-David and colleagues’ work on machine learning featured as front-page article on Nature

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.

Please also see Machine learning leads mathematicians to unsolvable problem, by Davide Castelvecchi, a feature article in Nature that explores the significance of this result.