Mathematicians have discovered a computer problem that no one can ever solve


Mathematicians have discovered a problem that they can not solve. It's not that they're not smart enough; there is simply no answer.

The problem relates to machine learning – the type of artificial intelligence model used by some computers to "learn" to perform a specific task.

When Facebook or Google recognizes a photo of you and suggests you tag yourself, it uses machine learning. When a freestyle car drives on a busy intersection, it's machine learning in action. Neuroscientists use machine learning to "read" the thoughts of someone. The thing about machine learning is that it is based on mathematics. And therefore mathematicians can study it and understand it from a theoretical point of view. They can write absolute proofs about how machine learning works and apply them in all cases. [Photos: Large Numbers That Define the Universe]

In this case, a team of mathematicians devised a problem of automatic learning called "maximum estimate" or "EMX".

More from LiveScience

To understand how EMX works, imagine this: You want to place ads on a website and maximize the number of viewers targeted by those ads. Your ads are aimed at sports fans, cat lovers, car enthusiasts, exercise enthusiasts, and more. But you do not know in advance who will visit the site. How do you choose a selection of ads that will optimize the number of visitors you target? EMX must find the answer with just a small amount of data about who visits the site.

The researchers then asked a question: When can EMX solve a problem?

In other problems of machine learning, mathematicians can usually tell if the learning problem can be solved in a given case according to the dataset that they possess. . Can the underlying method used by Google to recognize your face be applied to predicting stock market trends? I do not know, but someone could. The problem is that mathematics are somehow broken. It has been broken since 1931, when the logician Kurt Gödel published his famous incompleteness theorems. They showed that in any mathematical system, some questions can not be solved. They are not really difficult – they are unknowable. Mathematicians learned that their ability to understand the universe was fundamentally limited. Gödel and another mathematician, Paul Cohen, found an example: the continuum hypothesis.

The assumption of the continuum is as follows: mathematicians already know that there are infinitely many different sizes. For example, there are infinitely many integers (numbers such as 1, 2, 3, 4, 5, etc.); and there is an infinity of real numbers (which include numbers such as 1, 2, 3, etc., but they also include numbers such as 1.8, 5.222.7, and pi). But even if there are infinitely many integers and real numbers, there are clearly more real numbers than whole numbers. Which raises the question, are there infinites larger than the set of integers but smaller than the set of real numbers? The continuum hypothesis says, yes, there are some.

Gödel and Cohen showed that it was impossible to prove that the continuum hypothesis was correct, but also to prove that it was false. "Is the continuum hypothesis true?" is an unanswered question.

In an article published Monday, Jan. 7 in the journal Nature Machine Intelligence, researchers showed that EMX was inextricably linked to the continuum hypothesis.

It turns out that EMX can solve a problem only if the continuum assumption is true. But if that's not true, EMX can not. This means that the question "can EMX learn to solve this problem?" has an answer as unknowable as the continuum hypothesis itself.

The good news is that the solution to the continuum hypothesis is not very important for most mathematics. Similarly, this permanent mystery might not create a major obstacle to machine learning.

"EMX being a new model of machine learning, we do not yet know its utility for developing real algorithms," writes Lev Reyzin, professor of mathematics at the University of Illinois at Chicago. in an article by Nature News & V iews. "So these results may not be of practical importance," wrote Reyzin.

Reyzin wrote that coming up against an insoluble problem is a kind of pet peeve in the minds of machine learning researchers.

This is the proof, the machine's learning has "matured as a mathematical discipline," wrote Reyzin.

"Machine learning," adds Reyzin, joins the many subdomains of mathematics that deal with the burden of inviolability and accompanying discomfort. " Perhaps results such as this one will bring to the field of machine learning a good dose of humility, even as machine learning algorithms continue to revolutionize the world around us. "

Originally published on Science live.