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

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

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

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

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

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

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

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

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

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

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

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

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

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