Sign In

Communications of the ACM

ACM News

Machine Learning Leads Mathematicians to Unsolvable Problem


  Austrian-born mathematician Kurt Gdel in portrait at Institute of Advanced Study  Austrian mathematician Kurt Gdel is known for his incompleteness theorems.

A team of researchers has stumbled on a question that is mathematically unanswerable because it is linked to logical paradoxes discovered by Austrian mathematician Kurt Gdel in the 1930s that cant be solved using standard mathematics.

Credit: Alfred Eisenstaedt/ LIFE Picture Collection/Getty

A team of researchers has stumbled on a question that is mathematically unanswerable because it is linked to logical paradoxes discovered by Austrian mathematician Kurt Gödel in the 1930s that can't be solved using standard mathematics.

The mathematicians, who were working on a machine learning problem, show that the question of 'learnability'—whether an algorithm can extract a pattern from limited data—is linked to a paradox known as the continuum hypothesis. Gödel showed that the statement cannot be proved either true or false using standard mathematical language. The latest result appeared on January 7 in Nature Machine Intelligence1.

"For us, it was a surprise," says Amir Yehudayoff at the Technion–Israel Institute of Technology in Haifa, who is a co-author on the paper. He says that although there are a number of technical maths questions that are known to be similarly 'undecidable', he did not expect this phenomenon to show up in a relatively simple problem in machine learning.

John Tucker, a computer scientist at Swansea University, U.K., says that the paper is "a heavyweight result on the limits of our knowledge", with foundational implications for both mathematics and machine learning.

 

From Nature
View Full Article

 


 

No entries found

Sign In for Full Access
» Forgot Password? » Create an ACM Web Account