Shulou(Shulou.com)06/02 Report--

2020-05-19 23:09:16

Author | Sergei Ivanov

Compilation | end of cluster

If we look at history, we will find that history is often written by successful people.

Turing, Minsky, McCarthy, these names are familiar. However, in the history of artificial intelligence, there seem to be few Soviet scientists of their time.

Really, is there no AI under the Iron Curtain?

Looking at the past, we will find that this is not the case-the competition between Western countries and the Soviet Union in the development of artificial intelligence is no less than their competition in the field of space. The Soviet Union's investment and development in AI is not inferior to that of western countries.

This article will focus on the work of Andrey Leman, the co-inventor of Weisfeiler-Leman algorithm, and his colleagues, and take you back to the history of artificial intelligence in the Soviet Union.

Andrey Leman (1940-2012), known for co-inventing the Weisfeiler-Leman algorithm, made an important contribution to INES, the first database in the Soviet Union, and Kaissa, the first computer program to win a chess competition, and was an early member of the Kronrod team that developed the first AI program.

His whole life, from winning the Mathematical Olympiad at school to working in an artificial intelligence laboratory and then moving to Silicon Valley, is the hallmark of a generation of talented Soviet engineers and mathematicians.

1 Enlightenment from the Mathematical Olympiad

Like the typical education of smart young boys at that time, Andrey Leman also excelled in math, excelled in the Mathematical Olympiad and studied at the best university in the country.

In the era when there was no Internet, the Mathematical Olympiad was the source of inspiration for the career of mathematical research, and the field naturally attracted Andrey.

Andrey won the Mathematical Olympiad

It can be said that this interest in solving difficult problems continued throughout his life: first as a mathematician devoted to solving mathematical problems, and later as a programmer dedicated to solving computer problems. Later, he compiled a book based on all these problems, which has been an important reference for Soviet students for many years.

In 1957, at the age of 17, Andrey became a freshman at Moscow State University, the top university in the Soviet Union. In 1962, after graduating from the university, he joined the first artificial intelligence laboratory in the Soviet Union.

He studied with Boris Weisfeiler in college and worked with him for many years after graduation, until Boris Weisfeiler emigrated in 1975.

2 the first artificial intelligence laboratory in the Soviet Union

Alexander Kronrod, founder of artificial Intelligence in the Soviet Union

If you want to say who is the founder of artificial intelligence in the Soviet Union, the answer is Alexander Kronrod, the head of the first artificial intelligence laboratory in the Soviet Union.

Kronrod's entire scientific career had some twists and turns: at first, he was a promising young mathematician devoted to complex review and differential equations, then volunteered to join the army at the beginning of World War II, for which he won several medals but was injured twice in the course of the war. So in 1945, he joined the Kurchatov Institute of numerical Mathematics, until he began to realize that computing can be more rich than "pure" mathematics.

Four years later, he became the head of the mathematics department of the new Institute of theoretical and Experimental Physics (ITEP), dedicated to leading the innovation of nuclear physics, an important research direction for the whole country. If it were not for his firm belief in artificial intelligence research, the research institute would only stay in the scope of numerical simulation, and would never involve the related research of artificial intelligence. At the same time, Kronrod's high reputation allowed him and his research team to start working on intelligent systems that can play cards and chess.

Institute of theoretical and Experimental Physics (ITEP)

At that time, a hot topic in the field of computer science was the computational complexity of discrete algorithms, and the Kronrod team also made a research contribution to it. Two members of its research team, G. Adelson-Velsky and E. Landis, proposed the first self-balanced binary tree (Self-balancing Binary Search Tree), which is now called AVL tree.

The element insertion method of AVL tree

With the introduction of the first polynomial solvable problem and NP complete problem to the field of computer science, the laboratory began to find fast algorithms for solving various problems.

Most of the problems can be quickly excluded from the P problem and the NP complete problem set, but two very important problems in practice, linear programming and graph isomorphism, do not belong to the above two kinds of problems.

Later, another Soviet mathematician, Leonid Khachiyan, constructed a polynomial time algorithm for linear programming, but the graph isomorphism problem still does not belong to the class P problem.

The problem of graph isomorphism has naturally attracted the attention of Kronrod laboratory members including Andrey Leman and Boris Weisfeiler. The first important result of their research on this problem is the Weisfeiler-Leman algorithm, which we are very familiar with now.

Andrey Leman and Boris Weisfeiler

In recent years, with the development of graph machine learning, the computer science community pays more and more attention to Weisfeiler-Leman algorithm.

At that time, this work on graph isomorphism also led Leman to publish his first paper under the guidance of Kronrod. However, due to a personal feud between the head of the High Accreditation Council (HAC) and the Kronrod, the paper was rejected and rated as "this is not math".

I'm not a mathematician, I'm a programmer. -Andrey then responded angrily.

He then shifted his research interest from combinatorial mathematics to the problem of more partial programmers, and published his second paper on database management under the guidance of V.Arlazarov in 1973. His contribution to the Soviet Union's first widely used database, INES, also won him the Soviet Council of Ministers Award (USSR Council of Ministers Prize).

However, Andrey does not confine itself to database programming, while working on other software engineering issues, including the development of the first AI "chess player" to become a world champion.

3 the chess AI competition between the Soviet Union and the United States

In 1966, Claude Shannon, John McKinsey, Ed Fredkin and Joseph Weizenbaum gathered together.

A few years after Alan Turing invented the universal Turing machine, Claude Shannon, the father of information theory, tried to teach computers to play chess. The idea became so popular that both the United States and the Soviet Union developed programs that could play chess.

In the United States, the program was developed by John McKinsey and his students at MIT. As we all know, the term "artificial intelligence" was put forward by McKinsey during a discussion with Turing in 1952, both of which were pioneers in the field of artificial intelligence.

In the Soviet Union, the program was developed by a team led by Kronrod at ITEP, called Kaissa. The Kronrod Lab started the project in 1963, when its members included talented mathematicians such as G. Adelson-Velskyi, V. Arlazarov and Andrey Leman.

It is worth mentioning that in 1965, McCarthy also visited the Soviet Union and supported Kronrod in hosting the first chess match between the two programs they developed in 1967. Kaissa showed great opening knowledge and analytical skills in four games, winning the championship with a score of 3:1.

The first chess game between computers, the Soviet Union (black) VS the United States (white)

In 1969, Kronrod and other mathematicians signed a letter defending another Soviet mathematician, Esenin-Volpin, who received unfair charges. However, this kind of behavior was strictly prohibited in the university, and eventually Kronrod was fired and his laboratory was disbanded.

V. Arlazarov

Later, his lab members added the Institute of Control problems (ICP), but Kronrod did not join. V. Arlazarov succeeded him as the team leader who continued to lead the Kaissa project research, dedicated to making Kaissa the champion of the AI Chess World Championship.

In 1974, the AI World Chess Championship was held in Stockholm, in which 13 programs from eight countries competed for the world championship. In the end, Kaissa won four games and won the gold medal, surpassing US rivals Chess-4, Chaos and Ribbit by three points each.

In the scene of the game, McKinsey is answering the phone on the right.

Later, Kronrod said, "Chess is the fruit fly of artificial intelligence." Fruit flies are good experimental animals, and researchers can use them to test hypotheses.

4 Silicon Valley emigration trend

Later, Andrey continued to work with his colleagues at Kronrod Lab: at the Institute of Control Studies from 1968 to 1976 and at the Institute of Systems Analysis from 1976 to 1990 until the fall of the Iron Curtain in the Soviet Union.

In 1990, he moved to Silicon Valley with many other scientists.

Based on Cognitive Technology Inc, a Silicon Valley start-up, they developed an optical recognition system that has become a leader in the field of scanning documents in different languages. In addition, the wedge-shaped OCR solution they developed has been adopted by a number of IT giants such as Oracle, IBM and Samsung.

Wedge-shaped OCR solution, the first successful product developed by Andrey and colleagues

Andrey worked as a programmer for several high-tech start-ups from 1995 to 2012, and his last employer was a genetics company, Invitae, where the infrastructure systems he developed are still widely used by employees. Although he is still a "beginner" in the field of bioinformatics, his curiosity in solving challenging problems has also made him fruitful in this field.

Andrey in the United States

Andrey died in 2012, but in people's minds, he will always be a reliable colleague, a loyal friend, a sense of humor and always ready to help others.

He and his colleagues developed AI from a branch of mathematics to one of the most influential independent fields in computer science, and their research has become a chapter in the history of artificial intelligence in the Soviet Union.

Via https://towardsdatascience.com/a-forgotten-story-of-soviet-ai-4af5daaf9cdf

Https://www.toutiao.com/i6828572610914157070/

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.