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

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

Аргумент из области информатики

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

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

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