Как Яндекс борется с переобучением и смещением в ранжирующих моделях (CatBoost) с помощью метода «Не заглядывать вперед»

Описание

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

Патент решает фундаментальные проблемы в обучении моделей машинного обучения (ML): переобучение (overfitting) и смещение модели (model bias). В частности, он устраняет проблему «утечки данных» (data leakage) или «утечки информации» (information leakage), которая возникает, когда модель при обучении непреднамеренно использует информацию о целевом значении текущего объекта или будущих объектов. Это улучшает способность модели к обобщению (generalization) на новых данных. Также патент решает проблему вычислительной сложности (квадратичной сложности $N^2$), возникающей при применении этого подхода к градиентному бустингу.

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

Запатентован метод расчета Параметра Качества Прогнозирования (Prediction Quality Parameter) во время обучения моделей на основе деревьев решений (включая ансамбли, такие как Градиентный Бустинг). Суть изобретения заключается в применении парадигмы «Не заглядывать вперед» (Do not look ahead). Качество прогноза для обучающего объекта рассчитывается с использованием только тех объектов, которые предшествуют ему в строго упорядоченном списке.

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

Механизм работает следующим образом:

1. Обучающие объекты упорядочиваются (по времени или случайно, если временной связи нет). Этот порядок фиксируется.
2. При расчете качества прогноза для объекта во время построения дерева используются только данные (целевые значения) тех объектов, которые расположены раньше в списке и попали в тот же лист дерева.
3. Для эффективного применения в Градиентном Бустинге (чтобы избежать сложности $N^2$) список разбивается на иерархию «чанков» (Chunks). Аппроксимации (предсказания предыдущих деревьев) рассчитываются на основе этих чанков, что позволяет сохранить почти линейную сложность вычислений, соблюдая принцип «Не заглядывать вперед».

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

Высокая. Описанная методология является одним из ключевых элементов библиотеки CatBoost, разработанной Яндексом и активно используемой как внутри компании для ранжирования, так и вовне. Борьба с переобучением и смещением данных критически важна для современных систем машинного обучения.

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

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

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

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

Approximation (Аппроксимация / Параметр Аппроксимации Качества Прогнозирования)

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

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

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

Chunks (Чанки)

Подмножества упорядоченного списка обучающих объектов. Используются при реализации Градиентного Бустинга для эффективного расчета аппроксимаций с соблюдением принципа «Не заглядывать вперед», снижая вычислительную сложность с квадратичной до почти линейной.

Decision Tree (Дерево Решений)

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

«Do not look ahead» paradigm (Парадигма «Не заглядывать вперед»)

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

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

Система, используемая для генерации модели прогнозирования (например, CatBoost).

Ordered List of Training Objects (Упорядоченный Список Обучающих Объектов)

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

Overfitting (Переобучение) / Data Leakage (Утечка данных)

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

Prediction Quality Parameter (Параметр Качества Прогнозирования)

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

Target (Целевое значение)

Фактическое значение (метка), связанное с обучающим объектом, которое MLA пытается предсказать (например, оценка релевантности документа).

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

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

Claim 1 (Независимый пункт): Описывает базовый метод «Не заглядывать вперед» для одного дерева решений.

1. Система получает набор обучающих объектов (документ + целевое значение).
2. Объекты организуются в упорядоченный список (определяя предшествующие и последующие объекты).
3. Объекты пропускаются через дерево решений (категоризируются в дочерние узлы/листья).
4. Генерация Prediction Quality Parameter для данного объекта выполняется с использованием только целевых значений тех обучающих объектов, которые встречаются до данного объекта в упорядоченном списке.

Claim 14 (Независимый пункт): Описывает применение метода «Не заглядывать вперед» к ансамблю деревьев (Градиентный Бустинг).

1. Шаги 1-3 аналогичны Claim 1 (Получение, Упорядочивание, Спуск).
2. Генерация Prediction Quality Approximation Parameter (аппроксимации) для данного объекта основывается на двух компонентах:
   1. Целевых значениях только тех обучающих объектов, которые встречаются до данного объекта.
   2. Prediction Quality Approximation Parameters (предсказаниях предыдущих деревьев в ансамбле) для данного обучающего объекта.

Claim 16 (Зависимый от 15/14): Решает проблему вычислительной сложности (проблема $N^2$, упомянутая в описании), возникающую при расчете аппроксимаций в Градиентном Бустинге.

• Расчет параметров аппроксимации (упомянутых в 14b) включает разделение упорядоченного списка обучающих объектов на множество чанков (chunks), организованных как минимум в два уровня.

Claim 20 (Зависимый от 19/16/15/14): Определяет, как используются чанки для поддержания эффективности.

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

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

Этот патент не применяется к фазам поиска в реальном времени (CRAWLING, INDEXING, QUERY PROCESSING, RANKING, BLENDER).

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

Алгоритм используется системой MLA (например, серверами, обучающими модель) для расчета Prediction Quality Parameter. Этот параметр направляет выбор признаков (features) и разделений (splits) при построении деревьев решений.

На что влияет

• Патент влияет на надежность (robustness) и способность к обобщению (generalizability) результирующей модели ранжирования. Уменьшая переобучение, он направлен на то, чтобы модель хорошо работала на невиданных данных (новых запросах и документах) и была менее склонна к изучению ложных корреляций, присутствующих только в обучающих данных.
• Он не нацелен на конкретные типы контента, ниши или типы запросов; это общая методология ML, применяемая к обучающим данным, используемым Яндексом.

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

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

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

Процесс А: Одно Дерево Решений (Claim 1)

1. Инициализация: Доступ к набору обучающих объектов (документ + целевое значение).
2. Упорядочивание: Организация объектов в упорядоченный список. Если временная связь есть, используется она. Если нет — генерируется случайный порядок, который фиксируется как прокси времени.
3. Построение дерева (Итерация): Выбор потенциальной комбинации признака и разделения (feature/split) для узла дерева.
4. Спуск объектов: Пропуск обучающих объектов через дерево в соответствии с установленным порядком. Каждый объект попадает в определенный лист.
5. Расчет качества (Без заглядывания вперед): Для каждого объекта рассчитывается Prediction Quality Parameter. Критически важно: расчет основывается ТОЛЬКО на целевых значениях тех объектов, которые (i) находятся раньше в упорядоченном списке И (ii) попали в тот же лист.
6. Агрегация: Индивидуальные параметры качества агрегируются (например, усредняются) для получения оценки качества листа, затем узла и, наконец, всего уровня дерева для данной комбинации признака/разделения.
7. Выбор лучшего разделения: Повторение шагов 3-6 для всех возможных комбинаций. Выбирается та комбинация, которая дает наилучший агрегированный параметр качества.

Процесс Б: Ансамбль / Градиентный Бустинг (Claims 14, 16, 20)

1. Инициализация и Упорядочивание: Аналогично Процессу А.
2. Разбиение на чанки: Упорядоченный список разбивается на иерархию chunks (например, чанки по 100, 200, 400 объектов) для эффективного расчета аппроксимаций.
3. Расчет Аппроксимаций: Для каждого объекта рассчитываются аппроксимации (предсказания предыдущих деревьев) в контексте разных чанков.
4. Построение дерева (Итерация) и Спуск: Аналогично Процессу А.
5. Расчет качества (С учетом Аппроксимаций): Для текущего объекта рассчитывается Prediction Quality Approximation Parameter. Он зависит от:
   • Целевых значений предыдущих объектов в том же листе.
   • Аппроксимаций (предсказаний предыдущих деревьев) для этих предыдущих объектов.
6. Эффективное использование Аппроксимаций (Anti-$N^2$): При использовании аппроксимаций (шаг 5) выбирается аппроксимация, рассчитанная на основе самого большого чанка, который НЕ содержит текущий объект (т.е. не содержит данных из «будущего» текущего объекта).
7. Агрегация и Выбор: Аналогично Процессу А.

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

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

• Система использует Обучающие Объекты (Training Objects). Каждый объект содержит:
  • Индикацию документа (и связанных с ним признаков, хотя сами признаки не являются фокусом этого патента).
  • Целевое значение (Target), связанное с документом (например, метка релевантности, присвоенная асессором).
• Для Градиентного Бустинга также используются Аппроксимации (Approximations) (предсказания предыдущих деревьев) для обучающих объектов.

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

• Prediction Quality Parameter (для одного дерева) / Prediction Quality Approximation Parameter (для ансамбля).
• Патент не определяет конкретную формулу для этого параметра, но указывает, что он рассчитывается на основе целевых значений (targets) и, в случае ансамблей, предыдущих аппроксимаций (approximations).
• Ключевым ограничением является то, что используются только данные объектов, предшествующих текущему объекту в упорядоченном списке.
• В описании патента ([0060], но не в Claims) приводится пример формулы для расчета аппроксимации:
  $$f(x) = \sum_{i=1}^{k} f(t_i) + \sum_{i=1}^{k} g(approx_i)$$
  Где i=1…k – это обучающие объекты, которые (i) попали в тот же лист, что и объект x, И (ii) расположены до объекта x в упорядоченном списке.

Выводы

1. Фундаментальная методология обучения: Патент описывает ключевую методологию обучения ML-моделей Яндекса (в частности, CatBoost), которая направлена на борьбу с переобучением и смещением данных. Это не алгоритм ранжирования, а способ сделать алгоритм ранжирования более надежным.
2. Принцип «Do not look ahead»: Основной механизм — использование строгого упорядочивания обучающих данных (даже если оно искусственное/случайное) для симуляции временного потока. Это предотвращает утечку информации из «будущего» в «прошлое» во время обучения.
3. Решение проблемы сложности в Градиентном Бустинге: Патент решает сложную техническую проблему эффективной реализации этого подхода (борьба с квадратичной сложностью $N^2$) с помощью иерархического механизма «чанков» (Chunks).
4. Инфраструктурный характер: Это чисто инфраструктурный патент. Он не дает прямых инсайтов о факторах ранжирования, поведенческих метриках или SEO-тактиках.

Практика

Патент скорее инфраструктурный и не дает практических выводов для SEO.

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

• Прямых рекомендаций для SEO из этого патента нет.
• Понимание этого патента подтверждает, что Яндекс инвестирует значительные ресурсы в сложные методологии машинного обучения для создания надежных, обобщающих моделей ранжирования (robust models).
• Это подчеркивает долгосрочную стратегическую важность создания качественного контента и обеспечения положительного пользовательского опыта. Именно такие сигналы (в конечном итоге, через оценки асессоров или поведенческие логи) формируют обучающие данные (Training Objects и Targets) для этих сложных моделей.

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

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

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

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

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

Практических примеров для SEO нет, так как патент описывает внутренний процесс обучения модели машинного обучения, а не ее применение в ранжировании.

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