Бустинг представляет собой жадный алгоритм построения композиции алгоритмов. Основная идея заключается в том, чтобы, имея множество относительно слабых алгоритмов обучения, построить их хорошую линейную комбинацию. Он похож на бэггинг тем, что базовый алгоритм обучения фиксирован. Отличие состоит в том, что обучение базовых алгоритмов для композиции происходит итеративно, и каждый следующий алгоритм стремится компенсировать недостатки композиции всех предыдущих алгоритмов.
На примере бустинга стало ясно, что хорошим качеством могут обладать сколь угодно сложные композиции классификаторов, при условии, что они правильно настраиваются. Это развеяло существовавшие долгое время представления о том, что для повышения обобщающей способности необходимо ограничивать сложность алгоритмов.
Впоследствии этот феномен бустинга получил теоретическое обоснование. Оказалось, что взвешенное голосование не увеличивает эффективную сложность алгоритма, а лишь сглаживает ответы базовых алгоритмов. Эффективность бустинга объясняется тем, что по мере добавления базовых алгоритмов увеличиваются отступы обучающих объектов. Причём бустинг продолжает раздвигать классы даже после достижения безошибочной классификации обучающей выборки.
Общая схема бустинга:
Используя различные аппроксимации для пороговой функции потерь $[z < 0]$, будем получать различные виды бустинга. Примеры:
from urllib.request import urlopen
import numpy as np
%matplotlib inline
import xgboost as xgb
from matplotlib import pyplot as plt
from sklearn.datasets import load_boston, load_digits, load_iris
from sklearn.ensemble import AdaBoostClassifier, GradientBoostingRegressor
from sklearn.metrics import confusion_matrix, mean_squared_error
from sklearn.model_selection import GridSearchCV, KFold, train_test_split
from sklearn.tree import DecisionTreeClassifier, DecisionTreeRegressor
x = np.linspace(-2, 2, 500)
plt.figure(figsize=(8, 5))
plt.plot(x, x < 0, lw=2, label="Threshold function: $[M < 0$]")
plt.plot(x, np.exp(-x), lw=2, label="AdaBoost")
plt.plot(x, np.log2(1 + np.exp(-x)), lw=2, label="LogitBoost")
plt.plot(x, (1 - x) ** 2, lw=2, label="GentleBoost")
plt.plot(x, np.exp(-x * (x + 2)), lw=2, label="BrownBoost")
plt.title("Various approximations of the threshold function")
plt.legend(loc="best")
plt.xlabel("Margin")
plt.ylabel("Loss");
Как было сказано, алгоритм AdaBoost получается из описанной схемы, при аппроксимации пороговой функции потерь с помощью функции $e^{-z}$. Cуществует теорема (Freund, Schapire, 1996), дающая для достаточно богатых семейств базовых классификаторов явные формулы для базового алгоритма $b_t(x)$ и коэффициента $\alpha_t$ при нём, на которых достигается минимум функционала $\hat{Q}_t$.
Сам алгоритм выглядит следующим образом:
Таким образом, вновь добавляемый алгоритм обучается путём минимизации взвешенной частоты ошибок на обучающей выборке, а не стандартного функционала, равного частоте ошибок. Вес объекта увеличивается в $e^{\alpha_t}$ раз, когда $b_t$ допускает на нём ошибку, и уменьшается во столько же раз, когда $b_t$ правильно классифицирует этот объект. Таким образом, непосредственно перед настройкой базового алгоритма наибольший вес накапливается у тех объектов, которые чаще оказывались трудными для классификации предыдущими алгоритмами.
Пусть базовые алгоритмы – всего лишь "пеньки", то есть деревья решений глубины 1.
Веса объектов, на которых базовый алгоритм ошибается, увеличиваются (кружки увеличиваются в размере). В конце базовые алгоритмы "голосуют", их веса определялись $\alpha_t$ в процессе построения.Сначала было обнаружено отстутствие переобучения бустинга вплоть до 1000 базовых классификаторов, позже это было теоретически обосновано.
Метод градиентного бустинга в некотором смысле является обобщением остальных методов бустинга, поскольку он позволяет оптимизировать произвольную дифференцируемую функцию потерь. Данный алгоритм похож на метод градиентного спуска, применяемый для решения задач оптимизации. Основная идея заключается в том, что каждый следующий добавляемый в композицию алгоритм настраивается на остатки предыдущих алгоритмов.
Пусть дана функция потерь дифференцируемая $\Large L(F(x), y)$. Сам алгоритм выглядит следующим образом:
Одной из возможных модификаций данного алгоритма является стохастический градиентный бустинг (SGB), который заключается в том, чтобы вычислять суммы вида $\sum_{i=1}^n$ не по всей обучающей выборке, а только по некоторой её случайной подвыборке. Такой подход является одним из способов регуляризации данного алгоритма и позволяет улучшить качество композиции, сходимость алгоритма и время обучения.
Другой способ регуляризации - это введение параметра $\gamma$, называемого темпом обучения. При добавлении нового слагаемого в композицию, будем добавлять его, умноженное на этот коэффициент. Как правило, чем меньше темп обучения, тем лучше качество итоговой композиции.
Для задач регресси обычно использую квадратичную функцию потерь $L(x, y) = (x - y)^2$ или модуль отклонения $L(x, y) = |x - y|$. В задаче классификации используется логистическая функция потерь, которая позволяет возвращать вероятности принадлежности объектов к классам.
Одним из наиболее популярных семейств базовых алгоритмов являются решающие деревья. Именно такой вариант градиентного бустинга реализован в sklearn.
Проблема многих алгоримтов построения деревьев в том, что в них не уделяется должного внимания регуляризации. В классическом градиентном бустинге применяются такие меры:
Xgboost использует еще больше параметров для регуляризации базовых деревьев.
Целевая функция для оптимизации в Xgboost состоит из двух слагаемых: специфичной функции потерь и регуляризатора $\Omega (f_k)$ для каждого из $K$ деревьев, где $f_k$ - прогноз $k$-ого дерева.
$$ obj(\theta) = \sum_{i}^{\ell} l(y_i - \hat{y_i}) + \sum_{k=1}^{K} \Omega (f_k) $$Функция потерь зависит от решаемой задачи (Xgboost адаптирован под задачи классификации, регрессии и ранжирования, (подробней хорошо описано в документации Xgboost), а регуляризатор выглядит следующим образом:
$$ \Omega(f) = \gamma T + \frac{1}{2} \lambda \sum_{j=1}^{T}w_j^2 $$Первое слагаемое ($\gamma T$) штрафует модель за большое число листьев $T$, а второе ($\frac{1}{2} \lambda \sum_{j=1}^{T}w_j^2$) контролирует сумму весов модели в листьях.
В sklearn доступны алгоритмы AdaBoost и GradientBoosting для задач классификации и регрессии. В качестве примера рассмотрим решение задачи восстановления одномерной регрессии с помощью GradientBoostingRegressor.
n_train = 150
n_test = 1000
noise = 0.1
# Generate data
def f(x):
x = x.ravel()
return np.exp(-(x ** 2)) + 1.5 * np.exp(-((x - 2) ** 2))
def generate(n_samples, noise):
X = np.random.rand(n_samples) * 10 - 5
X = np.sort(X).ravel()
y = (
np.exp(-(X ** 2))
+ 1.5 * np.exp(-((X - 2) ** 2))
+ np.random.normal(0.0, noise, n_samples)
)
X = X.reshape((n_samples, 1))
return X, y
X_train, y_train = generate(n_samples=n_train, noise=noise)
X_test, y_test = generate(n_samples=n_test, noise=noise)
# One decision tree regressor
dtree = DecisionTreeRegressor(random_state=42)
dtree.fit(X_train, y_train)
d_predict = dtree.predict(X_test)
with plt.xkcd():
plt.figure(figsize=(10, 6))
plt.plot(X_test, f(X_test), "b")
plt.scatter(X_train, y_train, c="b", s=20)
plt.plot(X_test, d_predict, "g", lw=2)
plt.xlim([-5, 5])
plt.title("Decision tree regressor, MSE = %.2f" % np.sum((y_test - d_predict) ** 2))
gbtree = GradientBoostingRegressor(n_estimators=100, subsample=0.5, random_state=42)
gbtree.fit(X_train, y_train)
gb_predict = gbtree.predict(X_test)
plt.figure(figsize=(10, 6))
plt.plot(X_test, f(X_test), "b")
plt.scatter(X_train, y_train, c="b", s=20)
plt.plot(X_test, gb_predict, "r", lw=2)
plt.xlim([-5, 5])
plt.title(
"Boosted ensemble of decision tree regressors, MSE = %.2f"
% np.sum((y_test - gb_predict) ** 2)
);
Рассмотрим пример использования AdaBoostClassifier с деревьями решений единичной глубины (decision stumps) в качестве базовых алгоритмов для решения задачи классификации.
# Loading Pima Indians Diabetes data from UCI Machine learning repository
url = "https://archive.ics.uci.edu/ml/machine-learning-databases/pima-indians-diabetes/pima-indians-diabetes.data"
raw_data = urlopen(url)
data = np.loadtxt(raw_data, delimiter=",")
X_train, X_test, y_train, y_test = train_test_split(
data[:, :8], data[:, 8], random_state=0
)
dt = DecisionTreeClassifier(random_state=42).fit(X_train, y_train)
# AdaBoost
ada = AdaBoostClassifier(DecisionTreeClassifier(max_depth=1), random_state=42).fit(
X_train, y_train
)
print("Decision tree accuracy: %.2f" % dt.score(X_test, y_test))
print("AdaBoost accuracy: %.2f" % ada.score(X_test, y_test))
Пример использования Xgboost для классификации на данных Iris.
iris = load_iris()
X = iris["data"]
y = iris["target"]
kf = KFold(n_splits=5, shuffle=True, random_state=13)
for train_index, test_index in kf.split(y):
xgb_model = xgb.XGBClassifier().fit(X[train_index], y[train_index])
predictions = xgb_model.predict(X[test_index])
actuals = y[test_index]
print(confusion_matrix(actuals, predictions))
Пример восстановления регрессии с Xgboost на данных boston.
boston = load_boston()
y = boston["target"]
X = boston["data"]
kf = KFold(n_splits=5, shuffle=True, random_state=17)
for train_index, test_index in kf.split(y):
xgb_model = xgb.XGBRegressor().fit(X[train_index], y[train_index])
predictions = xgb_model.predict(X[test_index])
actuals = y[test_index]
print(mean_squared_error(actuals, predictions))
Простой пример подбора параметров с GridSearchCV.
X = boston["data"]
y = boston["target"]
xgb_model = xgb.XGBRegressor()
xgb_grid = GridSearchCV(xgb_model, {"max_depth": [2, 4, 6]}, verbose=1)
xgb_grid.fit(X, y)
print(xgb_grid.best_score_)
print(xgb_grid.best_params_)
Ранняя остановка используется для того, чтобы прекратить обучение модели (градиентный спуск), если ошибка за несколько итераций не уменьшилась.
digits = load_digits()
X = digits["data"]
y = digits["target"]
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=17)
clf = xgb.XGBClassifier()
clf.fit(
X_train,
y_train,
early_stopping_rounds=10,
eval_metric="merror",
eval_set=[(X_test, y_test)],
)
errors_by_iter = clf.evals_result()["validation_0"]["merror"]
plt.plot(range(1, len(errors_by_iter) + 1), errors_by_iter)
plt.xlabel("iter")
plt.ylabel("error")
plt.ylim(0, 0.2);