Участник:Ezamyatin

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

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

• Возможность добавлять регуляризацию
• Возможность работать с разреженными данными
• Возможность распределенного обучения
• Эффективная реализация

Идея алгоритма

[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]\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]f_t(x_i)[/math] находится в точке [math]f_t(x_i) = \frac{-g_i}{h_i}[/math]

Процесс обучение отдельного дерева

1. Изначально дерево содержит единственную вершину

2. Пытаемся разбить каждую вершину и считаем gain

3. Жадно сплитим вершину

Пример использования с помощью библиотеки 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')