Введение в HNSW Иерархический Навигируемый Малый Мир

Введение в HNSW Иерархический навигируемый малый мир

Введение

Инновации в области искусственного интеллекта происходят на сверхзвуковой скорости. Одним из фронтов этой инновации являются поисковые движки на векторах. Что такое эти поисковые движки, вы спросите? Простыми словами, они помогают обучать большие модели языка (LLM), проходя через большие наборы данных и выбирая то, что является актуальным. Теперь существует множество способов индексирования в векторных базах данных. Из них выделяется иерархическая навигационная маленькая вселенная (HNSW) как высокопроизводительный и масштабируемый метод. Все основные векторные магазины предоставляют HNSW в качестве метода индексирования. Он быстрый, эффективный, надежный и надежный. Итак, в этой статье мы разобъем внутреннее устройство HNSW и узнаем, что делает его таким быстрым.

Цели изучения

• Понять, что такое вложения и векторные базы данных.
• Ознакомиться с различными способами индексирования в векторных базах данных.
• Узнать, что такое HNSW и как он работает.
• Понять HNSWlib, реализацию только с заголовками HNSW.

Эта статья была опубликована в рамках Блогона по науке о данных.

Что такое вложения?

Вложения – это векторные представления данных (текст, изображение) в пространстве высоких размерностей.

Два семантически связанных набора данных будут близко расположены в векторном пространстве, в то время как непохожие данные будут далеко друг от друга. Другими словами, вложения слова для Месси и футбола будут близко расположены в пространстве вложений, в то время как вложения слова для футбола и Джо Байдена будут далеко друг от друга в пространстве вложений.

• Как работает PPO со стрижкой?
• «Продвинутый Python метаклассы»
• «NaN значения в стандартной библиотеке Python»

Длина векторов может варьироваться от нескольких сотен до тысяч и более. Это затрудняет хранение, запросы и поиск. Но каждое приложение на основе Retrieval Augmented Generation (RAG) требует быстрого поиска и запросов вложений данных. Вот где появляются векторные базы данных.

Что такое векторные базы данных?

Как и традиционные базы данных, которые стремятся хранить структурированные и неструктурированные данные, векторные базы данных хранят, ищут и запрашивают векторные вложения в высоких размерностях. Они предоставляют пользовательские интерфейсы для взаимодействия с вложениями и ассоциированными данными. Векторные базы данных в своей сути не отличаются от традиционных баз данных. Векторные базы данных используют традиционные базы данных для хранения сериализованных вложений. Например, Chroma использует SQLite в качестве памяти хранения, а Pgvector использует базу данных Postgres для хранения вложений и связанных с ними метаданных. То, что отличает традиционную базу данных от векторной базы данных, это используемый алгоритм индексирования.

Индексирование в векторных базах данных

Индексирование относится к процессу организации векторов высоких размерностей таким образом, чтобы обеспечивался эффективный поиск ближайших соседних векторов.

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

• Алгоритм линейного поиска (плоский индекс): это алгоритм линейного поиска, что означает, что он сравнивает вектор запроса со всеми остальными векторами, хранящимися в базе данных. Это самый простой метод, который работает хорошо с небольшими наборами данных.
• Алгоритм на основе кластеров (IVF): Обратный файл является кластерным методом индексирования. Он использует кластеризацию по методу k-средних для кластеризации всех векторов. При предоставлении вектора запроса он вычисляет расстояние между вектором запроса и центроидами каждого кластера и начинает искать ближайших соседей в кластере с центроидом, ближайшим к вектору запроса. Это значительно сокращает время запроса.
• Квантование (скалярное и продуктовое квантование): Техника квантования включает уменьшение объема памяти больших вложений за счет сокращения их точности.
• Графовый метод (HNSW): Самый распространенный метод индексации. Он использует иерархическую графовую архитектуру для индексирования векторов. И это то, что мы собираемся рассмотреть.

Понимание HNSW

Большие модели языка (LLM) становятся все более популярными, и многие организации хотят реализовать их в своих продуктовых стеках. Однако есть проблема: LLM имеют ограниченное окно контекста. Окно контекста – это количество токенов, которое может воспринять модель искусственного интеллекта. Например, у GPT 3.5 Turbo есть длина контекста 4096. Вот где блеснут векторные поисковые базы данных. Вместо того, чтобы бросать весь книжный фон в контекст LLM, мы находим наиболее актуальные части и подаем их на вход LLM для получения точных результатов.

Среди всех различных способов индексации в векторных базах данных, обсужденных выше, HNSW является наиболее надежным и масштабируемым. Именно поэтому он также является наиболее широко используемым методом индексации. HNSW образуется путем объединения двух алгоритмов: пропущенного списка и навигируемого малого мира. Чтобы понять HNSW, нам нужно знать эти алгоритмы. Так что погружаемся в них.

Пропущенный список

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

Зачем нам нужен пропущенный список? Временная сложность поиска связного списка составляет O(n). Это может быть не идеальным для реальных сценариев использования, где скорость выполнения имеет первостепенное значение. Вот почему нам может потребоваться более эффективный алгоритм связного списка.

Пропущенные списки имеют ожидаемую временную сложность O(log n). Они работают намного лучше при произвольном доступе, чем связные списки. Так как они имеют слоистую структуру с несколькими узлами на каждом уровне, наихудшая пространственная сложность составляет O(n log n), где n – количество узлов на нижнем уровне.

Как работает пропущенный список?

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

На приведенной выше картинке нижний уровень представляет собой полный связный список. По мере движения вверх количество узлов в каждом слое уменьшается вдвое. Такая структура называется пропущенными списками, потому что на более высоких уровнях они позволяют пропустить узлы при обходе.

Рассмотрим следующий пример.

При поиске k:

• если k = целевой элемент
• если k >= перейти вправо
• если k < перейти вниз

Мы начинаем с верхнего левого угла и движемся вправо, пока не найдем k или число меньше k. Затем мы спускаемся на слой ниже и продолжаем процесс, пока не достигнем k. Сложность поиска составляет O(log n), так как мы пропускаем половину элементов на каждом уровне.

Хотя случайный доступ происходит быстрее, вставка и удаление медленнее, так как они добавляют дополнительные накладные расходы на обновление и удаление на нескольких уровнях.

При вставке мы начинаем с нижнего списка и добавляем узел в подходящую позицию. Так как пропущенные списки поддерживают иерархическую структуру, мы должны определить, появляется ли узел на более высоком уровне. Процесс происходит случайным образом, как подбрасывание монеты. Вероятность появления узла на его непосредственно верхнем слое равна 0.5. В идеальном пропущенном списке количество узлов на 1-м уровне будет ~n/2, а на 2-м уровне ~n/4, где n – количество узлов на нижнем уровне или полный связный список.

Рассмотрим следующий пример.

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

Удаление происходит аналогично. Находим целевое число и удаляем узел. Если элемент присутствует на более высоком уровне, удаляем его и обновляем связанный список.

Навигируемый малый мир (NSW)

Навигируемый малый мир – это графовый алгоритм для нахождения приближенных ближайших соседей. Точки данных в графе называются узлами. Каждый узел связан с набором соединений, близких друг к другу.

Это жадный алгоритм. Он начинает с предопределенной точки в графе и выбирает узлы, близкие к целевому узлу. Расстояние между узлами может быть измерено с помощью евклидовой или косинусной схожести. Этот процесс повторяется, пока не будут достигнуты ближайшие соседи целевого узла.

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

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

Как в случае векторных баз данных, нам нужно иметь дело с несколькими миллионами векторных данных. Поэтому нам нужен лучший алгоритм, который масштабируется хорошо и предлагает лучшую возможность поиска. В то время как NSW достаточно хорошо справляется с небольшими наборами данных, нам нужен еще более эффективный алгоритм для работы с сотнями миллионов или миллиардами точек данных. Именно здесь на сцену выходит HNSW.

Иерархический навигируемый малый мир (HNSW)

HNSW расширяет NSW путем включения иерархической архитектуры Skip Lists. Это устраняет проблему масштабируемости NSW. Как и Skip Lists, HNSW создает многоуровневую структуру NSW вместо связанных списков. Как и Skip Lists, верхний уровень будет содержать меньшее количество данных с самыми длинными связями. Количество элементов увеличивается по мере спуска по иерархии. На самом нижнем уровне находятся все данные. Как и в skip lists, вероятность существования элемента экспоненциально уменьшается по мере движения вверх по иерархии.

Но как искать в HNSW?

Поиск в HNSW

Теперь вспомним и skip list, и NSW. В skip list мы начинаем с верхнего уровня, а в NSW мы начинаем с предварительно заданной точки. В HNSW мы начинаем с предварительно заданной точки на самом верхнем уровне и жадно обходим граф, чтобы найти ближайший элемент к целевой точке данных на этом уровне. Как только мы достигаем ближайшей вершины, мы спускаемся на уровень ниже и повторяем процесс, пока не найдены “K” ближайших соседей целевой вершины. См. ниже рисунок

Вставка и удаление в HNSW

Вставка в HNSW следует тому же принципу, что и в Skip lists. Мы проходим по уровням, находим ближайших соседей элемента. Затем мы спускаемся вниз и повторяем тот же процесс, пока не найдем всех ближайших соседей на нижнем уровне.

Следующая задача – определение двусторонних связей с вставленным элементом. Обычно это определяется предопределенным параметром m. Мы соединяем m ближайших соседей с вставленной вершиной. Это один из способов определения связей с вставленной вершиной. Можно также использовать другие эвристики. Например, вместо того чтобы связываться только с самыми близкими узлами той же области, мы также связываем вставленную вершину с ближайшей вершиной ближайшей области для формирования более связанного графа.

Как и в skip list, вероятность появления узла в более высоких слоях определяется случайным образом. Функция для этого выглядит как floor(-ln(rand(0, 1))), где rand(0, 1) – случайное число, выбираемое из равномерного распределения между (0, 1].

Удаление происходит по аналогичному подходу. Мы начинаем с верхнего слоя и удаляем цель, пока она не появится на нижнем слое.

Сложности в HNSW

Временные сложности поиска, вставки и удаления в HNSW зависят от нескольких факторов, включая высоту архитектуры, количество соседних узлов на узел и метрику расстояния. Но в среднем время выполнения поиска, вставки и удаления имеет временную сложность O(log n). Строительство HNSW может быть затратным процессом. Нам нужно вставить n количество узлов с временной сложностью O(log n). Поэтому общая временная сложность построения графа будет O(n log n).

Базы данных векторов создаются для обработки сотен миллионов вложений. Для индексации такого объема данных требуется высокоэффективный, надежный и масштабируемый алгоритм. HNSW отвечает всем требованиям.

Недостатки HNSW

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

• Большой объем памяти: HNSW поддерживает иерархическую структуру вложений, что существенно увеличивает потребление памяти по сравнению с такими алгоритмами, как NSW. Это может вызывать проблемы для устройств с ограниченными ресурсами.
• Настройка параметров: HNSW имеет разные настраиваемые параметры. Требуется тщательная настройка параметров для повышения производительности.
• Сложность: Реализация HNSW с нуля может быть сложной. Большинство векторных баз данных используют надежные готовые решения, такие как FAISS или HNSWlib.

HNSWlib: реализация HNSW только в виде заголовочного файла

HNSWlib – это реализация алгоритма HNSW на языке C++ только в виде заголовочного файла с привязками к Python. Он был написан автором статьи о HNSW, Юрием Малковым. Это основная реализация алгоритма.

Итак, приступим.

Вы можете установить HNSWlib с помощью любого менеджера пакетов Python.

pip install hnswlib

Объявление и инициализация индекса HNSW.

import hnswlib
import numpy as np
import pickle

dim = 16
num_elements = 100
hnsw_index = hnswlib.Index(space='l2', dim=dim) # объявление индекса
hnsw_index.init_index(max_elements=num_elements, ef_construction=200, M=16)

• Параметр space – это метрика расстояния, которая будет использоваться для вычисления расстояния между узлами. Реализация Python поддерживает квадрат Л2, косинусное расстояние и скалярное произведение.
• Параметр dim – это размерность векторов встроенного представления.
• Метод init_index инициализирует индекс.
• Параметр ef_construction определяет компромисс между временем построения и точностью.
• M – это количество двунаправленных связей, создаваемых при вставке узла.

Теперь, когда мы создали индексы, давайте добавим несколько векторов.

data1 = np.float32(np.random.random((num_elements, dim)))
ids1 = np.arange(num_elements)

data2 = np.float32(np.random.random((100, dim)))
ids2 = np.arange(100)

data3 = np.float32(np.random.random((100, dim)))
ids3 = np.arange(100)

hnsw_index.add_items(data1, ids1)
hnsw_index.add_items(data2, ids2)
hnsw_index.set_ef(50) # установка компромисса скорости и точности при запросе
hnsw_index.set_num_threads(4) # установка количества потоков во время пакетного построения

Теперь давайте посмотрим, как мы можем выполнить приближенный поиск ближайшего соседа k.

labels, distances = hnsw_index.knn_query(data, k=1)

Сериализация объекта индекса с использованием pickle.

hnsw_pickle = pickle.dumps(hnsw_index)
hnsw_cp = pickle.loads(hnsw_pickle)

Удаление элементов.

for id in ids2:
    hnsw_index.mark_deleted(id)

Это освободит последние 100 элементов из индекса. При желании, вы можете также повторно использовать память, выделенную для удаленных элементов.

hnsw_index.add_items(data3, ids3, replace_deleted=True)

Заключение

HNSW – один из самых важных алгоритмов для разработки методов поиска векторов. Он является основным алгоритмом индексации, используемым во всех основных векторных базах данных. Надеюсь, вы поняли, как работает HNSW, изучив эту статью. С развитием искусственного интеллекта мы увидим разработку более крупных и сложных моделей обучения, что приведет к увеличению необходимости использовать HNSW и повышению его значимости и применения.

Основные выводы

• Векторные базы данных – это специальные хранилища данных для хранения высокоразмерных векторных вложений.
• Индексация встроенных представлений позволяет базам данных обрабатывать запросы, вставку и удаление векторов.
• Существуют разные способы индексации векторов, такие как IVF, Annoy, Quantization и HNSW.
• HNSW – это комбинация двух алгоритмов: пропускных списков и навигируемого “Small World” алгоритма.

Часто Задаваемые Вопросы

Медиа, показанные в этой статье, не принадлежат Analytics Vidhya и используются по усмотрению автора.