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

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

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

Самое неожиданное свойство метода опорных векторов заключается в следующем: какие бы изогнутые границы он ни проводил, эти границы всегда будут прямыми линиями (или гиперплоскостями). В этом нет противоречия. Причина заключается в том, что прямые линии будут находиться в другом пространстве. Допустим, примеры живут на плос­кости (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» и послушайте.

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