Верховный алгоритм - [18]

Тем не менее простота физики уникальна. За пределами физики и инженерии достижения математики не так бесспорны: иногда она представляет собой единственный разумный и эффективный путь, а иногда математические модели слишком грубы, чтобы быть полезными. Тенденция к излишнему упрощению вытекает, однако, из ограничений человеческого разума, а не только из ограничений математики как таковой. Жесткий (вернее, студенистый) диск в голове человека в основном занят восприятием и движениями, и для упражнений в математике нам приходится заимствовать области, предназначенные эволюцией для языка. У компьютеров таких ограничений нет, и они могут с легкостью превращать большие объемы данных в очень сложные модели. Машинное обучение — это то, что получается, когда необъяснимая эффективность математики сливается с необъяснимой эффективностью данных. Биология и социология никогда не будут такими простыми, как физика, однако метод, благодаря которому мы откроем их истины, может оказаться несложным.

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

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

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

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

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

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

P и NP (к сожалению, названия не самые очевидные) — важнейшие классы проблем в информатике. Проблема относится к группе P, если ее можно эффективно решить, а к NP — если можно эффективно проверить ее решение. Знаменитый вопрос о равенстве классов P и NP — каждая ли эффективно проверяемая проблема эффективно решаема. Благодаря NP-полноте все, что нужно для ответа на этот вопрос, — доказать, что