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

Алгоритм XGBoost (eXtreme Gradient Boosting) - это реализация градиентного бустинга над деревьями решений, которая годами держится в топе на соревнованиях по табличным данным. Идея бустинга противоположна случайному лесу: деревья строятся не параллельно и независимо, а последовательно, и каждое новое дерево исправляет ошибки уже собранного ансамбля. XGBoost добавляет к классическому бустингу регуляризацию, точную работу со вторыми производными функции потерь и инженерные оптимизации, за счёт чего обучается быстро и редко переобучается. Ниже разберём математику аддитивной модели, роль learning rate и регуляризации, раннюю остановку и типичные ошибки. Чтобы сразу почувствовать, как скорость обучения и число деревьев влияют на ошибку, - покрути калькулятор ниже.

Что такое XGBoost и чем он отличается от случайного леса

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

$$\hat{y}_i = \sum_{m=1}^{M} f_m(x_i), \qquad f_m \in \mathcal{F},$$

где $f_m$ - $m$-е дерево решений из пространства деревьев $\mathcal{F}$, а $M$ - общее число деревьев (бустинг-итераций). Случайный лес снижает прежде всего дисперсию (усреднение похожих сильных деревьев), а бустинг последовательно снижает смещение, наращивая выразительность модели маленькими шагами. Поэтому деревья в XGBoost обычно мелкие (глубина 3-6): каждое из них - слабый ученик, а сила берётся из их числа.

Аддитивная модель и градиентный шаг

Ансамбль строится жадно: на итерации $m$ мы уже имеем модель $\hat{y}_i^{(m-1)}$ и добавляем к ней одно новое дерево $f_m$, минимизируя суммарную функцию потерь:

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

где $\eta$ - learning rate (скорость обучения, шаг бустинга). Чтобы понять, чему должно учиться новое дерево, XGBoost раскладывает функцию потерь $L$ в ряд Тейлора до второго порядка вокруг текущего прогноза. Для каждого объекта считаются градиент $g_i$ и гессиан $h_i$:

$$g_i = \frac{\partial L(y_i, \hat{y}_i^{(m-1)})}{\partial \hat{y}_i^{(m-1)}}, \qquad h_i = \frac{\partial^2 L(y_i, \hat{y}_i^{(m-1)})}{\partial (\hat{y}_i^{(m-1)})^2}.$$

Использование второй производной (гессиана) - ключевое отличие XGBoost от классического градиентного бустинга, который опирается только на градиент. Второй порядок даёт более точный шаг, как метод Ньютона по сравнению с обычным градиентным спуском.

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

Каждое дерево, по сути, аппроксимирует антиградиент потерь - направление, в котором нужно подвинуть прогноз. Для квадратичной ошибки антиградиент - это в точности остаток $y_i - \hat{y}_i$, поэтому интуиция «каждое дерево учится на остатках предыдущих» строго верна для регрессии.

Целевая функция с регуляризацией

XGBoost минимизирует не просто сумму потерь, а потери плюс штраф за сложность деревьев - в этом «eXtreme» относительно обычного бустинга. Целевая функция на итерации $m$:

$$\mathcal{L}^{(m)} = \sum_{i=1}^{n} L\left(y_i, \hat{y}_i^{(m-1)} + f_m(x_i)\right) + \Omega(f_m),$$

где регуляризатор для дерева с $T$ листьями и весами листьев $w_j$ задаётся как

$$\Omega(f) = \gamma\, T + \frac{1}{2}\lambda \sum_{j=1}^{T} w_j^2.$$

Здесь $\gamma$ штрафует за число листьев (то есть за разбиения - чем больше $\gamma$, тем консервативнее дерево), а $\lambda$ - это L2-регуляризация весов листьев. Подставив тейлоровское приближение, можно вывести оптимальный вес листа $j$ и выигрыш от разбиения в замкнутой форме:

$$w_j^{*} = -\frac{\sum_{i \in I_j} g_i}{\sum_{i \in I_j} h_i + \lambda}, \qquad \text{Gain} = \frac{1}{2}\left[\frac{G_L^2}{H_L+\lambda} + \frac{G_R^2}{H_R+\lambda} - \frac{(G_L+G_R)^2}{H_L+H_R+\lambda}\right] - \gamma,$$

где $I_j$ - множество объектов, попавших в лист $j$, а $G_L, H_L$ и $G_R, H_R$ - суммы градиентов и гессианов в левой и правой ветках кандидата на разбиение. XGBoost перебирает признаки и пороги, выбирая разбиение с максимальным $\text{Gain}$; если лучший $\text{Gain}$ оказывается отрицательным (штраф $\gamma$ перевесил выигрыш), разбиение не делается - это встроенная регуляризация структуры дерева.

Learning rate и число деревьев

Множитель $\eta$ (в библиотеке - eta или learning_rate) задаёт, какую долю вклада каждого дерева мы добавляем в ансамбль. Маленький $\eta$ (0,01-0,1) делает шаги осторожными: ошибка падает медленнее, зато модель устойчивее и реже переобучается, но требует больше деревьев. Большой $\eta$ (0,3 и выше) быстро снижает ошибку обучения, но рискует «проскочить» оптимум и переобучиться. Снижение ошибки приближённо описывается законом убывающей геометрической прогрессии:

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

где $\mathcal{L}_0$ - стартовая ошибка, $\mathcal{L}_{\min}$ - неустранимый «пол» (шум данных и ограничения модели), а $\rho$ - эффективность одного дерева. Из формулы видно главное правило настройки: $\eta$ и $M$ работают в связке - уменьшив learning rate вдвое, нужно примерно вдвое увеличить число деревьев, чтобы дойти до того же уровня ошибки. На практике берут небольшой $\eta$ и подбирают $M$ по валидации.

Переобучение и ранняя остановка

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

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

Стандартный приём - ранняя остановка (early_stopping_rounds): обучение прекращается, если валидационная метрика не улучшается заданное число итераций подряд, и берётся модель на лучшей итерации. Дополнительно переобучение сдерживают: уменьшением max_depth (мельче деревья), увеличением lambda, gamma и min_child_weight, а также подвыборкой строк (subsample) и столбцов (colsample_bytree) - заимствованной у случайного леса рандомизацией, которая снижает корреляцию деревьев.

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

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

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

• Путают бустинг с бэггингом. В случайном лесу деревья независимы и усредняются (снижают дисперсию), в XGBoost - последовательны и исправляют друг друга (снижают смещение). Это разные ансамблевые стратегии, а не «лес против одного дерева».
• Ставят большой learning rate ради скорости. Высокий $\eta$ быстро роняет ошибку обучения, но валидационная начинает расти раньше - выгоднее маленький $\eta$ и больше деревьев с ранней остановкой.
• Контролируют число деревьев на глаз, без валидации. Ошибка обучения падает почти до нуля всегда; о переобучении говорит только рост ошибки на отложенной выборке. Нужен early_stopping_rounds.
• Забывают про регуляризацию. Параметры $\gamma$, $\lambda$, min_child_weight - это не «опциональные крутилки», а главный рычаг против переобучения; на дефолтах глубокие деревья легко запоминают шум.
• Считают, что XGBoost универсален. На картинках и тексте он почти всегда проигрывает нейросетям - его ниша именно табличные данные.

FAQ

Чем XGBoost отличается от обычного градиентного бустинга? Тремя вещами: разложением потерь до второго порядка (использует гессиан, а не только градиент), встроенной регуляризацией $\Omega(f)=\gamma T + \tfrac{1}{2}\lambda\sum w_j^2$ в целевой функции и инженерными оптимизациями (гистограммы, параллельный перебор разбиений, обработка пропусков). За счёт этого он точнее и быстрее классического GBM.

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

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

Коротко

XGBoost - это градиентный бустинг над неглубокими деревьями: ансамбль $\hat{y}=\sum_m f_m(x)$ строится последовательно, каждое дерево делает шаг по антиградиенту функции потерь, а целевая функция включает штраф за сложность $\gamma T + \tfrac{1}{2}\lambda\sum w_j^2$. Скорость обучения $\eta$ и число деревьев $M$ настраиваются вместе, переобучение сдерживают регуляризацией и ранней остановкой. Сильная сторона - табличные данные; на изображениях и тексте выигрывают нейросети.