Запрети мне псевдолейблить

Что за HNSW такой?

Базовый подход, на котором работает Qdrant, — это HNSW (Hierarchical Navigable Small World). Давайте разберёмся, что это такое и как оно работает.

Small world graphs — это такие графы, которые характеризуются высоким коэффициентом кластеризации и малым расстоянием между любой парой вершин. Navigable Small World использует эти свойства для поиска ближайших соседей в многомерном пространстве. Представим, что мы строим такую структуру на наших эмбеддингах, чтобы перемещаться по ней было эффективно. Как добиться этой эффективности?

Начинаем с эмбеддинга случайного объекта из нашей базы и шагаем по рёбрам графа в сторону эмбеддинга-запроса, пока не сойдёмся к локальному минимуму. Для каждой пары эмбедингов мы можем посчитать расстояние, так что идти в сторону ближайшего к эмбедингу-запросу вполне себе можем на каждом шаге. Если бы мы связали ребрами все эмбеддинги, каждый с каждым, то минимальное расстояние находилось бы за один шаг, но пришлось бы просмотреть n дистанций. Если связать все эмбеддинги в двусвязный список, то на каждом шаге будет выполняться только одно сравнение, но шагов придётся сделать столько, сколько у нас точек, что тоже не очень эффективно. Зато уже n/2 в среднем! Как найти баланс? Никак, надо тестить на каждой новой базе

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

1. Посчитаем расстояние от каждого объекта до каждого.
2. Возьмём случайный объект из базы и проверим, есть ли он в нашем графе поиска. Если есть — пропускаем. В первом прогоне его, конечно, там нет, но дальше цикл будет работать.
3. Возьмём X процентов ближайших объектов к целевому и построим между ними рёбра.
4. Сделаем то же самое с Y процентами самых дальних объектов.
5. Повторяем с пункта 2, пока не добавим в граф все объекты из базы.

Теперь на первых шагах мы будем часто пользоваться длинным ребрами, и в конце искать оптимум за счет коротких.
Да, в редких случаях (скажем, в 1% случаев) мы не найдём самого ближайшего соседа, но зато будем работать гораздо быстрее — скажем, в 12 раз. Конечно, всё сильно зависит от реализации, но ускорение впечатляет.

Вот и получается, что HNSW позволяет балансировать между количеством шагов и сравнений, что делает его отличным выбором для поиска ближайших соседей в больших базах данных.

А еще HNSW- в русской раскладке это РТЫЦ. Живите с этим

www.group-telegram.com/ua/pseudolabeling.com/163

2.4K viewsedited  Aug 16, 2024 at 09:01

Что за HNSW такой?

Базовый подход, на котором работает Qdrant, — это HNSW (Hierarchical Navigable Small World). Давайте разберёмся, что это такое и как оно работает.

Small world graphs — это такие графы, которые характеризуются высоким коэффициентом кластеризации и малым расстоянием между любой парой вершин. Navigable Small World использует эти свойства для поиска ближайших соседей в многомерном пространстве. Представим, что мы строим такую структуру на наших эмбеддингах, чтобы перемещаться по ней было эффективно. Как добиться этой эффективности?

Начинаем с эмбеддинга случайного объекта из нашей базы и шагаем по рёбрам графа в сторону эмбеддинга-запроса, пока не сойдёмся к локальному минимуму. Для каждой пары эмбедингов мы можем посчитать расстояние, так что идти в сторону ближайшего к эмбедингу-запросу вполне себе можем на каждом шаге. Если бы мы связали ребрами все эмбеддинги, каждый с каждым, то минимальное расстояние находилось бы за один шаг, но пришлось бы просмотреть n дистанций. Если связать все эмбеддинги в двусвязный список, то на каждом шаге будет выполняться только одно сравнение, но шагов придётся сделать столько, сколько у нас точек, что тоже не очень эффективно. Зато уже n/2 в среднем! Как найти баланс? Никак, надо тестить на каждой новой базе

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

1. Посчитаем расстояние от каждого объекта до каждого.
2. Возьмём случайный объект из базы и проверим, есть ли он в нашем графе поиска. Если есть — пропускаем. В первом прогоне его, конечно, там нет, но дальше цикл будет работать.
3. Возьмём X процентов ближайших объектов к целевому и построим между ними рёбра.
4. Сделаем то же самое с Y процентами самых дальних объектов.
5. Повторяем с пункта 2, пока не добавим в граф все объекты из базы.

Теперь на первых шагах мы будем часто пользоваться длинным ребрами, и в конце искать оптимум за счет коротких.
Да, в редких случаях (скажем, в 1% случаев) мы не найдём самого ближайшего соседа, но зато будем работать гораздо быстрее — скажем, в 12 раз. Конечно, всё сильно зависит от реализации, но ускорение впечатляет.

Вот и получается, что HNSW позволяет балансировать между количеством шагов и сравнений, что делает его отличным выбором для поиска ближайших соседей в больших базах данных.

А еще HNSW- в русской раскладке это РТЫЦ. Живите с этим

BY Запрети мне псевдолейблить