Как Яндекс конвертирует нечисловые данные (URL, домены, регионы) в ранжирующие сигналы: Ядро алгоритма CatBoost

Описание

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

Патент решает фундаментальную проблему в машинном обучении, известную как переобучение (overfitting), вызванное утечкой целевой переменной (target leakage) при обработке категориальных факторов. Традиционные методы преобразования категорий в числа часто приводят к тому, что модель становится излишне оптимистичной на обучающих данных и плохо работает на новых данных. Патент предлагает робастный метод кодирования, который минимизирует это искажение и повышает надежность и точность прогностических моделей, в частности, алгоритмов ранжирования.

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

Запатентован метод и система для преобразования категориальных факторов в числовое представление для использования в алгоритмах машинного обучения (MLA), в частности, в градиентном бустинге на деревьях решений. Суть изобретения заключается в использовании упорядоченной статистики (Ordered Target Statistics). Числовое значение для категории рассчитывается не по всей выборке сразу, а только на основе исторических данных, предшествующих текущему объекту в специально упорядоченном списке. Этот патент описывает ядро библиотеки CatBoost.

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

Система сначала создает упорядоченный список обучающих объектов. Если у данных нет естественного временного порядка, создается случайный порядок (перестановка/permutation). При расчете числового значения для категориального фактора объекта X система анализирует только те объекты, которые находятся ДО объекта X в этом списке. Она вычисляет статистику (например, отношение числа положительных исходов NumberWINs к общему числу вхождений NumberOCCURENCES этой категории в «прошлом»). Это предотвращает утечку информации. Для повышения стабильности система может обучать несколько моделей (протомоделей) на разных перестановках данных.

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

Чрезвычайно высокая. Описанные в патенте механизмы являются основой библиотеки CatBoost, которая была выпущена Яндексом в 2017 году и является основным алгоритмом машинного обучения, используемым в ранжировании поиска Яндекса (L2/L3) и метриках качества (например, Proxima).

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

Влияние на SEO значительно (7/10), но носит инфраструктурный характер. Патент не описывает конкретные факторы ранжирования, но описывает математический аппарат, с помощью которого Яндекс обрабатывает ВСЕ сигналы, включая критически важные для SEO категориальные факторы (URL, домены, анкоры, регионы). Понимание этого механизма подчеркивает сложность и робастность системы ранжирования Яндекса, делая краткосрочные манипуляции и использование статистических аномалий неэффективными.

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

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

MLA (Machine Learning Algorithm)

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

Ансамбль деревьев решений (Ensemble of decision trees)

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

Градиентный бустинг (Gradient Boosting)

Техника машинного обучения, при которой новые модели (деревья) последовательно добавляются в ансамбль, исправляя ошибки предыдущих.

Категориальный фактор (Categorical Factor)

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

Обучающий объект (Training Object)

Единица данных для обучения модели. Состоит из набора факторов и известного результата (целевой переменной/индикатора события).

Индикатор события (Event Indicator)

Целевое значение. В патенте упоминаются WIN (положительный результат, например, клик или высокая оценка) и LOSS (отрицательный результат).

Упорядоченный список (Ordered List) / Перестановка (Permutation)

Ключевой элемент патента. Последовательность обучающих объектов. Если естественного временного порядка нет, используется случайная перестановка для создания «искусственного времени».

Протомодель (Proto-model)

Одна из нескольких моделей, обучаемых параллельно, каждая на своей уникальной перестановке данных. Используются для выбора наилучшей структуры дерева и снижения переобучения (механизм, известный как Ordered Boosting).

Счетчик (Count)

Числовое представление категориального фактора, вычисленное по формулам патента на основе исторических данных (Ordered Target Statistics).

NumberWINs (Число срабатываний)

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

NumberOCCURRENCES (Число вхождений)

Общее число вхождений данной категории в данных, предшествующих текущему объекту в упорядоченном списке.

$R_{constant}$ (Константа сглаживания)

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

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

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

Claim 1 (Независимый пункт): Описывает основной механизм преобразования (Ordered Target Statistics) с использованием нескольких моделей.

1. Система создает набор моделей (набор моделей) для MLA, каждая основана на ансамбле деревьев.
2. Для КАЖДОЙ модели набор обучающих объектов организуется в соответствующий упорядоченный список (перестановку). Это подразумевает, что у разных моделей списки разные.
3. При создании итерации дерева решений выбирается одна модель и ее упорядоченный список для определения структуры дерева.
4. При обработке категориального фактора для данного объекта его числовое представление создается на основе ТОЛЬКО предыдущих обучающих объектов в этом списке.
5. Расчет основывается на: (i) числе общих вхождений (NumberOCCURENCES) того же значения категории в прошлом и (ii) числе положительных результатов (NumberWINs) для этого значения в прошлом.

Claim 3: Уточняет формулу расчета с использованием константы для сглаживания.

Числовое представление (Count) рассчитывается как:

$$ Count = \frac{Number_{WINS}}{Number_{OCCURENCES}+R_{constant}} $$

Claim 5: Расширяет метод на комбинации категориальных факторов. Числовое представление рассчитывается на основе совместных вхождений и срабатываний для всей комбинации в прошлом.

Claim 10: Уточняет, что если у данных нет присущего временного порядка, используется случайный порядок обучающих объектов.

Claim 13 (Важный для понимания CatBoost): Описывает архитектуру обучения с использованием протомоделей (Ordered Boosting).

1. Набор моделей включает набор протомоделей и итоговую модель.
2. На каждой итерации обучения выбирается наилучшая работающая протомодель (на основе алгоритма проверки).
3. Эта наилучшая протомодель используется для создания дерева решений итоговой модели для данной итерации.

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

Изобретение относится к этапу обучения (Training Phase) моделей машинного обучения, которые затем используются в поиске. Это не алгоритм, работающий в реальном времени при обработке запроса, а фундаментальный механизм подготовки самой ранжирующей формулы (CatBoost).

Офлайн-процессы и обработка данных
Основное применение патента происходит во время обучения моделей на исторических данных. Система взаимодействует с хранилищем обучающих объектов (логи запросов, кликов, оценки асессоров) и инфраструктурой машинного обучения Яндекса.

RANKING – Ранжирование (Уровни L2, L3)
Обученные с помощью этого метода модели (CatBoost) являются основой ранжирования на уровнях L2 и L3. Патент описывает, как именно эти модели учатся интерпретировать категориальные признаки.

Слой Качества (QUALITY LAYER — Proxima)
Метрики качества, такие как Proxima, также часто реализуются как модели CatBoost, и, следовательно, используют описанные механизмы при обучении.

Процесс:

1. Подготовка данных: На вход принимаются обучающие объекты с факторами и целевой переменной.
2. Кодирование (Feature Engineering): На этом этапе происходит ключевой процесс патента — преобразование категориальных факторов в числовые с использованием упорядоченной статистики. Это происходит динамически во время построения деревьев.
3. Обучение модели: Алгоритм градиентного бустинга строит ансамбль деревьев, используя эти преобразованные числовые представления.

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

На что влияет

Алгоритм влияет на интерпретацию моделью любых категориальных факторов. В контексте SEO это критически важно для:

• Идентификаторов ресурсов: Домены, хосты, конкретные URL, структура разделов. Патент позволяет модели эффективно оценивать репутацию этих категорий на основе их исторической производительности без переобучения.
• Текстовых факторов: Тексты запросов, анкоры ссылок, отдельные токены (слова) могут рассматриваться как категориальные факторы высокой мощности.
• Географических и языковых факторов: Регионы, страны, языки.
• Комбинаций факторов: Система позволяет эффективно учитывать взаимодействие факторов (например, репутация Автора + Тематика статьи).
• Ниши и типы контента: Влияет на все ниши, особенно там, где важны категориальные признаки (E-commerce, Локальный поиск, Контентные проекты).

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

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

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

Процесс обучения модели (CatBoost) с использованием описанного механизма:

1. Инициализация: Создается набор протомоделей (например, 3 протомодели) и итоговая модель.
2. Создание перестановок: Для каждой протомодели генерируется уникальный случайный упорядоченный список (перестановка) всего набора обучающих данных.
3. Начало итерации (Построение нового дерева):
   1. Выбор структуры дерева: Случайным образом (или по правилу) выбирается одна из протомоделей. Она используется для определения структуры (выбора факторов и разделений) дерева на текущей итерации.
   2. Расчет числовых представлений (Ordered Target Statistics): При выборе разделений для категориальных факторов используется упорядоченная статистика. Для объекта X в списке модели M1, расчет ведется только по объектам, предшествующим X в списке M1.
   3. Обработка комбинаций (Динамически): Система может создавать и оценивать комбинации факторов «на лету» ([72]) во время построения структуры.
   4. Применение структуры ко всем моделям: Созданная структура дерева копируется во все остальные протомодели.
   5. Расчет значений в листьях: Каждая протомодель рассчитывает значения в листьях, используя СВОЙ упорядоченный список. Значения будут отличаться.
   6. Оценка и выбор лучшей модели (Ordered Boosting): Все протомодели оцениваются (например, по функции потерь).
   7. Обновление итоговой модели: Дерево из наилучшей протомодели добавляется в итоговую модель.
4. Повторение: Переход к следующей итерации (Шаг 3) до достижения критерия остановки.

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

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

Патент не специфицирует конкретные факторы ранжирования, а описывает общий механизм их обработки. На вход подаются обучающие объекты, включающие:

• Категориальные факторы: Любые данные, которые система рассматривает как категории (URL, домены, ID пользователей, тексты запросов, анкоры, регионы, типы страниц и т.д.).
• Числовые факторы: Любые количественные данные (PageRank, возраст документа, количество кликов и т.д.).
• Индикатор события (Целевая переменная): Метка, которую модель учится предсказывать. В патенте упоминаются WIN (положительный результат, например, клик или высокая оценка релевантности) и LOSS (отрицательный результат).

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

Ключевой метрикой является Счетчик (Count) — числовое представление категориального фактора.

Базовая формула (Формула 1 в патенте, Claim 2):

$$ Count = \frac{Number_{WINS}}{Number_{OCCURENCES}} $$

• $Number_{WINS}$: Число положительных исходов для данной категории среди объектов, предшествующих текущему в упорядоченном списке.
• $Number_{OCCURENCES}$: Общее число вхождений данной категории среди объектов, предшествующих текущему.

Формула со сглаживанием (Формула 2 в патенте, Claim 3):

$$ Count = \frac{Number_{WINS}}{Number_{OCCURENCES}+R_{constant}} $$

• $R_{constant}$: Заранее определенное значение (приор), используемое для сглаживания и предотвращения деления на ноль для новых или редких категорий.

Формула для комбинаций факторов (Формула 4 в патенте, Claim 6):

$$Count = \frac{NumberWINs (F1\ and\ F2)}{NumberOCCURENCES (F1\ and\ F2)}$$

Статистика рассчитывается для совместного вхождения значений факторов F1 и F2 в «прошлом».

Методы вычислений:

• Градиентный бустинг (Gradient Boosting): Основной алгоритм обучения.
• Сетки (Grids): В патенте ([79]-[82]) описывается использование предопределенных сеток для определения границ разделения (splits) для вычисленных счетчиков. Это позволяет определять пороги (например, Count > 0.5) «на лету».

Выводы

1. Это патент о CatBoost: Изобретение описывает фундаментальные механизмы (Ordered Target Statistics и Ordered Boosting), лежащие в основе библиотеки CatBoost, которая является главным алгоритмом ранжирования Яндекса.
2. Приоритет — борьба с переобучением и стабильность: Основная цель патента — сделать модель машинного обучения робастной и предотвратить переобучение. Это указывает на то, что Яндекс стремится к созданию стабильных моделей, устойчивых к шуму и манипуляциям.
3. Упорядоченная статистика как ключ: Использование исторических данных на основе искусственно созданного порядка (перестановок) является центральным элементом. Это позволяет эффективно использовать категориальные признаки высокой мощности (например, URL или домены).
4. Историческая производительность определяет ценность фактора: Ценность категориального признака (например, домена или раздела сайта) напрямую зависит от того, насколько успешно (в терминах WIN/LOSS, например, кликов) были объекты с этим признаком в прошлом.
5. Эффект «Холодного старта»: Новые значения категориальных факторов (например, новый раздел сайта или новый автор) не имеют истории. Их начальное значение будет определяться сглаживающим фактором (Приором). Они должны накопить позитивную статистику, чтобы их вес вырос.
6. Сложность модели и комбинации факторов: Система динамически обрабатывает комбинации факторов «на лету» ([72]), что позволяет учитывать сложные взаимодействия между признаками.

Практика

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

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

• Фокус на долгосрочном качестве и стабильных сигналах: Механизм упорядоченной статистики разработан для игнорирования краткосрочных аномалий и шума. Стабильно высокое качество ресурса и положительные поведенческие сигналы (WINs) на длинной дистанции формируют положительное числовое представление для категориальных факторов сайта (домена, URL, разделов).
• Улучшение поведенческих метрик (Целевых переменных): Целевые переменные (WINs), на которых обучается модель (клики, решение задачи пользователя), напрямую влияют на то, как будут закодированы категориальные факторы. Улучшение пользовательского опыта критически важно для обучения модели в пользу вашего сайта.
• Поддержание чистой и логичной структуры сайта (URL): Если части URL используются как категориальные факторы, логичная и стабильная структура помогает системе корректно агрегировать статистику по разделам.
• Стратегия запуска новых разделов: При запуске нового раздела (новое значение фактора) учитывайте эффект «холодного старта». Новый раздел начнет с нейтральной оценки и должен быстро накапливать позитивные сигналы (WINs), чтобы увеличить свой вес в модели.

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

• Попытки краткосрочных манипуляций и накруток: Алгоритм специально разработан для устойчивости к переобучению и статистическим выбросам. Накрутка ПФ будет менее эффективна, так как механизм перестановок и сглаживания минимизирует влияние аномальных событий на итоговую модель.
• Частая смена структуры URL или идентификаторов: Изменение структуры URL или ID категорий, которые используются как категориальные признаки, приведет к потере накопленной положительной истории, так как для системы это будут новые значения факторов («холодный старт»).
• Смешивание качественного и некачественного контента в одной категории: Размещение низкокачественного контента (генерирующего LOSSes) в сильном разделе будет постепенно снижать общую оценку этого категориального фактора, негативно влияя на весь раздел.

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

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

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

Сценарий: Влияние структуры URL на ранжирование

Предположим, структура URL используется как категориальный фактор. У сайта есть два раздела: /blog/ (старый, качественный контент, много кликов/WINs) и /news/ (новый, слабый контент, мало кликов/много LOSSes).

1. Обработка данных: Система упорядочивает исторические данные о посещениях.
2. Расчет Счетчиков (Ordered TS):
   • Для /blog/: Исторически много WINs. Count будет высоким (например, 0.8).
   • Для /news/: Исторически мало WINs. Count будет низким (например, 0.2).
3. Применение в ранжировании: При ранжировании новой страницы /blog/new-post/ модель CatBoost использует высокий Count (0.8) для фактора «Раздел URL», что дает странице буст. Страница /news/new-post/ получит низкий Count (0.2).
4. Действие SEO: Необходимо фокусироваться на улучшении качества контента и ПФ в разделе /news/, чтобы постепенно увеличить количество WINs и тем самым повысить будущий Count этого раздела. Перемещение контента из /blog/ в /news/ может привести к потере преимущества.

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