Mathematicians discovered a computer problem that nobody can solve



Mathematicians have discovered a problem that they can not solve. It's not that they are not smart enough; There is simply no response.

The problem has to do with machine learning: the kind of artificial intelligence models that some computers use to "learn" how to perform a specific task.

When Facebook or Google recognizes a photo of you and they suggest that you tag yourself, you are using machine learning. When a self-driven car navigates a busy intersection, that is machine learning in action. Neuroscientists use machine learning to "read" someone's thoughts. What happens with machine learning is that it is based on mathematics. And as a result, mathematicians can study and understand it on a theoretical level. They can write tests on how automatic learning works that are absolute and apply them in each case. [Photos: Large Numbers That Define the Universe]

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

To understand how EMX works, imagine this: you want to place ads on a website and maximize the number of viewers these ads will target. It has ads for sports fans, cat lovers, car enthusiasts and exercise fans, etc. But he does not know in advance who is going to visit the site. How do you select an ad selection that maximizes the number of viewers you target? EMX has to find the answer with only a small amount of information about who visits the site.

Then, the researchers asked a question: When can EMX solve a problem?

In other machine learning problems, mathematicians can usually tell if the learning problem can be solved in a given case based on the set of data they have. Can you apply the underlying method that Google uses to recognize your face to predict stock market trends? I do not know, but someone could.

The problem is that the mathematics is somewhat 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, there are certain questions that can not be answered. 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 named Paul Cohen found an example: the continuum hypothesis.

The hypothesis of the continuum is as follows: mathematicians already know that there are infinities of different sizes. For example, there are infinite integers (numbers like 1, 2, 3, 4, 5 and so on); and there are infinite real numbers (which include numbers like 1, 2, 3, etc., but they also include numbers like 1.8 and 5.222.7 and pi). But although there are infinite integers and infinite real numbers, clearly there are more real numbers than integers. What does the question pose, are there infinities larger than the set of integers but smaller than the set of real numbers? The continuum hypothesis says, yes, there are.

Godel and Cohen proved that it is impossible to prove that the continuum hypothesis is correct, but it is also impossible to prove that it is wrong. "Is the continuum hypothesis true?" It is an unanswered question.

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

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

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

"Because EMX is a new model of machine learning, we still do not know how useful it is to develop real-world algorithms," wrote Lev Reyzin, a professor of mathematics at the University of Illinois at Chicago, who did not work on the document. in an article accompanying Nature News & Views. "So, these results may not be of practical importance," Reyzin wrote.

Running against an unsolvable problem, Reyzin wrote, is a kind of pen on the cover of machine learning researchers.

It is evidence that machine learning has "matured as a mathematical discipline," Reyzin wrote.

Machine learning "now joins the many subfields of mathematics that deal with the burden of impossibility and the concern that comes with it," Reyzin wrote. Maybe results like this will bring a good dose of humility to the field of machine learning, even when machine learning algorithms continue to revolutionize the world around us. "

Originally published in Living science.


Source link

Check Also

OnePlus latest teaser suggests ‘Nord’ branding for your next budget phone

After officially confirming plans to launch a new affordable smartphone series, OnePlus has now hinted …