FAISS

FAISS (Facebook AI Similarity Search) — это библиотека с открытым исходным кодом, разработанная компанией Meta (организация признана экстремистской и запрещена в РФ) для эффективного поиска ближайших соседей и кластеризации плотных векторных представлений. Она предназначена для работы с наборами данных, размерность которых может достигать миллиардов векторов, и широко применяется в задачах информационного поиска, рекомендательных систем и машинного обучения.

История

Разработка FAISS началась в 2015 году в исследовательском подразделении Facebook (продукт Meta, признанной экстремистской и запрещённой в РФ) AI Research (FAIR). Основной целью было создание инструмента, способного решать проблему масштабирования поиска по сходству в многомерных пространствах, которая остро встала с ростом популярности нейросетевых эмбеддингов. Первая публичная версия библиотеки была выпущена в 2017 году под лицензией BSD. Ключевыми авторами проекта выступили Матье Дуэз, Джефф Джонсон и Эрве Жеглу.

В 2020 году была представлена версия FAISS для GPU, которая значительно ускорила обучение и выполнение запросов за счёт параллельных вычислений на видеокартах NVIDIA. В 2022 году, после смены бренда материнской компании, библиотека была переименована из «Facebook AI Similarity Search» в «FAISS», хотя аббревиатура осталась прежней. Проект продолжает активно развиваться, поддерживая как CPU, так и GPU, и интегрирован в основные фреймворки машинного обучения, такие как PyTorch и TensorFlow.

Классификация методов

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

Точный поиск (Exact Search)

Этот метод гарантирует нахождение истинных ближайших соседей для заданного запроса. Он основан на полном переборе всех векторов в базе данных и вычислении расстояния (например, евклидова или косинусного) до каждого. В FAISS для этого используется структура IndexFlatL2 (для L2-расстояния) или IndexFlatIP (для скалярного произведения). Точный поиск оптимален для небольших наборов данных (до нескольких сотен тысяч векторов), но становится неэффективным при миллионах и миллиардах записей из-за линейной вычислительной сложности O(N).

Приближённый поиск (Approximate Search)

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

Квантование (Quantization)

Наиболее распространённый метод — продуктовое квантование (Product Quantization, PQ). Исходные векторы разбиваются на подвекторы, каждый из которых квантуется отдельно с помощью небольшого кодового словаря. Это позволяет сжимать векторы в десятки раз, уменьшая объём памяти и ускоряя вычисления. В FAISS этот метод реализован в индексах IndexIVFPQ и IndexPQ.

Инвертированные файлы (Inverted Files, IVF)

Метод основан на предварительной кластеризации базы данных с помощью алгоритма k-средних (k-means). Каждый вектор относится к ближайшему центроиду кластера. При поиске сначала определяется несколько ближайших к запросу кластеров, а затем поиск выполняется только среди векторов этих кластеров. Это снижает количество вычислений с O(N) до O(N/количество кластеров). В FAISS используется IndexIVFFlat (с точным расстоянием внутри кластеров) и IndexIVFPQ (с квантованием внутри кластеров).

Иерархический навигационный граф (HNSW)

Метод Hierarchical Navigable Small World строит многоуровневую графовую структуру, где каждый узел — вектор, а рёбра соединяют ближайших соседей. Поиск начинается с верхнего уровня (с низкой плотностью) и постепенно спускается на нижние, уточняя результат. HNSW обеспечивает высокую скорость и точность, но требует больше памяти для хранения графа. В FAISS реализован в индексе IndexHNSW.

Устройство и характеристики

Индексы

Центральная концепция FAISS — это индекс (Index). Индекс представляет собой структуру данных, которая хранит векторы и предоставляет методы для их добавления, удаления и поиска. Каждый индекс имеет уникальный идентификатор (ID) и может быть сконфигурирован под конкретную задачу.

Основные параметры индексов:

• Размерность векторов (d): все векторы в одном индексе должны иметь одинаковую размерность.
• Метрика расстояния: L2 (евклидово), IP (скалярное произведение) или косинусное.
• Тип кодирования: плоский (Flat), квантованный (PQ), сжатый (SQ) и т.д.
• Параметры обучения: для методов, требующих обучения (например, k-means для IVF), необходимо задать количество кластеров (nlist) и количество проверяемых кластеров при поиске (nprobe).

Работа с GPU

FAISS поддерживает выполнение на GPU через CUDA. Это позволяет обрабатывать миллиарды векторов за секунды. GPU-индексы (например, GpuIndexFlatL2, GpuIndexIVFPQ) автоматически распределяют данные по видеопамяти и выполняют параллельные вычисления. Для работы с GPU требуется наличие совместимой видеокарты NVIDIA и установленного драйвера CUDA.

Масштабирование

FAISS поддерживает работу с наборами данных, превышающими объём оперативной памяти. Для этого используется механизм разделения на шарды (sharding) и индексы на диске (например, IndexShards). Векторы могут храниться на жёстком диске, а при поиске загружаться в память только необходимые части.

Применение

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

Поиск изображений и видео

Системы обратного поиска изображений (например, в Google Images или Pinterest) используют эмбеддинги, полученные из свёрточных нейронных сетей. FAISS позволяет находить похожие изображения среди миллионов или миллиардов образцов за миллисекунды.

Рекомендательные системы

В рекомендательных системах (например, в Netflix, Spotify, Amazon) FAISS используется для поиска ближайших соседей среди эмбеддингов пользователей и товаров. Это позволяет предлагать пользователям контент, похожий на тот, который им уже понравился.

Обработка естественного языка (NLP)

В задачах NLP, таких как поиск семантически похожих текстов или вопросно-ответные системы, FAISS применяется для поиска по эмбеддингам предложений, полученным из моделей типа BERT или Sentence-BERT.

Биоинформатика

В биоинформатике FAISS используется для поиска похожих последовательностей ДНК или белков, а также для кластеризации геномных данных.

Примеры использования

Пример 1: Точный поиск на CPU

```python import faiss import numpy as np

Генерация случайных векторов (1000 векторов размерностью 64)

d = 64 nb = 1000 xb = np.random.random((nb, d)).astype('float32')

Создание индекса для точного поиска по L2-расстоянию

index = faiss.IndexFlatL2(d) index.add(xb)

Поиск 5 ближайших соседей для одного запроса

xq = np.random.random((1, d)).astype('float32') D, I = index.search(xq, 5) print(I) # Индексы ближайших соседей print(D) # Расстояния до них ```

Пример 2: Приближённый поиск с IVF+PQ

```python import faiss import numpy as np

d = 64 nb = 10000 xb = np.random.random((nb, d)).astype('float32')

Создание индекса IVF с продуктовым квантованием

nlist = 100 m = 8 # Количество подвекторов для PQ index = faiss.IndexIVFPQ(faiss.IndexFlatL2(d), d, nlist, m, 8) index.train(xb) index.add(xb)

Поиск с проверкой 5 кластеров

index.nprobe = 5 xq = np.random.random((1, d)).astype('float32') D, I = index.search(xq, 5) print(I) ```

Интересные факты

• FAISS является одной из самых быстрых библиотек для поиска ближайших соседей на GPU. В тестах на наборе данных из 1 миллиарда векторов она способна выполнять поиск за несколько миллисекунд.
• Библиотека используется в продакшене крупнейших технологических компаний, включая Meta (организация признана экстремистской и запрещена в РФ), Microsoft, NVIDIA и Alibaba.
• FAISS поддерживает не только поиск, но и кластеризацию (например, k-means с использованием GPU), что делает её универсальным инструментом для анализа данных.
• В 2023 году была добавлена поддержка квантования с плавающей точкой (FP16 и BF16), что позволило ещё больше сжать векторы без значительной потери точности.

Критика

Несмотря на высокую производительность, FAISS имеет некоторые ограничения. Основной недостаток — это сложность настройки параметров индексов для достижения оптимального баланса между скоростью, точностью и потреблением памяти. Для новичков выбор правильного типа индекса и его параметров может быть нетривиальной задачей. Кроме того, FAISS не поддерживает динамическое обновление индексов (добавление новых векторов без перестроения) для всех типов индексов, что может быть критично для систем с постоянно обновляющимися данными. Наконец, библиотека ориентирована в первую очередь на плотные векторы и неэффективна для работы с разреженными данными.

Источники

1. Johnson, J., Douze, M., & Jégou, H. (2019). Billion-scale similarity search with GPUs. IEEE Transactions on Big Data, 7(3), 535-547.
2. Douze, M., et al. (2024). The Faiss library. arXiv preprint arXiv:2401.08281.
3. Официальная документация FAISS: https://github.com/facebookresearch/faiss
4. Jégou, H., Douze, M., & Schmid, C. (2011). Product quantization for nearest neighbor search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(1), 117-128.