Верховный алгоритм. Как машинное обучение изменит наш мир - Педро Домингос

На старших курсах колледжа я любил поиграть в тетрис. Игра очень затягивала: сверху падали разные фигуры, и их нужно было уместить как можно плотнее. Когда гора блоков достигала верхней границы экрана, игра заканчивалась. Тогда я и не подозревал, что это было мое введение в самую важную в теоретической информатике NP-полную задачу[24]. Оказывается, овладеть тетрисом — по-настоящему его постичь — не пустяковое дело, а одна из самых полезных вещей, которую только можно сделать. Справившись с задачей тетриса, можно одним ударом решить тысячи сложнейших, невероятно важных проблем науки, технологии и менеджмента. Дело в том, что по сути они одна и та же проблема, и это один из самых захватывающих фактов во всей науке.

Как белки принимают характерную для них форму? Как воссоздавать историю эволюции видов по их ДНК? Как доказывать теоремы с помощью пропозициональной логики? Как выявлять возможности для скупки ценных бумаг с учетом транзакционных издержек? Как определять трехмерную форму по двухмерному изображению? Сжатие данных на дисках, формирование стабильных коалиций в политике, моделирование турбулентности в сдвиговых потоках, нахождение самого безопасного портфеля инвестиций с заданной выручкой и кратчайшего пути, чтобы посетить ряд городов, оптимальное расположение элементов на микросхемах, лучшая расстановка сенсоров в экосистеме, транспортные потоки, социальное обеспечение и (самое главное) как выиграть в тетрис — все это NP-полные задачи. Если получится решить одну из них, можно будет эффективно решать все задачи класса NP. Кто бы мог предположить, что все эти проблемы, такие разные на вид, — в действительности одно и то же? Но если это так, то вполне возможно, что их все (или, точнее, все частные случаи, имеющие эффективное решение) может научиться решать один алгоритм.

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

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

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

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

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

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