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

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

Geographic Database (Географическая база данных)

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

Entity (Сущность)

Элемент структурированных данных, например, конкретный город, улица или страна. Каждая сущность имеет тип и одно или несколько названий.

Entity Graph (Граф сущностей)

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

Query Log (Лог запросов)

Хранилище ранее введенных пользователями запросов. Используется для анализа частоты форматов и популярности сущностей.

Template (Шаблон)

Определенный порядок типов сущностей в запросе. Например, <STREET, CITY, STATE> или <CITY, ZIPCODE>.

Template Distribution (Распределение шаблонов)

Набор данных, хранящий вероятности того, что произвольный запрос будет соответствовать определенному шаблону. Генерируется из Query Log.

Location Distribution (Распределение локаций)

Набор данных, хранящий вероятности того, что произвольный запрос ссылается на конкретную географическую сущность. Генерируется из Query Log и Geographic Database.

Language Model (Языковая модель)

В контексте патента — это набор вероятных комбинаций названий сущностей с соответствующими оценками (Scores), сгенерированный на основе Template Distribution и Location Distribution. Используется для расчета условных вероятностей и проверки орфографии.

Conditional Probability (Условная вероятность)

Вероятность появления слова при условии, что другое слово уже появилось в запросе (например, P("View" | "Mountain")). Вычисляется на основе Language Model.

R(Q) (Ранг типа сущности)

Числовое значение, присваиваемое типу сущности на основе его специфичности (например, STREET=5, CITY=4). Используется как весовой коэффициент.

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

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

1. Доступ к географической базе данных (сущности, типы, названия, связи) и логу запросов.
2. Генерация Template Distribution из лога запросов: количественная оценка вероятностей шаблонов (упорядоченных наборов типов сущностей).
3. Генерация Geographic Distribution (Location Distribution) из лога запросов: количественная оценка вероятностей того, что запросы ссылаются на конкретные географические сущности.
4. Генерация Language Model на основе Template Distribution и Geographic Distribution. Модель содержит комбинации названий сущностей и связанные с ними оценки (Scores), основанные на вероятности их появления в запросе.
5. Хранение Language Model.

Claim 2 и 3 (Зависимые): Описывают применение сгенерированной модели.

1. Вычисление условных вероятностей (Conditional Probabilities) появления слов в запросах на основе Language Model (Claim 2).
2. Применение в реальном времени (Claim 3): получение запроса, генерация альтернативного варианта, вычисление вероятностей обоих запросов с использованием условных вероятностей. Если вероятность альтернативы выше, она предлагается пользователю.

Claim 4 (Зависимый): Детализирует вычисление оценки (Score) для пары названий в языковой модели.

Оценка для пары (Название Сущности 1, Название Сущности 2) вычисляется с использованием: (a) вероятности соответствующего шаблона из Template Distribution и (b) вероятности Сущности 1 из Geographic Distribution.

Claim 7 (Зависимый): Описывает процесс выбора комбинаций для включения в языковую модель.

1. Для первой сущности определяется ее тип.
2. Идентифицируется набор связанных типов (related types). (Согласно описанию патента, это типы, которые следуют за типом первой сущности в шаблонах из Template Distribution).
3. Идентифицируется набор соседних сущностей (neighboring geographic entities), которые связаны с первой сущностью (в графе сущностей) и имеют тип из набора связанных типов.
4. Генерируются пары названий первой сущности и названий соседних сущностей.

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

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

INDEXING / Офлайн-обработка данных
Основная часть работы происходит офлайн:

• Анализ Geographic Database и построение Entity Graph.
• Анализ Query Logs.
• Генерация Template Distribution и Location Distribution.
• Генерация Language Model.
• Вычисление и сохранение Conditional Probabilities.

QUNDERSTANDING – Понимание Запросов
На этом этапе система применяет сгенерированную модель в реальном времени (Query Spell Check module):

• Интерпретация входящего запроса.
• Генерация вариантов запроса (например, с помощью правил редактирования).
• Оценка вероятности исходного запроса и его вариантов с использованием предварительно рассчитанных Conditional Probabilities.
• Выбор наиболее вероятного варианта в качестве предполагаемого намерения пользователя (Spelling Correction).

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

• Geographic Database (Сущности, типы, названия, связи).
• Query Log (Исторические запросы).

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

• Template Distribution.
• Location Distribution.
• Language Model.
• Таблица Conditional Probabilities.

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

• Запрос пользователя.
• Таблица Conditional Probabilities.

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

• Альтернативные (исправленные) варианты запроса с более высокой вероятностью.

На что влияет

• Конкретные типы контента и домены: Патент фокусируется на доменах со структурированными данными. Основной пример — географические данные (Local SEO, карты). Однако упоминается применимость к другим доменам: имена людей, медицина, биология, химия, фармацевтика.
• Специфические запросы: Влияет на запросы, содержащие названия сущностей из этих доменов, особенно если они содержат орфографические ошибки, опечатки или нестандартные форматы.
• Языковые и географические ограничения: Система учитывает региональные особенности. В патенте упоминается, что для разных локалей (locales) могут использоваться отдельные логи запросов и генерироваться отдельные Template Distributions, так как форматы адресов различаются (например, США vs Россия).

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

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

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

Процесс А: Генерация распределений (Офлайн)

1. Сбор данных: Получение доступа к Geographic Database и Query Log.
2. Генерация Template Distribution:
   1. Для каждого запроса в Query Log идентифицируется соответствующий шаблон (порядок типов сущностей).
   2. Подсчитывается количество запросов, соответствующих каждому уникальному шаблону.
   3. Счетчики нормализуются для получения вероятности каждого шаблона.
3. Генерация Location Distribution:
   1. Для каждой сущности в Geographic Database идентифицируются запросы в Query Log, содержащие одно из названий этой сущности.
   2. Проверяется, действительно ли эти запросы относятся к данной сущности (например, результаты запроса попадают в регион сущности – это разрешает неоднозначности).
   3. Подсчитывается количество подтвержденных запросов для каждой сущности.
   4. Счетчики нормализуются для получения вероятности упоминания каждой сущности.

Процесс Б: Генерация Языковой Модели (Офлайн)

1. Инициализация: Для каждой сущности E в Geographic Database:
2. Определение связанных типов: Определяется тип сущности E (например, STREET). Идентифицируется набор связанных типов $S_R$ — типы, которые следуют за типом E в шаблонах из Template Distribution (например, CITY, POSTAL_CODE).
3. Определение соседей: Идентифицируется набор соседних сущностей $S_N$, которые связаны с E в графе сущностей и имеют тип из $S_R$.
4. Генерация комбинаций: Создаются все пары названий, включающие название E и названия сущностей из $S_N$.
5. Расчет оценок (Scoring): Каждой комбинации (Q) присваивается оценка по формуле: $P(T(Q)) * P(L(Q)) * R(Q)$.
6. Сохранение: Комбинации и их оценки сохраняются в Language Model.

Процесс В: Расчет условных вероятностей (Офлайн)

1. Обработка корпуса: Language Model рассматривается как корпус документов, где каждая комбинация — это предложение, а ее оценка определяет частоту встречаемости.
2. Токенизация и Подсчет N-грамм: Предложения разбиваются на токены (слова) и подсчитывается частота встречаемости различных N-грамм.
3. Расчет вероятностей: Вычисляются условные вероятности. Например, P(w2|w1) = P(w1 w2) / P(w1).

Процесс Г: Проверка орфографии (Онлайн)

1. Получение запроса: Система получает запрос Q от пользователя.
2. Генерация вариантов: Генерируются варианты запроса (например, с использованием правил редактирования, основанных на типичных ошибках).
3. Оценка вероятностей: Вероятность исходного запроса и каждого варианта вычисляется как произведение условных вероятностей его слов (используя данные Процесса В).