Как Google использует квантование векторов для ускорения и масштабирования поиска (особенно Neural Matching)

Термины и определения

Codebook (Кодовая книга)

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

Cluster Center (Центр кластера)

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

Example Queries (Примеры запросов)

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

Inner Product / Dot Product (Внутреннее произведение / Скалярное произведение)

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

MIPS (Maximum Inner Product Search / Поиск максимального внутреннего произведения)

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

Mahalanobis distance (Расстояние Махаланобиса)

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

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

Процесс сжатия данных путем замены исходных значений (векторов) ссылками на ограниченный набор предопределенных значений (записей в кодовой книге). Позволяет снизить объем памяти и ускорить вычисления.

Query Covariance Matrix (Ковариационная матрица запросов)

Матрица, описывающая распределение данных в примерах запросов. Используется при кластеризации на основе расстояния Махаланобиса.

Subspace / Chunk (Субпространство / Фрагмент)

Часть вектора, полученная путем его разделения на несколько блоков. Квантование выполняется независимо в каждом субпространстве.

Vector (Вектор)

Математическое представление элемента данных (документа, запроса), часто в виде массива чисел (например, эмбеддинг).

Violated Constraints (Нарушенные ограничения)

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

Ключевые утверждения (Анализ Claims)

Claim 1 (Независимый пункт): Описывает офлайн-процесс подготовки базы данных.

1. Система переупорядочивает элементы векторов, используя случайное вращение (random rotation).
2. Каждый переупорядоченный вектор проецируется (разделяется) на K субпространств.
3. Для каждого субпространства генерируется кодовая книга (codebook). Генерация происходит с учетом ограничений (constraints), основанных на примерах запросов (example queries).
4. Каждому субпространству каждого элемента присваивается запись в соответствующей кодовой книге. Эти присвоения формируют квантованный элемент (quantized search item).
5. Кодовые книги и квантованные элементы сохраняются.

Claim 3 (Зависимый от 1): Описывает процесс онлайн-поиска.

1. Элементы вектора запроса переупорядочиваются с использованием того же случайного вращения.
2. Переупорядоченный вектор запроса проецируется на те же K субпространств.
3. Для каждого квантованного элемента вычисляется внутреннее произведение между субпространством запроса и соответствующей записью кодовой книги.
4. Вычисляется оценка сходства (similarity score) путем суммирования внутренних произведений по всем субпространствам.
5. Предоставляются элементы с наивысшими оценками.

Claim 5 (Зависимый от 1): Детализирует генерацию кодовой книги через кластеризацию.

Генерация включает кластеризацию субпространств элементов, нахождение центра кластера (cluster center) для каждого кластера и сохранение этого центра как записи в кодовой книге.

Claim 7 (Зависимый от 5): Уточняет метод кластеризации.

Кластеризация выполняется с использованием целевой функции, зависящей от задачи (task-dependent objective function), обученной предсказывать кластеры с использованием примеров запросов.

Claim 18 (Независимый пункт): Описывает альтернативный метод, фокусируясь на оптимизации.

1. Генерация субпространств из элементов базы данных.
2. Обучение кодовой книги для каждого субпространства путем оптимизации task-dependent objective function, которая минимизирует ошибку квантования в рамках мягких ограничений (soft constraints), установленных примерами запросов.
3. Обучение включает итеративное выявление нарушенных ограничений (violated constraints) и корректировку кодовых книг.
4. Проецирование вектора запроса.
5. Использование квантованных элементов и кодовых книг для выполнения поиска по внутреннему произведению.
6. Предоставление результатов с наивысшими оценками.

Где и как применяется

Изобретение является частью инфраструктуры, обеспечивающей эффективное выполнение векторного поиска.

INDEXING – Индексирование и извлечение признаков
На этом этапе происходит офлайн-обработка данных. Система использует исходные векторы документов (например, эмбеддинги, сгенерированные другими системами) и Example Queries для обучения кодовых книг и выполнения квантования. Результат (Quantized Search Items и Codebooks) сохраняется в индексе, заменяя или дополняя исходные векторы.

RANKING – Ранжирование (L1/L2 Retrieval)
Это основная область применения патента. На этапе отбора кандидатов (L1) или легковесного ранжирования (L2) система должна быстро найти документы, чьи векторы наиболее близки к вектору запроса (задача MIPS). Система использует описанный механизм быстрого аппроксимированного вычисления внутреннего произведения для мгновенного сокращения пространства поиска. Это критически важно для работы Neural Matching.

Входные данные:

• Исходные векторы базы данных (Search Items).
• Примеры запросов (Example Queries) (для оптимизации).
• Вектор входящего запроса (во время поиска).

Выходные данные:

• Кодовые книги (Codebooks).
• Квантованные векторы (Quantized Search Items).
• Список релевантных кандидатов с аппроксимированными оценками сходства (similarity scores) (во время поиска).

На что влияет

• Типы контента и запросы: Влияет на все типы контента и запросы, где применяются методы векторного поиска (например, Neural Matching) для отбора кандидатов. Это охватывает практически весь современный поиск.
• Инфраструктура: Основное влияние — снижение потребления памяти и ускорение вычислений на серверах Google.
• Мобильный поиск: Патент особо отмечает значимость снижения объема памяти для мобильных платформ, где ресурсы ограничены.

Когда применяется

Алгоритм применяется постоянно в процессе ранжирования:

• Офлайн: Периодически, при обновлении индекса и пересчете векторов, для генерации и оптимизации кодовых книг и квантования данных.
• Онлайн: При обработке каждого поискового запроса на этапе отбора кандидатов (L1/L2), когда требуется быстрое сравнение вектора запроса с векторами в индексе.

Пошаговый алгоритм

Процесс А: Офлайн-квантование и генерация кодовых книг

1. (Опционально) Предварительная обработка: Выполнение случайного вращения или случайной перестановки элементов векторов базы данных для равномерного распределения информации.
2. Проекция в субпространства: Разделение каждого вектора на K равных или неравных частей (субпространств).
3. Инициализация кодовых книг: Присвоение записям кодовых книг случайных векторов из соответствующих субпространств.
4. Итеративная оптимизация (Обучение): Повторение следующих шагов до сходимости или достижения лимита итераций:
   1. Поиск нарушенных ограничений: Использование примеров запросов для выявления ситуаций, когда квантование искажает порядок ранжирования (аппроксимация для неверного результата выше, чем для верного).
   2. Корректировка присвоений: Переназначение субпространств векторов на записи кодовой книги (центры кластеров) с учетом нарушенных ограничений и минимизации ошибки.
   3. Корректировка кодовых книг: Обновление значений центров кластеров (записей кодовой книги) с использованием градиентного спуска для минимизации целевой функции.
5. Сохранение: Запись финальных кодовых книг и квантованных представлений векторов в индекс.

Процесс Б: Онлайн-поиск (MIPS)

1. Получение запроса: Система получает вектор запроса.
2. (Опционально) Предварительная обработка: Применение того же случайного вращения или перестановки, что и к векторам базы данных.
3. Проекция в субпространства: Разделение вектора запроса на K частей.
4. (Опционально) Генерация таблицы кодовой книги: Предварительный расчет внутренних произведений между каждым субпространством запроса и всеми возможными записями в соответствующей кодовой книге.
5. Расчет сходства: Для каждого квантованного вектора в базе данных:
   1. Поиск значения: Определение записи кодовой книги, присвоенной каждому субпространству вектора.
   2. Получение внутреннего произведения: Быстрое получение значения внутреннего произведения для этого субпространства (используя таблицу из шага 4 или вычисляя на лету).
   3. Суммирование: Суммирование внутренних произведений по всем K субпространствам для получения аппроксимированной оценки сходства.
6. Возврат результатов: Выбор Топ-N элементов с наивысшими оценками сходства.
7. (Опционально) Переранжирование: Вычисление точного внутреннего произведения для Топ-N кандидатов и их пересортировка.

Какие данные и как использует

Данные на входе

Патент фокусируется на инфраструктуре и использует следующие типы данных:

• Системные/Внутренние данные:
  • Векторы базы данных (Search Items): Высокоразмерные векторы (например, эмбеддинги документов или пользователей), которые необходимо квантовать для эффективного поиска.
• Поведенческие факторы:
  • Примеры запросов (Example Queries): Реальные запросы, используемые в процессе обучения. Они критически важны для оптимизации кодовых книг. Система анализирует их распределение (Query Covariance Matrix) и использует их для выявления и исправления ошибок ранжирования (Violated Constraints), вызванных квантованием.

Патент не упоминает контентные, ссылочные, технические или другие традиционные SEO-факторы, так как оперирует уже на уровне готовых векторных представлений.

Какие метрики используются и как они считаются

• Внутреннее произведение (Inner Product): Основная метрика сходства между векторами, которую система пытается аппроксимировать.
• Ошибка квантования (Quantization Error): Разница между точным и аппроксимированным внутренним произведением. Цель системы — минимизировать эту ошибку.
• Нарушенные ограничения (Violated Constraints): Метрика качества ранжирования при квантовании. Система стремится минимизировать количество случаев, когда порядок ранжирования искажается из-за аппроксимации.
• Расстояние Махаланобиса (Mahalanobis distance): Используется в одном из вариантов кластеризации для генерации кодовых книг. Оно учитывает ковариационную матрицу запросов (Query Covariance Matrix), чтобы адаптировать кластеры под реальное распределение запросов.
• Целевая функция, зависящая от задачи (Task-dependent objective function): Сложная функция, которая оптимизируется для генерации кодовых книг. Она балансирует между минимизацией ошибки квантования и соблюдением ограничений ранжирования, налагаемых примерами запросов.

1. Фокус на инфраструктуре и масштабируемости: Патент описывает инженерные решения для ускорения и снижения ресурсоемкости векторного поиска (MIPS). Это позволяет Google применять сложные нейросетевые модели (такие как Neural Matching) в глобальном масштабе.
2. Адаптивное квантование на основе реальных данных: Ключевой аспект изобретения — использование реальных примеров запросов (Example Queries) для оптимизации процесса квантования. Это не просто сжатие данных, а адаптация инфраструктуры под реальное использование.
3. Минимизация ошибок ранжирования: Оптимизация направлена не только на точность аппроксимации значений, но и на сохранение правильного порядка ранжирования. Система активно ищет и исправляет "нарушенные ограничения" (violated constraints), когда квантование приводит к неверному ранжированию.
4. Необходимость для векторного поиска: Методы, подобные описанным в патенте, являются необходимым условием для работы современных систем поиска, основанных на сравнении эмбеддингов (векторов).
5. Отсутствие прямых SEO-выводов: Патент не содержит информации о факторах ранжирования или методах оценки качества контента. Он оперирует на уровне уже готовых векторов и их эффективной обработки.

Best practices (это мы делаем)

Этот патент носит преимущественно инфраструктурный характер и не дает прямых практических рекомендаций для SEO-специалистов по оптимизации сайтов (контент, ссылки, технические аспекты).

Единственный стратегический вывод:

• Подтверждение важности семантического соответствия: Патент описывает инфраструктуру, необходимую для работы Neural Matching и других систем векторного поиска. Это косвенно подтверждает необходимость фокусироваться на глубинном семантическом соответствии контента интенту пользователя, а не на поверхностной оптимизации под ключевые слова, так как именно семантика кодируется в векторах, которые обрабатывает данная система.

Worst practices (это делать не надо)

Патент не направлен против каких-либо конкретных SEO-тактик или манипуляций.

Стратегическое значение

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

Практические примеры

Практических примеров применения данного патента в SEO-работе нет, так как он описывает внутренние механизмы оптимизации вычислений Google.