Professor Shai Ben-David and colleagues prove that some problems in statistical machine learning cannot be resolved

Friday, November 30, 2018

One of the most important results in logic is Kurt Gödel’s work from 1931 that proved that some questions in mathematics cannot be resolved — that mathematics has limits.

photo of Professor Shair Ben-David
“People are now looking at concrete problems in mathematics and asking maybe some problems in mathematics that we don’t know how to answer fall into this category of questions that cannot be answered,” explains Cheriton School of Computer Science Professor Shai Ben-David.

Professor Ben-David and colleagues Pavel Hrubes, Shay Moran, Amir Shpilka and Amir Yehudayoff examined a general problem in machine learning that was framed originally by Vladimir Vapnik, one of the fathers of modern machine learning. Through their work, using techniques from set theory and logic, they show that some problems in machine learning cannot be resolved. The research has been accepted for publication in Nature Machine Intelligence Journal.

The fundamental result of statistical machine learning is the characterization of learnability by some combinatorial dimension, called the Vapnik-Chervonenkis dimension, Professor Ben-David continued. “If you look at a problem and figure out its Vapnik-Chervonenkis dimension you know how hard it is going to be to solve that problem. But this applies only for problems of binary label prediction. There is a more general set up for learning — Vapnik’s general statistical learning framework — that captures many other important learning problems. Nobody knew what dimension can characterize how hard those problems are.”

“Our results are the first-ever demonstration of a problem in concrete statistical machine learning that cannot be answered,” Professor Ben-David said. “As a corollary, we also proved that there cannot be any dimension that characterizes how hard it is to learn a general statistical problem, which is a big surprise to this community.”

“When we worked on this paper, Shay Moran was just finishing his PhD. I met Shay and his supervisor, Amir Yehudayoff, at a workshop. We found that our expertise and interests matched so we collaborated to obtain this surprising interdisciplinary result.”

To learn more about this research, please see Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff, A Learning Problem that is Independent of the Set Theory ZFC Axioms, 2018, arXiv:1711.05195.