Верховный алгоритм: как машинное обучение изменит наш мир Домингос Педро
Аналогия была искрой, из которой разгорелись величайшие научные достижения в истории человечества. Теория естественного отбора родилась, когда Дарвин, читая An Essay on the Principle of Population («Опыт о законе народонаселения») Мальтуса, был поражен сходством между борьбой за выживание в экономике и в природе. Модель атома появилась на свет, когда Бор увидел в ней миниатюрную Солнечную систему, где электроны соответствовали планетам, а ядро — Солнцу. Кекуле открыл кольцевую форму молекулы бензола, представив себе змею, пожирающую свой хвост.
У рассуждений по аналогии выдающаяся интеллектуальная родословная. Еще Аристотель выразил их в своем законе подобия: если две вещи схожи, мысль об одной из них будет склонна вызывать мысль о другой. Эмпирики, например Локк и Юм, пошли по этому пути. Истина, говорил Ницше, — это движущаяся армия метафор. Аналогии любил Кант, а Уильям Джеймс полагал, что чувство одинаковости — киль и позвоночник человеческого мышления. Некоторые современные психологи даже утверждают, что человеческое познание целиком соткано из аналогий. Мы полагаемся на них, чтобы найти дорогу в новом городе и чтобы понять такие выражения, как «увидеть свет» и «не терять лица». Подростки, которые в каждое предложение вставляют словечко «типа», согласятся, типа, что аналогия — это, типа, важная штука.
С учетом всего этого неудивительно, что аналогия играет видную роль в машинном обучении. Однако дорогу себе она пробивала медленно, и поначалу ее затмевали нейронные сети. Первое воплощение аналогии в алгоритме появилось в малоизвестном отчете, написанном в 1951 году Эвелин Фикс и Джо Ходжесом — статистиками из Университета Беркли, — и потом десятки лет не публиковалось в мейнстримных журналах. Однако тем временем начали появляться, а потом множиться другие статьи об алгоритме Фикс и Ходжеса, пока он не стал одним из самых исследуемых в информатике. Алгоритм ближайшего соседа — так он называется — будет первым шагом в нашем путешествии по обучению на основе аналогий. Вторым станет метод опорных векторов, который, как буря, налетел на машинное обучение на переломе тысячелетий и лишь недавно встретил достойного соперника в лице глубокого обучения. Третья и последняя тема — это полноценное аналогическое рассуждение, которое несколько десятилетий было базовым в психологии и искусственном интеллекте и примерно столько же — в машинном обучении.
Аналогизаторы — наименее сплоченное из пяти «племен». В отличие от приверженцев других учений, которых объединяет сильное чувство идентичности и общие идеалы, аналогизаторы представляют собой скорее свободное собрание ученых, согласных с тем, что в качестве основы обучения нужно полагаться на суждения о сходстве. Некоторые, например ребята, занимающиеся методом опорных векторов, могут даже не захотеть встать под общий зонтик. Но за окном идет дождь из глубоких моделей, и мне кажется, действовать сообща им не повредит. Аналогия — одна из центральных идей в машинном обучении, и аналогизаторы всех мастей — ее хранители. Может быть, в грядущем десятилетии в машинном обучении будет доминировать глубокая аналогия, соединяющая в один алгоритм эффективность ближайшего соседа, математическую сложность метода опорных векторов и мощь и гибкость рассуждения по аналогии. (Вот я и выдал один из своих секретных научных проектов.)
Попробуй подобрать мне пару
Алгоритм ближайшего соседа — самый простой и быстрый обучающийся алгоритм, какой только изобрели ученые. Можно даже сказать, что это вообще самый быстрый алгоритм, который можно придумать. В нем не надо делать ровным счетом ничего, и поэтому для выполнения ему требуется нулевое время. Лучше не бывает. Если вы хотите научиться узнавать лица и в вашем распоряжении есть обширная база данных изображений с ярлыками «лицо / не лицо», просто усадите этот алгоритм за работу, расслабьтесь и будьте счастливы. В этих изображениях уже скрыта модель того, что такое лицо. Представьте, что вы Facebook и хотите автоматически определять лица на фотографиях, которые загружают пользователи, — это будет прелюдией к автоматическому добавлению тегов с именами друзей. Будет очень приятно ничего не делать, учитывая, что ежедневно в Facebook люди загружают свыше трехсот миллионов фотографий. Применение к ним любого из алгоритмов машинного обучения, которые мы до сих пор видели (может быть, кроме наивного байесовского), потребовало бы массы вычислений. А наивный Байес недостаточно сообразителен, чтобы узнавать лица.
Конечно, за все надо платить, и цена в данном случае — это время проверки. Джейн Юзер только что загрузила новую картинку. Это лицо или нет? Алгоритм ближайшего соседа ответит: найди самую похожую картинку во всей базе данных маркированных фотографий — ее «ближайшего соседа». И если на найденной картинке лицо, то и на этой тоже. Довольно просто, но теперь придется за долю секунды (в идеале) просканировать, возможно, миллиарды фотографий. Алгоритм застают врасплох, и, как ученику, который не готовился к контрольной, ему придется как-то выходить из положения. Однако в отличие от реальной жизни, где мама учит не откладывать на завтра то, что можно сделать сегодня, в машинном обучении прокрастинация может принести большую пользу. Вообще говоря, всю область, в которую входит алгоритм ближайшего соседа, называют «ленивым обучением», и в таком термине нет ничего обидного.
Ленивые обучающиеся алгоритмы намного умнее, чем может показаться, потому что их модели, хотя и неявные, могут быть невероятно сложными. Давайте рассмотрим крайний случай, когда для каждого класса у нас есть только один пример. Допустим, мы хотим угадать, где проходит граница между двумя государствами, но знаем мы только расположение их столиц. Большинство алгоритмов машинного обучения зайдет здесь в тупик, но алгоритм ближайшего соседа радостно скажет, что граница — это прямая линия, лежащая на полпути между двумя городами.
Точки на этой линии находятся на одинаковом удалении от обоих столиц. Точки слева от нее ближе к Позитивску, поэтому ближайший сосед предполагает, что они относятся к Позистану, и наоборот. Конечно, если бы это была точная граница, нам бы крупно повезло, но и это приближение, вероятно, намного лучше, чем ничего. Однако по-настоящему интересно становится, когда мы знаем много городов по обеим сторонам границы:
Ближайший сосед способен провести очень сложную границу, хотя он просто запоминает, где находятся города, и в соответствии с этим относит точки к тому или иному государству. «Агломерацией» города можно считать все точки, которые к нему ближе, чем к любому другому. Границы между такими агломерациями показаны на рисунке пунктиром. Теперь и Позистан, и Негативия — просто объединение агломераций всех городов этих стран. В отличие от этого алгоритма, деревья решений (например) способны лишь проводить границы, проходящие попеременно с севера на юг и с востока на запад, что, вероятно, будет намного худшим приближением настоящей границы. Таким образом, хотя алгоритмы на основе дерева решений будут изо всех сил стараться за время обучения определить, где проходит граница, победит «ленивый» метод ближайшего соседа.
Все дело в том, что построить глобальную модель, например дерево решений, намного сложнее, чем просто одно за другим определить положение конкретных элементов запроса. Представьте себе попытку определить с помощью дерева решений, что такое лицо. Можно было бы сказать, что у лица два глаза, нос и рот, но что такое глаз и как его найти на изображении? А если человек закроет глаза? Дать надежное определение лица вплоть до отдельных пикселей крайне сложно, особенно учитывая всевозможные выражения, позы, контекст, условия освещения. Алгоритм ближайшего соседа этого не делает и срезает путь: если в базе данных изображение, больше всего похожее на то, которое загрузила Джейн, — это лицо, значит на загруженном изображении тоже лицо. Чтобы все работало, в базе данных должна найтись достаточно похожая картинка, например лицо в аналогичном положении, освещении и так далее, поэтому чем больше база данных, тем лучше. Для простой двухмерной проблемы, например угадывания границы между двумя странами, маленькой базы данных будет достаточно. Для очень сложной проблемы, например определения лиц, где цвет каждого пикселя — это измерение вариативности, понадобится огромная база данных. Сегодня такие базы существуют. Обучение с их помощью может быть слишком затратным для трудолюбивых алгоритмов, которые явно проводят границу между лицами и не-лицами, однако для ближайшего соседа граница уже скрыта в расположении точек данных и расстояниях, и единственная затрата — это время запроса.
Та же идея создания локальной модели вместо глобальной работает и за пределами проблем классификации. Ученые повсеместно используют линейную регрессию для прогнозирования непрерывных переменных, несмотря на то что большинство явлений нелинейны. К счастью, явления линейны локально, потому что гладкие кривые локально хорошо аппроксимируются прямыми линиями. Поэтому не пытайтесь подобрать прямую ко всем данным — сначала подгоните ее к точкам рядом с точкой запроса: получится очень мощный алгоритм нелинейной регрессии. Лень оправдывает себя. Если бы Кеннеди захотел получить полную теорию международных отношений, чтобы решить, что делать с ракетами на Кубе, у него были бы проблемы. Но он увидел аналогию между кризисом и ситуацией перед Первой мировой войной, и эта аналогия направила его к правильным решениям.
Как поведал Стивен Джонсон в книге The Ghost Map, алгоритм ближайшего соседа может спасать жизни. В 1854 году Лондон поразила вспышка холеры. В некоторых частях города от нее умер каждый восьмой житель. Господствовавшая тогда теория, что холера вызвана якобы плохим воздухом, не помогла предотвратить распространение эпидемии. Но Джон Сноу, физик, скептически относившийся к этой теории, придумал кое-что получше. Он отметил на карте Лондона все известные случаи холеры и разделил карту на области, расположенные ближе всего к общественным водокачкам. Эврика! Оказалось, что почти все смерти приходились на «агломерацию» конкретного водозабора, расположенного на Брод-стрит в районе Сохо. Сделав вывод, что вода там заражена, Сноу убедил местные власти выключить насос, и эпидемия сошла на нет. Из этого случая родилась эпидемиология, а еще это пример первого успешного применения алгоритма ближайшего соседа — почти за столетие до его официального открытия.
В алгоритме ближайшего соседа каждая точка данных — это маленький классификатор, предсказывающий класс для всех примеров запросов, на которые она правильно отвечает. Это как армия муравьев: отдельные солдаты сами по себе делают немного, но вместе способны сдвигать горы. Если груз слишком тяжел для одного муравья, он зовет соседей. Метод k-ближайших соседей действует в том же духе: тестовый пример классифицируется путем нахождения k-ближайших соседей, которые после этого голосуют. Если ближайшее изображение к только что загруженному — это лицо, но следующие два ближайших — нет, третий ближайший сосед решает, что загруженная картинка все же не лицо. Алгоритм ближайшего соседа подвержен переобучению: если точке данных присвоен неправильный класс, он распространится на всю свою агломерацию. Алгоритм k-ближайших соседей более устойчив, потому что ошибается только тогда, когда большинство из k-ближайших соседей зашумлены. Но за это приходится платить более замутненным зрением: из-за голосования размываются мелкие детали границы. Когда k идет вверх, дисперсия уменьшается, но увеличивается смещенность.
Брать k-ближайших соседей вместо одного — это еще не все. Интуиция подсказывает, что примеры, ближе всего расположенные к тестовому, должны быть важнее. Это ведет нас к взвешенному алгоритму k-ближайших соседей. В 1994 году группа ученых из Миннесотского университета и Массачусетского технологического института построила рекомендательную систему на основе, по их словам, «обманчиво простой идеи»: люди, которые соглашались на что-то в прошлом, с большей вероятностью согласятся на это и в будущем. Эта мысль вела прямиком к системам коллаборативной фильтрации, которые имеются на всех уважающих себя сайтах электронной торговли. Представьте, что вы, как Netflix, собрали базу данных, где каждый пользователь присваивает просмотренным фильмам рейтинг от одной до пяти звезд. Вы хотите определить, понравится ли вашему пользователю по имени Кен фильм «Гравитация», поэтому ищете пользователей, оценки которых лучше всего коррелируют с оценками Кена. Если все они присвоили «Гравитации» высокий рейтинг, вероятно, так поступит и Кен, и этот фильм можно ему посоветовать. Если, однако, у них нет единого мнения в отношении «Гравитации», все равно нужно как-то выйти из положения, и в данном случае пригодится список пользователей, упорядоченный по их корреляции с Кеном. Если Ли коррелирует с Кеном сильнее, чем Мег, его оценки должны считаться, соответственно, более важными. Спрогнозированная оценка Кена будет таким образом средней взвешенной оценок его соседей, где вес каждого соседа — это его коэффициент корреляции с Кеном.
Однако есть интересный момент. Представьте, что у Ли и Кена очень схожие вкусы, но, когда Кен дает фильму пять звездочек, Ли всегда выставляет три, когда Кен дает три, Ли — только одну и так далее. Нам хотелось бы использовать оценки Ли для прогнозирования оценок Кена, но, если сделать это «в лоб», мы всегда будем отклоняться на две звездочки. Вместо этого нужно предсказать, насколько рейтинги Кена будут выше или ниже его средней, основываясь на таком же показателе для Ли. Теперь видно, что Кен всегда на две звездочки выше своей средней, когда Ли на две звездочки выше своей, и наш прогноз будет попадать в точку.
Кстати говоря, для коллаборативной фильтрации явные оценки не обязательны. Если Кен заказал фильм на Netflix, это значит, что он ожидает, что фильм ему понравится. Так что «оценкой» может быть просто «заказал / не заказал», и два пользователя будут похожи, если они заказывают много одинаковых фильмов. Даже простой клик на что-то косвенно показывает интерес пользователя. Алгоритм ближайшего соседа работает во всех этих случаях. Сегодня для того, чтобы давать рекомендации посетителям сайта, используются все виды алгоритмов, но взвешенный k-ближайший сосед был первым, нашедшим широкое применение в этой области, и его до сих пор сложно победить.
Рекомендательные системы — это большой бизнес: Amazon они дают треть доходов, а Netflix — три четверти. А ведь когда-то метод ближайшего соседа считался непрактичным из-за высоких требований к памяти. В те времена память компьютеров делали из маленьких сердечников, напоминавших железные кольца, по одному для каждого бита, и хранение даже нескольких тысяч примеров было обременительно. Сейчас времена изменились. Тем не менее не всегда целесообразно запоминать все увиденные примеры, а затем искать среди них, особенно потому что большинство из них, вероятно, не имеют отношения к делу. Еще раз взгляните на карту Позистана и Негативии и обратите внимание, что, если Позитивск исчезнет, граница с Негативией не изменится: агломерации близлежащих городов расширятся и займут земли, которые занимала столица, но все они позистанские. Города, которые имеют значение, располагаются исключительно вдоль границы, поэтому все остальные можно опустить. Из этого вытекает простой способ повысить эффективность метода ближайшего соседа: нужно удалить примеры, которые были правильно классифицированы их соседями. Благодаря этому и другим приемам методы ближайшего соседа находят применение в самых неожиданных областях, например в управлении манипулятором робота в реальном времени. Но при этом в таких областях, как высокочастотный трейдинг, где компьютеры покупают и продают ценные бумаги в доли секунды, такие методы по-прежнему не в почете. В гонке между нейронными сетями, которые можно применять к примерам с фиксированным количеством сложений, умножений и сигмоид, и алгоритмом, который должен искать ближайшего соседа в большой базе данных, нейронная сеть обязательно победит.
Другая причина, по которой исследователи поначалу скептически относились к ближайшему соседу, заключается в том, что было непонятно, может ли он определять истинные границы между понятиями. Но в 1967 году ученые-информатики Том Кавер и Питер Харт доказали, что при наличии достаточного количества данных ближайший сосед в худшем случае подвержен ошибкам всего в два раза больше, чем лучший вообразимый классификатор. Если, скажем, как минимум один процент тестовых примеров неизбежно будет неправильно классифицирован из-за зашумленности данных, ближайший сосед гарантированно получит максимум два процента ошибок. Это было историческое открытие. До этого момента все известные классификаторы исходили из того, что граница имеет очень четкую форму, обычно прямую линию. Это давало и плюсы, и минусы: с одной стороны, можно было доказать правильность, как в случае с перцептроном, но при этом появлялись строгие ограничения на то, что такой классификатор может узнать. Метод ближайшего соседа был первым в истории алгоритмом, который мог воспользоваться преимуществом неограниченного количества данных, чтобы обучаться произвольно сложным понятиям. Человеку не под силу проследить границы, которые он образует в гиперпространстве из миллионов примеров, но благодаря доказательству Кавера и Харта мы знаем, что они, вероятно, недалеки от истины. Рэй Курцвейл считает, что сингулярность начинается, когда люди перестают понимать, что делают компьютеры. По этому стандарту не совсем преувеличением будет сказать, что это уже происходит и началось еще в 1951 году, когда Фикс и Ходжес изобрели метод ближайшего соседа — самый маленький алгоритм, какой только можно изобрести.
Проклятие размерности
Конечно, в райском саду есть и Змей. Его зовут Проклятие Размерности, и, хотя он в большей или меньшей степени поражает все алгоритмы машинного обучения, для ближайшего соседа он особенно опасен. В низких измерениях (например, двух или трех) ближайший сосед обычно работает довольно хорошо, но по мере увеличения количества измерений все довольно быстро начинает рушиться. Сегодня нет ничего необычного в обучении на тысячах или даже миллионах атрибутов. Для коммерческих сайтов, пытающихся узнать ваши предпочтения, атрибутом становится каждый клик. То же самое с каждым словом на веб-странице, с каждым пикселем в изображении. А у ближайшего соседа проблемы могут появиться даже с десятками или сотнями атрибутов. Первая проблема в том, что большая часть атрибутов не имеет отношения к делу: можно знать миллион фактов о Кене, но, вполне возможно, лишь немногие из них могут что-то сказать (например) о его риске заболеть раком легких. Для конкретно этого предсказания критически важно знать, курит Кен или нет, а информация о курении вряд ли поможет решить, понравится ли ему «Гравитация». Символистские методы со своей стороны довольно хорошо убирают неподходящие атрибуты: если в атрибуте не содержится информация о данном классе, его просто не включают в дерево решений или набор правил. Но метод ближайшего соседа неподходящие атрибуты безнадежно запутывают, потому что все они вносят свой вклад в сходство между примерами. Если не имеющих отношения к делу атрибутов будет достаточно много, случайное сходство в нерелевантных измерениях подавит имеющее значение сходство в важных, и метод ближайшего соседа окажется ничем не лучше случайного угадывания.
Еще одна большая и неожиданная проблема заключается в том, что большое число атрибутов может мешать, даже когда все они имеют отношение к делу. Может показаться, что много информации — это всегда благо. Разве это не лозунг нашего времени? Но по мере увеличения числа измерений начинает экспоненциально расти число обучающих примеров, необходимых для определения границ понятия. Двадцать булевых атрибутов дадут примерно миллион возможных примеров. С двадцать первым примеров станет два миллиона, с соответствующим числом способов прохождения между ними границы. Каждый лишний атрибут делает проблему обучения в два раза сложнее, и это если атрибуты булевы. Если атрибут высокоинформативный, польза от его добавления может превышать затраты. Но когда в распоряжении есть лишь малоинформативные атрибуты, например слова в электронном письме или пиксели изображения, это, вероятно, породит проблемы, несмотря на то что в совокупности они могут нести достаточно информации, чтобы предсказать то, что вы хотите.
Все даже хуже. Ближайший сосед основан на нахождении схожих объектов, а в высоких измерениях распадается сама идея сходства. Гиперпространство — как сумеречная зона. Наша интуиция, основанная на опыте жизни в трех измерениях, там не действует, и начинают происходить все более и более странные вещи. Представьте себе апельсин: шарик вкусной мякоти, окруженный тонкой кожицей. Мякоть в апельсине занимает, скажем, 90 процентов радиуса, а оставшиеся десять приходятся на кожуру. Это означает, что 73 процента объема апельсина — это мякоть (0,93). Теперь рассмотрим гиперапельсин: если мякоть занимает все те же 90 процентов радиуса, но, скажем, в сотне измерений, то она сократится примерно до всего лишь 31000 процента объема (0,9100). Гиперапельсин будет состоять из одной кожуры, и его никогда нельзя будет очистить!
Беспокоит и то, что происходит с нашей старой знакомой, гауссовой кривой. Нормальное распределение говорит, что данные в сущности расположены в какой-то точке (средняя распределения), но с некоторым расхождением вокруг нее (заданным стандартным отклонением). Верно? Да, но не в гиперпространстве. При нормальном распределении в высокой размерности будет выше вероятность получить пример далеко от средней, чем близко к ней. Кривая Гаусса в гиперпространстве больше похожа на пончик, чем на колокол. Когда ближайший сосед входит в этот беспорядочный мир, он безнадежно запутывается. Все примеры выглядят одинаково схожими и при этом слишком далеко отстоят друг от друга, чтобы делать полезные прогнозы. Если случайным образом равномерно рассеять примеры внутри высокоразмерного гиперкуба, большинство окажется ближе к грани этого куба, чем к своему ближайшему соседу. На средневековых картах неисследованные области обозначали драконами, морскими змеями и другими фантастическими существами или просто фразой «Здесь драконы». В гиперпространстве драконы повсюду, в том числе прямо в дверях. Попробуйте прогуляться в гости к соседу, и вы никогда туда не доберетесь: станете вечно блуждать в чужих землях и гадать, куда делись все знакомые предметы.
Деревья решений тоже не застрахованы от проклятия размерности. Скажем, понятие, которое вы пытаетесь получить, представляет собой сферу: точки внутри нее положительные, а снаружи — отрицательные. Дерево решений может приблизить сферу самым маленьким кубом, в который она помещается. Это не идеально, но и не очень плохо: неправильно классифицированы будут только углы. Однако в большем числе измерений почти весь объем гиперкуба окажется вне гиперсферы, и на каждый пример, который вы правильно классифицируете как положительный, будет приходиться много отрицательных, которые вы сочтете положительными, а это резко снижает точность.
На самом деле такая проблема есть у всех обучающихся алгоритмов — это вторая беда машинного обучения после переобучения. Термин «проклятие размерност» был придуман в 50-е годы Ричардом Беллманом[93], специалистом по теории управления. Он заметил, что алгоритмы управления, которые хорошо работают в трех измерениях, становятся безнадежно неэффективными в пространствах с большим числом измерений, например, когда вы хотите контролировать каждый сустав манипулятора или каждую ручку на химическом комбинате. А в машинном обучении проблема не только в вычислительных затратах: с ростом размерности само обучение становится все сложнее и сложнее.
Тем не менее не все потеряно. Во-первых, можно избавиться от не имеющих отношения к делу измерений. Деревья решений делают это автоматически, путем вычисления информационного выигрыша от каждого атрибута и выбора самых информативных. В методе ближайшего соседа мы можем сделать нечто похожее, сначала отбросив все атрибуты, которые дают прирост информации ниже определенного порога, а затем измерив схожесть в пространстве с меньшим числом измерений. В некоторых случаях это быстрый и достаточно хороший прием, но, к сожалению, ко многим понятиям он неприменим. Среди них, например, исключающее ИЛИ: если атрибут говорит что-то о данном классе только в сочетании с другими атрибутами, он будет отброшен. Более затратный, но хитрый вариант — «обернуть» выбор атрибута вокруг самого обучающегося алгоритма с поиском путем восхождения на выпуклые поверхности, который будет удалять атрибуты, пока это не повредит точности метода ближайшего соседа на скрытых данных. Ньютон многократно выбирал атрибуты и определил, что для предсказания траектории тела важна только его масса, а не цвет, запах, возраст и миллиард других свойств. Вообще говоря, самое важное в уравнении — все те количества, которые в нем не появляются: когда известны самые существенные элементы, часто оказывается легче разобраться, как они зависят друг от друга.
Одно из решений проблемы неважных атрибутов — определение их веса. Вместо того чтобы считать сходство по всем измерениям равноценным, мы «сжимаем» наименее подходящие. Представьте, что обучающие примеры — это точки в комнате и высота для наших целей не требуется. Если ее отбросить, все примеры спроецируются на пол. Произвести понижающее взвешивание — все равно что опустить в комнате потолок. Высота точки все еще засчитывается при вычислении расстояния до других точек, но уже меньше, чем ее горизонтальное положение. И, как и многое другое в машинном обучении, вес атрибутов можно найти путем градиентного спуска.
Может случиться, что потолок в комнате высокий, а точки данных лежат рядом с полом, как тонкий слой пыли на ковре. В этом случае нам повезло: проблема выглядит трехмерной, но в сущности она ближе к двухмерной. Мы не будем сокращать высоту, потому что это уже сделала природа. Такое «благословение неравномерности» данных в (гипер)пространстве часто спасает положение. У примеров могут быть тысячи атрибутов, но в реальности все они «живут» в пространстве с намного меньшим числом измерений. Именно поэтому метод ближайшего соседа бывает хорош, например, для распознавания написанных вручную цифр: каждый пиксель — это измерение, поэтому измерений много, но лишь мизерная доля всех возможных изображений — цифры, и все они живут вместе в уютном уголке гиперпространства. Форма низкоразмерного пространства c данными бывает, однако, довольно своенравна. Например, если в комнате стоит мебель, пыль оседает не только на пол, но и на столы, стулья, покрывала и так далее. Если можно определить примерную форму слоя пыли, покрывающей комнату, тогда останется найти координаты каждой точки на нем. Как мы увидим в следующей главе, целая субдисциплина машинного обучения посвящена открытию форм этих слоев путем, так сказать, прощупывания гиперпространства во тьме.
Змеи на плоскости
Метод ближайшего соседа оставался самым широко используемым обучающимся алгоритмом аналогистов вплоть до середины 1990-х, когда его затмили более гламурные кузены из других «племен». Но тут, сметая все на своем пути, на смену ворвался новый алгоритм, основанный на принципах сходства. Можно сказать, что это был еще один «дивиденд от мира», плод окончания холодной войны. Метод опорных векторов был детищем советского специалиста по частотному подходу Владимира Вапника[94]. Вапник большую часть своей карьеры работал в московском Институте проблем управления, но в 1990 году Советский Союз рухнул, и ученый уехал в США, где устроился на работу в легендарную Bell Labs[95]. В России Вапник в основном довольствовался теоретической, бумажной работой, но атмосфера в Bell Labs была иной. Исследователи стремились к практическим результатам, и Вапник наконец решился превратить свои идеи в алгоритм. В течение нескольких лет он с коллегами по лаборатории разработал метод опорных векторов, и вскоре опорные векторы оказались повсюду и принялись ставить новые рекорды точности.
На первый взгляд метод опорных векторов во многом похож на взвешенный алгоритм k-ближайших соседей: граница между положительными и отрицательными классами определяется мерой схожести примеров и их весами. Тестовый пример принадлежит к положительному классу, если в среднем он выглядит более похожим на положительные примеры, чем на отрицательные. Среднее взвешивается, и метод опорных векторов помнит только ключевые примеры, необходимые для проведения границы. Если еще раз посмотреть на Позистан и Негативию без городов, не расположенных на границе, останется такая карта:
Примеры здесь называются опорными векторами, потому что это векторы, которые «поддерживают» границу: уберите один, и участок границы соскользнет в другое место. Также можно заметить, что граница представляет собой зубчатую линию с резкими углами, которые зависят от точного расположения примеров. У реальных понятий, как правило, границы более плавные, а это означает, что приближение, сделанное методом ближайшего соседа, вероятно, не идеально. Благодаря методу опорных векторов можно сделать границу гладкой, больше похожей на эту:
Чтобы обучить метод опорных векторов, нужно выбрать опорные векторы и их вес. Меру схожести, которая в мире опорных векторов называется ядром, обычно назначают априорно. Одним из важнейших открытий Вапника было то, что не все границы, отделяющие положительные тренировочные примеры от отрицательных, равноценны. Представьте, что Позистан воюет с Негативией и государства разделены нейтральной полосой с минными полями с обеих сторон. Ваша задача — исследовать эту ничейную землю, пройдя с одного ее конца к другому, и не взлететь на воздух. К счастью, у вас в руках карта c расположением мин. Вы, понятное дело, выберете не просто любую старую тропинку, а станете обходить мины как можно более широким кругом. Именно так поступает метод опорных векторов: мины для него — это примеры, а найденная тропа — выученная граница. Самое близкое место, где граница подходит к примеру, — ее зазор, и метод опорных векторов выбирает опорные векторы и веса так, чтобы зазор был максимальным. Например, сплошная прямая граница на этом рисунке лучше, чем пунктирная:
Пунктирная граница четко разделяет положительные и отрицательные примеры, но опасно близко подходит к минам A и B. Эти примеры — опорные векторы. Удалите один из них, и граница с максимальным зазором переместится в другое место. Конечно, граница может быть изогнутой, из-за чего зазор сложнее визуализировать, но можно представить себе, как по ничейной земле ползет змея и зазор — ее жировые отложения. Если без риска взорваться на кусочки может проползти очень толстая змея, значит, метод опорных векторов хорошо разделяет положительные и отрицательные примеры, и Вапник показал, что в этом случае можно быть уверенным, что метод не подвержен переобучению. Интуиция подсказывает, что у толстой змеи меньше способов проскользнуть мимо мин, чем у тощей, и точно так же, если зазор большой, у него меньше шансов переобучиться данным, нарисовав слишком замысловатую границу.
Вторая часть истории — это то, как метод опорных векторов находит самую толстую змею, способную проползти между положительными и отрицательными минами. Может показаться, что обучения весам для каждого тренировочного примера путем градиентного спуска будет достаточно. Надо просто найти веса, которые максимизируют зазор, и любой пример, который заканчивается нулевым весом, можно отбросить. К сожалению, в таком случае веса начали бы расти безгранично, потому что с точки зрения математики чем больше веса, тем больше зазор. Если вы находитесь в метре от мины и удвоите размер всего, включая вас самих, от мины вас станут отделять два метра, но это не уменьшит вероятности, что вы на нее наступите. Вместо этого придется максимизировать зазор под давлением того, что веса могут увеличиться лишь до какой-то фиксированной величины. Или аналогично можно минимизировать веса под давлением того, что все примеры имеют данный зазор, который может быть единицей — точное значение произвольно. Это то, что обычно делает метод опорных векторов.
Оптимизация при наличии ограничений — проблема максимизации или минимизации функции, в отношении которой действуют некие условия. Вселенная, например, максимизирует энтропию при условии сохранения постоянства энергии. Проблемы такого рода широко распространены в бизнесе и технологиях. Можно стремиться максимизировать число единиц продукции, которое производит фабрика, при условии доступного числа машинных инструментов, спецификаций продукции и так далее. С появлением метода опорных векторов оптимизация при наличии ограничений стала критически важной и в машинном обучении. Неограниченная оптимизация сравнима с тем, как добраться до вершины горы, и именно это делает градиентный спуск (в данном случае восхождение). Ограниченная оптимизация — все равно что зайти как можно выше, но при этом не сходить с дороги. Но если дорога будет доходить до самой вершины, ограниченные и неограниченные проблемы будут иметь одно и то же решение. Однако чаще дорога сначала петляет вверх по горе, а затем сворачивает вниз, так и не достигнув вершины. Вы понимаете, что достигли высочайшей точки дороги, и не можете зайти выше, не съехав с нее. Другими словами, путь к вершине находится под прямым углом к дороге. Если дорога и путь к вершине образуют острый или тупой угол, всегда можно забраться еще выше, продолжая ехать по дороге, даже если вы не подниметесь так быстро, как если бы пошли прямо к вершине. Поэтому для решения проблемы ограниченной оптимизации надо следовать не по градиенту, а по его части, параллельной поверхности ограничения — в данном случае дороги, — и остановиться, когда эта часть будет равна нулю.
В целом нам надо справиться со многими ограничениями сразу (в случае метода опорных векторов — по одному на каждый пример). Представьте, что вы хотите подобраться как можно ближе к Северному полюсу, но не можете выйти из комнаты. Каждая из четырех стен комнаты — это ограничение, поэтому для решения задачи надо идти по компасу, пока вы не упретесь в угол, где встречаются северо-восточная и северо-западная стена. Эти стены будут активными ограничениями, потому что они не дадут вам достичь оптимума, а именно Северного полюса. Если одна из стен вашей комнаты смотрит точно на север, она станет единственным активным ограничением; для решения надо направиться в ее центр. А если вы Санта-Клаус и живете прямо на Северном полюсе, все ограничения окажутся неактивными и можно будет сесть и поразмышлять над проблемой оптимального распределения игрушек. (Бродячим торговцам легче, чем Санте.) В методе опорных векторов активные ограничения — опорные векторы, поскольку их зазоры уже наименьшие из разрешенных. Перемещение границы нарушило бы одно или больше ограничений. Все другие примеры не имеют отношения к делу и их вес равен нулю.
В реальности методу опорных векторов обычно разрешается нарушать некоторые ограничения, то есть классифицировать некоторые примеры неправильно или менее чем на зазор, потому что в противном случае будет возникать переобучение. Если где-то в центре положительной области есть негативный пример, создающий шум, нам не надо, чтобы граница вилась внутри положительной зоны просто ради того, чтобы правильно классифицировать этот пример. Однако за каждый неправильно определенный пример начисляются штрафные баллы, и это стимулирует метод опорных векторов сводить их к минимуму. Так что данный метод как песчаные черви в «Дюне»: большие, мощные и способные пережить довольно много взрывов, но не слишком много.
В поисках применения своему алгоритму Вапник и его сотрудники вскоре вышли на распознавание написанных от руки цифр, в котором их коллеги-коннекционисты в Bell Labs были мировыми экспертами. Ко всеобщему удивлению, метод опорных векторов с ходу справился не хуже многослойного перцептрона, который тщательно, годами оттачивали для распознавания цифр. Это подготовило почву для долгой интенсивной конкуренции между методами. Метод опорных векторов можно рассматривать как обобщение перцептрона, использование специфической меры сходства (скалярного произведения векторов) даст гиперплоскостную границу между классами. Но у метода опорных векторов имеется большое преимущество по сравнению с многослойными перцептронами: у весов есть единичный оптимум, а не много локальных, и поэтому их намного легче надежно найти. Несмотря на это, опорные векторы не менее выразительны, чем многослойные перцептроны: опорные векторы фактически действуют как скрытый слой, а их взвешенное среднее — как выходной слой. Например, метод опорных векторов может легко представлять функцию исключающего ИЛИ, имея один опорный вектор для каждой из четырех возможных конфигураций. Но и коннекционисты не сдавались без боя. В 1995 году Ларри Джекел, глава отдела Bell Labs, в котором работал Вапник, поспорил с ним на хороший обед, что к 2000 году нейронные сети будут так же понятны, как метод опорных векторов. Он проиграл. В ответ Вапник поспорил, что к 2005 году никто не будет пользоваться нейронными сетями. И тоже проиграл. (Единственным, кто бесплатно пообедал, был Янн Лекун, их свидетель.) Более того, с появлением глубокого обучения коннекционисты снова взяли верх. При условии обучаемости, сети со многими слоями могут выражать многие функции компактнее, чем метод опорных векторов, у которого всегда только один слой, а это иногда имеет решающее значение.
Другим заметным ранним успехом метода опорных векторов была классификация текстов, которая оказалась большим благом для зарождающегося интернета. В то время самым современным классификатором был наивный байесовский алгоритм, но, когда каждое слово в языке — это измерение, даже он мог начать переобучаться. Для этого достаточно слова, которое по случайности в тренировочных данных встречается на всех спортивных страницах и ни на каких других: в этом случае у наивного Байеса появятся галлюцинации, что любая страница, содержащая это слово, посвящена спорту. А метод опорных векторов благодаря максимизации зазора может сопротивляться переобучению даже при очень большом числе измерений.
В целом чем больше опорных векторов выбирает метод, тем лучше он обобщает. Любой обучающий пример, который не представляет собой опорный вектор, будет правильно классифицирован, если появится в тестовой выборке, потому что граница между положительными и отрицательными примерами по-прежнему будет на том же месте. Поэтому ожидаемая частота ошибок метода опорных векторов, как правило, равна доле примеров, являющихся опорными векторами. По мере роста числа измерений эта доля тоже будет расти, поэтому метод не застрахован от проклятия размерности, но он более устойчив к нему, чем большинство алгоритмов.
Кроме практических успехов, метод опорных векторов перевернул с ног на голову много воззрений, которые олицетворяли здравый смысл в машинном обучении. Например, опроверг утверждение, которое иногда путают с бритвой Оккама, что более простые модели точнее. Метод может иметь бесконечное число параметров и все равно не переобучаться при условии, что у него достаточно большой зазор.
Самое неожиданное свойство метода опорных векторов заключается в следующем: какие бы изогнутые границы он ни проводил, эти границы всегда будут прямыми линиями (или гиперплоскостями). В этом нет противоречия. Причина заключается в том, что прямые линии будут находиться в другом пространстве. Допустим, примеры живут на плоскости (x, y), а граница между положительными и отрицательными областями — это парабола y = x2. Ее невозможно представить в виде прямой линии, но, если мы добавим третью координату z [данные окажутся в пространстве (x, y, z)] и установим координату z каждого примера равной квадрату его координаты x, граница будет просто диагональной плоскостью, определенной y = z. В результате точки данных поднимутся в третье измерение, некоторые больше, чем другие, но ровно настолько, насколько нужно, и — вуаля! — в этом новом измерении положительные и отрицательные примеры можно будет разделить плоскостью. То, что метод делает с ядрами, опорными векторами и весами, можно рассматривать как картирование данных в более высокоразмерное пространство и нахождение в этом пространстве гиперплоскости с максимальным зазором. Для некоторых ядер полученное поле имеет бесконечное число измерений, но для метода опорных векторов это совершенно не важно. Может быть, гиперпространство — это и сумеречная зона, но метод опорных векторов знает, как находить в ней путь.
Вверх по лестнице
Две вещи схожи, если они в определенном отношении совпадают друг с другом. Если они в чем-то совпадают, вероятно, в чем-то они будут отличаться. В этом суть аналогии. Это указывает и на две главные подпроблемы рассуждения по аналогии: как понять, насколько похожи две вещи, и как решить, какие выводы можно сделать из этих сходств. Пока мы исследовали «маломощную» область аналогии — алгоритмы вроде ближайшего соседа и метод опорных векторов, — ответы на оба вопроса были очень простыми. Такие алгоритмы наиболее популярны, но глава об аналогическом обучении будет неполной, если мы хотя бы бегло не рассмотрим более мощные части спектра.
Самый главный вопрос во многих аналогических обучающихся алгоритмах — как измерять сходство. Это может быть просто евклидово расстояние между точками данных или, сложнее, целая программа с многочисленными слоями подпрограмм, которая в конце выдает значение сходства. Так или иначе функция сходства контролирует, как алгоритм машинного обучения обобщает из известных примеров в новые. Именно здесь мы вводим в обучающийся алгоритм наши знания о данной области: это ответ аналогизаторов на вопрос Юма. Аналогическое обучение можно применять ко всем видам объектов, а не только к векторам атрибутов, при условии, что есть какой-то способ измерить сходство между ними. Например, сходство между двумя молекулами можно определить по числу идентичных субструктур, которые они содержат. Метан и метанол схожи, потому что в них есть три связи углерода с водородом, а отличаются они только тем, что в метаноле один атом водорода замещен гидроксильной группой:
Однако это не означает, что схожи химические свойства веществ, ведь метан — это газ, а метанол — спирт. Вторая часть аналогического рассуждения — попытка разобраться, какие выводы можно сделать о новом объекте на основе найденных аналогов. Это бывает и очень просто, и очень сложно. В случае алгоритма ближайшего соседа и метода опорных векторов это просто предсказание класса нового объекта на основе классов ближайших соседей или опорных векторов. Но в случае рассуждения по прецедентам — еще одного типа аналогического обучения — результатом может стать сложная структура, сформированная из элементов найденных объектов. Представьте, что ваш принтер печатает абракадабру и вы звоните в службу поддержки Hewlett-Packard. Есть шанс, что они уже много раз встречались с аналогичной проблемой, поэтому будет правильно найти старые записи и сложить из них потенциальное решение. Мало просто найти жалобы, у которых много общих атрибутов с вашей: например, в зависимости от установленной операционной системы — Windows или Mac OS X — нужен будет очень разный набор настроек и системы, и принтера. Когда самые подходящие случаи найдены, требуемой последовательностью шагов, необходимых для решения вашей проблемы, может оказаться сочетание этапов из разных случаев плюс какие-то дополнительные, специфические элементы.
В настоящее время службы поддержки — это самое популярное применение рассуждения на основе прецедентов. Большинство из них все еще используют посредника-человека, но Eliza IPsoft уже сама общается с клиентом. Эта система дополнена интерактивным 3D-изображением женщины и на сегодняшний день уже решила более 20 миллионов проблем клиентов в основном престижных американских компаний. «Привет из Роботистана, самого дешевого нового направления аутсорсинга», как недавно писали в одном блоге по аутсорсингу. Поскольку аутсорсинг постоянно охватывает все новые профессии, вместе с ним совершенствуется и аналогическое обучение. Уже созданы первые роботы-адвокаты, которые отстаивают тот или иной вердикт на основе прецедентов. Одна из таких систем точно предсказала результаты более 90 процентов рассмотренных ею дел о нарушении производственной тайны. Может быть, в будущем на сессии киберсуда где-нибудь в облаке Amazon робот-адвокат будет оспаривать штраф за превышение скорости, который робот-полицейский выписал вашему беспилотному автомобилю, а вы тем временем станете нежиться на пляже. Тогда мечта Лейбница о сведении всех аргументов к вычислениям наконец сбудется.
Вероятно, труд композитора находится еще выше на лестнице умений. Дэвид Коуп, почетный профессор музыки в Калифорнийском университете в Санта-Круз, разработал алгоритм, который пишет новые музыкальные произведения в стиле известных композиторов путем отбора и рекомбинации коротких отрывков из их сочинений. На конференции, в которой я несколько лет назад участвовал, Коуп продемонстрировал три пьесы: одну на самом деле написанную Моцартом, другую — композитором, имитировавшим его, и третью — сгенерированную системой. Затем Коуп попросил аудиторию проголосовать. Вольфганг Амадей победил, но имитатор-человек уступил компьютеру. Поскольку это была конференция по искусственному интеллекту, публика осталась довольна. На других мероприятиях восторгов было куда меньше. Некоторые слушатели сердито обвиняли Коупа в том, что он уничтожает музыку. Если Коуп прав, то творчество — высшее из непостижимого — сводится к аналогии и рекомбинации. Попробуйте свои силы: найдите в Google «david cope mp3» и послушайте.
Однако самый изящный трюк аналогизаторов — это обучение на проблемах из разных областей. Люди практикуют это постоянно: менеджер может перейти, скажем, из медиакомпании в компанию, занимающуюся потребительскими товарами, и не начнет с нуля, потому что многие управленческие навыки повторяются. На Уолл-стрит приглашают работать множество физиков, потому что физические и финансовые проблемы кажутся очень разными, но зачастую имеют схожую математическую структуру. Тем не менее все алгоритмы машинного обучения, которые мы до сих пор видели, пасуют, если мы натренируем их для предсказания, скажем, броуновского движения, а потом заставим делать прогнозы на фондовой бирже. Цены на бирже и скорости частиц, взвешенных в жидкости, — это разные переменные, поэтому обучающийся алгоритм даже не будет знать, с чего начать. Однако аналогизаторы могут сделать это, используя отображение структур — алгоритм, изобретенный психологом из Северо-Западного университета Дедре Джентнером. Отображение структур берет два описания, находит связное соответствие между некоторыми их элементами и соотношениями, а затем, основываясь на этом соответствии, переносит другие свойства одной структуры на другую. Например, если структуры — это Солнечная система и атом, можно отобразить планеты как электроны, а солнце — как ядро и заключить, подобно Бору, что электроны вращаются вокруг ядра. Истина, конечно, не такая прямолинейная, и уже сделанные аналогии часто приходится корректировать, но иметь возможность учиться на основе единичного примера, как этот, несомненно, ключевой атрибут универсального обучающегося алгоритма. Когда мы сталкиваемся с новым типом рака — а это происходит постоянно, потому что рак непрерывно мутирует, — модели, которые мы узнали из предыдущих случаев, оказываются неприменимы. У нас нет ни времени, чтобы собирать данные о новом типе опухоли, ни множества пациентов: может быть, пациент вообще уникальный, и он срочно нуждается в лекарстве. В таком случае надежду дает сравнение новой разновидности рака с уже известными: попытаться найти похожий случай и предположить, что сработают те же стратегии лечения.
Есть ли что-то, на что неспособна аналогия? Нет, считает Даглас Хофштадтер, когнитивный психолог и автор книги Gdel, Escher, Bach: An Eternal Golden Braid[96]. Хофштадтер немного похож на доброго близнеца Гринча — похитителя Рождества[97] и, вероятно, является самым знаменитым аналогизатором в мире. В книге Surfaces and Essences: Analogy as the Fuel and Fire of Thinking («Поверхности и сущности: аналогия в роли топлива и огня мышления») Хофштадтер и Эммануэль Сандер страстно доказывают, что все разумное поведение сводится к аналогии. Все, что мы узнаём или открываем, начиная со значения повседневных слов, например «мама» и «играть», до гениальных прозрений Альберта Эйнштейна и Эвариста Галуа, — это продукт аналогии. Когда малыш Тим видит, что какие-то женщины присматривают за другими детьми так же, как его собственная мама присматривает за ним, он обобщает понятие «мамочка» до мамы каждого человека, а не только его. Это, в свою очередь, трамплин к таким понятиям, как «мать-природа». «Самая счастливая мысль» Эйнштейна, из которой выросла общая теория относительности, была аналогией между гравитацией и ускорением: если вы едете в лифте, невозможно сказать, с какой из этих сил связан ваш вес, потому что результат одинаков. Мы плывем по широкому океану аналогий, манипулируем ими в своих целях, а они, не ведая того, манипулируют нами. В книгах аналогии встречаются на каждой странице (например, заголовки этого и предыдущего раздела). Gdel, Escher, Bach: An Eternal Golden Braid — расширенная аналогия между теоремой Гёделя, искусством Эшера и музыкой Баха. Если Верховный алгоритм — это не аналогия, он несомненно должен быть в чем-то схож с ней.
Взойди и сияй
В когнитивистике давно не утихают дебаты между символистами и аналогизаторами. Символисты показывают вещи, которые умеют моделировать они, но не умеют аналогизаторы. Затем аналогизаторы решают задачу, указывают на слабые места символистов, и цикл повторяется. Обучение на основе примеров, как его иногда называют, предположительно лучше подходит для моделирования запоминания отдельных эпизодов нашей жизни, а правила, предположительно, лучше выбрать для рассуждений с абстрактными концепциями, например «работа» и «любовь». Когда я был студентом, меня осенило: это ведь просто указывает на существование континуума, и надо уметь учиться на всем его протяжении. Правила — это, по сути, обобщенные частные случаи, где мы «забыли» некоторые атрибуты, потому что они не имеют значения. Частные же случаи — очень конкретные правила с условием для каждого атрибута. В жизни аналогичные эпизоды постепенно абстрагируются и образуют основанные на правилах структуры, например «есть в ресторане». Вы знаете, что пойти в ресторан — это и заказать что-нибудь из меню, и дать чаевые, и следуете этим «правилам поведения» каждый раз, когда едите вне дома. При этом вы, вероятно, и не вспомните, в каком заведении впервые все это осознали.
В своей диссертации я разработал алгоритм, объединяющий обучение на основе частных случаев и на основе правил. Правило не просто подходит к сущностям, которые удовлетворяют всем его условиям: оно подходит к любой сущности, которая похожа на него больше, чем на любое другое правило, и в этом смысле приближается к удовлетворению его условий. Например, человек с уровнем холестерина 220 мг/дл ближе, чем человек с 200 мг/дл, подходит к правилу «Если холестерин выше 240 мг/дл, есть риск сердечного приступа». RISE, как я назвал этот алгоритм, в начале обучения относится к каждому обучающему примеру как к правилу, а затем постепенно обобщает эти правила, впитывая ближайшие примеры. В результате обычно получается сочетание очень общих правил, которые в совокупности подходят к большинству примеров, плюс большое количество конкретных правил, которые подходят к исключениям, и так далее по «длинному хвосту» конкретных воспоминаний. RISE в то время предсказывал успешнее, чем лучшие обучающие алгоритмы, основанные на правилах и частных случаях. Мои эксперименты показали, что его сильной стороной было именно сочетание плюсов обоих подходов. Правила можно подобрать аналогически, и поэтому они перестают быть хрупкими. Частные случаи могут выбирать разные свойства в разных областях пространства и тем самым борются с проклятием размерности намного лучше метода ближайшего соседа, который везде выбирает одни и те же свойства.
RISE был шагом в сторону Верховного алгоритма, потому что соединял в себе символическое и аналогическое обучение. Однако это был лишь маленький шажок, потому что он не обладал полной силой этих парадигм и в нем по-прежнему не хватало трех оставшихся. Правила RISE нельзя было по-разному сложить в цепочку: они просто предсказывали класс примера на основе его атрибутов. Правила не могли рассказать о более чем одной сущности одновременно. Например, RISE не умел выражать правила вроде «Если у A грипп и B контактировал с A, то у B тоже может быть грипп». В аналогической части RISE лишь обобщал простой алгоритм ближайшего соседа. Он не может учиться в разных областях, используя отображение структур или какую-то схожую стратегию. Заканчивая работу над диссертацией, я не знал, как сложить в один алгоритм всю мощь пяти парадигм, и на время отложил проблему. Но, применяя машинное обучение к таким проблемам, как реклама из уст в уста, интеграция данных, программирование на примерах и персонализация сайтов, я постоянно замечал, что все парадигмы по отдельности дают лишь часть решения. Должен быть способ лучше.
Итак, проходя через территории пяти «племен», мы собирали их открытия, вели разговоры о границах и задумывались, как сложить вместе кусочки мозаики. Сейчас мы знаем неизмеримо больше, чем в начале пути, но чего-то по-прежнему не хватает. В центре мозаики зияет дыра, и поэтому собрать ее трудно. Проблема в том, что все алгоритмы машинного обучения, которые мы до сих пор видели, нуждаются в учителе, который покажет им правильный ответ. Они не могут научиться отличать опухолевую клетку от здоровой, если кто-то не повесит ярлыки «опухоль» и «здоровая клетка». А люди могут учиться без учителя, и делают это с самого первого дня своей жизни. Мы подошли к вратам Мордора[98], и долгий путь будет напрасным, если не обойти это препятствие. Но вокруг бастионов и стражников есть тропинка, и награда близка. Следуйте за мной…
ГЛАВА 8
ОБУЧЕНИЕ БЕЗ УЧИТЕЛЯ
Если вы родитель, все тайны обучения разворачивались прямо на ваших глазах в первые три года жизни ребенка. Новорожденный не умеет говорить, ходить, узнавать предметы и даже не понимает, что то, на что он смотрит, будет существовать и когда он отвернется. Но проходит месяц за месяцем, и маленькими и большими шажками, путем проб, ошибок и больших когнитивных скачков ребенок разбирается, как устроен мир, как ведут себя люди, как с ними общаться. К третьему году плоды обучения сливаются в стабильное «я», в поток сознания, который не прекратится до самой смерти. Более старшие дети и взрослые способны «путешествовать во времени» — вспоминать прошлое, но лишь до этой границы. Если бы мы могли вернуться в младенчество и раннее детство и снова увидеть мир глазами маленького ребенка, многое, что озадачивает нас в механизмах обучения и даже самого бытия, внезапно стало бы очевидным. Но пока величайшая тайна селенной — это не ее зарождение или границы и не нити, из которых она соткана, а то, что происходит в мозге маленького ребенка: как из массы серого желе вырастает средоточие сознания.
Хотя наука о механизмах обучения детей все еще молода и исследования начались всего несколько десятилетий назад, ученые уже добились замечательных успехов. Младенцы не умеют заполнять анкеты и не соблюдают протоколов, однако удивительно много информации о том, что происходит у них в голове, можно получить благодаря видеозаписи и изучению их реакций во время эксперимента. Складывается связная картина: разум младенца — это не просто реализация заложенной генетической программы и не биологический прибор для фиксирования корреляций данных, получаемых из органов чувств. Разум ребенка сам активно синтезирует реальность, и со временем она меняется довольно радикально.
Очень удобно, что ученые-когнитивисты все чаще выражают теории детского обучения в форме алгоритмов. Это вдохновляет многих исследователей машинного обучения — ведь все, что нужно, уже есть там, в мозге ребенка, и надо только каким-то образом ухватить суть и записать ее в компьютерном коде. Некоторые ученые даже утверждают, что для создания разумных машин нужно сконструировать робота-ребенка и позволить ему ощутить мир так, как это делают обычные дети. Мы, исследователи, станем ему родителями (может быть, это будет краудсорсинг, и термин «глобальная деревня»[99] приобретет совершенно новое значение). Маленький Робби — давайте назовем его в честь пухлого, но высокого робота из «Запретной планеты»[100] — единственный робот-ребенок, которого нам надо построить. Как только он обучится всему, что человек знает в три года, проблема искусственного интеллекта будет решена. После этого можно скопировать содержимое его мозга в столько роботов, во сколько захотим, и они будут развиваться дальше: самое сложное уже сделано.
Вопрос, конечно, в том, какие алгоритмы должны работать в мозге Робби в момент рождения. Ученые, находящиеся под влиянием детской психологии, косо смотрят на нейронные сети, потому что работа нейронов на микроскопическом уровне кажется бесконечно далекой от сложности даже простейших действий ребенка: потянуться к предмету, схватить его и рассмотреть широко распахнутыми, полными любопытства глазами. Чтобы за деревьями увидеть планету, обучение ребенка придется моделировать на более высоком уровне абстракции. Самое удивительное, наверное, то, что дети учатся в основном самостоятельно, без надзора, хотя, несомненно, получают огромную помощь от своих родителей. Ни один из алгоритмов, которые мы до сих пор видели, на это не способен, но вскоре мы познакомимся с несколькими вариантами и на шаг приблизимся к Верховному алгоритму.
Как свести рыбака с рыбаком
Мы нажимаем кнопку «Включить», Робби открывает глаза-видеокамеры в первый раз, и его сразу заливает «цветущий и жужжащий беспорядок» мира, как сказал Уильям Джеймс. Новые изображения возникают десятками в секунду, и одна из первоочередных задач — научиться организовывать их в более крупные элементы: реальный мир состоит не из случайных пикселей, которые каждое мгновение меняются, как им вздумается, а из стабильных во времени объектов. Если мама отошла подальше, вместо нее не появится «уменьшенная мама». Если на стол поставить тарелку, в столе не появится белая дырка. Младенец не отреагирует, если плюшевый мишка скроется за ширмой и вместо него появится самолет, а годовалый ребенок удивится: он каким-то образом уже сообразил, что мишки отличаются от самолетов и не могут просто так превращаться друг в друга. Вскоре после этого он разберется, что некоторые предметы похожи друг на друга, и начнет формировать категории. Если девятимесячному малышу дать гору игрушечных лошадок и карандашей, он и не подумает их разделить, а в полтора года уже догадается.
Организация мира в предметы и категории совершенно естественна для взрослого, но не для младенца, и в еще меньшей степени для робота Робби. Можно, конечно, одарить его зрительной корой в виде многослойного перцептрона и показать подписанные примеры всех предметов и категорий в мире — вот мама рядом, а вот мама далеко, — но так мы никогда не закончим. На самом деле нам нужен алгоритм, который будет спонтанно группировать схожие объекты и разные изображения одного и того же объекта. Это проблема кластеризации, одна из наиболее интенсивно изучаемых тем в науке о машинном обучении.
Кластер — это набор схожих сущностей или как минимум набор сущностей, которые похожи друг на друга больше, чем на элементы других кластеров. Делить все на кластеры — в природе человека, и часто это первый шаг на пути к знанию. Даже глядя в ночное небо, мы невольно видим скопления звезд, а потом придумываем красивые названия формам, которые они напоминают. Наблюдение, что определенные группы веществ имеют очень схожие химические свойства, стало первым шагом к открытию периодической системы элементов: каждая группа в ней заняла свой столбец. Все, что мы воспринимаем — от лиц друзей до звуков речи, — это кластеры. Без них мы бы потерялись. Дети не научатся говорить, пока не приобретут навык определять характерные звуки, из которых состоит речь. Это происходит в первые годы жизни, и все слова, которые они потом узнают, не значат ничего без кластеров реальных вещей, к которым эти слова относятся. Сталкиваясь с большими данными — очень большим количеством объектов, — мы вначале группируем их в удобное число кластеров. Рынок в целом — слишком общий, отдельные клиенты — слишком мелкие, поэтому маркетологи делят его на сегменты, как они называют кластеры. Даже объекты как таковые, по сути, кластеры наблюдений за ними, начиная с маминого лица под разными углами освещения и заканчивая различными звуковыми волнами, которые ребенок слышит как слово «мама». Думать без объектов невозможно, и, наверное, именно поэтому квантовая механика такая неинтуитивная наука: субатомный мир хочется нарисовать в воображении в виде сталкивающихся частиц или интерферирующих волн, но на самом деле это ни то ни другое.
Кластер можно представить по его элементу-прототипу: образу мамы, который сразу приходит на ум, типичной кошки, спортивного автомобиля, загородного дома и тропического пляжа. Для маркетолога Пеория в штате Иллинойс это средний американский городок. Самый обычный гражданин США — это Боб Бернс, пятидесятитрехлетний завхоз из Уиндема в штате Коннектикут, по крайней мере, если верить книге Кевина О’Кифа The Average American. По всем числовым атрибутам — например, росту, весу, объему талии и обуви, длине волос и так далее — можно легко найти среднего члена кластера: его рост — это средний рост всех остальных, вес — средний вес и так далее. Для описательных атрибутов, например пола, цвета волос, почтового индекса и любимого вида спорта, «средним» значением будет просто самое распространенное. Средние члены кластеров, описанные таким набором атрибутов, могут существовать или не существовать в реальности, но это в любом случае удачные точки для ориентации: когда планируешь маркетинг нового продукта, удобнее представить себе Пеорию как место введения его на рынок и Боба Бернса как целевого клиента, а не оперировать абстрактными сущностями вроде «рынка» или «клиента».
Такие усредненные объекты, конечно, полезны, но можно поступить еще лучше: вообще весь смысл больших данных и машинного обучения как раз в том, чтобы избежать грубых рассуждений. Кластеры могут быть очень специализированными группами людей или даже различными аспектами жизни одного и того же человека: Элис, покупающая книги для работы, для отдыха или в подарок на Рождество, Элис в хорошем настроении и грустящая Элис. Amazon заинтересована в том, чтобы отделять книги, которые Элис покупает себе, от тех, которые она покупает для своего молодого человека, потому что тогда можно будет дать ей в нужное время подходящую рекомендацию. К сожалению, покупки не сопровождаются ярлыками «подарок для себя» и «для Боба», поэтому Amazon приходится самой разбираться, как их группировать.
Представьте, что объекты в мире Робби делятся на пять кластеров (люди, мебель, игрушки, еда и животные), но неизвестно, какие вещи к каким кластерам относятся. С проблемой этого типа Робби столкнется, как только мы его включим. Простой вариант сортировки объектов по кластерам — взять пять произвольных предметов, сделать их прототипами кластеров, а затем сравнить новые сущности с каждым прототипом, относя их к кластеру самого схожего. (Как и в аналогическом обучении, здесь важно выбрать меру сходства. Если атрибуты числовые, это может быть просто евклидово расстояние, но это далеко не единственный вариант.)
Теперь прототипы надо обновить. Подразумевается, что прототип кластера должен быть средним его членов: когда кластеры состояли из одного члена, все так и было, но теперь мы добавили к ним новые элементы, и ситуация изменилась. Поэтому мы вычислим средние свойства членов для каждого кластера и сделаем полученный результат новым прототипом. Теперь нужно снова обновить принадлежность объектов кластерам: поскольку прототипы изменились, мог измениться и прототип, наиболее близкий данному объекту. Давайте представим, что прототип одной категории — это мишка, а другой — банан. Если взять крекер в виде животного, при первом подходе он может попасть в группу с медведем, а при втором — с бананом. Изначально крекер выглядел как игрушка, но теперь он будет отнесен к еде. Если переместить крекер в одну группу с бананом, прототип для этой группы тоже может измениться: это уже будет не банан, а печенье. Этот полезный цикл, который относит объекты ко все более и более подходящим кластерам, станет продолжаться, пока кластеры сущностей (а с ними и прототипы кластеров) не прекратят меняться.
Такой алгоритм называется метод k-средних, и появился он еще в 50-е годы ХХ века. Он простой, красивый, при этом довольно популярный, но имеет ряд недостатков, одни из которых устранить легче, а другие — сложнее. Во-первых, количество кластеров надо зафиксировать заранее, а в реальном мире Робби постоянно натыкается на новые виды предметов. Один вариант решения — позволить открывать новый кластер, если объект слишком сильно отличается от имеющихся. Другой — разрешить кластерам делиться и сливаться в процессе работы. Так или иначе, вероятно, будет целесообразно включить в алгоритм приоритеты для меньшего количества кластеров, чтобы избежать ситуации, когда у каждого предмета будет собственный кластер (идеальное решение, если кластеры должны содержать схожие предметы, но смысл явно не в этом).
Более серьезная проблема заключается в том, что метод k-средних работает, только когда кластеры легко различимы: они, как пузыри в гиперпространстве, плавают далеко друг от друга, и у всех схожий объем и схожее количество членов. Если какое-то условие не выполнено, начинаются неприятности: вытянутые кластеры делятся надвое, маленькие поглощаются более крупными соседями и так далее. К счастью, можно поступить лучше.
Допустим, мы пришли к выводу, что разрешить Робби слоняться по реальному миру — слишком медленный и громоздкий способ обучения, и вместо этого посадили его смотреть сгенерированные компьютером изображения, как будущего летчика в авиационном тренажере. Мы знаем, из каких кластеров взяты картинки, но не скажем об этом Робби, а будем создавать их, случайно выбирая кластер (скажем, «игрушки»), а потом синтезируя пример этого кластера (маленький пухлый бурый плюшевый медведь с большими черными глазами, круглыми ушами и галстуком-бабочкой). Кроме того, мы будем произвольно выбирать свойства примера: размер мишки — в среднем 25 сантиметров, мех с вероятностью 80 процентов бурый, иначе — белый и так далее. После того как Робби увидит очень много сгенерированных таким образом картинок, он должен научиться делить их на кластеры «люди», «мебель», «игрушки» и так далее, потому что люди, например, больше похожи на людей, а не на мебель. Возникает интересный вопрос: какой алгоритм кластеризации лучше с точки зрения Робби? Ответ будет неожиданным: наивный байесовский алгоритм — первый алгоритм для обучения с учителем, с которым мы познакомились. Разница в том, что теперь Робби не знает классов и ему придется их угадать!
Очевидно: если бы Робби их знал, все пошло бы отлично — как в наивном байесовском алгоритме, каждый кластер определялся бы своей вероятностью (17 процентов сгенерированных объектов — игрушки) и распределением вероятности каждого атрибута среди членов кластера (например, 80 процентов игрушек коричневые). Робби мог бы оценивать вероятности путем простого подсчета числа игрушек в имеющихся данных, количества коричневых игрушек и так далее, но для этого надо знать, какие предметы — игрушки. Эта проблема может показаться крепким орешком, но, оказывается, мы уже знаем, как ее решить. Если бы в распоряжении Робби имелся наивный байесовский классификатор и ему необходимо было определить класс нового предмета, нужно было бы только применить классификатор и вычислить вероятность класса при данных атрибутах объекта. Маленький, пухлый, коричневый, похож на медведя, с большими глазами и галстуком-бабочкой? Вероятно, игрушка, но, возможно, животное.
Итак, Робби сталкивается с проблемой «курица или яйцо»: зная классы предметов, он мог бы получить модели классов путем подсчета, а если бы знал модели, мог бы сделать заключение о классах объектов. Если вы думаете, что опять застряли, это далеко не так: чтобы стартовать, надо просто начать угадывать классы для каждого предмета каким угодно способом, даже произвольно. На основе этих классов и данных можно получить модели классов, на основе этих моделей — вновь сделать вывод о классах и так далее. На первый взгляд это кажется безумием: придется бесконечно кружиться между выводами о классах на основе моделей и моделей на основе их классов, и даже если это закончится, нет причин полагать, что кластеры получатся осмысленные. Но в 1977 году трое статистиков из Гарварда — Артур Демпстер, Нэн Лэрд и Дональд Рубин — показали, что сумасшедший план работает: после каждого прохождения по этой петле модель кластера улучшается, а после достижения моделью локального максимума похожести повторения заканчиваются. Они назвали эту схему EM-алгоритмом, где E — ожидания (expectation, заключение об ожидаемых вероятностях), а M — максимизация (maximization, оценка параметров максимальной схожести). Еще они показали, что многие предыдущие алгоритмы были частными случаями EM. Например, чтобы получить скрытые модели Маркова, мы чередуем выводы о скрытых состояниях с оценкой вероятностей перехода и наблюдения на их основе. Когда мы хотим получить статистическую модель, но нам не хватает какой-то ключевой информации (например, классов примеров), всегда можно использовать EM-алгоритм, что делает его одним из самых популярных инструментов в области машинного обучения.
Вы, возможно, заметили определенное сходство между методом k-средних и EM-алгоритмом, поскольку оба чередуют отнесение сущностей к кластерам и обновление описаний кластеров. Это не случайность: метод k-средних сам по себе — частный случай EM-алгоритма, который получается, если у всех атрибутов «узкое» нормальное распределение, то есть нормальное распределение с очень маленькой дисперсией. Если кластеры часто перекрываются, объект может относиться, скажем, к кластеру A с вероятностью 0,7 и к кластеру B с вероятностью 0,3, и нельзя просто отнести его к кластеру A без потери информации. EM-алгоритм учитывает это путем частичного приписывания объекта к двум кластерам и соответствующего обновления описаний этих кластеров, однако, если распределения очень сконцентрированы, вероятность, что сущность принадлежит к ближайшему кластеру, всегда будет приблизительно равна единице, и нужно только распределить объекты по кластерам и усреднить их в каждом кластере, чтобы вычислить среднее — то есть получится алгоритм k-среднего.
До сих пор мы рассматривали получение всего одного уровня кластеров, но мир, конечно, намного богаче, и одни кластеры в нем вложены в другие вплоть до конкретных предметов: живое делится на растения и животных, животные — на млекопитающих, птиц, рыб и так далее до домашнего любимца — пса Фидо. Но проблем это не создает: получив набор кластеров, к ним можно относиться как к объектам и, в свою очередь, объединять их в кластеры все более высокого уровня, вплоть до кластера всех объектов. Или же можно начать с грубой кластеризации, а затем все больше дробить кластеры на подкластеры: игрушки Робби делятся на мягкие игрушки, конструкторы и так далее. Мягкие игрушки — на плюшевых медведей, котят и так далее. Дети, видимо, начинают изучение мира где-то посередине, а потом идут и вверх, и вниз. Например, понятие «собака» они усваивают до того, как узнают о «животных» и «гончих». Для Робби это может стать хорошей стратегией.
Открытие формы данных
Независимо от того, поступают ли данные в мозг Робби из его органов чувств или в виде потока миллионов кликов клиентов Amazon, сгруппировать множество в меньшее число кластеров — лишь половина дела. Второй этап — сократить описание объектов. Первый образ мамы, который видит Робби, будет состоять, может быть, из миллиона пикселей, каждый своего цвета, однако человеку вряд ли нужен миллион переменных, чтобы описать лицо. Аналогично каждый товар, на который вы кликнули на сайте Amazon, дает частицу информации о вас, но на самом деле Amazon интересны не ваши клики, а ваши вкусы. Вкусы довольно стабильны и в какой-то мере подразумеваются в кликах, количество которых растет безгранично во время пользования сайтом и должно понемногу складываться в картину предпочтений точно так же, как пиксели складываются в картинку лица. Вопрос в том, как реализовать это сложение.
У человека есть примерно 50 лицевых мышц, поэтому 50 чисел должно с лихвой хватить для описания всех возможных выражений лица. Форма глаз, носа, рта и так далее — всего того, что помогает отличить одного человека от другого, — тоже не должна занимать больше нескольких десятков чисел. В конце концов, художникам в полиции достаточно всего десяти вариантов каждой черты лица, чтобы составить фоторобот, позволяющий опознать подозреваемого. Можно добавить еще несколько чисел для описания освещения и наклона, но на этом все. Поэтому, если вы дадите мне примерно сотню чисел, этого должно хватить для воссоздания лица, и наоборот: мозг Робби должен быть способен взять картинку лица и быстро свести ее ко все той же сотне по-настоящему важных чисел.
Специалисты по машинному обучению называют этот процесс понижением размерности, потому что он уменьшает множество видимых измерений (пикселей) до нескольких подразумеваемых (выражение и черты лица). Понижение размерности важно для того, чтобы справиться с большим объемом данных, например данными, поступающими каждую секунду из органов чувств. Может быть, действительно лучше один раз увидеть, чем сто раз услышать, но обрабатывать и запоминать изображения в миллион раз сложнее, чем слова. Тем не менее зрительная кора головного мозга каким-то образом довольно хорошо справляется с уменьшением такого объема информации до приемлемого, достаточного, чтобы ориентироваться в мире, узнавать людей и предметы и помнить увиденное. Это великое чудо познания настолько естественно для нас, что мы его даже не замечаем.
Наводя порядок в своей библиотеке, вы тоже выполняете своего рода понижение размерности от обширного пространства тем до одномерной полки. Некоторые тесно связанные книги неизбежно окажутся далеко друг от друга, но все равно можно расставить их так, чтобы такие случаи были редкими. Алгоритм понижения размерности делает именно это.
Представьте, что я дал вам координаты GPS всех магазинов в Пало-Альто в Калифорнии и вы нанесли их на листок бумаги:
Наверное, взглянув на эту схему, вы сразу поймете, что главная улица городка ведет с юго-запада на северо-восток. Хотя вы не рисовали саму улицу, интуиция подсказывает, где она проходит, потому что все точки лежат на прямой линии (или рядом с ней — магазины могут быть по разные стороны улицы). Догадка верна: эта улица — Юниверсити-авеню, и, если вы окажетесь в Пало-Альто и захотите перекусить и сделать покупки, туда и надо идти. Еще лучше, что, когда магазины сконцентрированы на одной улице, для описания их расположения нужно уже не два числа, а всего одно — номер дома, а для большей точности — расстояние от магазина до пригородной железнодорожной станции в юго-западном углу, откуда начинается Юниверсити-авеню.
Если нанести на карту еще больше магазинов, вы, вероятно, заметите, что часть из них находится на перекрестках, чуть в стороне от Юниверсити-авеню, а некоторые — вообще в других местах:
Тем не менее большинство магазинов все равно расположены довольно близко к центральной улице, и, если разрешено использовать для описания положения магазина только одно число, расстояние от вокзала вдоль этой улицы будет довольно удачным вариантом: пройдя этот отрезок и оглядевшись, вы с достаточной вероятностью найдете нужный магазин. Итак, вы только что понизили размерность «расположения магазинов в Пало-Альто» с двух измерений до одного.
У Робби, однако, нет преимуществ, которые дает человеку сильно развитая зрительная система, поэтому, если вы попросите его забрать белье из химчистки Elite Cleaners и учтете на его карте только одну координату, ему нужен будет алгоритм, чтобы «открыть» Юниверсити-авеню на основе GPS-координат магазинов. Ключ к решению проблемы — заметить, что, если поставить начало координат плоскости x, y в усредненное расположение магазинов и медленно поворачивать оси, магазины окажутся ближе всего к оси x при повороте примерно на 60 градусов, то есть когда ось совпадает с Юниверсити-авеню:
Это направление — так называемая первая главная компонента данных — будет направлением, вдоль которого разброс данных наибольший. (Обратите внимание: если спроецировать магазины на ось x, на правом рисунке они будут находиться дальше друг от друга, чем на левом.) Обнаружив первую главную компоненту, можно поискать вторую, которой в данном случае станет направление наибольшей дисперсии под прямым углом к Юниверсити-авеню. На карте остается только одно возможное направление (направление перекрестков). Но если бы Пало-Альто находился на склоне холма, одна или две главные компоненты частично были бы расположены непосредственно на холме, а третья — последняя — оказалась бы направлена в воздух. Ту же идею можно применить к тысячам и миллионам измерений данных, как в случае изображений лиц: нужно последовательно искать направления наибольшей дисперсии, пока оставшаяся вариабельность не окажется наименьшей. Например, после поворота осей на рисунке выше координата y большинства магазинов будет равна нулю, поэтому среднее y окажется очень маленьким, и, если его вообще проигнорировать, потеря информации получится незначительной. А если мы все же решим сохранить y, то z (направленная вверх) наверняка будет несущественна. Как оказалось, линейная алгебра позволяет провести процесс поиска главных компонент всего за один цикл, но еще лучше то, что даже в данных с очень большим количеством измерений значительную часть дисперсии зачастую дают всего несколько измерений. Если это не так, все равно визуальный поиск двух-трех важнейших измерений часто оказывается очень успешным, потому что наша зрительная система дает удивительные возможности восприятия.
Метод главных компонент (Principal Component Analysis, PCA), как называют этот процесс, — один из важнейших инструментов в арсенале ученого. Можно сказать, что для обучения без учителя это то же самое, что линейная регрессия для контролируемого множества. Знаменитая «клюшкообразная» кривая глобального потепления, например, была получена в результате нахождения главной компоненты различных рядов данных, связанных с температурой (годичные кольца деревьев, ледяные керны и так далее), и допущения, что это запись температуры как таковой. Биологи используют метод главных компонент, чтобы свести уровни экспрессии тысяч различных генов в несколько путей. Психологи обнаружили, что личность можно выразить пятью факторами — это экстраверсия, доброжелательность, добросовестность, нейротизм и открытость опыту, — которые оценивают по твитам и постам в блогах. (У шимпанзе, предположительно, есть еще одно измерение — реактивность, — но их с помощью Twitter не оценишь.) Применение метода главных компонент к голосам на выборах в Конгресс и данным избирателей показывает, что, вопреки расхожему мнению, политика в основном не сводится к противостоянию либералов и консерваторов. Люди отличаются в двух основных измерениях — экономических и социальных вопросах, — и, если спроецировать их на одну ось, либертарианцы смешаются с популистами, хотя их позиции полярно противоположны, и возникнет иллюзия, что в центре много умеренных. Попытка апеллировать к ним вряд ли окажется выигрышной стратегией. С другой стороны, если либералы и либертарианцы преодолеют взаимную неприязнь, они могут стать союзниками в социальных вопросах, где и те и другие выступают за свободу личности.
Когда Робби подрастет, он сможет применять один из вариантов метода главных компонент для решения проблемы «эффекта вечеринки», то есть чтобы выделить из шума толпы отдельные голоса. Схожий метод может помочь ему научиться читать. Если каждое слово — измерение, тогда текст — точка в пространстве слов, и главные направления этого пространства окажутся элементами значения. Например, «президент Обама» и «Белый дом» в пространстве слов далеко отстоят друг от друга, но в пространстве значений близки, потому что обычно появляются в схожих контекстах. Хотите верьте, хотите нет, но такой тип анализа — все, что требуется и компьютерам, и людям для оценки сочинений на экзаменах SAT (стандартизованный тест для приема в высшие учебные заведения США). В Netflix используется похожая идея. Вместо того чтобы рекомендовать фильмы, которые понравились пользователям со схожими вкусами, система проецирует и пользователей, и фильмы в «пространство вкуса» с низкой размерностью и рекомендует картины, расположенные в этом пространстве рядом с вами. Это помогает найти фильмы, которые вы никогда не видели, но обязательно полюбите.
Тем не менее главные компоненты набора данных о лице вас, скорее всего, разочаруют. Вопреки ожиданиям, это будут, например, не черты лица и выражения, а скорее размытые до неузнаваемости лица призраков. Дело в том, что метод главных компонент — линейный алгоритм, поэтому главными компонентами могут быть только взвешенные пиксель за пикселем средние реальных лиц (их еще называют «собственные лица», потому что они собственные векторы центрированной ковариационной матрицы этих данных, но я отхожу от темы). Чтобы по-настоящему понять не только лица, но и большинство форм в мире, нам понадобится кое-что еще, а именно нелинейное понижение размерности.
Представьте, что вместо карты Пало-Альто у нас есть GPS-координаты важнейших городов всей Области залива Сан-Франциско:
Глядя на эту схему, можно, вероятно, сделать предположение, что города расположены на берегу залива и, если провести через них линию, положение каждого города можно определить всего одним числом: как далеко он находится от Сан-Франциско по этой линии. Но метод главных компонент такую кривую найти не может: он нарисует прямую линию через центр залива, где городов вообще нет, а это только затуманит, а не прояснит форму данных.
Теперь представьте на секунду, что мы собираемся создать Область залива с нуля. Бюджет позволяет построить единую дорогу, чтобы соединить все города, и нам решать, как она будет проложена. Естественно, мы проложим дорогу, ведущую из Сан-Франциско в Сан-Бруно, оттуда в Сан-Матео и так далее, вплоть до Окленда. Такая дорога будет довольно хорошим одномерным представлением Области залива, и ее можно найти простым алгоритмом: «построй дорогу между каждой парой близлежащих городов». Конечно, у нас получится целая сеть дорог, а не одна, проходящая рядом с каждым городом, но можно получить и одну дорогу, если сделать ее наилучшим приближением сети, в том смысле, что расстояния между городами по этой дороге будут как можно ближе расстоянию вдоль сети.
Именно это делает Isomap — один из самых популярных алгоритмов нелинейного понижения размерности. Он соединяет каждую точку данных в высокоразмерном пространстве (пусть это будет лицо) со всеми близлежащими точками (очень похожими лицами), вычисляет кратчайшие расстояния между всеми парами точек по получившейся сети и находит меньшее число координат, которое лучше всего приближает эти расстояния. В отличие от метода опорных векторов, координаты лиц в этом пространстве часто довольно осмысленны: одна координата может показывать, в каком направлении смотрит человек (левый профиль, поворот на три четверти, анфас и так далее), другая — как лицо выглядит (очень грустное, немного грустное, спокойное, радостное, очень радостное) и так далее. Isomap имеет неожиданную способность сосредоточиваться на самых важных измерениях комплекса данных — от понимания движения на видео до улавливания эмоций в речи.
Вот интересный эксперимент. Возьмите потоковое видео из глаз Робби, представьте, что каждый кадр — точка в пространстве изображений, а потом сведите этот набор изображений к единственному измерению. Какое это будет измерение? Время. Как библиотекарь расставляет книги на полке, время ставит каждое изображение рядом с самыми похожими. Наверное, наше восприятие времени — просто естественный результат замечательной способности головного мозга понижать размерность. В дорожной сети нашей памяти время — главная автострада, и мы ее быстро находим. Другими словами, время — главная компонента памяти.
Жизнелюбивый робот
Кластеризация и понижение размерности приближают нас к пониманию человеческого обучения, но чего-то очень важного все равно не хватает. Дети не просто пассивно наблюдают за миром. Они активно действуют: замечают предметы, берут их в руки, играют, бегают, едят, плачут и задают вопросы. Даже самая продвинутая зрительная система будет бесполезна, если она не поможет Робби взаимодействовать со средой. Ему нужно не просто знать, где что находится, но и что надо делать в каждый момент. В принципе можно научить его выполнять пошаговые инструкции, соотнося показания сенсоров с соответствующими ответными действиями, но это возможно только для узких задач. Предпринимаемые действия зависят от цели, а не просто от того, что вы в данный момент воспринимаете, при этом цели могут быть весьма отдаленными. И потом, в любом случае нужно обойтись без пошагового контроля: дети учатся ползать, ходить и бегать сами, без помощи родителей. Ни один рассмотренный нами обучающий алгоритм так учиться не умеет.
У людей действительно есть один постоянный ориентир: эмоции. Мы стремимся к удовольствиям и избегаем боли. Коснувшись горячей плиты, вы непроизвольно отдернете руку. Это просто. Сложнее научиться не трогать плиту: для этого нужно двигаться так, чтобы избежать острой боли, которую вы еще не почувствовали. Головной мозг делает это, ассоциируя боль не просто с моментом прикосновения к плите, но и с ведущими к этому действиями. Эдвард Торндайк[101] назвал это законом эффекта: действия, которые ведут к удовольствию, станут с большей вероятностью повторяться в будущем, а ведущие к боли — с меньшей. Удовольствие как будто путешествует назад во времени, и действия в конце концов могут начать ассоциироваться с довольно отдаленными результатами. Люди освоили такой поиск косвенных наград лучше, чем любое животное, и этот навык критически важен для успеха в жизни. В знаменитом эксперименте детям давали зефир и говорили, что, если они выдержат несколько минут и не съедят его, им дадут целых два. Те, кому это удалось, лучше успевали в школе и позже, когда стали взрослыми. Менее очевидно, наверное, то, что с аналогичной проблемой сталкиваются компании, использующие машинное обучение для совершенствования своих сайтов и методов ведения бизнеса. Компания может принять меры, которые принесут ей больше денег в краткосрочной перспективе — например, начать по той же цене продавать продукцию худшего качества, — но не обратить внимания, что в долгосрочной перспективе это приведет к потере клиентов.
Обучающиеся алгоритмы, которые мы видели в предыдущих главах, руководствуются немедленным удовлетворением: каждое действие, будь то выявление письма со спамом или покупка ценных бумаг, получает непосредственное поощрение или наказание от учителя. Но есть целый подраздел машинного обучения, посвященный алгоритмам, которые исследуют мир сами по себе: трудятся, сталкиваются с наградами, определяют, как получить их снова. Во многом они похожи на детей, которые ползают по комнате и тащат все в рот.
Это обучение с подкреплением, и этот принцип, скорее всего, станет активно использовать ваш первый домашний робот. Если вы распакуете Робби, включите его и попросите приготовить яичницу с беконом, у него с ходу может не получиться. Но когда вы уйдете на работу, он изучит кухню, отметит, где лежит утварь, какая у вас плита. Когда вы вернетесь, ужин будет готов.
Важным предшественником обучения с подкреплением была программа для игры в шашки, созданная ученым Артуром Сэмюэлом, работавшим в 1950-х годах в IBM. Настольные игры — прекрасный пример проблемы обучения с подкреплением: надо построить длинную последовательность ходов без какой-то обратной связи, а награда или наказание — победа или поражение — ждет в самом конце. Программа Сэмюэла оказалась способна научиться играть так не хуже большинства людей. Она не искала напрямую, какой ход сделать при каждом положении на доске (это было бы слишком сложно), а скорее училась оценивать сами положения — какова вероятность выигрыша, если начать с этой позиции? — и выбирать ходы, ведущие к наилучшему положению. Поначалу программа умела оценивать только конечные позиции: победа, ничья и поражение. Но раз определенные позиции означают победу, значит, позиции, из которых можно к ней прийти, хорошие. Томас Уотсон-старший, президент IBM, предсказал, что после презентации программы акции корпорации поднимутся на 15 пунктов. Так и произошло. Урок был усвоен, IBM развила успех и создала чемпионов по игре в шахматы и Jeopardy!.
Мысль, что не все состояния ведут к награде (положительной или отрицательной), но у каждого состояния имеется ценность, — центральный пункт обучения с подкреплением. В настольных играх награды есть только у конечных позиций (например, 1, 0 и –1 для победы, ничьей и поражения). Другие позиции не дают немедленной награды, но их ценность в том, что они могут обеспечить награду в будущем. Позиция в шахматах, из которой можно поставить мат в определенное количество ходов, практически так же хороша, как сама победа, и потому имеет высокую ценность. Такого рода рассуждения можно распространить вплоть до хороших и плохих дебютов, даже если на таком расстоянии от цели связь с наградой далеко не очевидна. В компьютерных играх награды обычно выражаются в очках, и ценность состояния — это количество очков, которые можно накопить, начиная с этого состояния. В реальной жизни отдача с задержкой менее выгодна, чем немедленная отдача, поэтому ее можно уменьшать на определенный процент, как это делается в случае инвестиций. Естественно, награда зависит от того, какие действия вы выберете, и цель обучения с подкреплением — всегда выбирать действие, ведущее к наибольшей награде. Стоит ли снять трубку и пригласить знакомую на свидание? Это может и положить начало чудесному роману, и привести к болезненному разочарованию. А если ваша подруга согласится на свидание, оно может пойти как удачно, так и неудачно. Надо каким-то образом абстрагироваться от бесконечных вариантов развития событий и принять решение. Обучение с подкреплением делает это путем оценки ценности каждого состояния — общей суммы наград, которых можно ожидать, начиная с него, — и выбора действий, которые ее максимизируют.
Представьте, что вы, как Индиана Джонс, пробираетесь по лабиринту и доходите до развилки. Карта подсказывает, что туннель слева ведет к сокровищнице, а справа — в яму со змеями. Ценность места, где вы стоите — прямо на распутье, — равна ценности сокровищ, потому что вы пойдете налево. Если всегда выбирать наилучшее возможное действие, ценность текущего состояния будет отличаться от ценности последующего только непосредственной наградой за выполнение этого действия, если таковая имеется. Если известны непосредственные награды каждого состояния, можно использовать их для обновления ценности соседних состояний и так далее, пока значения всех состояний не будут согласованы: ценность сокровища распространяется назад по лабиринту до развилки и еще дальше. Зная ценность состояний, вы поймете, какое действие выбрать в каждом из них (то, которое дает максимальное сочетание немедленной награды и ценности результирующего состояния). Все это было открыто еще в 1950-е годы теоретиком управления Ричардом Беллманом[102]. Однако настоящая проблема обучения с подкреплением появляется, когда карты местности у вас нет и остается только исследовать ее самостоятельно, определяя награды. Иногда получается найти драгоценности, иногда падаешь в яму со змеями. Каждое предпринятое действие дает информацию и о непосредственной награде, и о результирующем состоянии. Это можно сделать путем обучения с учителем. Однако нужно обновить и значение состояния, из которого вы только что пришли, чтобы привести его в соответствие с наблюдаемым значением, а именно суммой полученной награды и значения нового состояния, в котором вы оказались. Конечно, значение может пока быть неправильным, но, если достаточно долго ходить вокруг, в конце концов будут найдены правильные значения всех состояний и соответствующих действий. В этом в двух словах заключается обучение с подкреплением.
Обратите внимание, что обучение с подкреплением сталкивается с той же дилеммой изучения–применения, с которой мы познакомились в главе 5: чтобы максимизировать награды, вы, естественно, всегда хотите выбирать действие, ведущее к состоянию с наибольшим значением, но это не дает открыть потенциально большие награды в других местах. Алгоритмы обучения с подкреплением решают эту проблему, иногда выбирая лучшее действие, а иногда — случайное. (В головном мозге, кажется, для этого есть даже «генератор шумов».) На ранних этапах, когда можно получить много информации, имеет смысл больше изучать. Когда территория известна, лучше будет сосредоточиться на применении знания. Люди делают это на протяжении жизни: дети учатся, а взрослые используют (кроме ученых, которые похожи на вечных детей). Детская игра намного серьезнее, чем может показаться: если эволюция создала существо, которое в первые несколько лет своей жизни беспомощно и только обременяет родителей, такая расточительность должна давать большие преимущества. По сути, обучение с подкреплением — своего рода ускоренная эволюция, которая позволяет попробовать, отбросить и отточить действия в течение одной жизни, а не многих поколений, и по этим меркам оно крайне эффективно.
Начало серьезным исследованиям обучения с подкреплением положили в 1980-х годах работы Рича Саттона и Энди Барто из Массачусетского университета. Ученые чувствовали, что обучение в очень большой степени зависит от взаимодействия со средой, а контролирующие алгоритмы этого не улавливают, и нашли вдохновение в психологии обучения животных. Саттон продолжил заниматься этой темой и стал ведущим сторонником обучения с подкреплением. Еще один ключевой шаг был сделан в 1989 году, когда Крис Уоткинс из Кембриджа, которого изначально мотивировали экспериментальные наблюдения за обучением детей, пришел к современной формулировке обучения с подкреплением как оптимального контроля в неизвестной среде.
Тем не менее алгоритмы обучения с подкреплением, которые мы видели до сих пор, не очень реалистичны, потому что не знают, что делать в данном состоянии, если раньше в нем не были, а в реальном мире не бывает двух совершенно одинаковых ситуаций. Нужно уметь делать обобщения, выводя из посещенных состояний новые. К счастью, этому мы уже научились: достаточно просто обернуть обучение с подкреплением вокруг одного из алгоритмов обучения с учителем, с которыми мы познакомились раньше, например многослойного перцептрона. Теперь нейронная сеть будет предсказывать значение состояния, а сигналом ошибки для обратного распространения станет разница между предсказанными и наблюдаемыми значениями. Но есть и проблема. В обучении с учителем целевое значение состояния всегда одно и то же, а в обучении с подкреплением оно продолжает меняться в силу обновлений соседних состояний, поэтому обучение с подкреплением и обобщением часто не умеет приходить к стабильному решению, если только обучающийся алгоритм внутри не простейший, например линейная функция. Несмотря на это, обучение с подкреплением в сочетании с нейронными сетями принесло ряд заметных успехов. Одним из первых достижений стала программа, играющая в нарды на уровне человека. Позже алгоритм обучения с подкреплением, разработанный в лондонском стартапе DeepMind, победил хорошего игрока в Pong и другие простые аркады. Для прогнозирования ценности действий на основе «сырых» пикселей экрана игровой приставки в нем использовалась глубокая сеть. Благодаря непрерывному зрению, обучению и контролю система имела как минимум поверхностное сходство с искусственным мозгом. Неудивительно, что Google заплатила за DeepMind полмиллиарда долларов, хотя у компании не имелось ни продукции, ни выручки и сотрудников было немного.
Кроме компьютерных игр, ученые использовали обучение с подкреплением для управления гимнастами — человечками из палочек, парковки задним ходом, пилотирования вертолетов вверх ногами, управления автоматическими телефонными диалогами, выделения каналов в сетях сотовой связи, вызова лифта, составления расписаний загрузки космического челнока и многих других целей. Обучение с подкреплением повлияло на психологию и нейробиологию. В мозге оно осуществляется благодаря нейромедиатору дофамину, который позволяет распространить разницу между ожидаемыми и фактическими наградами. Обучением с подкреплением можно объяснить условные рефлексы по Павлову, и, в отличие от бихевиоризма, такой подход допускает, что у животных есть внутренние психические состояния. Этот вид обучения используют пчелы-сборщицы и мыши, ищущие сыр в лабиринте. Человеческая повседневность — это поток почти незаметных чудес, которые возможны отчасти благодаря обучению с подкреплением. Вы встаете, одеваетесь, завтракаете, едете на работу, и все это автоматически, думая о чем-то другом. Где-то в глубине обучение с подкреплением постоянно дирижирует процессом и тонко настраивает удивительную симфонию движений. Элементы обучения с подкреплением, также называемые привычками, составляют большую часть наших действий: проголодался — идешь к холодильнику и берешь что-нибудь перекусить. Как показал Чарльз Дахигг в книге The Power of Habit[103], понимание и управление этим циклом намеков, рутинных действий и наград — ключ к успеху не только для отдельных людей, но и для бизнеса, и даже для общества в целом.
Из всех отцов обучения с подкреплением самый большой энтузиаст этого метода — Рич Саттон. Для него обучение с подкреплением — Верховный алгоритм, и решение этой проблемы равноценно решению проблемы искусственного интеллекта. C другой стороны, Крис Уоткинс не удовлетворен этим подходом и видит много того, что могут делать дети и не могут алгоритмы обучения с подкреплением: решать проблемы, решать их лучше после какого-то количества попыток, планировать, усваивать все более абстрактное знание. К счастью, для этих высокоуровневых способностей у нас тоже есть обучающиеся алгоритмы, и самый важный из них — алгоритм образования фрагментов, или chunking.
Повторенье — мать ученья
Учиться — значит становиться лучше с практикой. Сейчас вы, может быть, и не помните, как сложно было научиться завязывать шнурки. Сначала не получалось вообще ничего, хотя вам было целых пять лет. Потом шнурки, наверное, развязывались быстрее, чем вы успевали их завязать. Но постепенно вы научились завязывать их быстрее и лучше, пока движения не стали совершенно автоматическими. То же самое происходило, например, с ползанием, ходьбой, бегом, ездой на велосипеде и вождением автомобиля, чтением, письмом и арифметикой, игрой на музыкальных инструментах и занятиями спортом, приготовлением пищи и работой на компьютере. По иронии судьбы, больше всего пользы приносит самое болезненное обучение: поначалу сложен каждый шаг, вы раз за разом терпите неудачу, и, даже если получается, результаты не впечатляют. Освоив замах в гольфе или подачу в теннисе, можно годами оттачивать мастерство, но все эти годы дадут меньше, чем первые несколько недель. С практикой вы становитесь искуснее, но скорость не постоянна: сначала улучшения приходят быстро, потом все медленнее, а затем совсем замедляются. Неважно, осваиваете вы игры или учитесь играть на гитаре: кривая зависимости улучшения результатов от времени — насколько хорошо вы что-то делаете и сколько времени это занимает — имеет очень характерную форму:
Этот тип кривой называют степенным законом, потому что изменение эффективности зависит от возведения времени в какую-то отрицательную степень. Например, на рисунке выше время до завершения пропорционально числу попыток, возведенному в минус вторую степень (или, эквивалентно, единице, разделенной на квадрат числа попыток). Практически все человеческие навыки следуют степенному закону, и разным умениям соответствуют разные степени. (А вот Windows с практикой не ускоряется — Microsoft есть над чем поработать.)
В 1979 году Аллен Ньюэлл и Пол Розенблюм[104] начали задумываться, в чем причина так называемого степенного закона практики. Ньюэлл был одним из основателей науки об искусственном интеллекте и ведущим когнитивным психологом, а Розенблюм — его студентом в Университете Карнеги–Меллон. В то время ни одна из существующих моделей практики не могла объяснить степенной закон. Ньюэлл и Розенблюм подозревали, что он как-то связан с образованием фрагментов — понятием из психологии восприятия и памяти. Информацию мы воспринимаем и запоминаем фрагментами и одномоментно можем удерживать в краткосрочной памяти лишь определенное количество таких кусочков (согласно классической статье Джорджа Миллера — семь, плюс-минус два). Критически важно, что группировка объектов позволяет обрабатывать намного больше информации, чем если бы мы этого не делали, поэтому в телефонных номерах ставят дефисы: 17-23-458-38-97 запомнить намного легче, чем 17234583897. Герберт Саймон[105], давний коллега Ньюэлла и один из основоположников изучения искусственного интеллекта, до этого открыл, что основное различие между начинающим и профессиональным шахматистом заключается в том, что новичок воспринимает шахматные позиции по одной за раз, в то время как профессионал видит более крупные паттерны, состоящие из многих элементов. Совершенствование шахматной игры в основном сводится к усвоению большего количества более крупных кусков. Ньюэлл и Розенблюм выдвинули гипотезу, что аналогичный процесс имеет место не только в шахматах, но и в усвоении навыков.
В восприятии и памяти фрагмент — это просто символ, который соответствует паттерну других символов: например, ИИ означает искусственный интеллект. Ньюэлл и Розенблюм адаптировали эту идею для теории решения проблем, уже разработанной Ньюэллом в соавторстве с Саймоном. Тогда в ходе эксперимента участников просили решать задачи, например выводить на доске одну математическую формулу из другой и одновременно вслух комментировать свои действия. Ученые выяснили, что человек решает проблемы путем разложения их на подпроблемы, подподпроблемы и так далее и систематически уменьшает различия между начальным состоянием (скажем, первой формулой) и целевым состоянием (второй формулой). Однако для того чтобы это сделать, надо найти рабочую последовательность действий, а на это требуется время. Гипотеза Ньюэлла и Розенблюма заключалась в том, что, решая подпроблему, мы каждый раз формируем фрагмент, который позволяет прямо перейти из состояния до решения в состояние после. Фрагмент в этом смысле состоит из двух частей: стимула (паттерна, который вы узнаёте во внешнем мире или в краткосрочной памяти) и реакции (последовательности действий, которую вы в результате выполняете). Полученный фрагмент хранится в долгосрочной памяти. В следующий раз, когда надо будет решить ту же подпроблему, можно будет легко применить его и сэкономить время на поиски. Это происходит на всех уровнях, пока не появится фрагмент для целой проблемы, позволяющий решить ее автоматически. Чтобы завязать шнурки, вы завязываете первый узел, делаете на одном конце петлю, оборачиваете вокруг нее другой конец и продеваете ее через петлю посередине. Каждое из этих действий для пятилетнего ребенка далеко не тривиально, но после усвоения соответствующих фрагментов дело почти сделано.
Розенблюм и Ньюэлл применили свою программу образования фрагментов для решения ряда проблем, измерили время, необходимое для каждой попытки, и — подумать только — получили ряд степенных кривых. Но это было только начало. Ученые встроили образование фрагментов в Soar — общую теорию познания, над которой Ньюэлл работал с Джоном Лэрдом[106], еще одним своим студентом. Программа Soar не действовала в рамках заданной иерархии целей — она умела определять новые подпроблемы и решать их каждый раз, когда сталкивалась с препятствием. Формируя новый фрагмент, Soar обобщала его, чтобы применить к схожим проблемам при помощи метода, похожего на обратную дедукцию. Образование фрагментов в Soar оказалось хорошей моделью не только для степенного закона практики, но и для многих феноменов обучения. Его можно было применять даже для получения нового знания путем разбивки данных на фрагменты и аналогии. Это привело Ньюэлла, Розенблюма и Лэрда к гипотезе, что образование фрагментов — единственный механизм, необходимый для обучения, иными словами — Верховный алгоритм.
Ньюэлл, Саймон, их студенты и последователи были классическими специалистами по искусственному интеллекту и твердо верили, что самое главное — решать проблемы. Обучающийся алгоритм может быть простым и ехать на закорках у мощного решателя задач. Действительно, обучение — просто еще один вид решения проблем. Ньюэлл и его соратники сосредоточили усилия на сведении всего обучения к образованию фрагментов, а всего познания — к Soar, но не достигли успеха. Проблема заключалась в следующем: по мере того как решатель задач узнавал все больше фрагментов, а сами фрагменты усложнялись, цена их проверки часто становилась слишком высокой, и программа не ускорялась, а замедлялась. Людям каким-то образом удается этого избежать, но ученые пока не разобрались, как именно. В довершение всего попытки свести обучение с подкреплением, обучение с учителем и все остальное к образованию фрагментов порождало больше проблем, чем решало. В итоге разработчики Soar признали поражение и встроили в программу другие типы обучения в качестве отдельных механизмов. Но, несмотря на это, разбивка на фрагменты остается выдающимся примером обучающегося алгоритма, вдохновенного психологией, и настоящий Верховный алгоритм, какой бы он ни был, несомненно будет уметь совершенствоваться с практикой.
Метод образования фрагментов и обучение с подкреплением используются в бизнесе не так широко, как обучение с учителем, кластеризация и понижение размерности, но есть и более простой тип обучения путем взаимодействия со средой: определение последствий (и действие в соответствии с полученной информацией). Если домашняя страница вашего интернет-магазина голубого цвета и вы задумываетесь, не сделать ли ее красной для повышения продаж, протестируйте новый вариант на 100 тысячах случайно отобранных клиентов и сравните результаты с теми, кто видел обычный сайт. Эту методику, называемую A/B-тестированием, поначалу применяли в основном при испытаниях лекарств, но с того времени она распространилась на многие области, где данные под рукой — от маркетинга до предоставления помощи иностранным государствам. Его можно обобщить для одновременной проверки многих сочетаний изменений, не запутываясь, какие изменения ведут к каким приобретениям (или потерям). Amazon, Google и другие компании верят этому тестированию безгранично. Вы, скорее всего, сами того не подозревая, участвовали в тысячах A/B-тестов. Этот метод показывает ошибочность расхожего мнения, что большие данные хороши для нахождения корреляций, но не причинно-следственных связей. Если оставить в стороне философские тонкости, определение причинности — нахождение последствий действий, и оно доступно каждому — от годовалого ребенка, который плещется в ванночке, и до президента, ведущего кампанию по переизбранию, — был бы поток данных, на который есть возможность влиять.
Как найти соотношения
Если мы одарим нашего Робби всеми способностями к обучению, которые до сих пор видели в этой книге, он будет достаточно умным, но немного аутичным. Мир для него окажется скоплением отдельных предметов: он начнет узнавать их, манипулировать ими и даже делать в их отношении прогнозы, но не будет понимать, что мир — это сеть взаимосвязей. Робби-врач станет ставить диагнозы человеку с гриппом на основе симптомов, но не заподозрит свиной грипп на том основании, что пациент контактировал с носителем вируса. До появления Google поисковые движки решали, соответствует ли веб-страница вашему запросу, заглядывая в ее содержимое, — что еще можно сделать? Идея Брина и Пейджа заключалась в том, что самый сильный признак, указывающий на то, что страница подходит, — это ссылки на нее с других подходящих страниц. Аналогично, если вы хотите предсказать, рискует ли подросток начать курить, — лучшее, что вы можете сделать, — проверить, курят ли его близкие друзья. Форма фермента неотделима от формы молекул, которые он переносит, как замок неотделим от ключа. Хищника и жертву объединяют сильно взаимосвязанные свойства, каждое из которых эволюционировало, чтобы победить соперника. Во всех этих случаях лучший способ понять сущность — будь то человек, животное, веб-страница или молекула, — понять, как она связана с другими сущностями. Для этого требуется новый род обучения, который относится к данным не как к случайной выборке не связанных друг с другом объектов, а как к возможности взглянуть на сложную сеть. Узлы в этой сети взаимодействуют: то, что вы делаете с одним, влияет на другие и возвращается, чтобы повлиять на вас. Реляционные обучающиеся алгоритмы, как они называются, могут не иметь социальных навыков, но близки к этому. В традиционном статистическом обучении каждый человек как остров, вещь в себе. В реляционном обучении люди — кусочки континента, часть главного. Они реляционные обучающиеся алгоритмы, связанные и подключенные друг к другу, и, если мы хотим, чтобы Робби вырос восприимчивым, социально адаптированным роботом, его тоже надо подключить.
Первая сложность, с которой мы сталкиваемся, заключается в следующем: если данные образуют одну большую сеть, вместо большого числа примеров для обучения у нас, видимо, будет всего один, а этого недостаточно. Наивный байесовский алгоритм узнает, что высокая температура — один из симптомов гриппа, путем подсчета больных гриппом пациентов с лихорадкой. На основе одного случая он либо сделает вывод, что грипп всегда вызывает высокую температуру, либо что он никогда ее не вызывает. И то и другое ложно. Мы хотели бы определить, что грипп — заразная болезнь, посмотрев на паттерны инфекции в социальной сети — группа зараженных людей тут, группа незараженных там, — но посмотреть мы можем только на один паттерн, даже если он представляет собой сеть из семи миллиардов людей, поэтому неясно, как тут делать обобщения. Ключ к решению — обратить внимание на то, что при погружении в большую сеть в нашем распоряжении оказывается много примеров пар. Если у пары знакомых выше вероятность заболеть гриппом, чем у пары людей, которые никогда не встречались, то знакомство с заболевшим делает и вас уязвимее для этой болезни. К сожалению, не получится просто посчитать в имеющихся данных пары знакомых, где оба больны гриппом, и превратить результат в вероятность. Дело в том, что знакомых у людей много и все парные вероятности не сложатся в связную модель, которая позволит, например, вычислить риск гриппа, зная, какие знакомые больны. Когда примеры не были связаны между собой, этой проблемы не возникало: ее не будет, скажем, в обществе бездетных пар, каждая из которых живет на собственном необитаемом острове. Но такой мир нереален, и эпидемий в нем не появится в любом случае.
Решение заключается в том, чтобы получить набор свойств и узнать их вес, как в сетях Маркова. Для каждого человека X можно ввести свойство «X болен гриппом», для каждой пары знакомых X и Y — свойство «и X, и Y больны гриппом» и так далее. Как и в марковских сетях, максимально правдоподобный вес будет заставлять свойство встречаться с частотой, наблюдаемой в данных. Вес «X болен гриппом» будет высоким, если много людей больны гриппом. Вес «и X, и Y больны гриппом» окажется выше, если шанс заболеть гриппом у Y с больным знакомым X выше, чем у случайно выбранного члена сети. Если 40 процентов людей и 16 процентов всех пар знакомых больны гриппом, вес свойства «и X, и Y больны гриппом» будет нулевым, потому что для правильного воспроизведения статистики данных (0,4 0,4 = 0,16) это свойство не нужно. Однако если вес свойства положительный, грипп с большей вероятностью будет возникать в группах, а не произвольно инфицировать людей, и вероятность заболеть гриппом станет выше, если больны знакомые.
Обратите внимание, что сеть имеет отдельное свойство для каждой пары — «и у Элис, и у Боба грипп», «и у Элис, и у Криса грипп» и так далее. Но узнать вес для каждой пары не получится, потому что для пары есть только одна точка данных (инфицированы или нет) и нельзя сделать обобщение для членов сети, которым мы еще не поставили диагноз (есть ли грипп и у Иветт, и у Зака?). Вместо этого мы можем узнать единичный вес для всех свойств такой формы на основе всех частных случаев, которые наблюдали. В результате «и X, и Y больны гриппом» будет шаблоном свойств, который можно применить к каждой паре знакомых (Элис и Бобу, Элис и Крису и так далее). Веса для всех частных случаев шаблона связаны в том смысле, что у них всех будет одинаковое значение, и таким образом обобщение окажется возможным, несмотря на то что пример у нас всего один (сеть в целом). В нереляционном обучении параметры модели связаны только одним способом: по всем независимым примерам (например, все пациенты, которым мы поставили диагноз). В реляционном обучении каждый шаблон свойств, который мы создаем, связывает параметры всех его частных случаев.
Мы не ограничены парными или индивидуальными свойствами. Facebook хочет выявить ваших потенциальных друзей, чтобы порекомендовать их вам. Для этого используется правило «Друзья друзей, вероятно, тоже друзья», а каждый частный случай этого правила включает троих: если Элис и Боб — друзья, и Боб и Крис — друзья, то Элис и Крис — потенциальные друзья. В шутке Генри Менкена[107] о том, что мужчина богат, когда он зарабатывает больше мужа сестры своей жены, присутствует упоминание о четырех людях. Каждое из этих правил можно превратить в шаблон свойств реляционной модели, а вес для них можно получить на основе того, как часто свойство встречается в данных. Как и в марковских сетях, сами свойства тоже можно вывести из данных.
Реляционные обучающиеся алгоритмы способны переносить обобщения из одной сети в другую (например, получить модель распространения гриппа в Атланте и применить ее в Бостоне) и учиться на нескольких сетях (например, для Атланты и Бостона при нереалистичном допущении, что в Атланте никто никогда не контактировал с бостонцами). В отличие от «традиционного» обучения, где все примеры должны иметь одинаковое количество атрибутов, в реляционном обучении размер сетей может быть разным: более крупная сеть просто будет содержать больше частных случаев тех же шаблонов, что и меньшая. Конечно, перенос обобщения из меньшей сети в большую может быть точным, а может и не быть, но смысл в том, что ничто не мешает это делать, а крупные сети локально часто ведут себя как небольшие.
Самый изящный трюк, на который способен реляционный обучающийся алгоритм, — превратить периодического учителя в неутомимого. Для обычного классификатора примеры без классов бесполезны: если я узнаю симптомы пациентов, но не их диагнозы, это не поможет мне научиться диагностике. Однако если мне известно, что кто-то из друзей пациента болен гриппом, это косвенный признак, что грипп может быть и у него. Поставить диагноз нескольким людям в сети, а затем распространить его на их знакомых и знакомых их знакомых — тоже неплохо, хотя и хуже, чем индивидуальный диагноз. Полученные таким образом диагнозы могут быть зашумленными, но общая статистика корреляции симптомов с гриппом будет, вероятно, намного точнее и полнее, чем выводы на основе горсти изолированных диагнозов. Дети очень хорошо умеют извлекать максимальную пользу из периодического надзора за ними (при условии, что они его не проигнорируют). Реляционные обучающиеся алгоритмы частично обладают такой способностью.
Однако за мощь приходится платить. В обычных классификаторах, например дереве решений или перцептроне, вывод о классе объекта на основе его атрибутов можно сделать после нескольких просмотров данных и небольших арифметических вычислений. В случае сети класс каждого узла косвенно зависит от всех остальных узлов, и сделать о нем вывод изолированно нельзя. Можно прибегнуть к тем же видам методик логического вывода, что и в случае байесовских сетей, например к циклическому распространению доверия или MCMC, но масштаб будет другим: в типичной байесовской сети могут быть тысячи переменных, а в социальных сетях — миллионы и даже больше узлов. К счастью, модель сети состоит из многократных повторений одних и тех же черт с теми же самыми весами, поэтому часто получается сжать сеть в «сверхузлы», состоящие из многочисленных узлов, которые, как мы знаем, имеют одинаковые вероятности, и теперь нужно решить намного меньшую проблему с тем же результатом.
У реляционного обучения долгая история, уходящая как минимум в символистские методики 1970-х годов, например обратную дедукцию. Но с зарождением интернета оно приобрело новый импульс. Сети внезапно стали повсеместными, а их моделирование — неотложной задачей. Явление, которое мне показалось особенно любопытным, — сарафанное радио. Как распространяется информация в социальной сети? Можно ли измерить влияние каждого ее участника и породить волну слухов, нацелившись на минимально необходимое число наиболее влиятельных? С моим студентом Мэттом Ричардсоном мы разработали алгоритм, который делал именно это, и применили его к сайту Epinions.com с обзорами продукции, где пользователи имели возможность рассказывать, чьим обзорам они доверяют. Помимо всего прочего, мы обнаружили, что рекламировать продукты одному самому влиятельному члену, которому доверяют многие участники сети, которым, в свою очередь, доверяют многие другие пользователи и так далее, — не менее эффективный метод, чем маркетинг, направленный на треть всех пользователей по отдельности. Затем последовала целая лавина исследований этой проблемы. С тех пор я применял реляционное обучение ко многим другим задачам, включая прогнозирование, кто будет образовывать связи в социальной сети, интегрирование баз данных и способности роботов картировать окружающую обстановку.
Если вы хотите понять, как работает мир, реляционное обучение стоит иметь в арсенале. В цикле романов Айзека Азимова «Основание» ученому Гэри Селдону удается математически предсказать будущее человечества и тем самым спасти его от упадка. Пол Кругман, наряду с другими, признался, что эта соблазнительная мечта сделала его экономистом. Согласно Селдону, люди похожи на молекулы газа, и, даже если сами индивидуумы непредсказуемы, на общества это не распространяется просто по закну больших чисел. Реляционное обучение объясняет, почему это не так. Если бы люди были независимы и каждый принимал решения изолированно, общества действительно были бы предсказуемы, потому что случайные решения складывались бы в довольно постоянное среднее. Но когда люди взаимодействуют, более крупные группы бывают не более, а менее предсказуемы, чем небольшие. Если уверенность и страх заразны, каждое из этих состояний станет некоторое время доминировать, но периодически все общество будет качать от одного к другому. Это, однако, совсем не так уж плохо. Если получится измерить, как сильно люди влияют друг на друга, можно оценить и то, сколько времени пройдет перед таким сдвигом, даже если он произойдет впервые. Это еще один способ, благодаря которому «черные лебеди» не обязательно непредсказуемы.
Многие жалуются, что чем больше объем данных, тем легче увидеть в них мнимые паттерны. Может быть, это и правда, если данные представляют собой просто большой набор не связанных друг с другом объектов, но, если они взаимосвязаны, картина меняется. Например, критики применения добычи данных для борьбы с терроризмом утверждают, что, даже если не брать этические аспекты, такой подход не сработает, потому что невиновных слишком много, а террористов слишком мало, и поиск подозрительных паттернов либо даст много ложных срабатываний, либо никого не поймает. Человек, снимающий на видеокамеру ратушу Нью-Йорка, — это турист или злоумышленник, присматривающий место для теракта? А человек, заказавший большую партию нитрата аммония, — мирный фермер или изготовитель взрывных устройств? Все эти факты по отдельности выглядят достаточно безобидно, но, если «турист» и «фермер» часто разговаривают по телефону и последний только что въехал тяжело груженным пикапом на Манхэттен, наверное, самое время к ним присмотреться. Агентство национальной безопасности США любит искать данные в списках телефонных разговоров не потому, что это, вероятно, законно, а потому, что эти списки зачастую более информативны для предсказывающих алгоритмов, чем содержание самих звонков, которое должен оценивать живой сотрудник.
Кроме социальных сетей, «приманка» реляционного обучения — возможность разобраться в механизмах работы живой клетки. Клетка — сложная метаболическая сеть, где гены кодируют белки, регулирующие другие гены. Это длинные, переплетающиеся цепочки химических реакций, продукты, мигрирующие из одной органеллы в другую. Независимых сущностей, которые делают свою работу изолированно, там не найти. Лекарство от рака должно нарушить функционирование раковой клетки, не мешая работе нормальных. Если у нас в руках окажется точная реляционная модель обоих случаев, можно будет попробовать много разных лекарств in silico, разрешая модели делать выводы об их положительных и отрицательных эффектах, и, выбрав только хорошие, испытать их in vitro и, наконец, in vivo.
Как и человеческая память, реляционное обучение плетет богатую сеть ассоциаций. Оно соединяет воспринимаемые объекты, которые робот вроде Робби может усвоить путем кластеризации и уменьшения размерности, с навыками, которые можно приобрести путем подкрепления и образования фрагментов, а также со знанием более высокого уровня, которое дают чтение, учеба в школе и взаимодействие с людьми. Реляционное обучение — последний кусочек мозаики, заключительный ингредиент, который нужен нам для нашей алхимии. Теперь пришло время отправиться в лабораторию и превратить эти элементы в Верховный алгоритм.
ГЛАВА 9
КУСОЧКИ МОЗАИКИ ВСТАЮТ НА МЕСТО
Машинное обучение — это и наука, и технология, и обе составляющие дают нам подсказки, как их объединить. В науке объединяющие теории часто начинаются с обманчиво простых наблюдений: два не связанных на первый взгляд феномена оказываются сторонами одной медали, и осознание этого факта, как первая костяшка домино, порождает каскад новых открытий. Упавшее на землю яблоко и луна в небе: и то и другое вызвано гравитацией, и — правда это или выдумка, — когда Ньютон разобрался в природе этого явления, гравитация оказалась ответственной за приливы, предсказание равноденствий, траектории комет и многое другое. В повседневной жизни электричество и магнетизм не сопровождают друг друга: одно дело — вспышка молнии, а совсем другое — притягивающая железо руда, причем и то и другое встречается довольно редко. Но когда Максвелл понял, как изменение электрического поля порождает магнетизм и наоборот, стало ясно, что сам свет — это тесный союз обоих явлений, и сегодня мы знаем, что электромагнетизм далеко не редок и пронизывает всю материю. Периодическая система элементов Менделеева не только упорядочила все известные элементы всего в двух измерениях, но и предсказала, где искать новые. Наблюдения на борту «Бигля» внезапно обрели смысл, когда «Опыт закона о народонаселении» Мальтуса подсказал Дарвину естественный отбор в качестве организующего принципа. Как только Крик и Уотсон с помощью структуры двойной спирали объяснили загадочные свойства ДНК, они увидели, что эта молекула может реплицировать саму себя, и начался переход биологии от стадии «собирания марок» (как уничижительно назвал ее Резерфорд) к единой науке. В каждом из этих случаев оказывается, что у обескураживающе разнообразных наблюдений есть общая причина и, когда ученые ее находят, становится возможным использовать ее для предсказания новых явлений. Аналогично, хотя алгоритмы машинного обучения, с которыми мы познакомились в этой книге, могут показаться довольно несхожими — некоторые основаны на работе мозга, некоторые — на эволюции, а некоторые — на абстрактных математических принципах, — на самом деле у них есть много общего, и получившаяся в результате теория обучения принесет много новых прозрений.
Не все знают, что многие из важнейших технологий — результаты изобретения единого, объединяющего механизма, который делает то, для чего раньше требовалось много разных инструментов. Интернет — сеть, соединяющая между собой сети. Без нее каждый тип сети нуждался бы в собственном протоколе, чтобы контактировать с другими, как мы нуждаемся в отдельном словаре для каждой языковой пары. Протоколы интернета — это эсперанто, дающее каждому компьютеру иллюзию прямого разговора с любым другим компьютером, и это позволяет электронным письмам и интернету игнорировать детали физической инфраструктуры, по которой они передаются. Реляционные базы данных делают нечто схожее с корпоративными приложениями, позволяя разработчикам и пользователям мыслить в категориях абстрактных реляционных моделей и игнорировать способы, которыми компьютеры отвечают на запросы. Микропроцессор — совокупность цифровых электронных элементов, которая может имитировать любое другое собрание. Виртуальные машины позволяют одному компьютеру выдавать себя за сотню компьютеров для сотни разных людей одновременно и делают возможным облачное хранение данных. Графические пользовательские интерфейсы позволяют нам редактировать документы, электронные таблицы, презентации и многое другое с использованием общего языка окон, меню и кликов мыши. Компьютер сам по себе — объединяющее, единое устройство, способное решать любую логическую или математическую проблему при условии, что мы сумеем его соответствующим образом запрограммировать. Даже электричество — своего рода объединитель: его можно получать из многих источников — угля, газа, ядерной реакции, воды, ветра, солнца, — и у него бесконечное множество применений. Электростанция не знает и не хочет знать, как будет потребляться вырабатываемый ею ток, а фонарь в подъезде, посудомоечная машина и новенькая Tesla не помнят, откуда взялось питающее их электричество. Электричество — это эсперанто в мире энергии. Верховный алгоритм — это объединитель в мире машинного обучения: он позволяет любому приложению использовать любой обучающийся алгоритм, абстрагируя эти алгоритмы в общую форму — единственную, которую нужно знать приложениям.
Наш первый шаг к Верховному алгоритму будет на удивление простым. Как оказывается, несложно соединить много разных обучающихся алгоритмов в один, используя так называемое метаобучение. Его используют Netflix, Watson, Kinect и бесчисленное множество других программ, и это одна из самых мощных стрел в колчане машинного обучения. Это также ступенька к более глубокому объединению алгоритмов, о котором мы поговорим дальше.
Из многих моделей — одна
Вот вам задача: за 15 минут соедините деревья решений, многослойные перцептроны, системы классификации, наивный байесовский алгоритм и метод опорных векторов в один алгоритм, который будет обладать лучшими свойствами каждого из элементов. Быстро: что вы можете сделать? Очевидно, что детали отдельных алгоритмов в нем использовать нельзя: просто не хватит времени. Давайте попробуем следующее решение. Представьте, что каждый из обучающихся алгоритмов — эксперт в комитете. Каждый внимательно рассматривает подлежащий классификации случай — какой диагноз поставить пациенту? — и уверенно дает прогноз. Вы сами — не эксперт, а председатель этого комитета, и ваша работа — объединить рекомендации в окончательное решение. В руках у вас, по сути, новая проблема классификации, где вместо симптомов пациентов входом будет мнение экспертов, но машинное обучение можно применить к этой проблеме таким же образом, как эксперты применяли его к исходным данным. Такой подход называется метаобучением, потому что это обучение обучающимся алгоритмам. Сам метаалгоритм может быть любым, от дерева решений до простого взвешенного голосования. Чтобы узнать веса или дерево решений, атрибуты каждого исходного примера заменяются прогнозами обучающихся алгоритмов. Алгоритмы, которые часто предсказывают правильный класс, получают высокий вес, а неточные будут чаще игнорироваться. В случае дерева решений использование обучающегося алгоритма может зависеть от предсказаний других алгоритмов. Как бы то ни было, чтобы получить прогноз алгоритма для данного примера, сначала надо применить алгоритм к исходному обучающему набору, исключив этот пример, и использовать получившийся в результате классификатор, иначе есть риск, что в комитете будут доминировать алгоритмы, страдающие переобучением, поскольку они могут предсказывать правильный класс, просто его запоминая. Победитель Netflix Prize использовал метаобучение для соединения сотен алгоритмов машинного обучения. Watson использует его для выбора окончательного ответа из имеющихся кандидатов. Нейт Сильвер соединяет результаты опросов аналогичным образом, чтобы спрогнозировать результаты выборов.
Этот тип метаобучения называют стэкингом, а придумал его Дэвид Уолперт, автор теоремы «Бесплатных обедов не бывает», с которой мы познакомились в главе 3. Еще более простой метаалгоритм — это бэггинг, изобретенный статистиком Лео Брейманом. Бэггинг генерирует случайные вариации обучающего набора путем перевыборки, применяет к каждой вариации один и тот же алгоритм машинного обучения и соединяет результаты путем голосования. Это нужно для того, чтобы уменьшить дисперсию: объединенная модель гораздо менее чувствительна к капризам данных, чем любая единичная, поэтому это замечательно легкий способ улучшить точность. Если модели — деревья решений и мы будем еще больше варьировать их, формируя случайный поднабор атрибутов в каждом дереве, получится так называемый случайный лес. Случайный лес — это один из самых точных имеющихся классификаторов. Kinect компании Microsoft использует его для определения ваших действий и регулярно выигрывает соревнования по машинному обучению.
Один из самых сообразительных метаалгоритмов — бустинг, созданный двумя теоретиками обучения, Йоавом Фройндом и Робом Шапире. Бустинг не соединяет разные обучающиеся алгоритмы, а раз за разом применяет к данным один и тот же классификатор, используя новую модель, чтобы исправить ошибки предыдущей путем присвоения весов обучающим примерам. Вес каждого неправильно классифицированного примера увеличивается после каждого цикла обучения, заставляя последующие циклы больше сосредоточиваться на нем. Название «бустинг» — усиление — связано с тем, что этот процесс может резко улучшить классификатор, который незначительно, но стабильно лучше случайного угадывания, и сделать его почти идеальным.
Метаобучение исключительно успешно, но это не очень глубокий способ объединения моделей. Кроме того, он дорог и требует многократного обучения, а соединенные модели могут получиться довольно непрозрачными. («Я уверен, что у вас рак предстательной железы, потому что на это указывают дерево решений, генетический алгоритм и наивный байесовский классификатор, хотя многослойный перцептрон и метод опорных векторов с этим не согласны».) Более того, все объединенные модели — на самом деле просто одна хаотичная модель. Нельзя ли получить единый обучающийся алгоритм, который делает то же самое? Можно.
Верховный алгоритм
Наш объединенный обучающийся алгоритм, наверное, лучше всего ввести с помощью аллегории. Если представить себе машинное обучение в виде континента, разделенного на территории пяти «племен», то Верховный алгоритм будет столицей, расположенной в уникальном месте, где сходятся их границы. Вы приближаетесь к городу издалека и видите, что состоит он из трех концентрических, обнесенных стеной колец. Внешний и без сомнения самый широкий круг — это Городок оптимизации. Дома здесь — алгоритмы всех форм и размеров. Одни только строятся, и вокруг них суетятся местные жители, другие сияют свежестью, третьи выглядят старыми и заброшенными. Выше на холме стоит Цитадель оценки. Из ее особняков и дворцов постоянно исходят приказы алгоритмам внизу. На самой вершине в небо взлетает Башня представлений. Здесь живут отцы города. Их непреложные законы определяют, что можно сделать, а чего нельзя, и не только в городе, но и на всем континенте. На вершине центральной, самой высокой башни развевается флаг Верховного алгоритма: красно-черный, с пятиконечной звездой, внутри которой надпись, но вы пока не можете ее разобрать.
Город разделен на пять секторов, по одному для каждого из пяти «племен». Сектора простираются от Башни представлений вниз, к внешним стенам, опоясывающим Башню, группы дворцов в Цитадели оценки и улицы и дома Городка оптимизации, над которой они возвышаются. Пять секторов и три кольца делят город на 15 районов — 15 форм, 15 кусочков мозаики, которую вам надо сложить:
Вы пристально вглядываетесь в карту, пытаясь расшифровать ее секрет. Пятнадцать кусочков довольно точно подходят друг к другу, но вам надо понять, как они соединяются, чтобы получить всего три элемента: представление, оценку и оптимизацию Верховного алгоритма. Каждый обучающийся алгоритм состоит из этих элементов, но они разнятся от «племени» к «племени».
Представления — формальный язык, на котором алгоритм машинного обучения выражает свои модели. Формальный язык символистов — логика, частные случаи которой — правила и деревья решений. Для коннекционистов это нейронные сети. Для эволюционистов — генетические программы, включая системы классификации. Для байесовцев — графические модели, общий термин для байесовских и марковских сетей. Для аналогизаторов — частные случаи, возможно, с весами, как в методе опорных векторов.
Элемент оценки — функция присвоения баллов, которая говорит, насколько хороша модель. Символисты используют точность и информационный выигрыш. Коннекционисты — непрерывное измерение погрешности, например квадрат ошибки, который представляет собой сумму квадратов различий между предсказанными и истинными значениями. Байесовцы применяют апостериорную вероятность, аналогизаторы (как минимум специалисты по методу опорных векторов) — зазор. В дополнение к оценке того, насколько хорошо модель подходит к данным, все «племена» учитывают другие желательные свойства, например простоту модели.
Оптимизация — это алгоритм, который ищет и выдает модель с наивысшей оценкой. Характерный поисковый алгоритм символистов — обратная дедукция. Коннекционистов — градиентный спуск. Эволюционистов — генетический поиск, включая кроссинговер и мутации. Байесовцы в этом отношении необычны: они не просто ищут лучшую модель, но и усредняют по всем моделям, взвешивая их вероятность. Для эффективного взвешивания они пользуются алгоритмами вероятностного вывода, например MCMC. Аналогизаторы (или, точнее, адепты метода опорных векторов) используют условную оптимизацию для нахождения лучшей модели.
У вас за плечами многодневный путь, солнце начинает быстро клониться к горизонту, и надо поторопиться, пока не стемнело. Во внешней стене пять массивных ворот, каждые под охраной своего «племени», и ведут они в соответствующие районы Городка оптимизации. Давайте пройдем через Ворота градиентного спуска, шепнув стражнику пароль — «глубокое обучение», — и начнем по спирали подниматься к Башням представления. Улицы уходят круто вверх по склону холма к Воротам квадратичной ошибки, ведущим в цитадель, но вы сворачиваете влево, к эволюционистскому сектору. Дома в районе градиентного спуска — это гладкие кривые и густо переплетенные паттерны, напоминающие скорее джунгли, а не город. Но когда градиентный спуск уступает место генетическому поиску, картина резко меняется. Дома здесь выше, структура громоздится на структуру, но сами структуры незаполненные, почти пустые. Они как будто ждут, что в них придут кривые градиентного спуска. Вот он, способ их соединить: надо использовать генетический поиск, чтобы найти структуру модели, а потом позволить градиентному спуску заполнить ее параметры. Именно так поступает природа: эволюция создает структуры головного мозга, а индивидуальный опыт моделирует их.
Первый шаг сделан, и вы спешите в байесовский район. Даже на расстоянии видно, как он лепится к Кафедральному собору теоремы Байеса. Переулок MCMC делает случайные зигзаги. Чтобы не терять времени, вы срезаете путь и выходите на улицу Распространения степени уверенности, но она, похоже, образует бесконечную петлю. И тут вы видите то, что надо: широкий бульвар Наибольшего правдоподобия, ведущий вверх, к воротам Апостериорной вероятности. Вместо того чтобы усреднять все модели, можно направиться прямиком к самой вероятной, с уверенностью, что в итоге прогнозы будут почти такими же. Генетическому поиску можно позволить подобрать структуру модели, а градиентному спуску — ее параметры. Со вздохом облегчения вы понимаете, что это весь вероятностный вывод, который вам нужен, по крайней мере, пока не придет время с помощью модели отвечать на вопросы.
Вы продолжаете свой путь. Район условной оптимизации напоминает лабиринт узких улочек и тупиков. Повсюду плечом к плечу стоят примеры всех сортов, периодически уступая место опорному вектору. Очевидно: чтобы не врезаться в примеры неправильного класса, нужно просто добавить ограничения в уже собранный оптимизатор. Но если подумать, делать это совсем не обязательно. При обучении методу опорных векторов обычно разрешается нарушать зазоры, чтобы избежать переобучения, при условии, что каждое нарушение штрафуется. В этом случае веса оптимальных примеров можно снова получить с помощью одной из форм градиентного спуска. Это было несложно, и вы чувствуете, что начинаете набивать руку.
Плотные ряды частных случаев резко обрываются, и вы попадаете в район Обратной дедукции. Вокруг широкие аллеи и старинные каменные здания. Архитектура здесь геометрическая, строгая, состоящая из прямых линий и прямых углов. Квадратные даже стволы у сильно обрезанных деревьев, а их листья тщательно подписаны предсказаниями класса. Обитатели этого района, видимо, строят свои дома особым образом: они начинают с крыши, которую называют выводами, и постепенно заполняют пустые места между крышей и землей — предпосылками, на их языке. Один за другим они находят каменные блоки, которые хорошо подойдут для заполнения пробелов, и поднимают их на место. Вы замечаете, что форма многих пробелов одинакова, и работа пойдет быстрее, если обрезать и складывать блоки, подгоняя их, а потом повторять процесс столько раз, сколько нужно. Другими словами, для обратной дедукции можно использовать генетический поиск. Прекрасно. Кажется, вы свели все пять оптимизаторов к простому рецепту: генетический поиск структуры и градиентный спуск для параметров. И даже это может быть лишним. Во многих проблемах генетический поиск можно свести к восхождению на выпуклые поверхности, если выполнить три условия: не включать кроссинговер, пробовать в каждом поколении все возможные точечные мутации и всегда выбирать одну лучшую гипотезу, чтобы «заразить» ею следующее поколение.
А что это за статуя впереди? Это Аристотель, который неодобрительно взирает на переплетение и хаос квартала градиентного спуска. Круг замкнулся. У вас есть объединенный оптимизатор, необходимый для Верховного алгоритма, но сейчас не время для поздравлений. Опустилась ночь, а сделать предстоит еще очень много. Вы идете в Цитадель оценки через впечатляющие, но довольно узкие Ворота точности. Надпись над ними гласит: «Оставь надежды на переобучение, всяк сюда входящий». Огибая дворцы алгоритмов оценки всех пяти «племен», вы мысленно ставите кусочки на место. Точность вы станете использовать для оценки предсказаний типа «да или нет», квадратичную ошибку — для непрерывных предсказаний. Приспособленность — просто эволюционистское название функции подсчета очков: ее можно сделать какой вздумается, в том числе точностью и квадратом ошибки. Апостериорная вероятность уменьшает квадрат ошибки, если проигнорировать априорную вероятность и если ошибки следуют нормальному распределению. Зазор, если разрешить нарушать его за определенную цену, становится более мягкой версией точности: вместо того чтобы платить нулевой штраф за правильное предсказание и единицу за каждое неправильное предсказание, штраф будет нулевым, пока вы не попадаете в зазор, а потом он начинает расти. Готово! Сложить алгоритмы оценки оказалось намного проще, чем объединить оптимизаторы. Но над вами нависли Башни представления, и они наполняют вас дурными предчувствиями.
Вы дошли до последнего этапа поисков и стучитесь в дверь Башни опорных векторов. Вам открывает грозного вида стражник, и тут вы понимаете, что не знаете пароль. «Ядро!» — выпаливаете вы, пытаясь не выдать испуг. Страж кланяется и уступает дорогу. Собравшись с духом, вы входите внутрь, тихо браня себя за беспечность. Весь первый этаж башни занимают щедро обставленные округлые покои, а в центре на почетном месте стоит нечто напоминающее мраморное представление метода опорных векторов. Осматривая комнату, вы замечаете где-то сбоку дверь. Она должна вести в центральную башню — Башню Верховного алгоритма. Похоже, дверь не охраняют, и вы решаете срезать путь. Проскользнув через дверной проем и пройдя по короткому коридору, вы оказываетесь в еще большем пятиугольном помещении с дверью в каждой стене. В центре куда-то ввысь уходит винтовая лестница. Оттуда доносятся голоса, и вы ныряете в дверь напротив. Она ведет в Башню нейронных сетей. Вы снова оказываетесь в округлом помещении, в центре которого на этот раз стоит многослойный перцептрон. Его элементы отличаются от метода опорных векторов, но их расположение замечательно схоже. Вдруг вас осеняет: метод опорных векторов — это же просто многослойный перцептрон, но скрытый слой состоит из ядер, а не из сигмоид, а выходной слой — не еще одна S-кривая, а линейная комбинация.
Может быть, другие представления тоже имеют схожую форму? С растущим возбуждением вы бежите обратно в пятиугольную комнату, а оттуда — в Башню логики. Глядя на стоящее в центре изображение набора правил, вы пытаетесь увидеть схему. Есть! Каждое правило — это просто очень сильно стилизованный нейрон. Например, правило «Если это гигантская рептилия и она дышит огнем — это дракон» — это просто перцептрон с весами один для «это гигантская рептилия» и «дышать огнем» и порогом 1,5. А набор правил — многослойный перцептрон со скрытым слоем, содержащий один нейрон для каждого правила и выходящий нейрон для дизъюнкции этих правил. Где-то в глубине души вас гложут сомнения, но сейчас думать о них некогда. Вы бежите через пятиугольную комнату в Башню генетических программ и уже видите, как поставить их в строй. Генетические программы — это просто программы, а программа — это просто логический конструкт. Скульптура генетической программы в комнате имеет форму дерева, подпрограммы ветвятся на еще большее количество подпрограмм, и, присматриваясь к листьям, вы замечаете, что это всего лишь правила. Итак, программы сводятся к правилам, а если правила можно свести к нейронам, значит, можно и программы.
Вперед, в Башню графических моделей! К сожалению, скульптура в круглой комнате оказывается совершенно не похожей на остальные. Графическая модель — это продукт факторов: условных вероятностей, в случае байесовских сетей, и неотрицательных функций состояния — в случае сетей Маркова. Как вы ни стараетесь, уловить связь с нейронными сетями и наборами правил не получается. Вас на секунду охватывает разочарование, но вы надеваете свои лого-очки, которые превращают функции в логарифмы. Эврика! Произведение факторов стало суммой условий, прямо как метод опорных векторов, голосующий набор правил и многослойный перцептрон без S-образной кривой на выходе. Например, можно превратить наивный байесовский классификатор дракона в перцептрон, вес которого для «дышит огнем» будет разностью логарифмов P(дышит огнем | дракон) и P(дышит огнем | не дракон). Но, конечно, графические модели намного более обобщенные, потому что могут представлять вероятностные распределения по многим переменным, а не только распределение одной переменной (класс) при известных других (атрибутах).
Получилось! Или нет? Внедрить метод опорных векторов в нейронные сети и нейронные сети в графические модели можно. То же касается объединения генетических программ и логики. Но как соединить логику и графические модели? Что-то здесь не так. С запозданием вы видите, в чем проблема: у логики есть измерение, которого не хватает графическим моделям, и наоборот. Скульптуры в пяти комнатах подходили друг к другу, потому что это были простые аллегории, но в реальности все сложнее. Графические модели не позволяют представить правила, включающие больше одного объекта, например «Друзья друзей — тоже друзья». Все их переменные должны быть свойствами того же предмета. Еще они не могут представлять произвольные программы, которые передают наборы переменных из одной подпрограммы в другую. Логика умеет делать и то и другое, но она, в свою очередь, не может представлять неопределенность, двузначность и степени схожести. Без представления, которое может делать все это, универсального обучающего алгоритма не получишь.
Вы напрягаете извилины в поисках решения, но чем больше стараетесь, тем хуже выходит. Может быть, объединение логики и вероятностей неподвластно человеку? Усталость подкашивает вас и погружает в сон. Просыпаетесь вы от грозного рыка: на вас набросился похожий на гидру Монстр Сложности. Он щелкает зубами, но в последний момент вы уворачиваетесь и отчаянно рубите чудовище мечом обучения — только им можно его победить — и отрубаете все его головы. Пока не отросли новые, вы бросаетесь к лестнице.
Запыхавшись, вы взбираетесь на самый верх и видите свадебный обряд. Предиктус, Первый лорд Логики, повелитель Символического королевства и Защитник программ, говорит Марковии, Княжне вероятностей и Царице сетей: «Объединим же наши владения! В мои правила добавишь ты веса, и породим мы новые представления, которые умножатся и заселят землю». Княжна добавляет: «А потомство наше мы назовем Марковскими логическими сетями».
У вас кружится голова. Вы выходите на балкон. Над городскими крышами уже взошло солнце. Вокруг во всех направлениях простираются леса серверов: они тихо шумят в ожидании Верховного алгоритма. Караваны везут золото из копей, где добывают данные. Далеко на западе на солнце играет море информации, на котором виднеются точки кораблей. Вы поднимаете голову и смотрите на флаг Верховного алгоритма. Теперь надпись внутри пятиконечной звезды четко видна:
P = ewn / Z.
Что бы это могло значить?
Логические сети Маркова
В 2003 году мы с Мэттом Ричардсоном начали размышлять над проблемой объединения логики и вероятностей. Сначала у нас получалось не очень, потому что мы пытались добиться результата с помощью байесовских сетей, а их жесткая форма — строгая последовательность переменных, условные распределения детей у родителей — не сочеталась с гибкостью логики. Но в канун Рождества я осознал, что есть способ лучше. Если переключиться на марковские сети, можно использовать любую логическую формулу в качестве шаблона для свойств такой сети, а это объединило бы логику и графические модели. Давайте посмотрим, как это сделать.
Вспомните, что сеть Маркова, во многом как перцептрон, определяется взвешенной суммой свойств. Представьте, что у вас есть коллекция фотографий людей. Мы случайным образом выбираем одну и вычисляем ее свойства, например «у этого человека седые волосы», «этот человек пожилой», «этот человек женщина» и так далее. В перцептроне мы проводим взвешенную сумму этих свойств через порог, чтобы решить, например, это ваша бабушка или нет. В марковских сетях мы делаем нечто совершенно другое (по крайней мере на первый взгляд): взвешенная сумма возводится в степень, превращается в произведение факторов, и это произведение будет вероятностью выбора конкретно этой картинки из коллекции, независимо от того, есть ли на ней ваша бабушка. Если у вас много картинок с изображениями пожилых людей, взвешенная сумма этого свойства растет. Если большинство из них — мужчины, вес свойства «этот человек — женщина» идет вниз. Свойства могут быть какими угодно, поэтому сети Маркова — замечательно гибкий способ представления вероятностных распределений.
На самом деле я погрешил против истины: произведение факторов — это еще не вероятность, потому что сумма вероятностей всех картинок должна быть равна единице, и нет гарантии, что произведение факторов для всех картинок приведет к такому результату. Нам нужно их нормализовать, то есть разделить каждое произведение на сумму факторов. В таком случае сумма всех нормализованных произведений будет гарантированно равна единице, потому что это просто некое число, разделенное само на себя. Вероятность картинки, таким образом, будет взвешенной суммой ее свойств, возведенной в степень и нормализованной. Если вы вспомните уравнение в пятиконечной звезде, то, наверное, начнете догадываться, что оно означает. P — это вероятность, w — вектор весов (будем обозначать вектора жирным шрифтом), n — вектор чисел, а их скалярное произведение · возводится в степень и делится на Z, сумму всех произведений. Если первый компонент n равен единице, когда первое свойство изображения верно, и нулю в противном случае и так далее, то w·n — это просто сокращение для взвешенной суммы черт, о которой мы постоянно говорили.
Поэтому уравнение дает нам вероятность изображения (или чего угодно) согласно марковской сети, но оно более общее, потому что это не просто уравнение марковской сети, а уравнение логической сети Маркова — так мы ее назвали. В логической сети Маркова числа в n не обязательно должны быть равны нулю или единице, и они обращаются не к свойствам, а к логическим формулам. В конце главы 8 мы уже увидели, как выйти за пределы сетей Маркова в реляционные модели, определенные в терминах шаблонов свойств, а не просто свойств. «И у Элис, и у Боба грипп» — это свойство, специфичное для Элис и Боба. «И у X, и у Y грипп» — это шаблон свойств, частными случаями которого могут быть Элис и Боб, Элис и Крис и любая другая пара. Шаблон свойств — мощный инструмент, потому что он может суммировать миллиарды свойств в одном коротком выражении. Однако для определения шаблонов свойств нам нужен формальный язык, и он у нас есть: это логика.
Логическая сеть Маркова — просто набор логических формул и их весов. В приложении к конкретному набору объектов он определяет марковскую сеть их возможных состояний. Например, если объекты — Элис и Боб, возможным состоянием будет то, что Элис и Боб — друзья, у Элис грипп и у Боба тоже. Давайте предположим, что у логической сети Маркова две формулы: «у всех грипп» и «если у человка грипп, у его друзей тоже грипп». В стандартной логике это была бы довольно бесполезная пара утверждений: первое исключало бы все состояния, где хотя бы один человек здоров, а второе было бы избыточным. Однако в логической сети Маркова первая формула означает только то, что для каждого человека X есть свойство «X болен гриппом» с тем же весом, что и формула. Если люди с большой вероятностью болеют гриппом, и у формулы, и у соответствующих свойств будет большой вес. Состояние, где здоровых людей много, менее вероятно, чем то, где таких людей мало, однако оно не исключено. А благодаря второй формуле состояние, при котором у кого-то грипп, а у его друзей — нет, будет менее вероятно, чем то, где здоровые и зараженные попадают в отдельные кластеры друзей.
Теперь вы, вероятно, догадались, что означает n в верховном уравнении: его первый компонент — число истинных случаев первой формулы в данном состоянии, второй — число истинных случаев второй формулы и так далее. Если рассмотреть десять знакомых, семь из которых больны гриппом, первый компонент из n будет равен семи, и так далее. (Не должна ли вероятность измениться, если больны гриппом семь из двадцати, а не десяти знакомых? Да, и она будет отличаться благодаря Z.) Если все веса в этих пределах будут стремиться к бесконечности, марковская логика сведется к стандартной, потому что нарушение хотя бы одного случая формулы вызовет схлопывание вероятности до нуля, делая состояние невозможным. С точки зрения вероятностей логическая сеть Маркова сводится к марковской сети, если все формулы описывают один объект. Итак, и логика, и марковские сети — частные случаи марковской логики, и это то объединение, которое мы искали.
Обучение в логической сети Маркова — открытие формул, которые верны в мире чаще, чем предсказывали бы случайные шансы, а также определение весов для этих формул, благодаря которым их предсказанные вероятности совпадают с наблюдаемыми частотами. Готовую логическую сеть Маркова можно использовать для ответа на такие вопросы, как «Какова вероятность, что у Боба грипп, при условии, что он друг Элис и у нее грипп?» И знаете что? Оказалось, что эта вероятность задана S-образной кривой, приложенной ко взвешенной сумме свойств, во многом как в многослойном перцептроне, а логическая сеть Маркова с длинными цепочками правил может представлять глубокую нейронную сеть с одним слоем на каждое звено цепи.
Конечно, не стоит верить прогнозам распространения гриппа, сделанным описанной выше простой логической сетью Маркова. Вместо этого представьте себе логическую сеть Маркова для диагностики и лечения рака. Такая сеть будет представлять распределение вероятностей состояний клетки. Каждый элемент клетки, каждая органелла, каждый метаболический путь, каждый ген и белок — это объект сети, а формулы логической сети Маркова кодируют зависимости между ними. Можно спросить сеть: «Эта клетка — раковая?» — проверить ее разными лекарствами и посмотреть, что произойдет. Пока у нас нет таких сетей, но ниже в этой главе я опишу, как их получить.
Подытожим: единый алгоритм машинного обучения, к которому мы пришли, в качестве представления использует логическую сеть Маркова, как функцию оценки — апостериорную вероятность, а оптимизатор в нем — генетический поиск в сочетании с градиентным спуском. При желании можно легко заменить апостериорную вероятность каким-то более точным измерением, а генетический поиск — восхождением на выпуклые поверхности. Мы достигли вершины и можем наслаждаться видами. Однако я бы не торопился называть такой алгоритм Верховным. Во-первых, критерий истины — практика, и, хотя за последнее десятилетие этот алгоритм (или его разновидности) успешно применяли во многих сферах, есть намного больше областей, в которых он не применялся, поэтому пока не ясно, насколько он универсален. Во-вторых, ряд важных проблем он не решает. Но перед тем, как ими заняться, давайте посмотрим, на что он способен.
От Юма до домашних роботов
Скачать обучающийся алгоритм, который я только что описал, можно на сайте alchemy.cs.washington.edu. Мы окрестили его Alchemy, чтобы напомнить самим себе, что, несмотря на все свои успехи, наука о машинном обучении все еще находится на стадии алхимии. Скачав его, вы увидите, что он включает намного больше элементов, чем приведенный выше базовый алгоритм, и что ему все еще не хватает целого ряда аспектов, которые, как мы выяснили, универсальный обучающийся алгоритм должен иметь, например кроссинговера. Тем не менее для простоты давайте называть нашего кандидата в универсальные обучающиеся алгоритмы Alchemy.
Alchemy отвечает на вопрос Юма тем, что кроме данных у него еще один вход: исходные знания в виде набора логических формул, с весами или без них. Эти формулы могут быть непоследовательными, неполными и просто ошибочными: алгоритм машинного обучения и вероятностное рассуждение с этим справятся. Ключевой момент заключается в том, что Alchemy не обязан учиться с нуля. Вообще говоря, мы даже можем приказать алгоритму оставить формулы без изменений и узнавать только веса. В таком случае Alchemy, вооруженный соответствующими формулами, может превратиться в машину Больцмана, байесовскую сеть, обучающийся алгоритм, основанный на случаях, и многие другие модели. Это объясняет, почему, несмотря на теорему «бесплатных обедов не бывает», универсальный обучающийся алгоритм возможен. Alchemy похож скорее на индуктивную машину Тьюринга, которую мы программируем вести себя или как очень мощный, или как очень ограниченный алгоритм — все зависит от нас. Alchemy объединяет машинное обучение так же, как интернет объединяет компьютерные сети, реляционные модели — базы данных, а графический пользовательский интерфейс — бытовые приложения.
Конечно, даже если пользоваться Alchemy без исходных формул (так тоже можно), это не лишит его знаний: допущения о мире неявно закодированы в выборе формального языка, оценивающей функции и оптимизатора. Поэтому естественно будет спросить: можно ли получить еще более обобщенный алгоритм машинного обучения, чем Alchemy? Какое допущение делала эволюция, начиная долгий путь от первой бактерии ко всем формам жизни, которые мы сегодня видим вокруг? Я думаю, простое допущение, из которого вытекает все остальное, таково: обучающийся алгоритм — часть мира. Это значит, что, какой бы он ни был, как физическая система он соблюдает те же законы, что и среда, в которой он находится, и тем самым уже неявно их «знает» и настроен на их открытие. В следующем разделе мы увидим, что это может означать и как воплотить этот принцип в Alchemy. А пока просто заметим, что это, наверное, лучший ответ, который вообще можно дать на вопрос Юма. С одной стороны, предположение, что алгоритм машинного обучения — часть мира, — это допущение: в принципе обучающийся алгоритм может соблюдать и другие законы, не те, которые соблюдает окружающий мир, поэтому это согласуется с мнением Юма, что обучение возможно только на основе предшествующего знания. С другой стороны, это допущение настолько базовое и с ним так сложно спорить, что, наверное, для этого мира его будет достаточно.
Если посмотреть на другой полюс, у инженеров знаний — самых решительных критиков машинного обучения — тоже есть повод полюбить Alchemy. На входе этот алгоритм может иметь не базовую структуру модели и не ряд грубых догадок, а большую, с любовью собранную базу знаний, если таковая у нас есть. Поскольку взаимодействия вероятностных правил гораздо богаче, чем детерминистских, вручную закодированное знание в марковской логике способно на многое, к тому же базы знаний в такой логике не обязаны быть непротиворечивыми и могут быть очень большими и вмещать много разных факторов, не распадаясь на части, — пока решение этой задачи ускользает от инженеров знаний.
Однако прежде всего Alchemy позволяет решить проблемы, над которыми так долго трудились «племена» машинного обучения. Давайте посмотрим на каждую из них по очереди.
Символисты на лету соединяют разные кусочки знания, точно так же как математики соединяют аксиомы, чтобы доказывать теоремы. Это резко контрастирует с нейронными сетями и другими моделями с фиксированной структурой. Alchemy делает это при помощи логики, как символисты, но с изюминкой. Чтобы доказать теорему в логике, надо найти только одну последовательность применения аксиом, которые ее создают. Поскольку Alchemy рассуждает в вероятностных категориях, она способна на большее: найти множественные последовательности формул, ведущие к данной теореме или ее отрицанию, и взвесить их, чтобы вычислить вероятность того, что теорема верна. Таким образом этот алгоритм может рассуждать не просто о математических универсалиях, но и о том, означает ли в новостной статье «президент», что это «Барак Обама», и в какую папку надо отправить электронное письмо. Верховный алгоритм символистов — обратная дедукция — постулирует, что новые логические правила должны служить ступенями между данными и желаемым выводом. Alchemy начинает с исходных правил и путем восхождения на выпуклые поверхности вводит новые правила, которые в сочетании с исходными правилами и данными делают выводы более вероятными.
Коннекционистские модели вдохновлены головным мозгом. Нейронам в них соответствуют сети S-образных кривых, а синапсам — взвешенные соединения между ними. В Alchemy две переменные соединены между собой, если они появляются вместе в какой-то формуле, и вероятность переменной при данных соседях — это сигмоида. (Я не буду объяснять, почему это так, но это прямое следствие верховного уравнения, которое мы видели в предыдущем разделе.) Свой верховный алгоритм — обратное распространение ошибки — коннекционисты используют для того, чтобы определить, какие нейроны отвечают за какие ошибки, и в соответствии с этим подобрать веса. Обратное распространение — это разновидность градиентного спуска, который используется в Alchemy для оптимизации весов логической сети Маркова.
Эволюционисты используют генетические алгоритмы для симуляции естественного отбора. Генетический алгоритм поддерживает популяцию гипотез и в каждом поколении проводит кроссинговер и мутации наиболее приспособленных из них, чтобы породить следующее поколение. Alchemy поддерживает популяцию гипотез в виде взвешенных формул, на каждом этапе по-разному их модифицирует и поддерживает вариации, которые больше всего увеличивают апостериорную вероятность данных (или какую-то другую оценивающую функцию). Если популяция — это одна гипотеза, все сводится к восхождению на выпуклые поверхности. В данный момент доступный для скачивания алгоритм Alchemy не включает кроссинговер, но его несложно добавить. Верховный алгоритм эволюционистов — это генетическое программирование, которое применяет кроссинговер и мутации к компьютерным программам, представленным в виде деревьев подпрограмм. Сами деревья подпрограмм могут быть представлены наборами логических правил, и язык программирования Prolog делает именно это: каждое правило в нем соответствует подпрограмме, а его предшественники — подпрограммам, которые она вызывает. Поэтому можно представить себе Alchemy с кроссинговером как генетическое программирование с использованием похожего на Prolog языка. Дополнительным преимуществом станет то, что правила могут быть вероятностными.
Байесовцы убеждены, что ключ к обучению — моделирование неопределенности, и применяют для этого формальные представления, например байесовские и марковские сети. Как мы уже видели, марковские сети — это особый тип логической сети Маркова, а байесовские сети можно легко представить с помощью основного уравнения логической сети Маркова со свойством для каждого возможного состояния переменной и ее родителей и логарифмом соответствующей условной вероятности в качестве весов. (Нормировочная константа Z удобно сводится к единице, то есть ее можно проигнорировать.) Верховный алгоритм байесовцев — это теорема Байеса, внедренная с помощью алгоритмов вероятностного вывода, например распространения степени уверенности и MCMC. Как вы, может быть, заметили, теорема Байеса — это частный случай верховного уравнения, где P = P(A|B), Z = P(B), а свойства и веса соответствуют P(A) и P(B|A). Система Alchemy включает для логического вывода и распространение степени уверенности, и MCMC, обобщенные, чтобы оперировать взвешенными логическими формулами. Применяя вероятностный вывод к предоставленным логикой линиям доказательств, Alchemy взвешивает аргументы «за» и «против» и выдает вероятность вывода. Это контрастирует с «типовой» логикой «все или ничего», которую применяют символисты и которая не работает, если дать ей противоречивые доказательства.
Аналогизаторы учатся, выдвигая гипотезу, что у объектов со схожими известными качествами неизвестные качества тоже схожи: пациенты с аналогичными симптомами имеют аналогичные диагнозы, читатели, которые купили в прошлом те же самые книги, будут их покупать и в будущем и так далее. Логические сети Маркова могут представлять схожесть между объектами в виде формул, например «Люди с одинаковыми вкусами покупают одинаковые книги». В таком случае чем больше одинаковых книг купили Элис и Боб, тем больше вероятность, что у них одинаковые вкусы, и (применяя ту же самую формулу в противоположном направлении) тем больше вероятность, что Элис купит книгу, если ее купил Боб. Сходство между ними представлено вероятностью совпадения вкусов. Чтобы извлечь из этого настоящую пользу, можно ввести разный вес для частных случаев одного правила: если Элис с Бобом купили одну и ту же редкую книгу, это, вероятно, дает больше информации, чем если бы они купили бестселлер, поэтому вес события будет выше. В данном случае свойства, сходства которых мы вычисляем, дискретны (купил / не купил), но можно представить сходство и между непрерывными характеристиками, например расстоянием между двумя городами, если ввести в логическую сеть Маркова такое сходство в виде свойства. Если функция оценки — не апостериорная вероятность, а похожая на зазор функция присвоения очков, получится обобщение метода опорных векторов, верховного алгоритма аналогизаторов. Более серьезным вызовом для нашего варианта верховного обучающего алгоритма будет воспроизведение отображения структур — мощной разновидности аналогии, способной переносить выводы из одной области (например, Солнечной системы) в другую. Этого можно достичь путем выведения формул, которые не обращаются к конкретным отношениям в исходной области. Например, утверждение «Друзья курильщиков тоже курят» относится к дружбе и курению, а «Связанные объекты имеют схожие свойства» — к любому отношению и свойству. Такие формулы можно получить путем обобщения частных случаев: «Друзья друзей тоже курят», «Коллеги экспертов тоже эксперты» и других таких паттернов в социальной сети, а затем применить полученные формулы, скажем, к сети с частными случаями вроде «Интересные страницы имеют ссылки на интересные страницы» или к молекулярной биологи, где случаями будут «Белки, которые взаимодействуют с регулирующими гены белками, тоже регулируют гены». Ученые в моем и не только моем коллективе сделали все это и многое другое.
Благодаря Alchemy возможны пять типов обучения без учителя, которые мы видели в предыдущей главе. Очевидно, что он способен на реляционное обучение, и пока в большинстве случаев его применяли именно так. Alchemy использует логику для представления отношений между объектами, а сети Маркова — чтобы они могли быть неопределенными. Его можно превратить в обучающийся алгоритм с подкреплением, обернув вокруг него отложенные награды и применяя его для получения значений каждого состояния таким же образом, как в традиционных обучающихся алгоритмах с подкреплением, например нейронных сетях. Мы можем выполнять с помощью Alchemy образование фрагментов, если введем новую операцию, которая будет сжимать цепочки правил в отдельные правила. (Например, «Если A, то B» и «Если B, то C» в «Если A, то С».) Логическая сеть Маркова с одной ненаблюдаемой переменной, соединенной со всеми наблюдаемыми, выполняет кластеризацию. (Ненаблюдаемая переменная — это переменная, значение которой мы никогда не видим в данных. Можно сказать, что она «скрыта» и ее можно только вывести.)
Если в логической сети Маркова более одной ненаблюдаемой переменной, она выполняет своего рода дискретное понижение размерности, делая выводы о значении этих (менее многочисленных) переменных на основе (более многочисленных) наблюдаемых. Alchemy может справиться и с логической сетью Маркова с непрерывными ненаблюдаемыми переменными, которые нужны, например, для анализа главных компонентов и Isomap. Таким образом, Alchemy в принципе может делать все, что мы хотим от Робби, или по меньшей мере все, что мы обсуждали в этой книге. В действительности мы использовали Alchemy, чтобы научить робота картировать среду, определяя по данным из сенсоров, где находятся стены и двери, их углы и расстояния и так далее, а это первый шаг к созданию квалифицированного домашнего робота.
Наконец, Alchemy можно превратить в метаалгоритм наподобие стэкинга, если закодировать индивидуальные классификаторы, как логическая сеть Маркова, и добавить или вывести обучающие формулы, чтобы их соединить. Именно это сделали в DARPA. Проект PAL (Personalized Assistant that Learns) был для них крупнейшим в области искусственного интеллекта и стал предшественником Siri. Целью PAL было создание автоматического секретаря. Марковская логика использовалась в нем как всеобъемлющее представление, соединяя выходы из разных модулей в решения, что делать. Кроме того, это позволяло модулям PAL учиться друг у друга путем эволюции в сторону консенсуса.
На сегодняшний день одним из самых успешных применений Alchemy было создание семантической сети (или графа знаний, как это называют в Google) на основе интернета. Семантическая сеть — набор понятий (например, «планеты» и «звезды») и отношений между этими понятиями (планеты вращаются вокруг звезд). Alchemy вывел из полученных из сети фактов более миллиона таких паттернов (например, то, что Земля вращается вокруг Солнца) и совершенно самостоятельно открыл такие понятия, как «планета». Мы использовали более совершенную версию, чем базовый алгоритм, которую я описываю в этой книге, но важнейшие идеи те же. Различные исследовательские группы применяли Alchemy в своей работе для решения проблем обработки естественных языков, компьютерного зрения, распознавания активности, анализа социальных сетей, а также в молекулярной биологии и многих других областях.
Несмотря на все успехи, у Alchemy есть ряд существенных недостатков. Пока не получается увеличить масштаб алгоритма, чтобы обрабатывать по-настоящему большие данные, и человеку без ученой степени в области машинного обучения пользоваться им будет сложно. Из-за этих проблем его звездный час пока не настал. Поэтому давайте посмотрим, как их устранить.
Машинное обучение в планетарном масштабе
В информатике проблема не решена по-настоящему до тех пор, пока она не решена эффективно. От знания, как что-то сделать, пользы мало, если это невозможно сделать в доступное время и с доступной памятью, а когда вы имеете дело с логическою сетью Маркова, эти ресурсы очень быстро заканчиваются. Мы рутинно учим логическую сеть миллионам переменных и миллиардам свойств, но это не так много, как может показаться, потому что число переменных очень быстро растет вместе с числом объектов в логической сети Маркова: если у вас есть социальная сеть с тысячей членов, это дает миллион возможных пар друзей и миллиард частных случаев формулы «друзья друзей — тоже друзья».
Логический вывод в Alchemy — сочетание логического и вероятностного выводов. Первый реализован путем доказательства теорем, а второй — путем распространения степени уверенности, MCMC и другими методами, которые мы рассматривали в главе 6. Мы соединили и то и другое в вероятностное доказательство теорем, и ключевым элементом системы Alchemy в настоящее время стал единый алгоритм вывода, способный вычислить вероятность любой логической формулы. Однако он может быть очень затратным с точки зрения вычислений. Если бы ваш мозг пользовался вероятностным доказательством теорем, тигр съел бы вас, прежде чем вы сообразили бы, что надо бежать. Это высокая цена за обобщенность марковской логики. Поскольку мозг человека эволюционировал в реальном мире, в нем должны быть закодированы дополнительные допущения, благодаря которым он делает выводы очень эффективно. В последние несколько лет мы начали понимать, какими могут быть эти допущения, и встроили их в Alchemy.
Мир — это не случайное скопление взаимодействий. В нем есть иерархическая структура: галактики, планеты, континенты, государства, города, микрорайоны, ваш дом, вы сами, ваши голова, нос, клетка на кончике носа, органеллы в ней, молекулы, атомы, субатомные частицы. В таком случае для моделирования мира нужна марковская логическая сеть, у которой также будет иерархическая структура. Это один из примеров допущения, что обучающийся алгоритм и среда схожи. Логическая сеть Маркова не должна знать априори, из каких элементов состоит мир. Все, что надо Alchemy, — допустить, что в мире есть элементы, и поискать их, как только что сделанная книжная полка «подразумевает» существование книг, но пока не знает, какие именно будут на ней стоять. Благодаря иерархической структуре выводы становятся возможными, потому что подэлементы мира взаимодействуют главным образом с другими подэлементами одного и того же элемента: соседи чаще разговаривают друг с другом, а не с людьми из других стран; молекулы, созданные в одной клетке, вступают в реакцию в основном с другими молекулами в той же клетке и так далее.
Другое свойство мира, облегчающее обучение и выведение заключений, — то, что объекты в нем не принимают произвольные формы, а делятся на классы и подклассы, и члены одного класса будут более схожи, чем члены разных классов. Живое или неживое, животное или растение, птица или млекопитающее, человек или нет: если знать все отличительные черты, имеющие отношение к рассматриваемому вопросу, можно свалить в одну кучу все объекты, у которых их нет, и сэкономить тем самым уйму времени. Как и ранее, логическая сеть Маркова не обязана знать априори, какие классы существуют в мире. Она может извлечь их из данных путем иерархической кластеризации.
Мир состоит из элементов, а элементы относятся к классам: соединение этих факторов в основном дает нам все, что нужно, чтобы позволить алгоритму Alchemy делать выводы. Мы можем получать имеющиеся в мире логические сети Маркова, разбивая его на элементы и подэлементы так, чтобы взаимодействия в основном происходили между субэлементами одного элемента, а затем будем группировать элементы в классы и подклассы. Если мир — это конструктор лего, его можно разложить на детали, запомнить, как они крепятся, а потом сгруппировать кирпичики по цвету и форме. Если мир — это «Википедия», можно извлечь объекты, о которых она повествует, объединить их в классы и узнать, как эти классы соотносятся друг с другом. Если потом кто-то спросит нас: «Арнольд Шварценеггер — звезда боевиков?» — мы ответим: «Да», потому что он кинозвезда и играет в боевиках. Шаг за шагом мы можем получать все большие логические сети Маркова, пока не дойдем до того, что один мой друг — сотрудник Google — называет «машинным обучением в планетарном масштабе»: моделированием всего в мире сразу, когда данные текут, а ответы вытекают непрерывным потоком.
Конечно, для обучения в таком масштабе нужно намного больше, чем простое внедрение алгоритмов, которые мы уже видели. Во-первых, в какой-то момент одного процессора станет мало: обучение придется распределить по многим серверам. Ученые, работающие в промышленности и в научных учреждениях, интенсивно исследуют, как, например, выполнять градиентный спуск, используя параллельно много компьютеров. Один из вариантов — разделить данные между процессорами, другой — разделить параметры модели. После каждого этапа результаты соединяются и работа перераспределяется. Так или иначе сделать это, не жертвуя качеством и не давая затратам на коммуникацию между процессорами вас задавить, — далеко не тривиальная задача. Другая проблема заключается в том, что, имея бесконечный поток поступающих данных, нельзя определиться с решением, пока не увидишь их целиком. Выйти из такой ситуации помогает, например, принцип выборочного обследования. Если вы хотите предсказать, кто победит на следующих президентских выборах, не обязательно спрашивать каждого избирателя, за кого он собирается голосовать: пробы из нескольких тысяч человек будет достаточно, если вы готовы смириться с некоторой долей неопределенности. Фокус в том, чтобы обобщить этот подход до сложных моделей с миллионами параметров, но это можно сделать, отбирая на каждом этапе ровно столько примеров из каждого потока, сколько нужно. Вы должны быть достаточно уверены в правильности решения и в том, что общая неопределенность по всем решениям остается в разумных пределах. Таким образом можно эффективно учиться на бесконечном количестве данных в конечное время: об этом я писал в одной из первых статей, предлагающих этот подход.
Системы больших данных — это как фильмы Сесила Демилля в машинном обучении: тысячи серверов вместо тысяч статистов. В самых крупных проектах надо собрать вместе все данные, верифицировать их, очистить и привести в приемлемую для обучающегося алгоритма форму — по сравнению с этим строительство пирамид покажется прогулкой в парке. Если говорить о масштабе фараонов, европейский проект FuturICT нацелен на построение модели всего мира — в буквальном смысле. Общества, правительства, культура, технология, сельское хозяйство, заболевания, глобальная экономика — ничего не будет упущено. Такие проекты, конечно, нам пока не по силам, но они предзнаменование того, что нас ждет в будущем, и они могут помочь нам нащупать границы масштабируемости и научиться их преодолевать.
Вычислительная сложность — это один вопрос. Другой — сложность человеческая. Если компьютеры страдают синдромом саванта, то алгоритмы машинного обучения иногда производят впечатление вундеркиндов, подверженных приступам дурного настроения: отчасти поэтому люди, способные заставить их слушаться, так много зарабатывают. Если вы умеете настроить все точно как надо, может произойти волшебство: алгоритм станет умен не по годам и одарит вас потоком идей, хотя процесс в чем-то похож на Дельфийского оракула: интерпретация пророчеств сама по себе может требовать большого мастерства. Но поверните ручку неправильно, и обучающийся алгоритм извергнет лавину бессмыслицы или вообще замкнется в себе. К сожалению, в этом отношении Alchemy не лучше большинства. Записать свои знания на языке логики, заложить данные и нажать кнопку — это здорово. Когда Alchemy выдает великолепно точные и эффективные логические сети Маркова — можно пойти в паб и отпраздновать успех. Но когда этого не происходит — а так бывает большую часть времени, — начинается битва. В чем проблема? В знаниях? В обучении? В выводе? С одной стороны, благодаря обучению и вероятностному выводу простая логическая сеть Маркова может выполнить работу сложной программы. С другой стороны, когда она не работает, ее намного сложнее отладить. Решение — сделать ее более интерактивной, способной к самоанализу и объяснению хода своих рассуждений. Это станет для нас еще одним шагом к Верховному алгоритму.
Сейчас вас примет доктор
Лекарство от рака — программа, которая на входе получает геном раковой опухоли, а на выходе дает лекарство, с помощью которого можно эту опухоль уничтожить. Теперь мы можем в общих чертах описать, как она будет выглядеть. Давайте назовем ее CanceRx. Несмотря на внешнюю простоту, эта программа станет одним из крупнейших и самых сложных проектов в истории: она так велика и сложна, что построить ее можно только с помощью машинного обучения. В ее основе — подробная модель работы живых клеток с подклассами для всех типов клеток человеческого организма и обобщающей моделью их взаимодействия. Эта модель в виде марковской логической сети или чего-то схожего соединит в себе знания из области молекулярной биологии с большим объемом данных из секвенсоров ДНК, микрочипов и многих других источников. Часть знания будет заложена вручную, но большая часть автоматически извлечена из литературы по биологии и медицине. Модель будет постоянно развиваться, включать в себя все новые результаты экспериментов, источники данных и истории болезни. В конце концов она узнает каждый метаболический путь, каждый регуляторный механизм, все химические реакции во всех типах человеческих клеток. Будет получена сумма знаний о молекулярной биологии человека.