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

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

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

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

Точки на этой линии находятся на одинаковом удалении от обоих столиц. Точки слева от нее ближе к Позитивску, поэтому ближайший сосед предполагает, что они относятся к Позистану, и наоборот. Конечно, если бы это была точная граница, нам бы крупно повезло, но и это приближение, вероятно, намного лучше, чем ничего. Однако по-настоящему интересно становится, когда мы знаем много городов по обеим сторонам границы:

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

Все дело в том, что построить глобальную модель, например дерево решений, намного сложнее, чем просто одно за другим определить положение конкретных элементов запроса. Представьте себе попытку определить с помощью дерева решений, что такое лицо. Можно было бы сказать, что у лица два глаза, нос и рот, но что такое глаз и как его найти на изображении? А если человек закроет глаза? Дать надежное определение лица вплоть до отдельных пикселей крайне сложно, особенно учитывая всевозможные выражения, позы, контекст, условия освещения. Алгоритм ближайшего соседа этого не делает и срезает путь: если в базе данных изображение, больше всего похожее на то, которое загрузила Джейн, — это лицо, значит на загруженном изображении тоже лицо. Чтобы все работало, в базе данных должна найтись достаточно похожая картинка, например лицо в аналогичном положении, освещении и так далее, поэтому чем больше база данных, тем лучше. Для простой двухмерной проблемы, например угадывания границы между двумя странами, маленькой базы данных будет достаточно. Для очень сложной проблемы, например определения лиц, где цвет каждого пикселя — это измерение вариативности, понадобится огромная база данных. Сегодня такие базы существуют. Обучение с их помощью может быть слишком затратным для трудолюбивых алгоритмов, которые явно проводят границу между лицами и не-лицами, однако для ближайшего соседа граница уже скрыта в расположении точек данных и расстояниях, и единственная затрата — это время запроса.

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

Как поведал Стивен Джонсон в книге The Ghost Map, алгоритм ближайшего соседа может спасать жизни. В 1854 году Лондон поразила вспышка холеры. В некоторых частях города от нее умер каждый восьмой житель. Господствовавшая тогда теория, что холера вызвана якобы плохим воздухом, не помогла предотвратить распространение эпидемии. Но Джон Сноу, физик, скептически относившийся к этой теории, придумал кое-что получше. Он отметил на карте Лондона все известные случаи холеры и разделил карту на области, расположенные ближе всего к общественным водокачкам. Эврика! Оказалось, что почти все смерти приходились на «агломерацию» конкретного водозабора, расположенного на Брод-стрит в районе Сохо. Сделав вывод, что вода там заражена, Сноу убедил местные власти выключить насос, и эпидемия сошла на нет. Из этого случая родилась эпидемиология, а еще это пример первого успешного применения алгоритма ближайшего соседа — почти за столетие до его официального открытия.

В алгоритме ближайшего соседа каждая точка данных — это маленький классификатор, предсказывающий класс для всех примеров запросов, на которые она правильно отвечает. Это как армия муравьев: отдельные солдаты сами по себе делают немного, но вместе способны сдвигать горы. Если груз слишком тяжел для одного муравья, он зовет соседей. Метод k-ближайших соседей действует в том же духе: тестовый пример классифицируется путем нахождения k-ближайших соседей, которые после этого голосуют. Если ближайшее изображение к только что загруженному — это лицо, но следующие два ближайших — нет, третий ближайший сосед решает, что загруженная картинка все же не лицо. Алгоритм ближайшего соседа подвержен переобучению: если точке данных присвоен неправильный класс, он распространится на всю свою агломерацию. Алгоритм k-ближайших соседей более устойчив, потому что ошибается только тогда, когда большинство из k-ближайших соседей зашумлены. Но за это приходится платить более замутненным зрением: из-за голосования размываются мелкие детали границы. Когда k идет вверх, дисперсия уменьшается, но увеличивается смещенность.

Брать k-ближайших соседей вместо одного — это еще не все. Интуиция подсказывает, что примеры, ближе всего расположенные к тестовому, должны быть важнее. Это ведет нас к взвешенному алгоритму k-ближайших соседей. В 1994 году группа ученых из Миннесотского университета и Массачусетского технологического института построила рекомендательную систему на основе, по их словам, «обманчиво простой идеи»: люди, которые соглашались на что-то в прошлом, с большей вероятностью согласятся на это и в будущем. Эта мысль вела прямиком к системам коллаборативной фильтрации, которые имеются на всех уважающих себя сайтах электронной торговли. Представьте, что вы, как Netflix, собрали базу данных, где каждый пользователь присваивает просмотренным фильмам рейтинг от одной до пяти звезд. Вы хотите определить, понравится ли вашему пользователю по имени Кен фильм «Гравитация», поэтому ищете пользователей, оценки которых лучше всего коррелируют с оценками Кена. Если все они присвоили «Гравитации» высокий рейтинг, вероятно, так поступит и Кен, и этот фильм можно ему посоветовать. Если, однако, у них нет единого мнения в отношении «Гравитации», все равно нужно как-то выйти из положения, и в данном случае пригодится список пользователей, упорядоченный по их корреляции с Кеном. Если Ли коррелирует с Кеном сильнее, чем Мег, его оценки должны считаться, соответственно, более важными. Спрогнозированная оценка Кена будет таким образом средней взвешенной оценок его соседей, где вес каждого соседа — это его коэффициент корреляции с Кеном.

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

Кстати говоря, для коллаборативной фильтрации явные оценки не обязательны. Если Кен заказал фильм на Netflix, это значит, что он ожидает, что фильм ему понравится. Так что «оценкой» может быть просто «заказал / не заказал», и два пользователя будут похожи, если они заказывают много одинаковых фильмов. Даже простой клик на что-то косвенно показывает интерес пользователя. Алгоритм ближайшего соседа работает во всех этих случаях. Сегодня для того, чтобы давать рекомендации посетителям сайта, используются все виды алгоритмов, но взвешенный k-ближайший сосед был первым, нашедшим широкое применение в этой области, и его до сих пор сложно победить.

Рекомендательные системы — это большой бизнес: Amazon они дают треть доходов, а Netflix — три четверти. А ведь когда-то метод ближайшего соседа считался непрактичным из-за высоких требований к памяти. В те времена память компьютеров делали из маленьких сердечников, напоминавших железные кольца, по одному для каждого бита, и хранение даже нескольких тысяч примеров было обременительно. Сейчас времена изменились. Тем не менее не всегда целесообразно запоминать все увиденные примеры, а затем искать среди них, особенно потому что большинство из них, вероятно, не имеют отношения к делу. Еще раз взгляните на карту Позистана и Негативии и обратите внимание, что, если Позитивск исчезнет, граница с Негативией не изменится: агломерации близлежащих городов расширятся и займут земли, которые занимала столица, но все они позистанские. Города, которые имеют значение, располагаются исключительно вдоль границы, поэтому все остальные можно опустить. Из этого вытекает простой способ повысить эффективность метода ближайшего соседа: нужно удалить примеры, которые были правильно классифицированы их соседями. Благодаря этому и другим приемам методы ближайшего соседа находят применение в самых неожиданных областях, например в управлении манипулятором робота в реальном времени. Но при этом в таких областях, как высокочастотный трейдинг, где компьютеры покупают и продают ценные бумаги в доли секунды, такие методы по-прежнему не в почете. В гонке между нейронными сетями, которые можно применять к примерам с фиксированным количеством сложений, умножений и сигмоид, и алгоритмом, который должен искать ближайшего соседа в большой базе данных, нейронная сеть обязательно победит.

Другая причина, по которой исследователи поначалу скептически относились к ближайшему соседу, заключается в том, что было непонятно, может ли он определять истинные границы между понятиями. Но в 1967 году ученые-информатики Том Кавер и Питер Харт доказали, что при наличии достаточного количества данных ближайший сосед в худшем случае подвержен ошибкам всего в два раза больше, чем лучший вообразимый классификатор. Если, скажем, как минимум один процент тестовых примеров неизбежно будет неправильно классифицирован из-за зашумленности данных, ближайший сосед гарантированно получит максимум два процента ошибок. Это было историческое открытие. До этого момента все известные классификаторы исходили из того, что граница имеет очень четкую форму, обычно прямую линию. Это давало и плюсы, и минусы: с одной стороны, можно было доказать правильность, как в случае с перцептроном, но при этом появлялись строгие ограничения на то, что такой классификатор может узнать. Метод ближайшего соседа был первым в истории алгоритмом, который мог воспользоваться преимуществом неограниченного количества данных, чтобы обучаться произвольно сложным понятиям. Человеку не под силу проследить границы, которые он образует в гиперпространстве из миллионов примеров, но благодаря доказательству Кавера и Харта мы знаем, что они, вероятно, недалеки от истины. Рэй Курцвейл считает, что сингулярность начинается, когда люди перестают понимать, что делают компьютеры. По этому стандарту не совсем преувеличением будет сказать, что это уже происходит и началось еще в 1951 году, когда Фикс и Ходжес изобрели метод ближайшего соседа — самый маленький алгоритм, какой только можно изобрести.