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

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

Lexical Synonym (Лексический синоним)

Термин, имеющий структурное или лексическое сходство с исходным термином. Примеры: стемминг, акронимы, аббревиатуры, различия в пунктуации, пробелах (Compounding/Decompounding) или диакритических знаках.

Altered Query (Измененный запрос)

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

Pseudostemming (Псевдостемминг)

Агрессивная техника стемминга. Определяет связь, если слова отличаются на одну правку ИЛИ если соотношение длины общего префикса к максимальной длине слова превышает порог (например, 0.5), И при этом Edit-Distance оставшихся частей слова ниже другого порога (например, 0.4).

Edit-Distance (Расстояние редактирования)

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

Session Switching (Переключение в сессии)

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

Common Results (Общие результаты)

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

Pseudo-query (Псевдозапрос)

Шаблон запроса, созданный путем замены фразы на токен. Используется для анализа контекста и поиска пар запросов, различающихся только этой фразой (например, [gm : car prices]).

Evidence Score (Оценка уверенности)

Итоговая оценка, рассчитываемая на основе статистических тестов (например, soft_and), определяющая степень уверенности системы в синонимичности двух терминов.

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

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

1. Система получает запрос с первым термином.
2. Идентифицирует синонимы. Процесс включает:
   1. Определение, удовлетворяют ли первый термин и второй термин (кандидат) критериям, связанным с определенным классом связанных терминов (т.е. являются ли они лексически связанными).
   2. В ответ на это (ДА), система выбирает порог (threshold), который отличается от порога по умолчанию (используемого для терминов без лексической связи).
   3. Генерация оценки (score) для пары терминов путем оценки их взаимосвязи (например, на основе Session Switching и Common Results).
   4. Определение того, что второй термин является синонимом, на основе применения оценки к выбранному (отличному от стандартного) порогу.
3. Генерация измененного запроса (altered query) с использованием второго термина.
4. Обработка измененного запроса.

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

Claim 2 (Зависимый от 1): Уточняет «определенный класс связанных терминов». Это: термины с общим корнем (common stem), различия в пунктуации или пробелах, акронимы, термины в пределах заданного edit-distance, различия в акцентах и аббревиатуры.

Claim 3 и 4 (Зависимые от 1): Уточняют критерии определения лексической связи. Расчет edit-distance (Claim 3) или идентификация общего префикса и сравнение его длины с длиной терминов (Claim 4 – механизм Pseudostemming).

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

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

QUNDERSTANDING – Понимание Запросов
Это основной этап применения патента. Он включает два подпроцесса:

1. Офлайн-генерация базы синонимов: Система анализирует query logs, идентифицирует потенциальные синонимы (статистически и лексически), рассчитывает evidence scores и валидирует синонимы, используя дифференцированные пороги в зависимости от типа связи (лексическая или нет).
2. Онлайн-обработка запроса: Когда пользователь вводит запрос, система обращается к сгенерированной базе синонимов. Если найдены валидированные синонимы, система создает altered queries (путем расширения или замены).

RANKING – Ранжирование
На этом этапе система выполняет поиск по altered queries, чтобы найти документы, соответствующие расширенному пониманию интента.

INDEXING – Индексирование и извлечение признаков
Лексические методы (стемминг, нормализация пунктуации) также могут применяться при индексировании контента для нормализации терминов в индексе.

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

• Логи запросов (Query Logs), включающие User ID, временные метки, текст запроса и списки топовых результатов (для расчета Common Results).
• Алгоритмы лексического анализа (стеммеры, расчет edit-distance и т.д.).

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

• База данных валидированных синонимов с оценками уверенности.
• Altered queries, используемые для поиска.

На что влияет

• Специфические запросы: Наибольшее влияние на запросы, содержащие аббревиатуры, акронимы, термины с вариативным написанием (например, с дефисом или без, слитное/раздельное написание).
• Языковые особенности: Влияет на языки с богатой морфологией (через стемминг и Pseudostemming), языки с диакритическими знаками и языки с составными словами (например, германские языки через Compounding/Decompounding).

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

• Условия (Офлайн): Генерация синонимов активируется при обработке логов запросов. Применение пониженных порогов происходит только тогда, когда система идентифицирует специфическую лексическую связь между терминами.
• Триггеры активации (Онлайн): Когда система обнаруживает в запросе термин, для которого в базе данных существует валидированный синоним (лексический или иной) с достаточной оценкой уверенности.

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

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

1. Сбор данных и подготовка: Сбор логов запросов. Сортировка по User ID и времени для идентификации сессий. Генерация pseudo-queries путем замены фраз на токены.
2. Идентификация кандидатов и сбор статистики: Группировка запросов по pseudo-query. Фразы, которыми они отличаются, становятся кандидатами. Для каждой пары рассчитывается статистика Session Switching и Common Results.
3. Лексический анализ (Детекция): Для каждой пары кандидатов (Термин А, Термин Б) проверяется наличие лексической связи с помощью набора детекторов:
   1. Decompounding/Compounding: Равны ли термины после удаления пунктуации и пробелов?
   2. Acronyms: Совпадает ли Термин А с первыми буквами фразы Термина Б (с учетом edit-distance порога, например, 0.25 от максимальной длины)?
   3. Pseudostemming: Отличаются ли термины на 1 правку? ИЛИ есть ли общий префикс (порог 0.5) и малое edit-distance между остатками (порог 0.4)?
   4. Abbreviations: Равны ли термины после удаления гласных (с учетом edit-distance порога, например, 0.25)?
   5. Diacriticals/Standard Stemming: Являются ли термины вариантами после стандартного стемминга или удаления диакритических знаков?
4. Классификация и Выбор порога:
   • Если на шаге 3 обнаружена лексическая связь: Выбираются пониженные пороги для статистических метрик. (Например, требование Common Results может быть снижено до нуля для акронимов; требование Session Switching может быть снижено в 3 раза для Compounding).
   • Иначе: Используются стандартные (более высокие) пороги.
5. Расчет оценки и Валидация: Расчет итоговой оценки уверенности (Evidence Score) на основе статистики из шага 2. Сравнение оценки с выбранным порогом из шага 4. Если оценка выше порога, синоним валидируется.

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

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

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

• Структурные факторы (Лексические данные): Анализируется структура самих терминов: наличие общих префиксов, расстояние редактирования (edit-distance), наличие пунктуации, пробелов, гласных, диакритических знаков.
• Поведенческие факторы: Используются логи запросов (Query Logs). Ключевой сигнал — Session Switching (частота, с которой пользователи меняют один термин на другой в рамках одной сессии).
• Системные данные: Используются списки топовых результатов для исходного и измененного запросов для расчета метрики Common Results.

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

Лексические метрики (для определения класса связи):

• Edit-distance ratio: Расстояние редактирования, деленное на максимальную длину строк. Пороги, упомянутые в патенте: 0.25 (для акронимов/аббревиатур), 0.4 (для остатков в Pseudostemming).
• Common prefix ratio: Длина общего префикса, деленная на максимальную длину строк. Порог, упомянутый в патенте: 0.5 (для Pseudostemming).

Статистические метрики (для расчета Evidence Score):

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

• frequently_alterable: Доля запросов, для которых измененный запрос также существует в логах.
• frequently_much_in_common: Доля пар запросов, которые имеют достаточное количество общих результатов (например, 3).
• frequently_altered: Частота Session Switching от исходного к измененному запросу.
• high_altering_ratio: Отношение частоты переключения в прямом направлении к обратному.

Функции расчета итоговой оценки:

• Функция масштабирования (Scale function): Используется для нормализации статистических метрик на основе базового (base) и высокого (high) значений.