Алгоритм XGBoost

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

Мотивация

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

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

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

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

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

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

где

• $J$ - число листов дерева;

• $\{w_i\}_i$ - значения прогнозов в его листьях;

• $\gamma \ge 0,\;\lambda \ge 0$ - гиперпараметры:

  • $\gamma$ — это коэффициент сложности, накладывающий штраф за само наличие новых листьев в дереве.

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

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

$$L^{(m)} \approx \sum_{n=1}^N \left[ \mathcal{L}(y_n, F_{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, F_{m-1}(\boldsymbol{x}_n))}{\partial F_{m-1}(\boldsymbol{x}_n)}, \quad h_n = \frac{\partial^2 \mathcal{L}(y_n, F_{m-1}(\boldsymbol{x}_n))}{\partial F_{m-1}(\boldsymbol{x}_n)^2}$$

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

$$\tilde{L}^{(m)} = \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})}$.

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

$$\tag{1} \tilde{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}$$

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

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

Подставив эти оптимальные значения в (1), получим структурную оценку качества дерева:

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

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

Как описывалось ранее, решающее дерево $f_m(\boldsymbol{x})$ строится сверху вниз, когда листы дерева итеративно разбиваются на левый и правый узел. Для поиска наилучшего разбиения узла на левое ($L$) и правое ($R$) подмножества используется критерий прироста (Gain). В XGBoost он рассчитывается как разность между структурной оценкой (2) до разбиения и после него.

Пусть $I$ — множество индексов объектов в текущем узле, которое разбивается на индексы объектов в левом узле $I_L$ и правом узле $I_R$, $I=I_L \cup I_R$.

Основываясь на структурной оценке (2), прирост при разбиении вычисляется как разность между качеством дерева до и после добавления нового разветвления. В терминах сумм по индексам объектов формула выглядит следующим образом:

$$\text{Gain} = \frac{1}{2} \left[ \frac{\left( \sum_{n \in I_L} g_n \right)^2}{\sum_{n \in I_L} h_n + \lambda} + \frac{\left( \sum_{n \in I_R} g_n \right)^2}{\sum_{n \in I_R} h_n + \lambda} - \frac{\left( \sum_{n \in I} g_n \right)^2}{\sum_{n \in I} h_n + \lambda} \right] - \gamma$$

Разбор компонентов формулы:

1. Первое слагаемое — вклад левого дочернего узла.
2. Второе слагаемое — вклад правого дочернего узла.
3. Третье слагаемое — вклад исходного узла до разбиения (используются суммы градиентов и гессианов всех объектов в узле).
4. $\gamma$ — штраф за создание нового листа (регуляризация).

Алгоритм жадно максимизирует этот критерий: если для всех возможных разбиений $\text{Gain} < 0$, то разбиение не производится. Это естественным образом ограничивает глубину дерева в зависимости от гиперпараметра $\gamma$.

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

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

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

Выделим ключевые особенности:

• Поиск порогов по сетке: для данных с огромным числом уникальных значений признаков XGBoost строит гистограммы распределения и перебирает в качестве порогов только квантили признака. Это значительно ускоряет обучение без существенной потери точности.
• Использование GPU: XGBoost поддерживает перенос вычислений на видеокарту, которая эффективно распараллеливает построение гистограмм и поиск разбиений, что дает кратное ускорение на больших датасетах.
• Работа с пропусками: алгоритм автоматически определяет «направление по умолчанию» для пропущенных или нулевых значений в каждом узле, выбирая ветку, которая минимизирует общие потери.
• Системные оптимизации:
  • данные хранятся во внутренних буферах процессора таким образом, чтобы минимизировать задержки при чтении градиентов.
  • возможность эффективно обрабатывать данные, не помещающиеся в оперативную память, за счет использования дискового пространства.
• Регуляризация и сэмплирование:
  • Поддержка не только $L_2$, но и $L_1$-регуляризации весов.
  • Column Subsampling: случайный выбор подмножества признаков для каждого дерева или уровня (аналогично случайному лесу).
  • Режим DART [3]: на каждой итерации случайно исключается часть построенных деревьев, что предотвращает их доминирование и снижает риск переобучения итоговой модели.

Благодаря перечисленным возможностям, метод долгое время был лучшим решением самостоятельно или в ансамбле с другими методами на платформе 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.