Как Google оптимизирует скорость и точность векторного поиска (MIPS) с помощью локального ортогонального разложения (LOD)

Описание

Какую задачу решает

Патент решает техническую проблему эффективности и точности (Recall) при выполнении Maximum Inner Product Search (MIPS) в больших базах данных векторных эмбеддингов. MIPS — это фундаментальная операция для поиска семантически похожих элементов (документов, изображений). Для ускорения поиска используются методы аппроксимации (например, IVFADC), которые сжимают векторы (квантование). Однако стандартные методы часто исходят из неверного предположения о равномерном распределении данных (остаточных векторов), что приводит к ошибкам в оценке сходства и снижению качества поиска.

Что запатентовано

Запатентован метод индексации и поиска, основанный на Local Orthogonal Decomposition (LOD). Суть изобретения заключается в разложении остаточного вектора (разницы между вектором документа и центром его кластера) на две ортогональные компоненты: параллельную заданному направлению и перпендикулярную ему. Эти компоненты квантуются (сжимаются) независимо и с использованием разных методов (например, скалярное квантование для параллельной и мультимасштабное квантование для перпендикулярной). Это позволяет более точно аппроксимировать сходство векторов, учитывая неравномерное распределение данных.

Как это работает

Система работает в два этапа: индексация и обработка запроса.

Индексация (Офлайн):

1. База данных векторов разбивается на разделы (partitions), каждый со своим центром.
2. Для каждого вектора вычисляется остаток (residual term).
3. Применяется LOD: остаток раскладывается на параллельную и перпендикулярную компоненты относительно заданного направления.
4. Компоненты квантуются разными методами (например, SQ/UQ и MSQ) и сохраняются в индексе.

Обработка запроса (Онлайн):

1. Система определяет разделы, наиболее близкие к вектору запроса.
2. В этих разделах система быстро вычисляет приблизительное внутреннее произведение (сходство), используя сохраненные квантованные параллельные и перпендикулярные компоненты.
3. Результаты с наибольшим сходством (net inner product) возвращаются как лучшие кандидаты.

Актуальность для SEO

Высокая. Современный поиск Google (включая Neural Matching) в значительной степени полагается на векторные эмбеддинги (созданные моделями типа BERT, MUM) для понимания семантической близости. Оптимизация MIPS критически важна для обеспечения скорости и точности поиска в реальном времени. Этот патент описывает конкретное инфраструктурное улучшение для повышения качества векторного поиска.

Важность для SEO

Влияние на SEO — косвенное/инфраструктурное (5/10). Патент не вводит новые факторы ранжирования и не предлагает тактик для SEO-специалистов. Он описывает внутренние математические методы оптимизации поиска по векторному сходству. Однако он имеет стратегическое значение, так как подтверждает фундаментальную роль семантического поиска, основанного на эмбеддингах. Понимание этого механизма подчеркивает, что ранжирование на этапе отбора кандидатов основано на математической близости векторов, что делает качество и семантическую глубину контента приоритетом.

Детальный разбор

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

Asymmetric Distance Computation (ADC)

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

Codeword (Кодовое слово) / Center Element

Вектор, представляющий центр раздела (partition) или кластера. Используется как точка отсчета для вычисления остаточных векторов.

Embeddings (Эмбеддинги)

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

Inverted File (IVF)

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

IVFADC

Фреймворк поиска, сочетающий Inverted File для грубого разделения и ADC для оценки остатков.

Local Orthogonal Decomposition (LOD)

Ядро изобретения. Метод разложения остаточного вектора на две компоненты: параллельную заданному направлению (v) и перпендикулярную ему.

Maximum Inner Product Search (MIPS)

Задача поиска элемента в базе данных, который максимизирует внутреннее произведение (Inner Product) с вектором запроса. Служит мерой семантического сходства.

Multiscale Quantization (MSQ)

Сложный метод квантования, применяемый в патенте к перпендикулярной компоненте. Включает матрицу вращения (Rotation Matrix) и масштабный коэффициент (Scale Factor).

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

Процесс сжатия векторов для экономии памяти и ускорения вычислений.

Residual Term (Остаточный вектор, rₓ)

Разница между исходным вектором элемента базы данных (x) и центром его раздела (cᵢ). $r_x = x — c_i$.

Scalar Quantization (SQ) / Uniform Quantization (UQ)

Простые методы квантования скалярных (одномерных) значений. Применяются в патенте к параллельной компоненте.

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

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

1. Система получает элементы базы данных и данные о направлении (direction data).
2. Генерируются разделы (partitions), каждый с центральным элементом.
3. Для каждого элемента вычисляется остаточный член (residual term).
4. Выполняется LOD: Применяются операции проекции к остаточному члену на основе заданного направления, создавая первую (параллельную) и вторую (перпендикулярную) компоненты.
5. Выполняется первая операция квантования на параллельной компоненте.
6. Выполняется вторая, отличающаяся от первой, операция квантования на перпендикулярной компоненте.
7. Квантованные компоненты и центральный элемент сохраняются в индексе.

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

Вторая операция квантования является мультимасштабным квантованием (multiscale quantization), которое включает коэффициент масштабирования (scale factor) и матрицу вращения (rotation matrix).

Claim 11 (Зависимый от 1): Уточняет метод квантования для параллельной компоненты.

Первая операция квантования может включать выполнение равномерного квантования (uniform quantization) на разнице, связанной с параллельной компонентой.

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

1. Система получает запрос.
2. Вычисляются внутренние произведения запроса с центрами разделов (center inner products).
3. Выбирается подмножество наиболее близких разделов.
4. Для каждого элемента в выбранных разделах генерируются параллельное (parallel inner product) и перпендикулярное (perpendicular inner product) внутренние произведения, используя соответствующие квантованные компоненты.
5. Вычисляется чистое внутреннее произведение (net inner product) как сумма центрального, параллельного и перпендикулярного произведений. Это показатель сходства.
6. Выбираются и возвращаются элементы с наибольшим сходством.

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

Изобретение относится к инфраструктуре векторного поиска и затрагивает этапы индексирования и ранжирования (на уровне отбора кандидатов).

INDEXING – Индексирование и извлечение признаков
На этом этапе система обрабатывает векторные эмбеддинги контента (полученные, например, от нейросетевых моделей) и создает сжатый индекс для быстрого поиска. Процесс включает партиционирование базы данных (VQ), вычисление остатков, применение LOD и дифференциальное квантование (SQ/UQ + MSQ).

RANKING – Ранжирование (L1 Retrieval / Отбор кандидатов)
На этом этапе система использует созданный индекс для быстрого отбора кандидатов в ответ на запрос. Когда поступает вектор запроса, механизм IVFADC, оптимизированный с помощью LOD, используется для быстрой оценки приблизительного сходства (Approximate MIPS). Это позволяет мгновенно сократить миллиарды документов до нескольких тысяч семантически близких кандидатов.

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

• Индексация: Векторные эмбеддинги элементов базы данных.
• Поиск: Вектор запроса и сжатый индекс.

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

• Индексация: Сжатый индекс (Inverted File с квантованными компонентами LOD).
• Поиск: Список Топ-K элементов с наибольшим приблизительным сходством (net inner product).

На что влияет

• Типы контента и форматы: Влияет на любой контент, представленный в виде плотных векторных эмбеддингов: веб-страницы, текст (Passage Ranking), изображения (визуальное сходство), видео, товары.
• Специфические запросы: Улучшает качество обработки запросов, где важна семантическая близость (например, сложные информационные запросы, системы вопросов и ответов, Neural Matching).
• Ниши, языки, география: Ограничений нет. Это универсальный математический метод оптимизации.

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

Алгоритм применяется всегда, когда система выполняет широкомасштабный поиск по векторному сходству (MIPS) для отбора кандидатов на ранжирование. Это стандартный механизм в современных системах векторного поиска.

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

Процесс А: Индексация базы данных (Офлайн)

1. Получение данных: Система получает базу данных векторов (X).
2. Грубое партиционирование (VQ/IVF): Векторы кластеризуются для создания разделов (Partitions) и определения центральных точек (Center Points, cᵢ).
3. Определение направления и остатков: Для каждого раздела определяется направление (v) (например, направление центральной точки). Для каждого элемента (x) вычисляется остаточный вектор $r_x = x — c_i$.
4. Локальное ортогональное разложение (LOD): Остаток раскладывается на параллельную и перпендикулярную компоненты относительно направления v. Используются матрицы проекции (например, параллельная матрица $H_v^\parallel = vv^T$ и перпендикулярная $H_v^\perp = I — vv^T$).
5. Дифференциальное квантование:
   • Перпендикулярная компонента квантуется с использованием MSQ (включая матрицу вращения и масштабный коэффициент).
   • Параллельная компонента квантуется с использованием SQ или UQ.
6. Сохранение индекса: Центры разделов и квантованные компоненты остатков сохраняются.

Процесс Б: Обработка запроса (Онлайн)

1. Получение запроса: Система получает вектор запроса (q).
2. Выбор разделов: Вычисляются внутренние произведения между q и всеми центрами разделов (Center IP). Выбираются Топ-K разделов.
3. Подготовка запроса: Если использовалось MSQ, запрос может быть умножен на матрицу вращения (Rotated Query).
4. Вычисление остаточных произведений (ADC): Для элементов в выбранных разделах аппроксимируется внутреннее произведение запроса и остатка:
   • Вычисляется параллельная часть (Parallel IP) с использованием данных SQ/UQ.
   • Вычисляется перпендикулярная часть (Perpendicular IP) с использованием данных MSQ.
5. Агрегация и ранжирование: Вычисляется чистое внутреннее произведение (Net IP): Center IP + Parallel IP + Perpendicular IP.
6. Выбор результатов: Элементы с наибольшими Net IP выбираются как лучшие кандидаты.

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

Патент фокусируется исключительно на обработке числовых векторов и не описывает, как эти векторы генерируются или какие конкретные SEO-факторы (контентные, ссылочные, поведенческие и т.д.) в них закодированы.

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

• Векторные данные (Эмбеддинги): Основные данные — это многомерные числовые векторы, представляющие элементы базы данных и запросы.

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

• Inner Product (Внутреннее произведение): Основная метрика сходства между векторами. Цель системы — эффективно аппроксимировать это значение. Рассчитывается как сумма компонентов: $IP_{\text{net}} = IP_{\text{center}} + IP_{\text{parallel}} + IP_{\text{perpendicular}}$.
• L2 Norm (Норма L2): Используется в процессе квантования и нормализации. В MSQ коэффициент масштабирования может выбираться так, чтобы сохранить норму L2 перпендикулярной компоненты.
• Projected IP Variance (Дисперсия проецируемого IP): Метрика, анализ которой мотивировал разработку LOD. Патент показывает, что эта дисперсия неравномерна по направлениям, что требует дифференцированного подхода к квантованию.
• Recall (Полнота): Метрика качества поиска, используемая для оценки эффективности метода. Показывает долю правильно найденных релевантных элементов.

Выводы

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

1. Фундаментальная роль MIPS и векторного поиска: Патент подтверждает, что MIPS является ключевой операцией для поиска релевантного контента на основе эмбеддингов (Neural Matching). Семантическая схожесть измеряется именно через внутреннее произведение векторов на этапе отбора кандидатов.
2. Сложность инфраструктуры поиска: Google применяет сложные математические методы (LOD, MSQ, VQ) для балансировки скорости, использования памяти и точности (Recall). Поиск сходства — это высоко оптимизированный процесс аппроксимации.
3. Учет структуры данных: Ключевой инсайт патента — данные в векторном пространстве распределены неравномерно. LOD разработан для учета этой неравномерности путем раздельной обработки компонент с разной дисперсией, что повышает точность поиска.
4. Фокус на эффективности: Улучшения направлены на повышение точности поиска при сохранении вычислительной эффективности, что критично для работы в масштабе веба.

Практика

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

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

• Фокус на семантическом соответствии и Topical Authority: Поскольку Google использует высокоточные методы MIPS для поиска семантически похожих документов, стратегия должна быть направлена на создание контента, который полностью покрывает тему и точно соответствует интенту пользователя. Это увеличивает вероятность того, что эмбеддинг вашего контента будет иметь высокое внутреннее произведение с вектором запроса.
• Четкое представление сущностей и их связей: Убедитесь, что контент структурирован так, чтобы нейронные сети (BERT, MUM) могли сформировать точное векторное представление. Используйте структурированные данные, четкую иерархию и явные связи между концепциями. Чем точнее эмбеддинг, тем эффективнее он будет обработан системами типа MIPS/LOD.
• Понимание принципов векторного поиска: Senior SEO-специалисты должны понимать основы векторного поиска. Это помогает интерпретировать изменения в выдаче, вызванные улучшениями в алгоритмах семантического сопоставления.

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

• Игнорирование семантики и фокус на Keyword Stuffing: Манипуляции с текстом, не улучшающие семантическое соответствие, бесполезны. Системы, основанные на MIPS, ищут смысловое сходство на уровне эмбеддингов, а не совпадение терминов.
• Создание поверхностного или несвязного контента: Контент без четкой темы или логической структуры получит «размытый» эмбеддинг. Такие документы с меньшей вероятностью будут выбраны на этапе отбора кандидатов системами, использующими MIPS.

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

Стратегическое значение патента заключается в подтверждении того, что эра поиска по ключевым словам окончательно уступила место эре семантического векторного поиска. Google активно инвестирует в инфраструктуру для поддержки этого направления. SEO-стратегии должны быть адаптированы к среде, где релевантность определяется математической близостью в многомерном семантическом пространстве.

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

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

Вопросы и ответы