Педро Домингос - Верховный алгоритм

P и NP (к сожалению, названия не самые очевидные) — важнейшие классы проблем в информатике. Проблема относится к группе P, если ее можно эффективно решить, а к NP — если можно эффективно проверить ее решение. Знаменитый вопрос о равенстве классов P и NP — каждая ли эффективно проверяемая проблема эффективно решаема. Благодаря NP-полноте все, что нужно для ответа на этот вопрос, — доказать, что одна NP-полная задача эффективно решаема (или нет). NP — не самый сложный класс проблем в информатике, но, по-видимому, самый сложный из «реалистичных»: если нельзя даже проверить решение проблемы до скончания времен, какой смысл пытаться ее решить? Люди хорошо научились приблизительно решать NP-задачи, и, наоборот, проблемы, которые нам кажутся интересными (тетрис, например), имеют в себе что-то от NP-класса. Согласно одному из определений искусственного интеллекта, он заключается в нахождении эвристических решений для NP-полных задач. Часто мы решаем такие задачи, редуцируя их до выполнимости. Классическая NP-полная задача звучит так: может ли данная логическая формула в принципе быть истинной или она противоречит самой себе? Если бы мы изобрели обучающийся алгоритм, способный научиться решать проблему выполнимости, он стал бы хорошим кандидатом на звание Верховного.

Но и без NP-полных задач само наличие компьютеров — серьезнейший признак существования Верховного алгоритма. Если бы вы отправились в начало ХХ века и рассказали, что вскоре будет изобретена машина, которая сможет решать проблемы во всех сферах человеческой деятельности — одна и та же машина для всех проблем, — никто бы не поверил. Вам бы объяснили, что машины могут делать что-то одно: сеялки не печатают, а пишущие машинки не сеют. Затем, в 1936 году, Алан Тьюринг25 придумал любопытное устройство с лентой и головкой, которая читает и пишет символы. Сегодня оно известно как машина Тьюринга. С ее помощью может быть решена каждая проблема, какую только можно решить с помощью логической дедук­ции. Более того, так называемая универсальная машина Тьюринга может симулировать любую другую, прочтя с ленты ее спецификацию, — другими словами, ее можно запрограммировать делать что угодно.

Верховный алгоритм предназначен для индукции, то есть процесса обучения, точно так же как машина Тьюринга для дедукции. Он может научиться симулировать любые другие алгоритмы путем чтения примеров их поведения на входе и выходе. Равно как многие модели вычислений эквивалентны машине Тьюринга, вероятно, существует много эквивалентных формулировок универсального обучающегося алгоритма. Суть в том, чтобы найти первую такую формулировку, как Тьюринг в свое время нашел первый вариант многоцелевого компьютера.

Алгоритмы машинного обучения против инженерии знаний

Конечно, к Верховному алгоритму скептически относятся столько же людей, сколько испытывают по поводу его существования энтузиазм. Сомнения — это естественно, особенно когда речь идет о своего рода «серебряной пуле». Самое решительное сопротивление оказывает вековечный враг машинного обучения — инженерия знаний. Ее адепты считают, что знание нельзя получить автоматически: его должны вложить в компьютер эксперты. Конечно, обучающиеся алгоритмы тоже могут извлечь кое-что из данных, но это никоим образом не настоящее знание. Для инженеров знаний большие данные — не золотая жила, а обманка.

На заре искусственного интеллекта машинное обучение представлялось очевидным путем к компьютерам с разумом, подобным человеческому. Тьюринг и другие ученые думали, что это единственный приемлемый путь. Однако затем инженеры знаний нанесли ответный удар, и к 1970 году машинное обучение было жестко оттеснено на второй план. В какой-то момент, в 1980-х годах, казалось, что инженерия знаний вот-вот завоюет мир, а компании и целые государства вкладывали в нее огромные инвестиции. Но вскоре пришло разочарование, и машинное обучение начало свой неумолимый рост — сначала тихо, а потом на гребне растущего вала данных.

Тем не менее все успехи машинного обучения не убедили инженеров знаний. Они уверены, что вскоре ограничения этого подхода станут очевидными и маятник качнется в другую сторону. Эту точку зрения разделяет Марвин Минский, профессор Массачусетского технологического института и пионер в области искусственного интеллекта. Минский не просто скептически относится к машинному обучению как альтернативе инженерии знаний: он вообще не верит, что в науке об искусственном интеллекте можно что-то объединить. Теория интеллекта по Минскому изложена в его книге The Society of Mind («Общество разума»), где он замечает, что «разум — это одна вещь за другой и ничего больше». Вся книга — длинный перечень, сотни отдельных идей, к каждой из которых дается краткое описание. Проблема такого подхода к искусственному интеллекту — в том, что он не работает. Это как коллекционирование марок компьютером. Без машинного обучения количество идей, необходимых, чтобы построить интеллектуальный агент, бесконечно. Если у робота будут все человеческие умения, кроме способности учиться, человек вскоре оставит его позади.