OPQ (Optimized Product Quantization) vs PQ — в чем разница?

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

Quantization|Product Quantization (PQ) и Product Quantization (OPQ) — методы сжатия векторов для приближённого поиска ближайших соседей (ANN). PQ разбивает вектор на подвекторы и квантует каждый независимо, но страдает от неравномерного распределения информации по подвекторам. OPQ решает эту проблему, добавляя перед квантованием ортогональное преобразование (вращение), которое выравнивает дисперсию компонент, что повышает точность поиска при том же коэффициенте сжатия. OPQ — это оптимизация PQ, дающая лучшее качество за счёт небольшого увеличения вычислительных затрат на обучение.

1. Product Quantization (PQ) — базовый метод

Product Quantization — это техника сжатия векторов, широко используемая в ANN-индексах (например, в Faiss). Идея:

1. Исходный вектор размерности викиразбивается наразбивается на равных подвекторов (субвекторов) размерности D/M.
2. Для каждого подвектора строится своя кодовая книга (codebook) из k центроидов (обычно k = 256, что даёт 8 бит на подвектор).
3. Каждый подвектор заменяется индексом ближайшего центроида из соответствующей кодовой книги.
4. Исходный вектор представляется как M целых чисел (индексов), что даёт сжатие в D / (M * log2(k)) раз (в битах).

Расстояние между запросом и сжатым вектором вычисляется приближённо через ADC (Asymmetric Distance Computation) — запрос остаётся несжатым, а для каждого подвектора заранее предвычисляются расстояния до центроидов.

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

2. Проблема PQ: неравномерность информации

Рассмотрим пример: вектор признаков изображения. Первые 32 компоненты могут отвечать за цвет, а следующие 32 — за текстуру. Дисперсия по компонентам может сильно различаться. PQ делит вектор на фиксированные блоки, не учитывая, что некоторые блоки содержат больше «полезной» информации.

Формально пусть x— исходный векторx = [x₁, x₂, ..., x_M] — разбиение на подвекторы. Ошибка квантования для каждого подвектора зависит от его собственной дисперсии. Если дисперсии сильно различаются, суммарная ошибка будет выше оптимальной, так как биты распределены равномерно, а не пропорционально важности.

3. Optimized Product Quantization (OPQ) — решение

OPQ (Product Quantization) — это модификация PQ, предложенная в работе Ge et al. (2013). Основная идея: перед разбиением на подвекторы применить к вектору ортогональное преобразование (вращение), которое выравнивает дисперсию по всем компонентам. После такого преобразования любой набор подвекторов будет иметь примерно одинаковую дисперсию, и PQ будет работать оптимально.

Ключевые шаги OPQ

1. Найти ортогональную матрицу R (размером D×D), такую что после применения y = R·xдисперсия компонент вектораy становится равномерной (или близкой к равномерной).
2. Применить PQ к преобразованным векторам y (разбить на M подвекторов, построить кодовые книги).
3. При поиске запрос q также преобразуется тем же вращением: q' = R·q, затем вычисляется расстояние через ADC.

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

4. Математическая постановка OPQ

Задача OPQ формулируется как минимизация ошибки квантования при ограничении на ортогональность преобразования:

Целевая функция

min_{R, C} Σ_i ||R·x_i - Q(R·x_i)||²

где:

• R — ортогональная матрица (R^T R = I),
• C — набор кодовых книг для PQ (M книг по k центроидов),
• Q(·) — оператор квантования (замена подвектора ближайшим центроидом),
• x_i — обучающие векторы.

Оптимизация проводится итеративно:

1. Фиксируем R обновляем кодовые книгиC (стандартный PQ на преобразованных данных).
2. Фиксируем викиобновляем обновляем (решаем задачу ортогонального Procrustes: минимизация суммы квадратов ошибок между преобразованными векторами и их квантованными версиями).

Алгоритм сходится к локальному оптимуму за несколько итераций (обычно 10–20).

5. Сравнение PQ и OPQ

Вывод OPQ даёт лучшее качество без увеличения времени поиска и объёма индекса (кроме небольшой матрицы R). Проигрыш только во времени обучения (в 2–5 раз дольше).

6. Когда использовать OPQ, а когда PQ?

• Используйте OPQ, если:

  • У вас есть время на предварительное обучение (обычно это разовая операция).
  • Данные имеют неоднородную структуру (например, эмбеддинги из нейросетей).
  • Требуется максимальная точность при заданном сжатии.
  • Размерность векторов велика (≥128), и вы используете M ≥ 8.

• Используйте PQ, если:

  • Данные уже хорошо сбалансированы (например, случайные проекции).
  • Время обучения критично (например, динамическое обновление индекса).
  • Размерность мала (≤64), выигрыш от OPQ незначителен.

На практике в современных ANN-библиотеках (Faiss, ScaNN) OPQ используется по умолчанию для индексов типа IndexIVFPQ с опцией use_opq=True.

7. Связь с другими методами квантования

• Scalar Quantization (SQ) — квантует каждую компоненту отдельно (обычно 8 бит). Проще, но хуже сжимает.
• Residual Quantization (RQ) — последовательное квантование остатков. Может дать лучшее качество, но сложнее в реализации.
• Additive Quantization (AQ) — обобщение PQ, где центроиды суммируются. Ещё точнее, но медленнее.
• IVF + PQ/OPQ — комбинация с инвертированным файлом (IVF) для ускорения поиска. OPQ часто используется внутри IVF.

8. Реализация в Faiss (Python)

Пример создания индекса с OPQ в Faiss:

import faiss
import numpy as np

# Параметры
d = 128          # размерность векторов
M = 16           # число подвекторов
nbits = 8        # бит на подвектор (k = 2^8 = 256)
nlist = 100      # количество кластеров IVF

# Обучающие данные (10000 векторов)
xt = np.random.rand(10000, d).astype('float32')

# Индекс IVF + OPQ
quantizer = faiss.IndexFlatL2(d)  # для IVF
index = faiss.IndexIVFPQ(quantizer, d, nlist, M, nbits)
index.verbose = True

# Включаем OPQ (ортогональное преобразование)
index.own_fields = True
index.pq = faiss.ProductQuantizer(d, M, nbits)
index.pq.verbose = True
index.pq.learn(xt)  # обычный PQ

# Для OPQ нужно отдельно обучить преобразование
# В Faiss есть готовая функция:
index = faiss.index_factory(d, f"OPQ{M}_{nbits},IVF{nlist},PQ{M}x{nbits}")
index.train(xt)
index.add(xt)

# Поиск
xq = np.random.rand(10, d).astype('float32')
D, I = index.search(xq, k=5)

Примечание В Faiss OPQ — это отдельный слой, который применяется перед PQ. Индекс "OPQ16_8,IVF100,PQ16x8" означает: сначала OPQ с M=16 и 8 битами, затем IVF с 100 кластерами, затем PQ с теми же параметрами.

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

Задача Сравнить точность поиска (recall@1) для PQ и OPQ на датасете SIFT1M (128-мерные дескрипторы).

Инструменты Python, Faiss, numpy, matplotlib.

Шаги:

1. Скачайте SIFT1M (или используйте случайные данные с неравномерной дисперсией).
2. Разделите на обучающую (100k), базу (1M) и запросы (10k).
3. Постройте два индекса:
   • IndexIVFPQ с обычным PQ (M=16, nbits=8, nlist=100).
   • IndexIVFPQ с OPQ (через index_factory с префиксом OPQ16_8).
4. Обучите оба индекса на одной обучающей выборке.
5. Выполните поиск top-1 для запросов, сравните recall (доля запросов, где истинный ближайший сосед попал в результат).
6. Постройте график зависимости recall от количества бит на вектор (меняя M от 4 до 32).

Ожидаемый результат OPQ покажет recall на 5–15% выше при одинаковом сжатии. Вы также увидите, что разница больше при малом M (сильное сжатие).

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

11. Навигация

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

Навигация

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