Начало работы с HNSWlib
Семантический поиск позволяет машинам понимать язык и выдавать лучшие результаты поиска, что очень важно для ИИ и аналитики данных. После того как язык представлен в виде вкраплений, поиск может осуществляться с помощью точных или приближенных методов. Приблизительный поиск ближайших соседей(ANN) - это метод, используемый для быстрого поиска точек в наборе данных, которые наиболее близки к заданной точке запроса, в отличие от точного поиска ближайших соседей, который может быть вычислительно дорогим для высокоразмерных данных. ANN позволяет ускорить поиск, предоставляя результаты, которые приблизительно близки к ближайшим соседям.
Одним из алгоритмов поиска приближенных ближайших соседей (ANN) является HNSW (Hierarchical Navigable Small Worlds), реализованный в HNSWlib, который и будет предметом сегодняшнего обсуждения. В этом блоге мы:
Поймем алгоритм HNSW.
Изучим HNSWlib и его ключевые особенности.
Настроим HNSWlib, рассмотрим построение индекса и реализацию поиска.
Сравним его с Milvus.
Понимание HNSW
Hierarchical Navigable Small Worlds (HNSW) - это структура данных на основе графов, которая позволяет эффективно искать сходство, особенно в высокоразмерных пространствах, путем построения многослойного графа сетей "малых миров". Представленная в 2016 году, HNSW решает проблемы масштабируемости, связанные с традиционными методами поиска, такими как перебор и поиск на основе деревьев. Он идеально подходит для приложений с большими массивами данных, таких как рекомендательные системы, распознавание образов и поиск с расширением (RAG).
Почему HNSW имеет значение
HNSW значительно повышает производительность поиска ближайших соседей в высокоразмерных пространствах. Сочетание иерархической структуры с возможностью навигации по малому миру позволяет избежать вычислительной неэффективности старых методов, обеспечивая высокую производительность даже при работе с массивными и сложными наборами данных. Чтобы лучше понять это, давайте посмотрим, как это работает сейчас.
Принцип работы HNSW
Иерархические слои: HNSW организует данные в иерархию слоев, где каждый слой содержит узлы, соединенные ребрами. Верхние слои более разреженные, что позволяет делать широкие "проходы" по графу, подобно тому, как при уменьшении масштаба карты можно увидеть только основные магистрали между городами. Плотность нижних слоев увеличивается, обеспечивая более тонкую детализацию и больше связей между ближайшими соседями.
Концепция навигационных малых миров: Каждый слой в HNSW основан на концепции сети "малого мира", где узлы (точки данных) находятся на расстоянии всего нескольких "хопов" друг от друга. Алгоритм поиска начинает с самого верхнего, самого редкого слоя и работает вниз, переходя к все более плотным слоям для уточнения поиска. Такой подход напоминает переход от глобального обзора к детализации на уровне соседей, постепенно сужая область поиска.
Рис. 1: Пример навигационного графа малого мира
- Структура, похожая на пропускной список: Иерархический аспект HNSW напоминает список пропусков - вероятностную структуру данных, в которой более высокие уровни имеют меньшее количество узлов, что позволяет ускорить начальный поиск.
Рис. 2: Пример структуры списка пропусков
Чтобы найти 96 в данном списке пропусков, мы начинаем с верхнего уровня в крайнем левом узле с заголовком. Двигаясь вправо, мы встречаем 31, что меньше 96, поэтому переходим к следующему узлу. Теперь нам нужно спуститься на уровень ниже, где мы снова видим 31; поскольку оно все еще меньше 96, мы спускаемся еще на один уровень. Снова найдя 31, мы двигаемся вправо и достигаем 96 - нашего целевого значения. Таким образом, мы находим 96 без необходимости спускаться на самые нижние уровни списка пропусков.
Эффективность поиска: Алгоритм HNSW начинает с узла входа на самом верхнем уровне, с каждым шагом переходя к более близким соседям. Он спускается по слоям, используя каждый из них для грубого и тонкого исследования, пока не достигнет самого нижнего слоя, где, вероятно, будут найдены наиболее похожие узлы. Такая многоуровневая навигация сокращает количество узлов и ребер, которые необходимо исследовать, что делает поиск быстрым и точным.
Вставка и обслуживание: При добавлении нового узла алгоритм определяет его входной уровень на основе вероятности и соединяет его с близлежащими узлами с помощью эвристики выбора соседей. Эвристика направлена на оптимизацию связности, создавая связи, которые улучшают навигацию, но при этом уравновешивают плотность графа. Такой подход позволяет сохранить устойчивость структуры и адаптировать ее к новым данным.
Хотя у нас есть фундаментальное понимание алгоритма HNSW, его реализация с нуля может оказаться непосильной задачей. К счастью, сообщество разработало такие библиотеки, как HNSWlib, чтобы упростить его использование и сделать его доступным, не заставляя вас ломать голову. Итак, давайте рассмотрим HNSWlib поближе.
Обзор HNSWlib
HNSWlib, популярная библиотека, реализующая HNSW, отличается высокой эффективностью и масштабируемостью, хорошо работая даже с миллионами точек. Она достигает сублинейной временной сложности за счет быстрых переходов между слоями графа и оптимизации поиска для плотных, высокоразмерных данных. Вот ключевые особенности HNSWlib:
Структура на основе графа: Многослойный граф представляет точки данных, обеспечивая быстрый поиск ближайших соседей.
Эффективность работы с высокоразмерными данными: Оптимизирована для работы с высокоразмерными данными, обеспечивая быстрый и точный приблизительный поиск.
Сублинейное время поиска: достигается сублинейная сложность за счет пропуска слоев, что значительно повышает скорость.
Динамические обновления: Поддерживает вставку и удаление узлов в режиме реального времени, не требуя полной перестройки графа.
Эффективность использования памяти: Эффективное использование памяти, подходящее для больших наборов данных.
Масштабируемость: Хорошо масштабируется до миллионов точек данных, что делает его идеальным для приложений среднего масштаба, таких как рекомендательные системы.
Примечание: HNSWlib отлично подходит для создания простых прототипов приложений векторного поиска. Однако из-за ограничений по масштабируемости для более сложных сценариев, включающих сотни миллионов или даже миллиарды точек данных, могут быть использованы лучшие варианты, такие как специально созданные векторные базы данных. Давайте посмотрим на это в действии.
Начало работы с HNSWlib: Пошаговое руководство
В этом разделе мы продемонстрируем использование HNSWlib в качестве библиотеки векторного поиска, создав индекс HNSW, вставив данные и выполнив поиск. Начнем с установки:
Установка и импорт
Чтобы начать работу с HNSWlib в Python, сначала установите ее с помощью pip:
pip install hnswlib
Затем импортируйте необходимые библиотеки:
import hnswlib
import numpy as np
Подготовка данных
В этом примере мы будем использовать NumPy
для генерации случайного набора данных с 10 000 элементов, каждый из которых имеет размерность 256.
dim = 256 # Dimensionality of your vectors
num_elements = 10000 # Number of elements to insert
Давайте создадим данные:
data = np.random.rand(num_elements, dim).astype(np.float32) # Example data
Теперь наши данные готовы, давайте создадим индекс.
Построение индекса
При построении индекса нам необходимо определить размерность векторов и тип пространства. Создадим индекс:
p = hnswlib.Index(space='l2', dim=dim)
space='l2'
: Этот параметр определяет метрику расстояния, используемую для сходства. Если установить значение'l2'
, то будет использоваться евклидово расстояние (норма L2). Если вместо этого установить значение'ip'
, то будет использоваться внутреннее произведение, что полезно для таких задач, как косинусное сходство.
dim=dim
: Этот параметр задает размерность точек данных, с которыми вы будете работать. Она должна соответствовать размерности данных, которые вы планируете добавить в индекс.
Вот как инициализировать индекс:
p.init_index(max_elements=num_elements, ef_construction=200, M=16)
max_elements=num_elements
: Здесь задается максимальное количество элементов, которые могут быть добавлены в индекс.Num_elements
- это максимальная емкость, поэтому мы задаем значение 10 000, так как мы работаем с 10 000 точками данных.
ef_construction=200
: Этот параметр управляет компромиссом между точностью и скоростью построения при создании индекса. Более высокое значение улучшает запоминание (точность), но увеличивает использование памяти и время построения. Обычные значения варьируются от 100 до 200.
M=16
: Этот параметр определяет количество двунаправленных связей, создаваемых для каждой точки данных, что влияет на точность и скорость поиска. Типичные значения находятся в диапазоне от 12 до 48; 16 часто является хорошим балансом для умеренной точности и скорости.
p.set_ef(50) # This parameter controls the speed/accuracy trade-off
ef
: Параметрef
, сокращение от "exploration factor", определяет, сколько соседей просматривается во время поиска. При более высоком значенииef
исследуется больше соседей, что, как правило, повышает точность (запоминание) поиска, но также делает его более медленным. И наоборот, более низкое значениеef
ускоряет поиск, но может снизить точность.
В данном случае значение ef
, равное 50, означает, что алгоритм поиска будет оценивать до 50 соседей при нахождении наиболее похожих точек данных.
Примечание: ef_construction
задает усилие поиска соседей при создании индекса, повышая точность, но замедляя построение. ef
управляет усилием поиска при выполнении запроса, динамически балансируя скорость и отзыв для каждого запроса.
Выполнение поиска
Чтобы выполнить поиск ближайших соседей с помощью HNSWlib, мы сначала создадим случайный вектор запроса. В этом примере размерность вектора соответствует индексированным данным.
query_vector = np.random.rand(dim).astype(np.float32) # Example query
labels, distances = p.knn_query(query_vector, k=5) # k is the number of nearest neighbors
query_vector
: Эта строка генерирует случайный вектор с той же размерностью, что и индексированные данные, обеспечивая совместимость для поиска ближайших соседей.knn_query
: Метод ищет ближайших соседейk
дляquery_vector
в пределах индексаp
. Он возвращает два массива:labels
, которые содержат индексы ближайших соседей, иdistances
, которые указывают расстояния от вектора запроса до каждого из этих соседей. Здесьk=5
указывает, что мы хотим найти пять ближайших соседей.
Вот результаты после печати меток и расстояний:
print("Nearest neighbors' labels:", labels)
print("Distances:", distances)
> Nearest neighbors' labels: [[4498 1751 5647 4483 2471]]
> Distances: [[33.718 35.484592 35.627766 35.828312 35.91495 ]]
Вот и все, простое руководство для начала работы с HNSWlib.
Как уже говорилось, HNSWlib - это отличный векторный поисковый механизм для создания прототипов или экспериментов с наборами данных среднего размера. Если у вас более высокие требования к масштабируемости или вам нужны другие функции корпоративного уровня, возможно, вам придется выбрать специально разработанную векторную базу данных, такую как Milvus с открытым исходным кодом или полностью управляемый сервис на Zilliz Cloud. Итак, в следующем разделе мы сравним HNSWlib с Milvus.
HNSWlib против специализированных векторных баз данных, таких как Milvus
Векторная база данных хранит данные в виде математических представлений, что позволяет моделям машинного обучения использовать поиск, рекомендации и генерацию текстов путем идентификации данных с помощью метрик сходства для контекстного понимания.
Библиотеки векторных индексов, такие как HNSWlib, улучшаютпоиск и извлечениевекторов, но не обладают функциями управления, присущими полноценным базам данных. С другой стороны, векторные базы данных, такие как Milvus, предназначены для работы с векторными вкраплениями в масштабе, обеспечивая преимущества в управлении данными, индексировании и запросах, которых обычно не хватает отдельным библиотекам. Вот некоторые другие преимущества использования Milvus:
Высокоскоростной поиск по векторному сходству: Milvus обеспечивает производительность поиска на миллисекундном уровне в векторных наборах данных миллиардного масштаба, что идеально подходит для таких приложений, как поиск изображений, рекомендательные системы, обработка естественного языка(NLP) и поиск с расширенной генерацией(RAG).
Масштабируемость и высокая доступность: Созданная для работы с огромными объемами данных, система Milvus масштабируется горизонтально и включает механизмы репликации и обхода отказа для обеспечения надежности.
Распределенная архитектура: Milvus использует распределенную, масштабируемую архитектуру, которая разделяет хранение и вычисления на нескольких узлах для гибкости и надежности.
Гибридный поиск: Milvus поддерживает мультимодальный поиск, гибридный разреженный и плотный поиск, а также гибридный плотный и полнотекстовый поиск, предлагая универсальные и гибкие функции поиска.
Гибкая поддержка данных: Milvus поддерживает различные типы данных - векторы, скаляры и структурированные данные - обеспечивая беспрепятственное управление и анализ в рамках одной системы.
Активное сообщество и поддержка: Процветающее сообщество регулярно предоставляет обновления, учебные пособия и поддержку, обеспечивая соответствие Milvus потребностям пользователей и достижениям в данной области.
Интеграция с искусственным интеллектом: Milvus интегрирован с различными популярными фреймворками и технологиями искусственного интеллекта, что облегчает разработчикам создание приложений с использованием привычного технологического стека.
Milvus также предоставляет полностью управляемый сервис в облаке Ziliz Cloud, который не доставляет хлопот и работает в 10 раз быстрее, чем Milvus.
Сравнение: Milvus против HNSWlib
Характеристика | Milvus | HNSWlib |
---|---|---|
Масштабируемость | Легко справляется с миллиардами векторов | Подходит для небольших наборов данных из-за экономии оперативной памяти |
Идеально подходит для | Прототипирования, экспериментов и приложений корпоративного уровня | Ориентирован на прототипы и легкие задачи ANN |
Индексирование | Поддерживает 10+ алгоритмов индексирования, включая HNSW, DiskANN, квантование и двоичное индексирование. | Используется только HNSW на основе графа |
Интеграция | Предлагает API и облачные нативные сервисы | Служит в качестве легкой автономной библиотеки |
Производительность | Оптимизируется для больших данных, распределенных запросов | Предлагает высокую скорость, но ограниченную масштабируемость |
В целом, Milvus предпочтительнее для крупных производственных приложений со сложными потребностями в индексировании, в то время как HNSWlib идеально подходит для прототипирования и более простых случаев использования.
Заключение
Семантический поиск может быть ресурсоемким, поэтому внутренняя структуризация данных, подобная той, которую выполняет HNSW, необходима для более быстрого поиска данных. Библиотеки, подобные HNSWlib, заботятся о реализации, поэтому у разработчиков есть готовые рецепты для прототипирования векторных возможностей. С помощью всего нескольких строк кода мы можем создать собственный индекс и выполнять поиск.
HNSWlib - отличный способ начать. Однако если вы хотите создавать сложные и готовые к производству приложения ИИ, то лучшим вариантом будут специально созданные векторные базы данных. Например, Milvus - это векторная база данных с открытым исходным кодом, обладающая множеством возможностей для предприятий, таких как высокоскоростной векторный поиск, масштабируемость, доступность, а также гибкость в отношении типов данных и языка программирования.
Читать далее
- Понимание HNSW
- Обзор HNSWlib
- Начало работы с HNSWlib: Пошаговое руководство
- HNSWlib против специализированных векторных баз данных, таких как Milvus
- Заключение
- Читать далее
On This Page
Try Managed Milvus for Free
Zilliz Cloud is hassle-free, powered by Milvus and 10x faster.
Get StartedLike the article? Spread the word