XGBoost — XGBoost

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

Ключевые тезисы

2 подтем — раскройте любую, чтобы увидеть объяснение, формулы, примеры и интерактивные графики.

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

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

L^{(m)} \approx i \sum [g_{i} h_{m} (x_{i}) + \frac{1}{2} ℏ_{i} h_{m}^{2} (x_{i})] + Ω (h_{m}), g_{i} = \partial_{F} L, ℏ_{i} = \partial_{F}^{2} L

Обозначения

w_{j}^{*} = - \frac{\sum _{i \in I_{j}} g _{i}}{\sum _{i \in I_{j}} ℏ _{i} + λ}

Обозначения

Оптимальный вес листа выводится аналитически — отсюда и скорость, и точность

Штраф за сложность прямо в критерии разбиения.

Ω (h) = γ T + \frac{λ}{2} j = 1 \sum T w_{j}^{2}

Обозначения

T

— число листьев;

γ

штрафует за их количество,

λ

— за величину весов

Разбиение делается только если выигрыш превышает $γ$ — встроенная предобрезка.
Sparsity-aware split: для объектов с пропуском алгоритм выучивает, в какую ветвь их отправлять.
Гистограммный режим (tree_method="hist") убирает необходимость сортировать признаки на каждом шаге.

Деревья и ансамбли

Последовательность вопросов «признак > порог», разбивающая пространство на прямоугольные области.

Бэггинг деревьев со случайными подвыборками объектов и признаков: усреднение резко снижает дисперсию.

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

Быстрый бустинг от Microsoft: гистограммное разбиение и рост дерева по листьям вместо по уровням.

Бустинг от Яндекса с упорядоченным кодированием категорий и упорядоченным бустингом против смещения.

Распределение вклада признаков на основе значений Шепли из теории игр — с гарантиями аддитивности и согласованности.

Перевод категориальных признаков в числа: one-hot, ordinal, target encoding, хеширование, эмбеддинги.