Как Google вычисляет семантическую близость запросов, анализируя поведение пользователей при переформулировках

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

Consecutive Queries (Последовательные запросы)

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

Co-occurrence Value (Значение совместной встречаемости)

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

Cost Matrix (Матрица стоимости)

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

Generalized Edit Distance (Обобщенное расстояние редактирования)

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

Historical Data (Исторические данные)

Логи поисковых запросов и сессий пользователей.

Pointwise Mutual Information (PMI) (Поточечная взаимная информация)

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

PMI Normalization (Нормализация PMI)

Процесс масштабирования значения PMI. Патент описывает три типа:

Joint Normalization (Совместная нормализация)

Симметричная метрика. Измеряет долю общей информации, которая является общей для обоих терминов.

Specialization Normalization (Нормализация специализации)

Асимметричная метрика. Дает более высокое значение, если второй термин является специализацией первого (например, "apple" -> "macintosh").

Generalization Normalization (Нормализация обобщения)

Асимметричная метрика. Дает более высокое значение, если второй термин является обобщением первого (например, "apple" -> "fruit").

Transition Cost (Стоимость перехода/замены)

Числовое значение, присваиваемое операции замены одного термина на другой. Обратно пропорционально их семантической близости (PMI). Высокая близость = низкая стоимость.

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

Claim 1 (Независимый пункт): Описывает основной метод определения Transition Costs на основе анализа логов.

1. Система выбирает пары запросов (Q1 и Q2) из пользовательских сессий, которые были поданы последовательно (с возможным небольшим числом промежуточных запросов).
2. Для каждой пары запросов выбираются пары терминов (T1 из Q1, T2 из Q2).
3. Определяется Co-occurrence value для каждой пары терминов. Это включает:
   • Идентификацию набора терминов S1 (есть в Q1, нет в Q2).
   • Идентификацию набора терминов S2 (есть в Q2, нет в Q1).
   • Если T1 принадлежит S1 и T2 принадлежит S2, то Co-occurrence value определяется на основе размера S1 и размера S2.
4. На основе агрегированных Co-occurrence values определяются итоговые Transition Costs.

Claim 2 (Зависимый от 1): Уточняет расчет Co-occurrence value.

Значение обратно пропорционально произведению размера набора S1 и размера S2. Это означает, что если один термин был заменен на один термин (S1=1, S2=1), значение будет 1. Если два термина были заменены на два других (S1=2, S2=2), значение для каждой из 4 возможных пар будет 1/(2*2) = 0.25.

Claim 3 (Зависимый от 1): Детализирует расчет Transition Costs.

1. Агрегирование Co-occurrence values для пары терминов по всем логам.
2. Определение вероятности совместной встречаемости этой пары терминов (это основа для расчета PMI).
3. Определение Transition Cost на основе этой вероятности.
4. Сохранение стоимости в Cost Matrix.

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

1. Выбор пар запросов и определение Co-occurrence values (аналогично Claim 1).
2. Определение Transition Costs (аналогично Claim 3, включая сохранение в Cost Matrix).
3. Нормализация Transition Costs в матрице на основе вероятности того, что первый термин встречается с любым другим термином, И/ИЛИ вероятности того, что второй термин встречается с любым другим термином.

Claim 9 (Зависимый от 8): Уточняет процесс нормализации.

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

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

Изобретение в основном применяется на этапе понимания запросов, но требует предварительной офлайн-обработки данных.

INDEXING / Офлайн-обработка
Компонент Cost Matrix Builder работает офлайн. Он анализирует Historical Data (логи запросов), чтобы рассчитать PMI и Transition Costs между терминами. Результат сохраняется в Transitional Cost Data (Cost Matrix).

QUNDERSTANDING – Понимание Запросов
Основной этап применения. Компонент Query Cost Engine использует предварительно рассчитанную Cost Matrix для оценки семантической близости между текущим запросом пользователя и кандидатами, предоставленными Query Suggestion Engine. Это позволяет ранжировать подсказки по семантической релевантности или принимать решение об автоматическом расширении/замене запроса (Query Expansion).

RANKING – Ранжирование
Механизм напрямую не участвует в ранжировании документов, но он влияет на то, КАКОЙ запрос будет использоваться для ранжирования. Если система решает расширить или заменить исходный запрос на основе низкой стоимости перехода (высокой семантической близости), то для этапа Ranking будет использован измененный запрос.

Входные данные (Офлайн):

• Historical Data (Логи поисковых сессий).

Выходные данные (Офлайн):

• Cost Matrix (Матрица стоимостей переходов между терминами). Возможно, несколько матриц для разных типов нормализации.

Входные данные (Рантайм):

• Текущий запрос пользователя.
• Набор кандидатов для подсказок/расширений.
• Cost Matrix.

Выходные данные (Рантайм):

• Оценка Generalized Edit Distance для каждого кандидата.

На что влияет

• Специфические запросы: Влияет на все типы запросов, где возможны переформулировки, синонимы или уточнения (информационные, транзакционные). Особенно важно для многословных запросов, где семантика комбинации терминов играет ключевую роль.
• Языковые ограничения: Метод не зависит от языка, так как основан на статистическом анализе логов, а не на лингвистических правилах.

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

• Триггеры активации: Активируется каждый раз, когда система генерирует или оценивает поисковые подсказки (включая автодополнение), предлагает связанные запросы ("Related Searches") или рассматривает возможность автоматического расширения запроса (Query Expansion).
• Временные рамки: Расчет Cost Matrix происходит периодически офлайн. Применение матрицы происходит в реальном времени при обработке запроса.

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

Процесс А: Офлайн-генерация Матрицы Стоимости (Cost Matrix)

1. Сбор данных: Получение доступа к Historical Data (логам поисковых сессий).
2. Выбор пар запросов: Идентификация пар последовательных запросов (Q1, Q2) в рамках сессий.
3. Идентификация изменений терминов: Для каждой пары (Q1, Q2):
   • Определить набор S1 (термины в Q1, которых нет в Q2).
   • Определить набор S2 (термины в Q2, которых нет в Q1).
4. Расчет Co-occurrence Value: Для каждой пары терминов (X из Q1, Y из Q2):
   • Если X=Y (идентичное совпадение), значение = 1.
   • Если X в S1 и Y в S2, значение = 1 / (Размер S1 * Размер S2).
   • Иначе, значение = 0.
5. Агрегация данных: Суммирование Co-occurrence Values для каждой пары терминов (X, Y) по всем логам. Получение общего количества N(X,Y).
6. Расчет вероятностей: Вычисление вероятности совместной встречаемости P(X,Y) и индивидуальных вероятностей P(X) и P(Y).
7. Расчет PMI: Вычисление Поточечной Взаимной Информации для каждой пары терминов: