Vector Search

Векторный поиск находит объекты, чьи эмбеддинги ближе всего к эмбеддингу запроса по метрике сходства, например косинусному сходству, скалярному произведению или евклидову расстоянию. Модель эмбеддингов размещает объекты с похожим смыслом или внешним видом рядом друг с другом, поэтому ближайшие векторы соответствуют наиболее похожим документам, изображениям или товарам, даже если в них нет ключевых слов, совпадающих с запросом. Точный векторный поиск — это поиск k ближайших соседей (k-NN) по всем сохранённым векторам. При больших масштабах системы используют индексы приближённого поиска ближайших соседей (ANN), которые сравнивают запрос лишь с небольшой долей векторов и при этом возвращают почти всех настоящих соседей.

Как работает векторный поиск#

Запрос и сохранённые объекты преобразуются в эмбеддинги одной моделью или парой совместно обученных моделей: кодировщиком предложений для текста, CLIP для сопоставления текста с изображениями или визуальным экстрактором признаков для сопоставления изображений. Метрика должна соответствовать способу обучения модели. Для векторов единичной длины косинусное сходство равно скалярному произведению, а сортировка по евклидову расстоянию даёт тот же порядок. Точный поиск требует одного сравнения с каждым сохранённым вектором на каждый запрос. Это быстро для десятков тысяч векторов, но слишком медленно для сотен миллионов, поэтому крупные системы используют одно из четырёх семейств индексов ANN:

• Графовые индексы, например HNSW: связывают каждый вектор с ближайшими соседями в многоуровневом графе; запрос обрабатывается жадным переходом к ближайшим к нему вершинам.
• Индексы кластеризации (IVF): группируют векторы с помощью k-means и сканируют только те кластеры, центроиды которых ближе всего к запросу.
• Векторное квантование: сжимает каждый вектор до нескольких байтов, как при продуктовом квантовании, чтобы расстояния можно было приближённо вычислять по компактным кодам в памяти.
• Графы на диске: хранят графовый индекс на SSD, как DiskANN, чтобы искать миллиарды векторов на одной машине.

Основную идею индекса IVF можно показать на коротком примере с NumPy и scikit-learn, сравнив его с точным поиском:

import numpy as np
from sklearn.cluster import KMeans

# 20,000 embeddings grouped by topic, normalized so a dot product is cosine similarity
rng = np.random.default_rng(0)
topics = rng.normal(size=(200, 64))
vectors = topics[rng.integers(200, size=20000)] + 0.5 * rng.normal(size=(20000, 64))
vectors /= np.linalg.norm(vectors, axis=1, keepdims=True)
query = vectors[0] + 0.1 * rng.normal(size=64)

# Exact search: score every stored vector
exact = np.argsort(-(vectors @ query))[:10]

# IVF index: cluster the vectors, then scan only the lists of the 5 closest centroids
kmeans = KMeans(n_clusters=100, n_init=1, random_state=0).fit(vectors)
probed = np.argsort(-(kmeans.cluster_centers_ @ query))[:5]
candidates = np.flatnonzero(np.isin(kmeans.labels_, probed))
approx = candidates[np.argsort(-(vectors[candidates] @ query))[:10]]

print(f"scanned {len(candidates) / len(vectors):.1%} of vectors")
print(f"recall@10: {len(set(exact) & set(approx)) / 10:.0%}")

Проверка 5 из 100 кластеров охватывает 5,1% векторов и при этом находит все 10 настоящих ближайших соседей: полнота@10 составляет 100%. Проверка большего числа кластеров повышает и полноту, и затраты, поэтому число проверяемых кластеров — главный параметр, который нужно настраивать в индексе IVF.

Векторный поиск и смежные понятия#

• Поиск по ключевым словам: ищет точные термины в инвертированном индексе и ранжирует результаты с помощью формул, например BM25. Он отлично справляется с именами, кодами и редкими словами, но не находит синонимы.
• Семантический поиск: поиск по смыслу — задача, для которой чаще всего используют векторный поиск. Системы семантического поиска нередко дополняют его переформулированием запроса или повторным ранжированием результатов.
• Гибридный поиск: одновременно выполняет поиск по ключевым словам и векторный поиск, а затем объединяет два ранжированных списка.
• Векторная база данных: система, которая хранит векторы с метаданными и поддерживает векторный поиск с фильтрацией, обновлением и постоянным хранением данных.

Примеры применения в реальных условиях#

• Генерация с дополненной выборкой (RAG): находит фрагменты документов, необходимые языковой модели для ответа на вопрос.
• Повторная идентификация объектов: сопоставляет эмбеддинг внешнего вида человека или транспортного средства с более ранними наблюдениями, чтобы связать один и тот же объект на разных камерах.
• Распознавание лиц: сравнивает эмбеддинг лица с зарегистрированными лицами и принимает ближайшее совпадение, если оно достаточно близко.
• Рекомендательные системы: предлагают товары, песни или видео, эмбеддинги которых близки к эмбеддингам недавних выборов пользователя.

Платформа Ultralytics использует векторный поиск для расширения обучающих наборов данных. Действие «Найти похожие изображения» берёт выбранное изображение, ищет ближайшие по эмбеддингу изображения в общедоступных наборах данных, а также в наборах данных пользователя и его команды, и показывает до 24 совпадений с оценками сходства. Их можно добавить в набор данных как неразмеченные обучающие изображения.