Алгоритм xgBoost

Рассмотрим подробнее алгоритм xgBoost (Extreme Gradient Boosting [1]), представляющий собой эффективную реализацию градиентного бустинга со многими возможностями и настройками.

Мотивация

Основное отличие XGBoost от классического градиентного бустинга заключается в использовании разложения Тейлора второго порядка для аппроксимации функции потерь и явном включении штрафа за сложность дерева в оптимизационную задачу. Это позволяет модели быстрее настраиваться и лучше обобщать данные.

Вывод целевой функции

Вспомним итерационный процесс: на шаге $m$ мы ищем такое дерево $f_m(\boldsymbol{x})$, чтобы минимизировать общую ошибку. Запишем целевую функцию $L$ на $m$-й итерации:

$$L^{(m)} = \sum_{n=1}^N \mathcal{L}(y_n, G_{m-1}(\boldsymbol{x}_n) + f_m(\boldsymbol{x}_n)) + \Omega(f_m)$$

Здесь $\mathcal{L}$ — функция потерь, а $\Omega(f_m)$ — регуляризатор, ограничивающий сложность дерева. Применим разложение Тейлора до второго порядка для функции $\mathcal{L}$ в окрестности точки $G_{m-1}(\boldsymbol{x}_n)$:

$$L^{(m)} \approx \sum_{n=1}^N \left[ \mathcal{L}(y_n, G_{m-1}(\boldsymbol{x}_n)) + g_n f_m(\boldsymbol{x}_n) + \frac{1}{2} h_n f_m^2(\boldsymbol{x}_n) \right] + \Omega(f_m)$$

где $g_n$ и $h_n$ — градиент и гессиан (вторая производная) функции потерь:

$$g_n = \frac{\partial \mathcal{L}(y_n, G_{m-1}(\boldsymbol{x}_n))}{\partial G_{m-1}(\boldsymbol{x}_n)}, \quad h_n = \frac{\partial^2 \mathcal{L}(y_n, G_{m-1}(\boldsymbol{x}_n))}{\partial G_{m-1}(\boldsymbol{x}_n)^2}$$

Поскольку значение $\mathcal{L}(y_n, G_{m-1}(\boldsymbol{x}_n))$ уже определено на предыдущих шагах, оно является константой. Для минимизации $L^{(m)}$ её можно отбросить:

$$L^{(m)} \approx \sum_{n=1}^N \left[ g_n f_m(\boldsymbol{x}_n) + \frac{1}{2} h_n f_m^2(\boldsymbol{x}_n) \right] + \Omega(f_m)$$

Оптимизация весов в листьях

Пусть дерево $f_m(\boldsymbol{x})$ имеет $J$ листьев, а функция $q(\boldsymbol{x})$ возвращает индекс листа для объекта $\boldsymbol{x}$. Вес (прогноз) в $j$-м листе обозначим $w_j$. Тогда $f_m(\boldsymbol{x}) = w_{q(\boldsymbol{x})}$. Регуляризатор определим как:

$$\Omega(f_m) = \gamma J + \frac{1}{2} \lambda \sum_{j=1}^J w_j^2$$

Сгруппируем объекты по листьям, в которые они попали. Пусть $I_j = \{n : q(\boldsymbol{x}_n) = j\}$ — множество индексов объектов в $j$-м листе. Перепишем $L^{(m)}$:

$$L^{(m)} = \sum_{j=1}^J \left[ \left( \sum_{n \in I_j} g_n \right) w_j + \frac{1}{2} \left( \sum_{n \in I_j} h_n + \lambda \right) w_j^2 \right] + \gamma J$$

Для краткости введём обозначения: $G_j = \sum_{n \in I_j} g_n$ (суммарный градиент в листе) и $H_j = \sum_{n \in I_j} h_n$ (суммарный гессиан).

Рассмотрим вклад одного $j$-го листа в общую ошибку. Это выражение имеет вид квадратичной функции $A w_j^2 + B w_j$, где:

$$A = \frac{1}{2}(H_j + \lambda), \quad B = G_j$$

Вспомним, что минимум параболы $y = Ax^2 + Bx + C$ при $A > 0$ достигается в точке $x^* = -B / (2A)$.

Применим это для нахождения оптимального веса $w_j^*$:

$$w_j^* = -\frac{G_j}{2 \cdot \frac{1}{2}(H_j + \lambda)} = -\frac{G_j}{H_j + \lambda}$$

Чтобы найти минимальное значение целевой функции $L^*$ для данной структуры дерева, подставим $w_j^*$ обратно в выражение для листа:

$$\begin{aligned} L_j^* &= G_j \left( -\frac{G_j}{H_j + \lambda} \right) + \frac{1}{2} (H_j + \lambda) \left( -\frac{G_j}{H_j + \lambda} \right)^2 \\ &= -\frac{G_j^2}{H_j + \lambda} + \frac{1}{2} \frac{G_j^2}{H_j + \lambda} = -\frac{1}{2} \frac{G_j^2}{H_j + \lambda} \end{aligned}$$

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

$$L^* = -\frac{1}{2} \sum_{j=1}^J \frac{G_j^2}{H_j + \lambda} + \gamma J$$

Критерий информативности

Для поиска наилучшего разбиения узла на левое ($L$) и правое ($R$) подмножества используется критерий прироста (Gain). Он рассчитывается как разность между структурной оценкой до разбиения и после него:

$$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$$

Если полученный $Gain$ меньше нуля, разбиение считается нецелесообразным, что является встроенным механизмом автоматической обрезки (pruning) дерева.

Данный критерий заменяет собой стандартные критерии Джини или энтропию. Он напрямую минимизирует аппроксимированную функцию потерь пользователя, что позволяет повысить точность на уровне каждого дерева.

Аналитический вид прироста Gain позволяет лучше проинтерпретировать значение коэффициентов регуляризации:

• $\gamma\ge 0$ — это коэффициент сложности, накладывающий штраф за само наличие новых листьев в дереве. Он выступает в роли «порога»: разбиение узла будет произведено только в том случае, если прирост в обучении (Gain) окажется больше $\gamma$. Это приводит к автоматической обрезке (pruning) дерева на этапе его построения.

• $\lambda\ge 0$ — это коэффициент $L_2$-регуляризации весов в листьях. Он занижает абсолютные значения весов $w_j$, стремясь прижать их к нулю. Это делает модель более консервативной, так как она меньше доверяет прогнозам в листьях с малым количеством объектов.

:::

Особенности библиотеки

XGBoost — это не просто алгоритм, а высокооптимизированная программная система. Чтобы ознакомиться с полным спектром её возможностей, рекомендуется обратиться к официальной документации [2]. Перечислим лишь основные возможности.

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

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

Помимо $L_2$-регуляризации ($\lambda$), XGBoost поддерживает $L_1$-регуляризацию на веса в листях деревьев. Также реализован режим DART (Dropouts meet Multiple Additive Regression Trees [3]), где на каждой итерации случайно исключается часть предыдущих деревьев. Это предотвращает доминирование первых деревьев в прогнозах и делает ансамбль более устойчивым к переобучению.

Также xgBoost поддерживает эффективную работу с разреженными данными и пропусками.

Благодаря перечисленным возможностям, метод долгое время был стандартом для побед на платформе Kaggle в задачах с табличными структурами данных.

Литература

1. Chen T., Guestrin C. Xgboost: A scalable tree boosting system //Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining. – 2016. – С. 785-794.
2. Документация XGBoost.
3. Vinayak R. K., Gilad-Bachrach R. Dart: Dropouts meet multiple additive regression trees //Artificial Intelligence and Statistics. – PMLR, 2015. – С. 489-497.