Читаем без скачивания Верховный алгоритм - Педро Домингос

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

Представьте, что вместо карты Пало-Альто у нас есть GPS-координаты важнейших городов всей Области залива Сан-Франциско:

Глядя на эту схему, можно, вероятно, сделать предположение, что города расположены на берегу залива и, если провести через них линию, положение каждого города можно определить всего одним числом: как далеко он находится от Сан-Франциско по этой линии. Но метод главных компонент такую кривую найти не может: он нарисует прямую линию через центр залива, где городов вообще нет, а это только затуманит, а не прояснит форму данных.

Теперь представьте на секунду, что мы собираемся создать Область залива с нуля. Бюджет позволяет построить единую дорогу, чтобы соеди­нить все города, и нам решать, как она будет проложена. Естественно, мы проложим дорогу, ведущую из Сан-Франциско в Сан-Бруно, оттуда в Сан-Матео и так далее, вплоть до Окленда. Такая дорога будет довольно хорошим одномерным представлением Области залива, и ее можно найти простым алгоритмом: «построй дорогу между каждой парой близлежащих городов». Конечно, у нас получится целая сеть дорог, а не одна, проходящая рядом с каждым городом, но можно получить и одну дорогу, если сделать ее наилучшим приближением сети, в том смысле, что расстояния между городами по этой дороге будут как можно ближе расстоянию вдоль сети.

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

Вот интересный эксперимент. Возьмите потоковое видео из глаз Робби, представьте, что каждый кадр — точка в пространстве изобра­жений, а потом сведите этот набор изображений к единственному измерению. Какое это будет измерение? Время. Как библиотекарь расставляет книги на полке, время ставит каждое изображение рядом с самыми похожими. Наверное, наше восприятие времени — просто естественный результат замечательной способности головного мозга понижать размерность. В дорожной сети нашей памяти время — главная автострада, и мы ее быстро находим. Другими словами, время — главная компонента памяти.

Жизнелюбивый робот

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

У людей действительно есть один постоянный ориентир: эмоции. Мы стремимся к удовольствиям и избегаем боли. Коснувшись горячей плиты, вы непроизвольно отдернете руку. Это просто. Сложнее научиться не трогать плиту: для этого нужно двигаться так, чтобы избежать острой боли, которую вы еще не почувствовали. Головной мозг делает это, ассоциируя боль не просто с моментом прикосновения к плите, но и с ведущими к этому действиями. Эдвард Торндайк101 назвал это законом эффекта: действия, которые ведут к удовольствию, станут с большей вероятностью повторяться в будущем, а ведущие к боли — с меньшей. Удовольствие как будто путешествует назад во времени, и действия в конце концов могут начать ассоциироваться с довольно отдаленными результатами. Люди освоили такой поиск косвенных наград лучше, чем любое животное, и этот навык критически важен для успеха в жизни. В знаменитом эксперименте детям давали зефир и говорили, что, если они выдержат несколько минут и не съедят его, им дадут целых два. Те, кому это удалось, лучше успевали в школе и позже, когда стали взрослыми. Менее очевидно, наверное, то, что с аналогичной проблемой сталкиваются компании, использующие машинное обучение для совершенствования своих сайтов и методов ведения бизнеса. Компания может принять меры, которые принесут ей больше денег в краткосрочной перспективе — например, начать по той же цене продавать продукцию худшего качества, — но не обратить внимания, что в долгосрочной перспективе это приведет к потере клиентов.

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

Это обучение с подкреплением, и этот принцип, скорее всего, станет активно использовать ваш первый домашний робот. Если вы распакуете Робби, включите его и попросите приготовить яичницу с беконом, у него с ходу может не получиться. Но когда вы уйдете на работу, он изучит кухню, отметит, где лежит утварь, какая у вас плита. Когда вы вернетесь, ужин будет готов.

Важным предшественником обучения с подкреплением была программа для игры в шашки, созданная ученым Артуром Сэмюэлом, работавшим в 1950-х годах в IBM. Настольные игры — прекрасный пример проблемы обучения с подкреплением: надо построить длинную последовательность ходов без какой-то обратной связи, а награда или наказание — победа или поражение — ждет в самом конце. Программа Сэмюэла оказалась способна научиться играть так не хуже большинства людей. Она не искала напрямую, какой ход сделать при каждом положении на доске (это было бы слишком сложно), а скорее училась оценивать сами положения — какова вероятность выигрыша, если начать с этой позиции? — и выбирать ходы, ведущие к наилучшему положению. Поначалу программа умела оценивать только конечные позиции: победа, ничья и поражение. Но раз определенные позиции означают победу, значит, позиции, из которых можно к ней прийти, хорошие. Томас Уотсон-старший, президент IBM, предсказал, что после презентации программы акции корпорации поднимутся на 15 пунктов. Так и произошло. Урок был усвоен, IBM развила успех и создала чемпионов по игре в шахматы и Jeopardy!.

Мысль, что не все состояния ведут к награде (положительной или отрицательной), но у каждого состояния имеется ценность, — центральный пункт обучения с подкреплением. В настольных играх награды есть только у конечных позиций (например, 1, 0 и –1 для победы, ничьей и поражения). Другие позиции не дают немедленной награды, но их ценность в том, что они могут обеспечить награду в будущем. Позиция в шахматах, из которой можно поставить мат в определенное количество ходов, практически так же хороша, как сама победа, и потому имеет высокую ценность. Такого рода рассуждения можно распространить вплоть до хороших и плохих дебютов, даже если на таком расстоянии от цели связь с наградой далеко не очевидна. В компьютерных играх награды обычно выражаются в очках, и ценность состояния — это количество очков, которые можно накопить, начиная с этого состояния. В реальной жизни отдача с задержкой менее выгодна, чем немедленная отдача, поэтому ее можно уменьшать на определенный процент, как это делается в случае инвестиций. Естественно, награда зависит от того, какие действия вы выберете, и цель обучения с подкреплением — всегда выбирать действие, ведущее к наибольшей награде. Стоит ли снять трубку и пригласить знакомую на свидание? Это может и положить начало чудесному роману, и привести к болезненному разочарованию. А если ваша подруга согласится на свидание, оно может пойти как удачно, так и неудачно. Надо каким-то образом абстрагироваться от бесконечных вариантов развития событий и принять решение. Обучение с подкреплением делает это путем оценки ценности каждого состояния — общей суммы наград, которых можно ожидать, начиная с него, — и выбора действий, которые ее максимизируют.