XGBoost

XGBoost — одна из самых популярных и эффективных реализаций алгоритма градиентного бустинга на деревьях на 2019-й год.

История

XGBoost изначально стартовал как исследовательский проект Тяньцзи Чена (Tianqi Chen) как часть сообщества распределенного глубинного машинного обучения. Первоначально он начинался как терминальное приложение, которое можно было настроить с помощью файла конфигурации libsvm. После победы в Higgs Machine Learning Challenge, он стал хорошо известен в соревновательный кругах по машинному обеспечению. Вскоре после этого были созданы пакеты для Python и R, и теперь у него есть пакеты для многих других языков, таких как Julia, Scala, Java и т. д. Это принесло библиотеке больше разработчиков и сделало ее популярной среди сообщества Kaggle, где она использовалось для большого количества соревнований.

Она вскоре стала использоваться с несколькими другими пакетами, что облегчает ее использование в соответствующих сообществах. Теперь у нее есть интеграция с scikit-learn для пользователей Python, а также с пакетом caret для пользователей R. Она также может быть интегрирована в рамах потока данных, таких как Apache Spark, Apache Hadoop, и Apache Flink с использованием абстрактных Rabit и XGBoost4J. Принцип работы XGBoost также был опубликован Тяньцзи Ченом (Tianqi Chen) и Карлосом Гастрин (Carlos Guestrin).

Описание алгоритма

Иллюстрация бустинга

В основе XGBoost лежит алгоритм градиентного бустинга деревьев решений. Идея алгоритма в том, что каждое следующе дерево предсказывает ошибку обученного ансамбля на каждом элементе обучающей выборки. Каждое отдельное дерево обучается одним из стандартных алгоритмов используемых для обучения деревьев решений. Таким образом предсказание складывается из предсказаний каждого отдельного дерева ансамбля.

Математика за алгоритмом

[math]\mathcal{L}^{(t)} = \sum_{i=1}^n l(y_i,\hat{y_i}^{(t-1)}+f_t(x_i))+\Omega(f_t)[/math] — функция для оптимизации градиентного бустинга, где:

[math]l[/math] — функция потерь, см. Общие понятия.

[math]y_i, \hat{y_i}^{t}[/math] — значение i-го элемента обучающей выборки и сумма предсказаний первых t деревьев соответственно.

[math]x_i[/math] — набор признаков i-го элемента обучающей выборки.

[math]f_t[/math] — функция (в нашем случае дерево), которую мы хотим обучить на шаге t. [math]f_t(x_i)[/math] — предсказание на i-ом элементе обучающей выборки.

[math]\Omega(f)[/math] — регуляризация функции [math]f[/math]. [math]\Omega(f) = \gamma T + \frac{1}{2} \lambda \lVert w \rVert ^2[/math], где T — количество вершин в дереве, [math]w[/math] — значения в листьях, а [math]\gamma[/math] и [math]\lambda[/math] — параметры регуляризации.

Дальше с помощью разложения Тейлора до второго члена можем приблизить это следующим выражением:

[math]\mathcal{L}^{(t)} = \sum_{i=1}^n l(y_i,\hat{y_i}^{(t-1)}) + g_i f_t(x_i) + 0.5 h_i f_t^2(x_i)) + \Omega(f_t)[/math], где

[math]g_i = \frac {\partial {l(y_i,\hat{y_i}^{t-1})}}{\partial{\hat{y_i}^{t-1}}}[/math], [math]h_i = \frac {\partial^2 {l(y_i,\hat{y_i}^{t-1})}}{\partial^2{\hat{y_i}^{t-1}}}[/math]

Поскольку мы хотим минимизировать ошибку модели на обучающей выборки, нам нужно найти минимум [math]\mathcal{L}^{(t)}[/math] для каждого t.

Минимум этого выражения относительно [math]f_t(x_i)[/math] находится в точке [math]f_t(x_i) = \frac{-g_i}{h_i}[/math].

Каждое отдельное дерево ансамбля [math]f_t(x_i)[/math] обучается стандартным алгоритмом. Для более полного описания см. Дерево решений и случайный лес.

Возможности XGBoost

Особенности модели

Реализация модели поддерживает особенности реализации scikit-learn и R с новыми дополнениями, такими как регуляризация. Поддерживаются три основные формы повышения градиента:

• Алгоритм Gradient Boosting также называется градиентной машиной повышения, включая скорость обучения.
• Stochastic Gradient Boosting с суб-выборкой в ​​строке, столбце и столбце на каждый уровень разделения.
• Регулярное усиление градиента с регуляцией L1 и L2.

Системные функции

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

• Параллелизация построения дерева с использованием всех ваших ядер процессора во время обучения.
• Распределенные вычисления для обучения очень крупных моделей с использованием кластера машин.
• Внекорпоративные вычисления для очень больших наборов данных, которые не вписываются в память.
• Кэш Оптимизация структуры данных и алгоритма для наилучшего использования аппаратного обеспечения.

Особенности алгоритма

Реализация алгоритма была разработана для эффективности вычислительных ресурсов времени и памяти. Цель проекта заключалась в том, чтобы наилучшим образом использовать имеющиеся ресурсы для обучения модели. Некоторые ключевые функции реализации алгоритма включают:

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

Основные параметры

• n_estimators — число деревьев.
• eta — размер шага. Пердотвращает переобучение.
• gamma — минимальное изменение значения loss функции для разделения листа на поддеревья.
• max_depth — максимальная глубина дерева.
• lambda/alpha — L2/L1 регуляризация.

Для более полного описания параметров модели см. документацию.

Пример использования с помощью библиотеки xgboost

from sklearn import datasets
iris = datasets.load_iris()
X = iris.data
y = iris.target

from sklearn.cross_validation import train_test_split
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

import xgboost as xgb

dtrain = xgb.DMatrix(X_train, label=y_train)
dtest = xgb.DMatrix(X_test, label=y_test)

param = {
   'max_depth': 3,
   'eta': 0.3, 
   'silent': 1, 
   'objective': 'multi:softprob',
   'num_class': 3}
num_round = 20

bst = xgb.train(param, dtrain, num_round)
preds = bst.predict(dtest)

import numpy as np
from sklearn.metrics import precision_score
best_preds = np.asarray([np.argmax(line) for line in preds])
print precision_score(y_test, best_preds, average='macro')

См. также

• Дерево решений и случайный лес
• Бустинг, AdaBoost

Источники информации

• Tianqi Chen, Carlos Guestrin. XGBoost: A Scalable Tree Boosting System
• XGBoost Mathematics Explained
• Gradient Boosting and XGBoost