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

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

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

Соединить коннекционизм и эволюционизм довольно легко: просто эволюционируйте структуру сети и получите параметры путем обратного распространения ошибки. Объединить логику и вероятностный подход намного сложнее. Попытки решить эту проблему предпринимал еще Лейбниц, который был пионером в обеих областях, а после него — лучшие философы и математики XIX и XX века, например Джордж Буль и Рудольф Карнап. Несмотря на все усилия, результаты были очень скромными. Позднее в бой вступили информатики и исследователи искусственного интеллекта, но к началу нового тысячелетия они достигли лишь частичных успехов, например, к байесовским сетям добавили логические конструкты. Большинство экспертов были убеждены, что объединить логику и вероятности вообще невозможно. Перспективы создания Верховного алгоритма выглядели неважно, особенно потому, что существовавшие тогда эволюционистские и коннекционистские алгоритмы тоже не могли справиться с неполной информацией и множественными наборами данных.

К счастью, с тех пор мы продвинулись вперед на пути к решению проб­лемы, и сегодня Верховный алгоритм кажется намного ближе. Решение мы увидим в главе 9, но сначала надо подобрать все еще недостающую очень важную часть мозаики: как учиться, если данных очень мало. Здесь вступает в игру одна из самых важных идей в машинном обучении: аналогия. У всех «племен», которые мы до сих пор встретили, есть одна общая черта: они получают явную модель рассматриваемого явления, будь то набор правил, многослойный перцептрон, генетическая программа или байесовская сеть. Если у них для этого недостаточно данных, они заходят в тупик. А аналоги­заторам для обучения достаточно всего одного примера, потому что они модели не формируют. Давайте посмотрим, чем они вместо этого занимаются.

ГЛАВА 7

ТЫ — ТО, НА ЧТО ТЫ ПОХОЖ

Фрэнк Абигнейл-младший — один из самых знаменитых мошенников в истории, Леонардо Ди Каприо сыграл его в фильме Спилберга «Поймай меня, если сможешь». Абигнейл подделывал чеки на миллионы долларов, прикидывался адвокатом и преподавателем колледжа, путешествовал по миру, выдавая себя за пилота Pan Am, и все это когда ему еще не исполнился 21 год. Но, наверное, самая сногсшибательная его проделка — это когда он в конце 1960-х почти год успешно изображал врача в Атланте. Казалось бы, чтобы заниматься медициной, нужно много лет учиться в медицинском институте, пройти ординатуру, получить лицензию и так далее, но Абигнейлу удалось обойти эти мелочи, и все были довольны.

Представьте на секунду, что вам предстоит провернуть нечто подобное. Вы тайком пробираетесь в пустой медицинский кабинет. Вскоре появляется пациент и рассказывает вам о своих симптомах. Надо поставить ему диагноз, только вот в медицине вы ничего не смыслите. В вашем распоряжении — шкаф с историями болезней: симптомы, диагнозы, назначенное лечение и так далее. Как вы поступите? Самое простое — это заглянуть в документы, поискать пациента с самыми похожими симптомами и поставить такой же диагноз. Если вы умеете вести себя с больным и убедительно говорить, как Абигнейл, этого может оказаться достаточно для успеха. Та же идея успешно применяется и за пределами медицины. Если вы молодой президент и столкнулись с мировым кризисом, как в свое время Кеннеди, когда самолет-разведчик обнаружил на Кубе советские ядерные ракеты, вполне вероятно, что готового сценария у вас не окажется. Вместо этого можно поискать похожие примеры в истории и попытаться сделать из них выводы. Объединенный комитет начальников штабов подталкивал президента напасть на Кубу, но Кеннеди только что прочитал The Guns of August92 — бестселлер о начале Первой мировой войны — и хорошо осознавал, что такой шаг легко может вылиться в тотальную войну. Кеннеди предпочел морскую блокаду — и, может быть, спас мир от ядерной катастрофы.

Аналогия была искрой, из которой разгорелись величайшие научные достижения в истории человечества. Теория естественного отбора родилась, когда Дарвин, читая An Essay on the Principle of Population («Опыт о законе народонаселения») Мальтуса, был поражен сходством между борьбой за выживание в экономике и в природе. Модель атома появилась на свет, когда Бор увидел в ней миниатюрную Солнечную систему, где электроны соответствовали планетам, а ядро — Солнцу. Кекуле открыл кольцевую форму молекулы бензола, представив себе змею, пожирающую свой хвост.

У рассуждений по аналогии выдающаяся интеллектуальная родословная. Еще Аристотель выразил их в своем законе подобия: если две вещи схожи, мысль об одной из них будет склонна вызывать мысль о другой. Эмпирики, например Локк и Юм, пошли по этому пути. Истина, говорил Ницше, — это движущаяся армия метафор. Аналогии любил Кант, а Уильям Джеймс полагал, что чувство одинаковости — киль и позвоночник человеческого мышления. Некоторые современные психологи даже утверждают, что чело­веческое познание целиком соткано из аналогий. Мы полагаемся на них, чтобы найти дорогу в новом городе и чтобы понять такие выражения, как «увидеть свет» и «не терять лица». Подростки, которые в каждое предложение вставляют словечко «типа», согласятся, типа, что аналогия — это, типа, важная штука.

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

Аналогизаторы — наименее сплоченное из пяти «племен». В отличие от приверженцев других учений, которых объединяет сильное чувство идентичности и общие идеалы, аналогизаторы представляют собой скорее свободное собрание ученых, согласных с тем, что в качестве основы обучения нужно полагаться на суждения о сходстве. Некоторые, например ребята, занимающиеся методом опорных векторов, могут даже не захотеть встать под общий зонтик. Но за окном идет дождь из глубоких моделей, и мне кажется, действовать сообща им не повредит. Аналогия — одна из центральных идей в машинном обучении, и аналогизаторы всех мастей — ее хранители. Может быть, в грядущем десятилетии в машинном обучении будет доминировать глубокая аналогия, соединяющая в один алгоритм эффективность ближайшего соседа, математическую сложность метода опорных векторов и мощь и гибкость рассуждения по аналогии. (Вот я и выдал один из своих секретных научных проектов.)

Попробуй подобрать мне пару

Алгоритм ближайшего соседа — самый простой и быстрый обуча­ющийся алго­ритм, какой только изобрели ученые. Можно даже сказать, что это вообще самый быстрый алгоритм, который можно придумать. В нем не надо делать ровным счетом ничего, и поэтому для выполнения ему требуется нулевое время. Лучше не бывает. Если вы хотите научиться узнавать лица и в вашем распоряжении есть обширная база данных изображений с ярлыками «лицо / не лицо», просто усадите этот алгоритм за работу, расслабьтесь и будьте счастливы. В этих изображениях уже скрыта модель того, что такое лицо. Представьте, что вы Facebook и хотите автоматически определять лица на фотографиях, которые загружают пользователи, — это будет прелюдией к автоматическому добавлению тегов с именами друзей. Будет очень приятно ничего не делать, учитывая, что ежедневно в Facebook люди загружают свыше трехсот миллионов фотографий. Применение к ним любого из алгоритмов машинного обучения, которые мы до сих пор видели (может быть, кроме наивного байесовского), потребовало бы массы вычислений. А наивный Байес недостаточно сообразителен, чтобы узнавать лица.