Machine Learning Algorithms

Machine learning as it is now

In popular machine learning methods, the program does not learn the algorithm. A classifier, a neural network, or, for more obviousness, regression methods learn at best a function (in a mathematical, not a programmer sense): having input data, output the output data. This may be, at best, the only step of the algorithm and it is not clear how to scale such a solution to the whole algorithm instead of one step. Without the ability to learn algorithms, these methods are far from AGI (Artificial General Intelligence). On the way to AGI, it would be nice to find a way for programs to learn algorithms with branching, loops, and routines. The next step is to teach programs to understand other programs. Further understand and improve yourself. I do not insist that it is in this way that people will go to AGI, but this is my humble vision.

Program as Applied Artificial Intelligence

Unlike other methods of machine learning, in my free time I created an interactive system that asks the user questions and after each answer gives a list of possible goals - what the user may like, whether it's a new game, movie, book, product or service. The meaning of the new search engine is that the user may not have an idea of ​​what exactly he (a) is looking for, therefore, he cannot form keywords to drive into existing search engines. But the answer to the questions of the program may, and there is always the option "I do not know / find it difficult to answer."

Implementation and Competitors

An example of how this works can be seen in others who have done something similar: Akinator . Let's not talk about the idea that came to me before Akinator appeared . I only got to implement it recently, and unlike Akinator, I posted it in open source - the open source code ProbQA is here. It is not known on which algorithm Akinator works. Anyone in C ++ can see my own algorithm, but in order to make it easier to read, I’ll tell you a little further. A matrix of N by K by M is used, where N is the number of questions, K is the number of answers, M is the number of goals. The program keeps statistics of how many times users have chosen the j-th target as the desired one for a set of questions and answers. Further, on the assumption of independence, the opposite is determined: the probability of the j-th goal in a set of questions and answers, including all the previous ones and each unasked question, as a candidate, be next. Each question is assigned a weight based on the priority function, which depends on the entropy of new (i.e., after a new question) probabilities of goals and on the Euclidean distance between old and new probabilities of goals. Next, the "best" question is selected in a weighted random manner.

Implemented only back-end in C ++. Waiting for someone to write front-end web applications. I myself do not specialize in this.

The program studies the algorithms

It turns out that the program ProbQA (Probabilistic Question Asking), in contrast to other methods of machine learning, is essentially capable of learning algorithms. She showed good results in the study of the binary search algorithm (dichotomy), see the picture below. We can say that she learns algorithms, because with her knowledge the program does the following: interaction with the user in several steps, leading to the ultimate goals. The program asks for input, then, depending on the input, branches and asks the user about something else.



The picture above shows the curve of the study of the dichotomy algorithm by the program. On the X axis, the number of questions asked by the program and answered by the user, on the Y axis, the percentage of correctly guessed binary search goals for 256 subsequent one after one attempts. Testing is always carried out on new data: we make a random number from 0 to 999, and let the program guess it by asking questions and receiving answers from the user (in this case, the user is a testing program that knows the number that has been guessed). Further, if ProbQA guessed correctly, or failed (asked more than 100 questions), we learn it by revealing the number chosen by the testing program.

As we can see from the picture, ProbQA training takes up to 100% accuracy the number of questions and answers, approximately equal to the size of the matrix. In our case, the matrix consists of 1000 questions multiplied by 5 answer options multiplied by 1000 goals. Each i-th question out of these 1000 has the form “How is the hidden number comparable to the number i?”. Answer options: 0 - “The hidden number is much less than i”, 1 - “The hidden number is slightly less than i”, 2 - “The hidden number is equal to i”, 3 - “The hidden number is slightly larger than i”, 4 - “The hidden number is much larger i ".

Now he is interested in the following question: what is the length of the chain of questions leading to the right goal? In the picture below we can see that at first (during training) the program asks a lot of questions, but when the program has already learned the algorithm, the average chain length drops somewhere to 7 questions.



The result can be considered good, given that a binary search algorithm written by a person asks ln (1000) / ln (4) = 5 questions. The remaining 2 questions are needed for the program to continue to learn, and not give all the best, without learning anything new. This is controlled by the priority function mentioned above and by the fact that not a “most-most” differentiating question is chosen, but a weighted-random one.

In addition to the fact that a human-written dichotomy algorithm does not study, it should be noted that such an algorithm is not error tolerant. If he receives an incorrect answer somewhere in the input, then after that he will not find the hidden number. While ProbQA sorts targets according to their probabilities.

Long-term perspective

So far, in the form of links in English, as information is low-tech and may fall into the category of "dreams."

1. Artificial Super-Neuron
2. New programming

If you want, I can write a separate article based on those two.