Алгоритм CatBoost: бустинг с обработкой категорий

Алгоритм CatBoost (Categorical Boosting) - это градиентный бустинг над деревьями решений от Яндекса, который из коробки умеет работать с категориальными признаками и заметно реже переобучается на небольших выборках. От XGBoost и LightGBM его отличают две идеи: упорядоченный бустинг (ordered boosting), который убирает сдвиг прогноза из-за утечки целевой переменной, и упорядоченное кодирование категорий через целевую статистику. Сверху - симметричные деревья, которые делают модель быстрой и устойчивой. Ниже разберём математику этих приёмов, роль learning rate и числа итераций, борьбу с переобучением и типичные ошибки. Чтобы сразу почувствовать, как упорядоченный бустинг сдвигает зону переобучения, - покрути калькулятор ниже.

Что такое CatBoost и место в семействе бустинга

CatBoost относится к семейству градиентного бустинга над деревьями: модель собирается как сумма вкладов многих неглубоких деревьев, и каждое следующее дерево исправляет ошибки уже накопленного ансамбля. Это та же общая схема, что и у алгоритма XGBoost, но в отличие от него и от случайного леса CatBoost спроектирован вокруг двух проблем, которые остальные реализации решают грубее: утечки целевой переменной при кодировании категорий и так называемого сдвига прогноза при обучении. Предсказание собирается аддитивно:

$$\hat{y}_i = \sum_{m=1}^{M} \eta \, f_m(x_i),$$

где $f_m$ - $m$-е дерево, $M$ - число итераций бустинга, а $\eta$ - learning rate (скорость обучения). Базовый ученик слабый, сила берётся из числа итераций - как и в любом бустинге. Отличие CatBoost не в этой формуле, а в том, как считаются остатки для обучения каждого дерева и как кодируются категориальные признаки.

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

Главная теоретическая идея CatBoost - упорядоченный бустинг (ordered boosting). В классическом бустинге остатки (антиградиенты) для объекта $x_i$ считаются по модели, которая уже видела этот самый объект на обучении. Из-за этого распределение остатков на обучении систематически отличается от распределения на новых данных - это и есть сдвиг прогноза (prediction shift), частный случай утечки целевой переменной, который ведёт к переобучению, особенно на маленьких выборках.

Рассчитать для своей задачи

CatBoost решает это так: данные случайно переставляются, и при оценке остатка для объекта на позиции $i$ используется отдельная модель $M_i$, обученная только на предшествующих объектах $x_1, \dots, x_{i-1}$ в этой перестановке. Остаток для $i$-го объекта:

$$r_i = y_i - M_{i-1}(x_i),$$

то есть прогноз $M_{i-1}$ не видел целевого значения $y_i$. Так оценка остатка становится несмещённой - модель для каждого объекта обучена без него самого. Чтобы приём не съел всю статистику для первых объектов перестановки, CatBoost использует несколько случайных перестановок и поддерживает набор вспомогательных моделей. На практике это даёт лучшее обобщение «из коробки», особенно когда данных немного.

Кодирование категорий: ordered target statistics

Вторая фирменная черта - обработка категориальных признаков без ручного one-hot кодирования. Наивный приём target encoding заменяет категорию средним значением таргета по этой категории, но это прямая утечка: значение $y_i$ участвует в признаке того же объекта $i$. CatBoost применяет ту же идею перестановки - упорядоченную целевую статистику (ordered target statistics): значение признака для объекта $i$ считается только по предыдущим объектам перестановки с той же категорией:

$$\hat{x}_i^{\,k} = \frac{\sum_{j<i}[\,x_j^k = x_i^k\,]\,y_j + a\,p}{\sum_{j<i}[\,x_j^k = x_i^k\,] + a},$$

где $a > 0$ - параметр сглаживания, $p$ - априорное среднее таргета, а сумма берётся по объектам, идущим до $i$ в перестановке. Сглаживание $a\,p$ страхует редкие категории от шумной оценки по одному-двум объектам. Кроме того, CatBoost автоматически строит комбинации категориальных признаков (например пара «город + категория товара») жадно по ходу роста дерева, что часто ловит взаимодействия, которые при ручном кодировании теряются.

Симметричные (oblivious) деревья

Базовый ученик в CatBoost - симметричное дерево (oblivious tree): на каждом уровне дерева для всех узлов используется одно и то же правило разбиения (один и тот же признак и порог). Дерево глубины $d$ - это, по сути, решающая таблица из $2^d$ листьев, где путь объекта задаётся $d$-битным индексом сравнений.

Рассчитать для своей задачи

Такая структура жёстче, чем у обычных деревьев XGBoost, зато даёт три выгоды: дерево работает как сильный регуляризатор (меньше параметров - меньше переобучения), предсказание считается очень быстро (несколько битовых операций вместо обхода ветвей), и модель легко векторизуется на GPU. Платой за симметрию была бы потеря выразительности, но её компенсируют большое число итераций и комбинации признаков.

Learning rate, число итераций и регуляризация

Как и в любом бустинге, learning rate $\eta$ и число итераций $M$ настраиваются в связке. Маленький $\eta$ (0,03-0,1) делает шаги осторожными: ошибка падает медленнее, зато модель устойчивее; большой $\eta$ быстро снижает ошибку обучения, но раньше уводит в переобучение. Приближённо снижение ошибки описывается убывающей геометрической прогрессией:

$$\mathcal{L}(M) \approx \mathcal{L}_{\min} + (\mathcal{L}_0 - \mathcal{L}_{\min})\,(1 - \eta\,\rho)^{M},$$

где $\mathcal{L}_0$ - стартовая ошибка, $\mathcal{L}_{\min}$ - неустранимый «пол» (шум данных), $\rho$ - эффективность одной итерации. За счёт упорядоченного бустинга валидационная ошибка CatBoost разворачивается в переобучение позже, чем у обычного бустинга при тех же $\eta$ и $M$, - это и видно в калькуляторе выше. Дополнительные рычаги против переобучения: l2_leaf_reg (L2-штраф на веса листьев), depth (обычно 6-10), random_strength и bagging_temperature (рандомизация), а также early_stopping_rounds по валидационной метрике.

Где CatBoost силён, а где нет

CatBoost - почти стандартный выбор для табличных данных с категориальными признаками: пользовательские профили, транзакции, логи, где много нечисловых полей высокой кардинальности. На таких данных он часто обыгрывает XGBoost и LightGBM без ручного кодирования и с меньшим тюнингом. Упорядоченный бустинг особенно помогает на небольших и средних выборках, где сдвиг прогноза заметнее. Зато на изображениях, звуке и тексте, где важна пространственная или последовательная структура, деревья проигрывают свёрточным и трансформерным сетям. На очень больших данных скорость обучения CatBoost (особенно в режиме упорядоченного бустинга) ниже, чем у LightGBM, поэтому выбор между тремя библиотеками решается замером на конкретной задаче, а не общими правилами.

Частые ошибки

• Кодируют категории вручную перед CatBoost. Смысл библиотеки в том, что она сама строит упорядоченную целевую статистику без утечки; ручной one-hot или target encoding снаружи лишает её этого преимущества и часто добавляет утечку.
• Путают упорядоченный бустинг с обычным. Ordered boosting считает остаток для объекта по модели, не видевшей этот объект, - это борьба со сдвигом прогноза, а не просто «другой порядок данных».
• Ставят большой learning rate ради скорости. Высокий $\eta$ быстро роняет ошибку обучения, но валидационная разворачивается раньше; выгоднее маленький $\eta$, больше итераций и ранняя остановка.
• Игнорируют валидацию и early_stopping_rounds. Ошибка обучения у бустинга падает почти до нуля всегда; о переобучении говорит только рост ошибки на отложенной выборке.
• Считают CatBoost универсальным. На картинках и тексте он почти всегда проигрывает нейросетям - его ниша именно табличные данные с категориями.

FAQ

Чем CatBoost отличается от XGBoost и LightGBM? Тремя вещами: упорядоченным бустингом (несмещённая оценка остатков без сдвига прогноза), нативной обработкой категориальных признаков через упорядоченную целевую статистику и симметричными деревьями (быстрое предсказание, сильная регуляризация). XGBoost опирается на точные вторые производные и регуляризацию структуры дерева, LightGBM - на рост листьями и гистограммы; CatBoost выигрывает прежде всего на категориальных данных и небольших выборках.

Нужно ли кодировать категориальные признаки перед CatBoost? Нет. Достаточно передать список индексов категориальных колонок (cat_features), и CatBoost сам построит упорядоченную целевую статистику и комбинации категорий без утечки. Ручное кодирование снаружи обычно только вредит.

Что важнее настраивать - learning rate или число итераций? Их настраивают в связке: фиксируют небольшой $\eta$ (0,03-0,1) и подбирают число итераций ранней остановкой по валидации. Уменьшение $\eta$ требует пропорционального роста числа итераций для того же качества, поэтому «оптимального» числа итераций без указания $\eta$ не существует.

Коротко

CatBoost - это градиентный бустинг над симметричными деревьями с двумя фирменными приёмами против утечки целевой переменной: упорядоченным бустингом (остаток объекта считается по модели, не видевшей этот объект) и упорядоченной целевой статистикой для категорий (значение признака - по предыдущим объектам перестановки). Ансамбль строится аддитивно $\hat{y}=\sum_m \eta f_m(x)$, learning rate $\eta$ и число итераций $M$ настраиваются вместе, переобучение сдерживают регуляризацией и ранней остановкой. Сильная сторона - табличные данные с категориальными признаками; на изображениях и тексте выигрывают нейросети.