CatBoost

Материал из MachineLearning.

Версия от 08:27, 26 июня 2026; Nikita Saveliuk (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Статья написана с использованием LLM Claude Opus 4.8 и проверена участником Nikita Saveliuk 12:27, 26 июня 2026 (MSD)

Содержание

1 Историческая справка
2 Постановка задачи
- 2.1 Смещение предсказания
3 Алгоритм
4 Свойства
- 4.1 Преимущества
- 4.2 Ограничения
5 Применение
6 См. также
7 Ссылки
8 Литература

CatBoost (от англ. Categorical Boosting) — алгоритм градиентного бустинга на решающих деревьях, разработанный компанией Яндекс и представленный в открытом доступе в 2017 году^[1]. Метод предназначен в первую очередь для работы с табличными данными, содержащими категориальные признаки, и решает две взаимосвязанные проблемы классического бустинга: корректное кодирование категорий без ручной предобработки и устранение систематического смещения оценки градиента, возникающего из-за того, что одни и те же объекты используются и для построения модели, и для оценки её ошибки.

В отличие от других популярных реализаций бустинга — XGBoost и LightGBM — CatBoost строит обструктурированные (симметричные) деревья и применяет принципиально иную схему вычисления остатков, названную авторами упорядоченным бустингом (англ. ordered boosting). Теоретическим основанием метода служит понятие смещения предсказания (англ. prediction shift): авторы показали, что стандартная процедура бустинга порождает оценку градиента, систематически отклоняющуюся от истинной, и предложили способ построения несмещённой оценки^[1].

Благодаря разумным значениям гиперпараметров «из коробки», встроенной обработке категорий и устойчивости к переобучению на малых выборках CatBoost стал одним из стандартных инструментов в прикладных задачах — наряду с XGBoost и LightGBM он входит в число наиболее используемых алгоритмов на табличных данных в соревнованиях по машинному обучению.

Историческая справка

Градиентный бустинг как общий метод оптимизации функционала в пространстве функций был предложен Джеромом Фридманом (Friedman, 2001) на основе более ранних работ по бустингу (Freund, Schapire)^[1]. На протяжении 2000-х годов бустинг на деревьях стал основным инструментом ранжирования в поисковых системах; в частности, обструктурированные деревья (англ. oblivious decision trees), позднее ставшие основой CatBoost, применялись в системах ранжирования ещё с конца 2000-х.

К середине 2010-х годов сложилась проблема: высокопроизводительные реализации бустинга (XGBoost, 2014; LightGBM, 2016) не имели нативной поддержки категориальных признаков и требовали ручного кодирования, которое либо взрывало размерность (One-hot encoding), либо порождало утечку целевой переменной (Target encoding). Команда Яндекса под руководством А. Гулина и А. В. Дорогуш представила CatBoost в 2017 году^[1], а в 2018 году вышла работа Л. Прохоренковой с соавторами, в которой был формализован эффект смещения предсказания и предложены упорядоченный бустинг и упорядоченное кодирование категорий как способ его устранения^[1]. Эта статья и считается основным теоретическим источником метода.

Постановка задачи

Пусть дана выборка $\mathcal{D} = \bigl\{(x_i, y_i)\bigr\}_{i=1}^{n}$ из независимых одинаково распределённых наблюдений, где $x_i \in \mathbb{R}^d$ — вектор признаков (часть координат может быть категориальной), $y_i$ — целевая переменная. Требуется построить функцию $F$ из $\mathbb{R}^{d}$ в $\mathbb{R}$ , минимизирующую ожидаемые потери

$\mathcal{L}(F) = \mathbb{E}_{(x,y)}\,\ell\bigl(y,\, F(x)\bigr)$ ,

где $\ell$ — дифференцируемая функция потерь. Градиентный бустинг строит приближение итерационно: $F_t = F_{t-1} + \eta\, h_t$ , где базовый предиктор $h_t$ аппроксимирует антиградиент функционала на текущем приближении, а $\eta$ — темп обучения.

Смещение предсказания

Ключевое наблюдение авторов CatBoost состоит в следующем. На шаге $t$ в качестве цели для обучения $h_t$ на объекте $x_i$ используется градиент $g_i = \partial \ell(y_i, F_{t-1}(x_i)) / \partial F_{t-1}(x_i)$ . Но модель $F_{t-1}$ сама была обучена с использованием объекта $x_i$ , поэтому значение $F_{t-1}(x_i)$ зависит от $y_i$ . В результате условное распределение градиента $g_i \mid x_i$ на обучающей выборке отличается от его распределения на новом объекте $x$ того же распределения. Это расхождение авторы называют смещением предсказания; оно накапливается с числом итераций и ведёт к переобучению, особенно заметному на выборках малого объёма.

Алгоритм

Упорядоченный бустинг

Чтобы получить несмещённую оценку градиента, CatBoost вводит искусственную «временну́ю» структуру на выборке. Фиксируется случайная перестановка $\sigma$ объектов, и для каждого объекта остаток вычисляется по модели, обученной только на предшествующих ему в этой перестановке объектах:

$r_{\sigma,i}^{(t)} = -\left.\frac{\partial \ell\bigl(y_i,\, F(x_i)\bigr)}{\partial F(x_i)}\right|_{F = F_{\sigma,i}^{(t-1)}}$ ,

где $F_{\sigma,i}^{(t-1)}$ — модель, построенная по множеству объектов $\{x_j \mid \sigma(j) < \sigma(i)\}$ . Поскольку при вычислении остатка для $x_i$ сам объект не участвовал в обучении, оценка градиента оказывается несмещённой.

Прямая реализация этой идеи потребовала бы хранить $n$ различных моделей (по одной для каждого префикса перестановки), что неприемлемо по памяти и времени. На практике поддерживается логарифмическое число вспомогательных моделей, а для снижения дисперсии оценки используется несколько независимых перестановок $\sigma$ , между которыми алгоритм чередуется в ходе обучения.

Упорядоченное кодирование категорий

Та же идея перестановки применяется к категориальным признакам. Простое кодирование средним по целевой переменной (англ. target statistics) вида «средний $y$ по всем объектам данной категории» использует $y_i$ при вычислении признака для $x_i$ и потому даёт утечку. CatBoost вычисляет статистику только по предшественникам объекта в перестановке:

$\hat{x}_i^{(c)} = \frac{\displaystyle\sum_{j\,:\;\sigma(j) < \sigma(i),\, c_j = c_i} y_j \;+\; a\,p}{\displaystyle\sum_{j\,:\;\sigma(j) < \sigma(i),\, c_j = c_i} 1 \;+\; a}$ ,

где $c_i$ — значение категориального признака объекта $x_i$ , $p$ — априорное значение (обычно среднее целевой переменной по всей выборке), $a > 0$ — параметр сглаживания. Для объектов с малым числом предшественников той же категории оценка «притягивается» к априору $p$ , что обеспечивает устойчивость на редких категориях.

Кроме того, CatBoost автоматически порождает комбинации категориальных признаков (англ. feature combinations): при разбиении в дереве уже использованные категории объединяются в составные, что позволяет улавливать взаимодействия признаков (например, «город» × «тип устройства») без ручной инженерии.

Обструктурированные деревья

В качестве базовых предикторов CatBoost использует обструктурированные (симметричные) деревья (англ. oblivious decision trees): на каждом уровне глубины применяется одно и то же условие разбиения ко всем узлам уровня. Дерево глубины $d$ полностью задаётся набором пар «признак—порог» $(f_1, \theta_1), \ldots, (f_d, \theta_d)$ , а индекс листа для объекта $x$ определяется битовым вектором

$b(x) = \bigl(b_1(x), \ldots, b_d(x)\bigr), \qquad b_k(x) = \mathbf{1}\bigl[x_{f_k} > \theta_k\bigr]$ .

Дерево имеет ровно $2^d$ листьев, и предсказание есть значение в листе с номером $b(x)$ , интерпретированным как двоичное число.

Свойства

Преимущества

Устойчивость к переобучению. Упорядоченный бустинг и упорядоченное кодирование устраняют смещение предсказания, что особенно заметно на выборках малого и среднего объёма, где конкурирующие реализации склонны переобучаться^[1].
Нативная обработка категорий. Достаточно указать индексы категориальных столбцов; ручное кодирование не требуется.
Малое число настраиваемых гиперпараметров. Значения по умолчанию дают разумный результат на широком классе задач; нередко достаточно настроить лишь темп обучения и число деревьев.
Эффективность обструктурированных деревьев. Симметричная структура ускоряет вычисление предсказания (путь сводится к набору независимых сравнений) и хорошо ложится на параллельные и GPU-вычисления; она же играет роль регуляризатора, ограничивая сложность отдельного дерева.

Ограничения

Скорость обучения. Поддержка нескольких перестановок и вспомогательных моделей делает обучение на CPU медленнее, чем у LightGBM; разница заметна на выборках в десятки миллионов объектов.
Потребление памяти. Хранение статистик по перестановкам увеличивает расход оперативной памяти.
Неуниверсальность преимущества. На сильно разреженных данных (например, текстах с TF-IDF-представлением) выигрыш в качестве относительно LightGBM и XGBoost, как правило, отсутствует.
Ограниченная гибкость деревьев. Симметричность снижает выразительность отдельного дерева; на некоторых задачах асимметричные деревья дают лучший результат при той же глубине.

Применение

CatBoost применяется прежде всего в задачах с большим числом категориальных признаков высокой кардинальности:

Ранжирование и рекомендации. Алгоритм поддерживает попарные и списочные функции потерь для обучения ранжированию и исторически использовался в поисковых и рекомендательных системах.
Кредитный скоринг и оценка риска. Признаки вида «регион», «тип занятости», «категория транзакции» естественно являются категориальными.
Предсказание вероятности клика (CTR). Задачи онлайн-рекламы с высококардинальными категориями (идентификаторы пользователей, доменов, объявлений).
Прикладные задачи на табличных данных. Регрессия и классификация в областях, где данные не обладают пространственной или временно́й структурой, удобной для нейросетевых моделей.

См. также

Ссылки

Литература

Prokhorenkova L., Gusev G., Vorobev A., Dorogush A. V., Gulin A. CatBoost: unbiased boosting with categorical features // Advances in Neural Information Processing Systems (NeurIPS). — 2018. — С. 6638–6648.
Dorogush A. V., Ershov V., Gulin A. CatBoost: gradient boosting with categorical features support // Workshop on ML Systems at NeurIPS. — 2017.
Friedman J. H. Greedy function approximation: a gradient boosting machine // The Annals of Statistics. — 2001 T. 29. — С. 1189–1232.
Hastie T., Tibshirani R., Friedman J. Boosting and Additive Trees // The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2nd ed.). — Springer, 2009.

Источник — «http://83.149.227.45/wiki/index.php?title=CatBoost»

Категории: Методы машинного обучения | Ансамблевые методы