источник картинки)
Сложность метода по размеру обучающей выборки в среднем равна $O(\log N)$ при равномерном распределении точек. При большой размерности пространства, однако, алгоритму приходится посещать больше ветвей дерева, чтобы найти ближайших соседей. Например, если $N \approx D$, то сложность становится примерно такой же, как и в случае полного перебора. В общем случае считается, что для того чтобы асимптотика действительно была логарифмической, нужно, чтобы $N \gtrsim 2^D$. Поэтому уже при количестве признаков порядка сотни алгоритм не даёт существенных преимуществ перед полным перебором.
Почти всегда находить именно самых близких соседей необязательно. Например, в задаче подбора рекомендаций фильмов пользователю чаще всего не нужны наиболее похожие картины, достаточно, к примеру, 10 из 15 наиболее близких. Поэтому, чтобы ускорить процесс поиска соседей, используют приближённые методы. Разберём основные идеи, которые применяются в таких методах.
Алгоритмы, основанные на деревьях, очень часто применяются в задачах поиска соседей. Идея всех таких методов заключается в итеративном разделении пространства случайными гиперплоскостями и построении на базе этого разделения дерева, в листах которого содержится малое число объектов.
Одним из наиболее ярких представителей этого семейства является Annoy — алгоритм, который используется Spotify для рекомендаций музыки. Задача подобных рекомендательных систем довольно простая — нужно посоветовать пользователю композиции, которые он ещё не слушал, но которые при этом с высокой вероятностью ему понравятся. Простая и рабочая идея — предлагать композиции, похожие на те, которые он уже слушает. Здесь на помощь как раз и приходят методы поиска ближайших соседей.
Annoy в какой-то степени похож на k-d-деревья. Сначала выбираются два случайных объекта обучающей выборки и проводится гиперплоскость, симметрично их разделяющая. Затем для каждого полученного полупространства итеративно запускается такая же процедура, которая продолжается до тех пор, пока в каждой области будет не более $M$ объектов ($M$ — гиперпараметр).
Таким образом задаётся бинарное дерево с глубиной порядка $O(\log N)$ в среднем.
Спускаясь по этому дереву, можно найти область, в которой лежит целевой объект и некоторое количество близких к нему элементов обучающей выборки. Проблема в том, что это не обязательно будут самые близкие объекты, поэтому для увеличения точности составляется лес из таких деревьев и берётся объединение соответствующих целевому объекту областей.
Чем больше таких деревьев берётся, тем более точным будет результат, но придётся тратить большее время на его поиск.
Преимуществом алгоритма является простота нахождения компромисса между скоростью работы и точностью с помощью тюнинга гиперпараметров. К минусам можно отнести то, что алгоритм плохо параллелится и переносится на GPU, не работает эффективно с батчами, а также то, что для добавления новой точки в обучающую выборку придётся перезапускать процедуру с самого начала.
Предположим, что мы можем построить такую хеш-функцию, которая переводит близкие объекты в один бакет. Тогда близких соседей целевого объекта можно найти, посчитав его хеш и посмотрев на коллизии. Оказывается, такие хеш-функции существуют, и на этой идее основано несколько алгоритмов, которые объединяются названием Locality-sensitive hashing (LSH). К этому классу алгоритмов относится, например, FAISS, используемый Facebook.
Определим формально семейство хеш-функций, которое мы хотим использовать. Нам нужно, чтобы вероятность коллизии на близких объектах была высокая, а на далёких — низкая. Назовём семейство хеш-функций $\mathcal{H}$ $(R, cR, p_1, p_2)$-чувствительным, если для любой $h(x)\in\mathcal{H}$:
Формулы могут выглядеть сложными, но это всего лишь формализация нашей интуиции. Картинка ниже поясняет определение: для близких красных объектов в шаре радиусом $R$ вероятность коллизии больше $p_1$, для далёких синих объектов на расстоянии больше $cR$ вероятность коллизии меньше $p_2$, а про серые объекты в слое между $R$ и $cR$ мы ничего не знаем.
Для каждой функции расстояния, используемой в задаче, существует своё подходящее семейство хеш-функций. Например, для евклидовой и манхэттенской метрик используются случайные проекции, где хеш-функция имеет следующий вид:
$$ h_{\boldsymbol{w}, b}(\boldsymbol{x}) = \left\lfloor \frac{\boldsymbol{w}^T\boldsymbol{x} + b}{r}\right\rfloor, $$
где $\boldsymbol{w}$ и $b$ — случайные параметры, а $r$ выбирается пользователем. $b$ выбирается равномерно из отрезка $[0, r]$, а $\boldsymbol{w}$ генерируется либо из нормального распределения, что соответствует евклидовой метрике, либо из распределения Коши — для манхэттенской метрики.
По сути, такая функция разбивает всё пространство на слои в направлении вектора $\boldsymbol{w}$. Параметр $r$ при этом задаёт ширину слоя.
На практике при использовании лишь одной хеш-функции разница между $p_1$ и $p_2$ оказывается очень маленькой, поэтому применяют различные методы для её увеличения. Первый способ — уменьшать размер бакетов в хеш-таблице путём использования композиции разных хеш-функций из одного семейства $g(x) = (h_1(x),\ldots,h_m(x))$. Преимущество этого способа как раз хорошо видно на примере случайных проекций. При использовании лишь одной хеш-функции бакетами являются слои бесконечного объёма. Однако при использовании композиции размером, как минимум равным количеству признаков $D$, из-за случайности выбора вектора $\boldsymbol{w}$ бакеты почти наверное станут замкнутыми фигурами с конечным объёмом. Второй способ повышения эффективности алгоритма — использовать несколько хеш-таблиц и искать соседей среди коллизий в каждой из них. На практике используют оба метода сразу, подбирая $m$ и $L$ — количество хеш-таблиц как гиперпараметры.
К плюсам алгоритма можно отнести хорошие теоретические гарантии на сублинейное время и, как и в Annoy, простой поиск трейд-оффа между точностью и скоростью работы. Минусами можно назвать высокую потребность в памяти, плохую адаптируемость под GPU, а также тот факт, что, несмотря на теоретические гарантии в среднем, на практике алгоритм может работать даже чуть дольше полного перебора из-за того, что, помимо самого поиска, требуется искать хеши объектов.
Следующий класс алгоритмов основан на построении специального графа близости (proximity graph) на объектах выборки и дальнейшем жадном поиске по этому графу. Алгоритмы этого семейства сейчас считаются state-of-the-art (SotA) для многих задач.
Рассмотрим подробнее этот класс алгоритмов на примере одного из наиболее популярных из них под названием Navigable small world (NSW). Идея его в следующем: на данных строится граф (он также называется NSW), который удовлетворяет двум следующим свойствам:
Между любыми двумя точками существует короткий путь, или, более формально, матожидание числа кратчайшего пути между двумя случайно выбранными вершинами растёт как $O(\log N)$.
Средняя степень вершины мала.
На первый взгляд может показаться, что тяжело выполнить одновременно оба свойства, но на самом деле большая часть графов в реальном мире являются NSW-графами. Самый простой пример — это известное правило шести рукопожатий: любые два случайных человека соединены короткой последовательностью личных контактов длиной не более шести, несмотря на то, что количество знакомых у среднего человека ($100$–$1000$) мало по сравнению с населением Земли.
В таких графах существует очень простой метод поиска соседей. Нужно выбрать случайную точку, среди её соседей выбрать того, который ближе всего к целевому объекту, и повторить процедуру уже для него. Показано, что такой жадный поиск имеет полилогарифмическую асимптотику.
Проблема такого подхода в том, что можно попасть в плотный кластер и очень долго оттуда выбираться. Для решения этой проблемы используется иерархия NSW, или Hierarchical navigable small world (HNSW). Исходный граф является нулевым слоем. Каждый следующий слой строится в два шага:
По построению количество слоёв будет $O(\log N)$.
Поиск начинается в самом верхнем слое. После нахождения ближайшей к целевому объекту вершины спускаемся на слой ниже и начинаем поиск из этой вершины. Повторяем процедуру, пока не спустимся до нулевого слоя. Таким образом, на каждом слое мы всё больше уточняем наш ответ. Стоит отметить, что для ускорения работы иногда поиск останавливают не при нахождении ближайшей вершины, а раньше, используя критерии остановки.
Интуитивно легко понять, почему такая иерархическая структура решает проблему плотных кластеров: в верхних слоях вершин мало, а расстояния между ними в среднем большие, а значит, таких кластеров там почти нет. Поэтому, попадая в нижний слой, мы чаще всего оказываемся уже в нужном кластере и просто уточняем результат работы алгоритма.
HNSW, так же как и рассмотренные ранее приближённые методы, позволяет искать трейд-офф между точностью и скоростью работы. Плюс ко всему на реальных данных он часто работает лучше других методов и сейчас считается SotA. Однако этот способ поиска не лишён и недостатков. Главный заключается в том, что нельзя добавлять точки в обучающую выборку без перестройки структуры. Помимо этого, он довольно требователен по памяти из-за того, что для каждого слоя приходится хранить как вершины, которые в него входят, так и связи между этими вершинами.
В завершение стоит сказать, что не существует универсального метода поиска соседей — каждый из описанных методов может быть лучше других в определённой задаче. К тому же, несмотря на то что приближённые методы имеют лучшую асимптотику, многие из них плохо переносятся на GPU. Из-за этого на практике полный перебор бывает быстрее любого из таких приближённых методов.