Как работает Product Quantization (PQ) для сжатия векторов?

Краткий тезис

Quantization|Product Quantization (PQ) — это метод сжатия векторных представлений, который разбивает исходный вектор на несколько подвекторов, каждый из которых квантуется независимо с помощью отдельной кодовой книги (codebook). Результатом является компактный код (индексы центроидов), позволяющий хранить вектор в 8–32 раза меньше исходного размера с контролируемой потерей точности. PQ широко применяется в векторных базах данных (Faiss, Milvus) для ускорения поиска и снижения потребления памяти.

1. Зачем нужно сжатие векторов?

В современных RAG-системах и поисковых движках используются эмбеддинги — плотные векторы размерностью от 128 до 1024 (и выше). При миллиардах документов хранение таких векторов «как есть» (float32) требует огромной памяти. Например, 1 млрд векторов размерностью 768 занимает около 3 ТБ. Сжатие позволяет:

• уменьшить RAM/SSD footprint;
• ускорить вычисление расстояний (меньше данных передаётся и обрабатывается);
• масштабировать поиск на большие коллекции без увеличения стоимости инфраструктуры.

Product Quantization — один из самых эффективных методов сжатия с возможностью аппроксимации расстояний без полного декодирования.

2. Основная идея PQ

Исходный вектор викиразмерностиразмерности непересекающихся подвекторов одинаковой длины d = D / M (предполагается, что D кратно M). Каждый подвектор квантуется отдельно с помощью k-средних (k-means) в своём подпространстве. Результат квантования — индекс ближайшего центроида из кодовой книги размером k (обычно k=256, что кодируется 8 битами). Итоговый код вектора — это последовательность из M индексов, занимающая M × log2(k) бит.

Пример: D=128, M=16, k=256 → каждый подвектор размерности 8, код = 16 байт (128 бит) вместо 128×4=512 байт (float32). Сжатие в 32 раза.

Термин кодовая книга (codebook) — набор центроидов, полученных кластеризацией подпространства. Для каждого подпространства своя книга.

3. Алгоритм обучения PQ

3.1 Разбиение на подпространства

Исходные векторы обучающей выборки (например, все векторы базы) делятся на M групп по координатам. Формально: если x = [x₁, x₂, ..., x_D], то подвектор uⱼ = [x_{(j-1)d+1}, ..., x_{j·d}] для j = 1..M.

3.2 Кластеризация каждого подпространства

Для каждого j-го подпространства:

• Собираем все соответствующие подвекторы из обучающих векторов.
• Запускаем k-means с k центроидами (обычно 256).
• Получаем кодовую книгу Cⱼ = {cⱼ₁, ..., cⱼₖ}, где каждый центроид — вектор размерности d.

3.3 Кодирование вектора

Для нового вектора x:

• Разбиваем на M подвекторов.
• Для каждого подвектора находим ближайший центроид в соответствующей книге (по евклидову расстоянию).
• Записываем индекс этого центроида (от 0 до k-1).
• Итоговый код — массив из M целых чисел (например, uint8).

3.4 Декодирование (восстановление)

Приближённый вектор получается конкатенацией центроидов по их индексам. Точное восстановление невозможно — это lossy compression.

4. Математическая формализация

Пусть x ∈ ℝᴰ. Разбиение: x = (u₁, u₂, ..., u_M), где uⱼ ∈ ℝᵈ, d = D/M.

Квантование: qⱼ(uⱼ) = argmin_{i=1..k} ||uⱼ - cⱼᵢ||².

Код: code(x) = (q₁(u₁), q₂(u₂), ..., q_M(u_M)).

Приближённое расстояние между запросом yyи закодированным векторомx вычисляется без полного декодирования с помощью Asymmetric Distance Computation (ADC):

dist(y, x) ≈ Σⱼ ||vⱼ - cⱼ_{qⱼ(uⱼ)}||²,

где vⱼ — подвектор запроса y в j-м подпространстве. Таким образом, для каждого подпространства предвычисляются расстояния от подвектора запроса до всех k центроидов, затем суммируются по индексам кода. Это O(M·k·d) на запрос, что значительно быстрее полного сравнения (O(D)).

Термин ADC — стандартный способ вычисления расстояния в PQ, при котором запрос остаётся в исходном пространстве (не квантуется), а база хранится в сжатом виде.

5. Параметры PQ и их влияние

Практическое правило выбирают M так, чтобы d было не меньше 4–8, а общий размер кода (M × log2(k)) соответствовал желаемому коэффициенту сжатия (обычно 8–32x).

6. Сравнение с другими методами сжатия векторов

Scalar Quantization преобразует каждую координату в quantization|8-битное целое (линейное масштабирование). PQ даёт лучшее сжатие за счёт учёта структуры данных, но требует обучения.

7. Применение в векторных базах данных

Faiss (Facebook AI Similarity Search) — самая популярная библиотека, реализующая PQ. Типичная связка: IVF (Inverted File) + PQ. Сначала векторы кластеризуются грубо (IVF), затем внутри каждого кластера векторы сжимаются PQ. Это даёт субмиллисекундный поиск по миллиардам векторов.

Milvus и Pinecone также используют PQ как один из методов индексации. В Milvus параметры PQ задаются при создании индекса: index_type: "IVF_PQ", nlist, m, nbits.

HNSW (Hierarchical Navigable Small World) редко комбинируют с PQ напрямую, но можно использовать PQ для сжатия векторов перед построением графа, чтобы уменьшить память.

8. Преимущества и недостатки PQ

Преимущества

• Высокий коэффициент сжатия (8–32x) с умеренной потерей точности.
• Быстрое вычисление расстояний через ADC (без декомпрессии).
• Хорошо масштабируется на большие коллекции.
• Поддерживает любой тип метрики (L2, косинусная через нормализацию).

Недостатки

• Требует обучения на представительной выборке (может быть дорого для очень больших данных).
• Потеря точности неизбежна; recall может упасть на 5–20% в зависимости от настроек.
• Не подходит для точного поиска (exact search) — только для приближённого (ANN).
• Размер кодовых книг растёт с M и k (M × k × d × 4 байта), что может быть существенно при очень большом M.

9. Практические рекомендации

• Выбор M: начните с M = D/8 (d=8). Если точность太低, уменьшите M (увеличьте d). Если нужно сильнее сжатие, увеличьте M.
• k=256 — стандарт, дающий 8 бит на подвектор. Увеличение до 4096 (12 бит) даёт прирост точности, но код становится длиннее.
• Обучение: используйте случайную подвыборку из 100k–1M векторов. Убедитесь, что данные нормализованы, если используется косинусная метрика.
• Комбинируйте с IVF: IVF+PQ даёт лучший баланс скорости и точности, чем чистый PQ.
• Оценка: измеряйте Recall@k на валидационном наборе. Если recall < 0.9, попробуйте уменьшить M или увеличить k.

10. Пет-проект для закрепления

Задача Реализовать простой Product Quantizer на Python с использованием numpy и сравнить сжатие и точность на синтетических данных.

Инструменты Python, numpy, sklearn (KMeans), faiss (опционально для проверки).

Шаги:

1. Сгенерировать 10000 векторов размерности 128 (например, случайные или из нормального распределения).
2. Разделить на обучающую (8000) и тестовую (2000) выборки.
3. Реализовать класс ProductQuantizer:
   • __init__(self, M, k) — сохраняет параметры.
   • fit(vectors) — разбивает на M подпространств, для каждого запускает KMeans (k центроидов).
   • encode(vectors) — возвращает массив кодов (M индексов для каждого вектора).
   • decode(codes) — восстанавливает приближённые векторы (конкатенация центроидов).
   • adc_distance(query, codes) — вычисляет расстояния от запроса до всех закодированных векторов через ADC.
4. Обучить PQ с M=16, k=256. Оценить сжатие (размер кода vs float32).
5. Для 100 случайных запросов вычислить точный top-10 (по L2) и приближённый top-10 через ADC. Посчитать recall@10.
6. Поэкспериментировать с разными M (8, 16, 32) и построить график зависимости recall от коэффициента сжатия.

Ожидаемый результат Работающий PQ, который сжимает векторы в ~16 раз при recall@10 около 0.85–0.95 (зависит от данных). Код должен быть выложен на GitHub с README.

11. Связь с другими вопросами

12. Навигация

• Предыдущий: 222
• Следующий: 224
• Индекс: 00. Индекс разборов

Навигация

• Предыдущий: 222
• Следующий: 224
• Индекс: 00. Индекс разборов