Как Яндекс обучает систему исправления опечаток и смены раскладки с помощью искусственно созданных реалистичных ошибок

Описание

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

Патент решает задачу эффективного исправления ошибок ввода пользователя в поисковых запросах. Он адресует два основных типа ошибок: (1) неточный ввод (Inaccurate Keyboard Input), например, из-за близости клавиш, и (2) ввод в неправильной раскладке клавиатуры (Wrong Keyboard Layout). Изобретение предлагает унифицированный подход к обоим типам ошибок, устраняя необходимость в отдельных моделях для каждого типа или в огромных, вручную составленных базах данных исправлений. Цель — повысить релевантность поиска путем точного понимания исходного намерения пользователя.

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

Запатентована система обучения и применения алгоритма машинного обучения (MLA) для коррекции ошибок ввода. Ядром изобретения является метод автоматической генерации обучающих данных: «реалистичных» (положительных) и «нереалистичных» (отрицательных) примеров опечаток. Генерация происходит с использованием алгоритма поиска (упоминается Beam Search), который учитывает статистику корпуса текстов (например, логи запросов) и физические характеристики раскладок клавиатуры.

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

Система работает в двух фазах. На фазе обучения (Training Phase) система берет слово из корпуса текстов и генерирует варианты его написания. Вероятность символа оценивается по двум критериям: частота его появления после префикса в корпусе (Co-occurrence Score) и физическая близость клавиши к оригинальному символу (Penalty Score). Наиболее вероятные варианты маркируются как «реалистичные» опечатки, а отброшенные — как «нереалистичные». Затем MLA обучается различать их, анализируя признаки, такие как частота встречаемости слов в вебе (URL, контент) и клики пользователей по подсказкам. На фазе применения (In-use Phase) входящий запрос пользователя проходит аналогичный процесс генерации кандидатов, которые затем ранжируются обученным MLA для выбора наилучшего исправления.

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

Высокая. Коррекция опечаток и автоматическое переключение раскладки являются критически важными функциями современных поисковых систем, особенно с учетом разнообразия устройств (мобильный ввод) и многоязычной аудитории. Унифицированный подход на основе ML и автоматическая генерация обучающих данных остаются актуальными для повышения эффективности обработки запросов.

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

Влияние на SEO умеренное (4/10). Это инфраструктурный патент, относящийся к этапу QUERY PROCESSING. Он не описывает алгоритмы ранжирования, но критически важен для привлечения трафика. Если система не сможет правильно интерпретировать запрос с опечаткой, связанный с вашим брендом или ключевым словом, вы потеряете трафик. Эффективная работа этой системы гарантирует, что поиск выполняется по корректному запросу.

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

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

Beam Search (Лучевой поиск)

Алгоритм поиска в дереве, упомянутый в описании патента. На каждом уровне сохраняет только ограниченное количество (Top-K) лучших кандидатов, отбрасывая остальные. Используется для эффективной генерации вероятных последовательностей символов (слов).

Candidate Score Value (Оценка кандидата)

Метрика, оценивающая вероятность того, что данный символ является следующим в последовательности. Рассчитывается на основе Co-occurrence Score и может корректироваться Penalty Score.

Co-occurrence Score Value (Оценка совместной встречаемости)

Метрика, основанная на частоте появления символа-кандидата после заданного префикса в корпусе текстов.

Corpus of Text (Корпус текстов)

Большой набор текстовых данных. В контексте патента в качестве основного корпуса предлагается использовать логи поисковых запросов (Search Log Database).

Features (Признаки) / Set of Features

Характеристики пары слов (исходное слово, слово-кандидат), используемые MLA для ранжирования. Включают URL Feature, Word Presence Feature, User-Click Feature.

MLA (Machine Learning Algorithm / Алгоритм машинного обучения)

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

Negative Reformulated Word (Отрицательный пример)

Искусственно сгенерированное слово, помеченное как «нереалистичная» опечатка. Генерируется из кандидатов, отброшенных в процессе генерации (например, Beam Search).

Penalty Score Value (Штрафная оценка)

Метрика, снижающая вероятность символа-кандидата. Основана на физическом расстоянии между клавишей оригинального символа и клавишей символа-кандидата на клавиатуре. Используется для моделирования реалистичности опечатки.

Positive Reformulated Word (Положительный пример)

Искусственно сгенерированное слово, помеченное как «реалистичная» опечатка. Генерируется из Top-K кандидатов в процессе генерации.

Training Pair (Обучающая пара)

Пара слов (Сгенерированная опечатка, Исходное слово) с меткой (Label Value: положительная или отрицательная), используемая для обучения MLA.

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

Патент разделяет процесс на фазу обучения (Training Phase) и фазу применения (In-use Phase). Основной акцент сделан на методологии создания обучающих данных.

Claim 1 (Независимый пункт): Описывает процесс обучения (Training Phase).

1. Получение первого слова из корпуса текстов.
2. Выбор префикса (первых N символов).
3. Определение набора символов-кандидатов для позиции N+1.
4. Присвоение оценки (Candidate Score Value) каждому кандидату, основанной как минимум на совместной встречаемости (co-occurrence) префикса и кандидата в корпусе.
5. Выбор Top-N кандидатов (первое подмножество) и отброшенных кандидатов (второе подмножество).
6. Генерация Positive Reformulated Words (положительных примеров) путем замены N+1 символа на кандидатов из первого подмножества. Формирование положительных обучающих пар с первой меткой.
7. Генерация Negative Reformulated Words (отрицательных примеров) путем замены N+1 символа на кандидатов из второго подмножества. Формирование отрицательных обучающих пар со второй меткой.
8. Обучение MLA: Определение набора признаков (Features) для каждой обучающей пары и ранжирование пар на основе этих признаков.

Это описание автоматизированного процесса создания размеченных данных для обучения ранжировщика исправлений. Ключевым моментом является разделение сгенерированных ошибок на реалистичные (Positive) и нереалистичные (Negative) на основе их вероятности, что позволяет MLA учиться отличать правильные исправления.

Claim 4 и 5 (Зависимые пункты): Уточняют расчет Candidate Score Value.

• В дополнение к Co-occurrence Score вводится Penalty Score.
• Penalty Score рассчитывается на основе физического расстояния между клавишей оригинального символа (N+1) и клавишей символа-кандидата на стандартной раскладке клавиатуры. Если символ отсутствует на раскладке (например, из другого языка), присваивается константное значение.

Это критически важный компонент для генерации «реалистичных» опечаток. Ошибка более вероятна, если клавиши расположены близко (низкий штраф) или если произошла смена раскладки.

Claim 7 (Зависимый пункт): Уточняет признаки (Set of Features), используемые MLA.

Признаки включают: URL feature (наличие слов в URL из базы краулера), Word presence feature (наличие слов в веб-ресурсах) и User-click feature (частота выбора пользователем предложенного исправления).

Claim 9 (Независимый пункт): Описывает процесс применения (In-use Phase).

1. Получение текстовой фразы (запроса) с первым словом.
2. Выполнение шагов, аналогичных Claim 1 (пункты 2-5): выбор префикса, оценка кандидатов, выбор Top-N кандидатов.
3. Генерация слов-кандидатов на исправление. Формирование пар (Исходное слово, Слово-кандидат).
4. Определение признаков (Features) для каждой пары.
5. Ранжирование пар с использованием обученного MLA для определения лучшей пары.
6. Генерация модифицированной текстовой фразы путем замены первого слова на слово-кандидат из лучшей пары.

Во время выполнения запроса система генерирует потенциальные исправления, используя тот же статистический и клавиатурный анализ, что и при обучении, но финальное решение принимает обученный MLA, основываясь на комплексных признаках.

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

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

QUERY PROCESSING – Понимание Запросов
Это основной слой применения. Система коррекции опечаток (Error Correction Application) анализирует входящий запрос пользователя до того, как он будет передан на этапы поиска и ранжирования. Цель — преобразовать потенциально ошибочный ввод в наиболее вероятный корректный запрос.

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

• Search Log Database (Логи запросов): Используются как корпус текстов для расчета Co-occurrence Score (статистика частотности слов и символов) и для извлечения User-Click Feature (как часто пользователи кликали по подсказкам исправлений).
• Crawler Database (База краулера): Используется для извлечения URL Feature (встречаемость слов в URL) и Word Presence Feature (встречаемость слов в контенте веб-ресурсов).

Входные данные: Сырая текстовая строка запроса пользователя.

Выходные данные: Модифицированная (исправленная) текстовая строка запроса или предложенный вариант исправления для пользователя.

На что влияет

• Специфические запросы: Наибольшее влияние оказывается на запросы, подверженные ошибкам: длинные слова, термины, имена собственные, запросы с мобильных устройств (из-за неточного ввода) и запросы, вводимые пользователями, переключающимися между языками (из-за ошибок раскладки).
• Брендовый трафик: Критически важно для корректной обработки опечаток в названиях брендов и продуктов.

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

Алгоритм применяется при обработке практически каждого поискового запроса. В патенте указано, что система может применяться ко всем словам в запросе или только к тем, которые не найдены в словаре.

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

Процесс разделен на две основные фазы.

Фаза А: Обучение (Офлайн)

Этап 1: Генерация обучающих данных (Training Data Generation)

1. Сбор данных: Извлечение слова (например, «apple») из корпуса текстов (Search Logs).
2. Инициализация поиска (Beam Search): Выбор префикса (например, «ap»).
3. Генерация кандидатов: Определение возможных следующих символов (например, ‘a’, ‘o’, ‘p’).
4. Расчет оценок: Для каждого кандидата вычисляется Candidate Score Value:
   1. Co-occurrence Score: Частота встречаемости (например, «apo» vs «apa») в логах.
   2. Penalty Score: Расстояние на клавиатуре между оригинальным символом (‘p’) и кандидатом (‘o’ или ‘a’). ‘o’ ближе к ‘p’, чем ‘a’, поэтому штраф для ‘o’ меньше.
5. Фильтрация (Beam): Выбор Top-K кандидатов с лучшими оценками (например, ‘o’, ‘p’). Отбрасывание остальных (например, ‘a’).
6. Итерация: Повторение шагов 3-5 для следующего символа до конца слова.
7. Формирование примеров:
   • Положительные (Realistic): Слова, полученные по Top-K путям (например, «apole», «applr»).
   • Отрицательные (Unrealistic): Слова, сформированные с использованием отброшенных кандидатов (например, «apale»).
8. Разметка: Формирование Training Pairs с метками: ((«apole», «apple»), Positive), ((«apale», «apple»), Negative).

Этап 2: Обучение модели (MLA Training)

1. Извлечение признаков: Для каждой обучающей пары рассчитываются признаки: URL Feature, Word Presence Feature, User-Click Feature.
2. Обучение: MLA обучается предсказывать метку (Positive/Negative) на основе этих признаков, формируя функцию ранжирования, которая определяет вероятность того, что одно слово является коррекцией другого.

Фаза Б: Применение (Онлайн)

1. Получение запроса: Пользователь вводит запрос (например, «appoe»).
2. Генерация кандидатов: Выполнение Этапа 1 (Beam Search, шаги 2-6) для введенного слова. Генерируется набор кандидатов на исправление (например, «apple», «apolo»).
3. Формирование пар: Создание пар для ранжирования: («appoe», «apple»), («appoe», «apolo»).
4. Ранжирование MLA: Извлечение признаков для этих пар и их ранжирование с помощью обученного MLA.
5. Выбор исправления: Выбор кандидата из пары с наивысшим рангом (например, «apple»).
6. Выполнение поиска: Использование исправленного слова для поиска или его предложение пользователю.

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

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

• Контентные факторы (Текстовые): Тексты исторических поисковых запросов (Corpus of Text) используются для расчета статистики совместной встречаемости (Co-occurrence Score). Тексты веб-ресурсов и URL из базы краулера используются для расчета признаков Word Presence Feature и URL Feature.
• Поведенческие факторы: Данные из логов поиска о взаимодействии пользователей с предложенными исправлениями (клики по подсказкам типа «Возможно, вы искали…»). Используются для расчета User-Click Feature.
• Структурные данные (Технические): Информация о стандартных раскладках клавиатуры (Keyboard Layouts). Используется для расчета Penalty Score.

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

• Candidate Score Value: Комбинированная оценка вероятности символа. Рассчитывается как Co-occurrence Score, скорректированный (уменьшенный) на Penalty Score.
• Co-occurrence Score Value: Частотная характеристика. Определяется путем подсчета частоты, с которой символ-кандидат следует за определенным префиксом в корпусе текстов (логах запросов).
• Penalty Score Value: Метрика, основанная на физической структуре клавиатуры. Рассчитывается как функция расстояния между клавишей оригинального символа и клавишей символа-кандидата. Если клавиши рядом, штраф низкий. Если символ из другой раскладки, применяется константный штраф.
• Признаки для MLA (Features):
  • URL Feature: Частота присутствия обоих слов пары в URL-адресах из базы краулера.
  • Word Presence Feature: Частота присутствия обоих слов пары в контенте веб-ресурсов.
  • User-Click Feature: Частота, с которой при вводе одного слова пары пользователи кликали на предложенное исправление, соответствующее второму слову пары.

Выводы

1. Унифицированный подход к ошибкам ввода: Яндекс разработал единую систему, которая одновременно обрабатывает как физические опечатки (неточный ввод), так и логические ошибки (неправильная раскладка), используя машинное обучение.
2. Автоматическая генерация реалистичных данных: Ключевая инновация патента — метод автоматического создания обучающей выборки «реалистичных» опечаток. Это достигается за счет комбинирования статистики языка (Co-occurrence Score) и физических ограничений ввода (Penalty Score на основе клавиатуры).
3. Важность внешних сигналов для коррекции: Финальная модель (MLA), принимающая решение об исправлении, обучается не только на структуре слов, но и на реальных данных из веба и поведения пользователей. Признаки встречаемости в URL, контенте и кликах по подсказкам определяют, какое слово является «правильным».
4. Инфраструктурное значение: Патент описывает фундаментальный компонент обработки запросов. Хотя он не влияет на ранжирование напрямую, он определяет, по какому именно запросу оно будет производиться.

Практика

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

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

• Обеспечение четкого присутствия ключевых терминов в контенте и URL: Система MLA использует Word Presence Feature и URL Feature для определения корректности слова. Убедитесь, что названия ваших брендов, продуктов и ключевые термины часто и правильно используются в тексте и, где это уместно, в URL. Это помогает системе идентифицировать ваши термины как эталонные (правильные) варианты при обучении и применении модели коррекции.
• Мониторинг опечаток в брендовых запросах: Полезно знать распространенные опечатки и варианты написания вашего бренда (включая ввод в другой раскладке). Хотя система Яндекса автоматизирована, понимание этих вариантов поможет оценить полноту охвата трафика.
• Для мультиязычных сайтов: Обеспечьте четкие языковые сигналы на сайте. Это помогает поисковой системе корректно индексировать контент, что косвенно улучшает качество данных для Word Presence Feature и помогает системе лучше понимать контекст и предполагаемый язык запроса.

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

• Оптимизация страниц под опечатки: Создание отдельных страниц или насыщение текста опечатками не имеет смысла. Система работает на уровне обработки запроса, исправляя его до начала ранжирования.
• Использование изображений вместо текста для важных названий: Если название бренда или продукта представлено только графикой, это ослабляет сигнал Word Presence Feature. Система коррекции может испытывать трудности с подтверждением того, что данный термин является корректным и часто используемым.
• Нечитаемые или запутанные URL: Использование сложных идентификаторов вместо понятных слов в URL ослабляет сигнал URL Feature, который мог бы помочь системе коррекции связать опечатки с правильным написанием термина.

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

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

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

Сценарий 1: Ошибка смены раскладки (Кириллица/Латиница)

1. Ввод пользователя: «zyltrc» (пользователь хотел ввести «яндекс» на кириллице, но использовал латинскую раскладку).
2. Действие системы (Генерация кандидатов): Система генерирует кандидатов. При расчете Penalty Score для символов из другой раскладки используется константный штраф. Статистика Co-occurrence помогает сформировать вероятные слова.
3. Действие системы (Ранжирование MLA): Система формирует пары, например («zyltrc», «яндекс») и («zyltrc», «zytrex»). MLA анализирует признаки. Word Presence Feature и URL Feature для «яндекс» будут очень высокими, а для «zytrex» низкими.
4. Результат: Пара («zyltrc», «яндекс») получает наивысший ранг. Поиск выполняется по запросу «яндекс».

Сценарий 2: Опечатка на мобильном устройстве (Неточный ввод)

1. Ввод пользователя: «appoe» (пользователь хотел ввести «apple»).
2. Действие системы (Генерация кандидатов): Система генерирует кандидатов. При генерации «apple» из «appoe», система видит, что ‘l’ и ‘o’ находятся близко. Penalty Score будет низким, что делает «apple» вероятным кандидатом.
3. Действие системы (Ранжирование MLA): Формируются пары, например («appoe», «apple») и («appoe», «apolo»). MLA анализирует признаки. User-Click Feature может показать, что пользователи часто вводят «appoe» и затем кликают на подсказку «apple». Word Presence Feature для «apple» значительно выше, чем для «apolo».
4. Результат: Пара («appoe», «apple») получает наивысший ранг. Поиск выполняется по запросу «apple».

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