Learning models that can not be proved by machine learning can be found

The development of machine learning has remarkable things, and many AIs using machine learning have appeared, recognizing a specific object from the image and correctly recognizing the human voice. However, computer researchers point out that such machine learning also has a problem "can not prove whether it can be solved or not".

Learnability can be undecidable | Nature Machine Intelligence
https://www.nature.com/articles/s42256-018-0002-3

Unprovability comes to machine learning
https://www.nature.com/articles/d41586-019-00012-4

Today, algorithms using machine learning are penetrating everywhere in everyday life, from AIs installed in PCs and smartphones to email spam filters. In machine learning, it is important to analyze available data and design algorithms to improve performance. Although it is difficult to explicitly program the computer as "to judge such an image as" human face ", it is difficult to explicitly program it, but by analyzing a large amount of images by machine learning, It will be able to distinguish between images with faces and images that are not.

Shai Ben-David , a professor of computer science at Waterloo University pointed out that the linkage between machine learning algorithms and mathematical logic makes it impossible to determine whether machine learning is possible in specific subjects.

In 1931, Austrian mathematician / logicologist Kurt Gedel announced the " incompleteness theorem ", which is considered to be the most important discovery for mathematical foundation and logic in the 20th century. The incompleteness theorem is the theorem that some axiomatic theories including natural number theory can neither prove nor disprove, and there are axioms that can not prove their own consistency.

And, in the 19th century, German mathematician Georg Cantor suggested, "There are other concentrations between the concentration of the whole natural number (countable concentration) and the concentration of the whole real number ( continuum concentration ) It is proved that "a continuum hypothesis " not to "is a proposition that can not be proved nor disproved." The research team of Ben-David et al. States that these mathematical theories influence the proof of machine learning.

Various learning models have been devised in machine learning, but basically by analyzing the database, predictors for predicting the results (mathematical functions themselves for prediction itself or ones close to it) It is the final goal to get. For a given model and family of functions, the model is said to be learnable if this goal can be achieved (with the desired predictor) under reasonable constraints.

However, as Ben-David and colleagues' research team are tied to incompleteness theorem and continuum hypothesis when considering the learning possibilities in machine learning, it is clear that there is a machine learning model that can not distinguish whether learning is possible He said that he found it. For the model " estimating the maximum (EMX) " that estimates the maximum value of data, the research team says that the learning possibility can not be proven in the framework of standard mathematics.

As an example of using the EMX model, Mr. Ben-David cited as "to find advertisements that attract the most users, without knowing which users are seeing ads and visiting particular websites" It is. This problem can be rephrased as "It is one that tells AI the ability to find a function with the largest expectation value of some functions out of several functions".

The EXM model is very similar to " probabilistic approximate correct model (PAC model) " often used in machine learning, but there are slight differences in learning standards. The EXM model is linked with the continuum hypothesis "It is proved that neither certification nor disproof can be proved", and as a result, the result that the result can not be proved or can not be falsified also for the EXM model itself is said to be derived.

The EXM model seems to be a new machine learning model, and Mr. Ben-David's discovery will not cause a serious blow to the existing machine learning field immediately. However, understanding that there are cases like this time in the machine learning model should be careful when adopting a new learning model, and it may be necessary to review already existing learning models I do not.