Алгоритмы векторного поиска: IVF и HNSW

В сфере искусственного интеллекта произошло заметное событие. metarock 13 минут назад Алгоритмы векторного поиска: IVF и HNSW Сложный 17 мин 397 Базы данных * Искусственный интеллект Алгоритмы * Машинное обучение * Python * Обзор Из песочницы О чем эта статья? В данной статье я хочу пройтись по двум самым популярным алгоритмам векторного поиска, используемым на практике. Попробуем понять, почему точный поиск не работает в высоких размерностях и почему мы в итоге приходим к приближенному поиску.

Заодно мы затронем тему метрик, чтобы понять, как вообще сравнивают эмбеддинги. Рассмотрим вспомогательный и очень простой алгоритм k-means из классического ML’а, лежащий в основе IVF. И наконец, подробно разберем два самых главных алгоритма IVF и HNSW с примерами их реализации на Python’е.

Технические детали

Curse of DimensionalityВведениеДля начала нам нужно понять, почему мы не можем просто взять и воспользоваться каким-нибудь стандартным алгоритмом вроде kd-tree для точного поиска и почему мы в итоге приходим к приближенному поиску. Оказывается, все дело в штуке, которая называется проклятием размерности (curse of dimensionality). С ростом числа измерений пространство растет экспоненциально в том смысле, что для сохранения той же плотности точек требуется экспоненциально больше данных.

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

Это явление называется concentration of distances. ИнтуицияПредставим, что у нас постепенно растет число измерений:1D - мы заполняем точками одну прямую2D - мы заполняем точками квадрат3D - мы заполняем точками кубВ общем случае, в d-мерном пространстве, у нас гиперкуб. С увеличением размерности нам нужно все больше и больше точек для заполнения этого пространства.

Отраслевые последствия

К каким проблемам это приводит? Данные становятся сильно разреженными, то есть, большая часть пространства остается пустой. Это усложняет задачи кластеризации, классификации и поиска.

Increased computation. Большее число измерений требует больше вычислений и времени на обработку данных. Модели могут начинать подстраиваться под шум в данных, а не под реальную закономерность.

Это снижает способность модели обобщать результаты на новые данные. Distances lose meaning. Различия между расстояниями точек данных становятся незначительными, из-за чего такие метрики, как евклидово расстояние, теряют информативность.

Этот прогресс даёт важные сигналы о будущем отрасли, и технологический мир внимательно наблюдает.