Как Google сегментирует сложные запросы на смысловые компоненты для генерации поисковых подсказок и связанных запросов

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

Component (Компонент запроса)

Сегмент (n-грамма), на который делится исходный запрос. Представляет собой семантически значимую единицу, устойчивую фразу (related phrase) или некомпозиционное соединение (non-compositional compound).

Component Refinements (Компонентные уточнения)

Уточнения (подсказки), сгенерированные для отдельного компонента запроса.

N-gram (N-грамма)

Последовательность из N последовательных токенов (слов или символов) в тексте.

Related Phrase (Связанная фраза / Устойчивая фраза)

N-грамма, термины которой встречаются вместе в тренировочных данных чаще, чем если бы они были независимы друг от друга.

User Preference Data (Данные о предпочтениях пользователей)

Агрегированные данные о поведении: логи запросов, показы (impressions), клики (clicks), время пребывания на документе (dwell time).

Click-Through Rate (CTR)

Метрика для оценки качества кандидата. Рассчитывается как общее количество кликов на документы, показанные в ответ на запрос-кандидат, деленное на общее количество показов этих документов. Ключевой фильтр в Claim 1.

Inverse Document Frequency (IDF, Обратная частота документа)

Мера того, насколько редок или распространен компонент в корпусе документов. Используется для ранжирования кандидатов.

Syntactic Similarity (Синтаксическая схожесть)

Мера схожести написания двух строк, часто измеряемая через редакционное расстояние (edit distance).

Training Data (Тренировочные данные)

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

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

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

1. Система получает запрос (термины в определенном порядке).
2. Запрос делится на множество возможных комбинаций упорядоченных n-грамм.
3. Для каждой комбинации выполняется расчет: определяется вероятность того, что каждая n-грамма является related phrase (встречается вместе чаще, чем случайно). Эти вероятности суммируются.
4. Идентифицируется комбинация с наибольшей суммарной вероятностью.
5. N-граммы этой комбинации идентифицируются как компоненты запроса (например, первый и второй компонент), сохраняя порядок.
6. Для каждого компонента определяются соответствующие компонентные уточнения.
7. Компонентные уточнения объединяются для создания кандидатов. При этом сохраняется порядок: уточнение первого компонента предшествует уточнению второго.
8. Кандидаты фильтруются: для каждого рассчитывается оценка на основе его Click-Through Rate (CTR). Кандидаты с оценкой ниже порога удаляются.
9. Оставшийся набор уточнений предоставляется в ответ на запрос.

Claim 3 (Зависимый от 1): Уточняет расчет вероятности.

Вероятность того, что n-грамма является related phrase, основана на функции её относительной частоты в Training Data.

Claim 5 (Зависимый от 1): Описывает дополнительный механизм ранжирования.

Кандидаты ранжируются по степени общности (commonality) с компонентами исходного запроса, имеющими наивысший IDF.

Claim 6 (Зависимый от 1): Описывает дополнительный механизм фильтрации на основе схожести.

Кандидаты фильтруются на основе Syntactic Similarity с компонентами запроса. Оценка схожести рассчитывается на основе edit distance (редакционного расстояния) между кандидатом и запросом. Кандидаты, не достигающие порога, удаляются.

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

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

INDEXING – Индексирование и извлечение признаков (Офлайн)
На этом этапе рассчитываются данные, необходимые для работы алгоритма: строятся языковые модели на основе Training Data для расчета вероятностей n-грамм; вычисляются значения IDF; агрегируются User Preference Data.

QUNDERSTANDING – Понимание Запросов
Основное применение патента. Component-Based Query Refinement Engine выполняет сегментацию запроса на компоненты, генерацию уточнений, их комбинирование и фильтрацию. Этот процесс может выполняться офлайн для популярных запросов и храниться в базе данных (Refinement Database), либо онлайн.

METASEARCH – Метапоиск и Смешивание
На финальном этапе система извлекает сгенерированные уточнения и формирует блоки поисковой выдачи, такие как «Связанные запросы» (Related Searches) или поисковые подсказки.

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

• Исходный запрос.
• Языковая модель (вероятности n-grams на основе Training Data).
• User Preference Data (CTR, клики, показы).
• Значения IDF для компонентов.

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

• Отфильтрованный и отранжированный список уточнений запроса (Query Refinements).

На что влияет

• Специфические запросы: Наибольшее влияние оказывается на многосоставные запросы, содержащие несколько семантических единиц (например, названия продуктов и атрибуты, имена собственные, сложные понятия: “canon eos 5d mark iv battery life”).
• Конкретные типы контента: Влияет универсально, так как механизм работает на уровне интерпретации запроса, независимо от типа искомого контента.

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

• Условия работы: Алгоритм применяется, когда необходимо сгенерировать набор связанных запросов или поисковых подсказок.
• Триггеры активации: Активируется для запросов, которые могут быть разделены на несколько компонентов. Если система определяет, что запрос состоит только из одного компонента (например, если суммарная вероятность разделенной комбинации не превышает определенный порог), применяются стандартные методы генерации уточнений.

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

Процесс работы Component-Based Query Refinement Engine.

Процесс А: Идентификация компонентов (Сегментация)

1. Разделение на комбинации: Исходный запрос делится на все возможные упорядоченные комбинации n-грамм. (Например, [a b c] делится на {[a],[b],[c]}, {[a b],[c]}, {[a],[b c]}, {[a b c]}).
2. Расчет вероятностей фраз: Для каждой n-граммы определяется вероятность того, что она является related phrase, на основе частоты в Training Data.
3. Суммирование вероятностей: Для каждой комбинации рассчитывается сумма вероятностей её составляющих n-грамм.
4. Выбор лучшей комбинации: Выбирается комбинация с наибольшей суммой вероятностей.
5. Идентификация компонентов: N-граммы из лучшей комбинации идентифицируются как компоненты запроса.

Процесс Б: Генерация и Комбинирование

1. Генерация компонентных уточнений: Для каждого компонента система получает набор уточнений (Component Refinements), используя стандартные методы (например, на основе User Preference Data).
2. Комбинирование уточнений: Система создает кандидатов путем комбинирования уточнений разных компонентов. Комбинации создаются так, чтобы сохранить исходный порядок компонентов запроса.

Процесс В: Фильтрация и Ранжирование

1. Фильтрация по начальной оценке: Кандидаты фильтруются на основе начальных оценок (например, частота запроса, CTR). Кандидаты ниже порога удаляются.
2. Ранжирование по IDF: Компоненты исходного запроса ранжируются по IDF. Кандидаты переранжируются на основе их общности с компонентами, имеющими наивысший IDF.
3. Фильтрация по пользовательским данным: Дополнительная фильтрация на основе сложных метрик User Preference Data (например, взвешенное количество кликов, CTR топовых результатов для кандидата).
4. Фильтрация по синтаксической схожести: Рассчитывается Syntactic Similarity (например, edit distance) между кандидатом и исходным запросом. Кандидаты с низкой схожестью удаляются.
5. Вывод результата: Оставшиеся кандидаты формируют финальный набор Query Refinements.

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

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

• Контентные/Лингвистические данные (Training Data): Большой корпус текстов (веб-страницы, логи запросов, электронные письма, блоги и т.д.). Используются для построения языковой модели и определения частоты n-grams.
• Поведенческие факторы (User Preference Data): Критически важны для генерации и фильтрации. Включают:
  • Логи запросов (частота поиска кандидата).
  • Click-Through Rate (CTR) кандидата.
  • Взвешенные клики (weighted clicks), учитывающие время просмотра документа (dwell time).
  • Клики (clicks) и показы (impressions).
• Системные данные (Corpus Statistics): Данные о корпусе документов, используемые для расчета IDF компонентов.

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

• Вероятность Related Phrase: Рассчитывается на основе относительной частоты n-граммы в Training Data. Используется для сегментации.
• Суммарная вероятность комбинации: Сумма вероятностей Related Phrase для всех n-грамм в комбинации. Используется для выбора лучшей сегментации.
• Initial Score (Начальная оценка): Метрика для первичной фильтрации. Может быть основана на частоте запроса, CTR и т.д.
• Inverse Document Frequency (IDF): Используется для определения важности (специфичности) компонентов исходного запроса.