XGBoost — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Возможности XGBoost)
(Математика за алгоритмом)
(не показано 10 промежуточных версий 6 участников)
Строка 2: Строка 2:
  
 
==История==
 
==История==
XGBoost изначально стартовал как исследовательский проект Тяньцзи Чена (Tianqi Chen) как часть сообщества распределенного глубинного машинного обучения. Первоначально он начинался как терминальное приложение, которое можно было настроить с помощью файла конфигурации libsvm. После победы в Higgs Machine Learning Challenge, он стал хорошо известен в соревновательный кругах по машинному обеспечению. Вскоре после этого были созданы пакеты для Python и R, и теперь у него есть пакеты для многих других языков, таких как Julia, Scala, Java и т. д. Это принесло библиотеке больше разработчиков и сделало ее популярной среди сообщества Kaggle<ref>[https://www.kaggle.com/ Kaggle]</ref>, где она использовалось для большого количества соревнований.
+
XGBoost изначально стартовал как исследовательский проект Тяньцзи Чена (Tianqi Chen) как часть сообщества распределенного глубинного машинного обучения. Первоначально он начинался как терминальное приложение, которое можно было настроить с помощью файла конфигурации libsvm. После победы в Higgs Machine Learning Challenge, он стал хорошо известен в соревновательный кругах по машинному обеспечению. Вскоре после этого были созданы пакеты для Python и R, и теперь у него есть пакеты для многих других языков, таких как Julia, Scala, Java и т. д. Это принесло библиотеке больше разработчиков и сделало ее популярной среди сообщества Kaggle<ref>[https://www.kaggle.com/ Kaggle]</ref>, где она использовалось для большого количества соревнований. Программное обеспечение разработано по методологии SCRUM.
  
 
Она вскоре стала использоваться с несколькими другими пакетами, что облегчает ее использование в соответствующих сообществах. Теперь у нее есть интеграция с scikit-learn для пользователей Python, а также с пакетом caret для пользователей R. Она также может быть интегрирована в рамах потока данных, таких как Apache Spark<ref>[https://spark.apache.org/ Apache Spark]</ref>, Apache Hadoop<ref>[https://hadoop.apache.org/ Apache Hadoop]</ref>, и Apache Flink<ref>[https://flink.apache.org/ Apache Flink]</ref> с использованием абстрактных Rabit<ref>[https://github.com/dmlc/rabit Rabit]</ref> и XGBoost4J<ref>[https://xgboost.readthedocs.io/en/latest/jvm/ XGBoost JVM]</ref>. Принцип работы XGBoost также был опубликован Тяньцзи Ченом (Tianqi Chen) и Карлосом Гастрин (Carlos Guestrin).
 
Она вскоре стала использоваться с несколькими другими пакетами, что облегчает ее использование в соответствующих сообществах. Теперь у нее есть интеграция с scikit-learn для пользователей Python, а также с пакетом caret для пользователей R. Она также может быть интегрирована в рамах потока данных, таких как Apache Spark<ref>[https://spark.apache.org/ Apache Spark]</ref>, Apache Hadoop<ref>[https://hadoop.apache.org/ Apache Hadoop]</ref>, и Apache Flink<ref>[https://flink.apache.org/ Apache Flink]</ref> с использованием абстрактных Rabit<ref>[https://github.com/dmlc/rabit Rabit]</ref> и XGBoost4J<ref>[https://xgboost.readthedocs.io/en/latest/jvm/ XGBoost JVM]</ref>. Принцип работы XGBoost также был опубликован Тяньцзи Ченом (Tianqi Chen) и Карлосом Гастрин (Carlos Guestrin).
Строка 8: Строка 8:
 
==Описание алгоритма==
 
==Описание алгоритма==
 
[[File:golf-MSE.png|700px|thumb|[https://explained.ai/gradient-boosting/images/golf-MSE.png Иллюстрация бустинга]]]
 
[[File:golf-MSE.png|700px|thumb|[https://explained.ai/gradient-boosting/images/golf-MSE.png Иллюстрация бустинга]]]
В основе '''XGBoost''' лежит алгоритм [[Бустинг, AdaBoost|градиентного бустинга]] [[Дерево решений и случайный лес|деревьев решений]]. Идея алгоритма в том, что каждое следующе дерево предсказывает ошибку обученного ансамбля на каждом элементе обучающей выборки. Каждое отдельное дерево обучается одним из стандартных алгоритмов используемых для обучения деревьев решений. Таким образом предсказание складывается из предсказаний каждого отдельного дерева ансамбля.
+
В основе '''XGBoost''' лежит алгоритм [[Бустинг, AdaBoost|градиентного бустинга]] [[Дерево решений и случайный лес|деревьев решений]].
 +
Градиентный бустинг — это техника машинного обучения для задач классификации и регрессии, которая строит модель предсказания в форме ансамбля слабых предсказывающих моделей, обычно деревьев решений.
 +
Обучение ансамбля проводится последовательно в отличие, например от [[Виды_ансамблей | бэггинга]]. На каждой итерации вычисляются отклонения предсказаний уже обученного ансамбля на обучающей выборке. Следующая модель, которая будет добавлена в ансамбль будет предсказывать эти отклонения. Таким образом, добавив предсказания нового дерева к предсказаниям обученного ансамбля мы можем уменьшить среднее отклонение модели, которое является таргетом оптимизационной задачи. Новые деревья добавляются в ансамбль до тех пор,
 +
пока ошибка уменьшается, либо пока не выполняется одно из правил "ранней остановки".
  
 +
Рассмотрим иллюстрацию бустинга. На ней рассматривается поведение модели на одной точке абстрактной задачи линейной регрессии. Предположим, что первая модель ансамбля <tex>F</tex> всегда выдает
 +
выборочное среднее предсказываемой величины <tex>f_0</tex>. Такое предсказание довольно грубое, поэтому среднеквадратичное отклонение на выбранной нами точке будет довольно большим. Мы попробуем это исправить обучив модель
 +
<tex>\Delta_1</tex>, которая будет "корректировать" предсказание предыдущего ансамбля <tex>F_0</tex>. Таким образом мы получим ансамбль <tex>F_1</tex>, предсказание которого будет суммироваться из предсказаний моделей <tex>f_0</tex> и <tex>\Delta_1</tex>. Продолжая такую последовательность мы приходим к ансамблю <tex>F_4</tex> предсказание которого суммируется из предсказаний <tex>f_0</tex>, <tex>\Delta_1</tex>, <tex>\Delta_2</tex>, <tex>\Delta_3</tex>, <tex>\Delta_4</tex> и предсказывает в точности значение заданного таргета.
 
===Математика за алгоритмом===
 
===Математика за алгоритмом===
 
<tex>\mathcal{L}^{(t)} = \sum_{i=1}^n l(y_i,\hat{y_i}^{(t-1)}+f_t(x_i))+\Omega(f_t)</tex> {{---}} функция для оптимизации градиентного бустинга, где:
 
<tex>\mathcal{L}^{(t)} = \sum_{i=1}^n l(y_i,\hat{y_i}^{(t-1)}+f_t(x_i))+\Omega(f_t)</tex> {{---}} функция для оптимизации градиентного бустинга, где:
Строка 24: Строка 30:
 
<tex>w</tex> {{---}} значения в листьях, а <tex>\gamma</tex> и <tex>\lambda</tex> {{---}} параметры регуляризации.
 
<tex>w</tex> {{---}} значения в листьях, а <tex>\gamma</tex> и <tex>\lambda</tex> {{---}} параметры регуляризации.
  
Дальше с помощью разложения Тейлора до второго члена можем приблизить это следующим выражением:
+
Дальше с помощью разложения Тейлора до второго члена можем приблизить оптимизируемую функцию <tex>\mathcal{L}^{(t)}</tex> следующим выражением:
  
<tex>\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)</tex>, где
+
<tex>\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)</tex>, где
  
 
<tex>g_i = \frac {\partial {l(y_i,\hat{y_i}^{t-1})}}{\partial{\hat{y_i}^{t-1}}}</tex>, <tex>h_i = \frac {\partial^2 {l(y_i,\hat{y_i}^{t-1})}}{\partial^2{\hat{y_i}^{t-1}}}</tex>
 
<tex>g_i = \frac {\partial {l(y_i,\hat{y_i}^{t-1})}}{\partial{\hat{y_i}^{t-1}}}</tex>, <tex>h_i = \frac {\partial^2 {l(y_i,\hat{y_i}^{t-1})}}{\partial^2{\hat{y_i}^{t-1}}}</tex>
  
Поскольку мы хотим минимизировать ошибку модели на обучающей выборки, нам нужно найти минимум <tex>\mathcal{L}^{(t)}</tex> для каждого ''t''.
+
Поскольку мы хотим минимизировать ошибку модели на обучающей выборке, нам нужно найти минимум <tex>\mathcal{L}^{(t)}</tex> для каждого ''t''.
  
 
Минимум этого выражения относительно <tex>f_t(x_i)</tex> находится в точке <tex>f_t(x_i) = \frac{-g_i}{h_i}</tex>.
 
Минимум этого выражения относительно <tex>f_t(x_i)</tex> находится в точке <tex>f_t(x_i) = \frac{-g_i}{h_i}</tex>.
Строка 64: Строка 70:
 
==Основные параметры==
 
==Основные параметры==
 
* ''n_estimators'' {{---}} число деревьев.
 
* ''n_estimators'' {{---}} число деревьев.
* ''eta'' {{---}} размер шага. Пердотвращает переобучение.
+
* ''eta'' {{---}} размер шага. Предотвращает переобучение.
 
* ''gamma'' {{---}} минимальное изменение значения ''loss'' функции для разделения листа на поддеревья.
 
* ''gamma'' {{---}} минимальное изменение значения ''loss'' функции для разделения листа на поддеревья.
 
* ''max_depth'' {{---}} максимальная глубина дерева.
 
* ''max_depth'' {{---}} максимальная глубина дерева.
Строка 81: Строка 87:
 
==Пример использования с помощью библиотеки xgboost==
 
==Пример использования с помощью библиотеки xgboost==
 
Загрузка датасета.
 
Загрузка датасета.
  from sklearn import datasets
+
  '''from''' sklearn '''import''' datasets
  iris = datasets.load_iris()
+
  iris = datasets.'''load_iris'''()
  X = iris.data
+
  X = iris.'''data'''
  y = iris.target
+
  y = iris.'''target'''
  
 
Разделение датасета на обучающую/тестовую выборку.
 
Разделение датасета на обучающую/тестовую выборку.
  from sklearn.cross_validation import train_test_split
+
  '''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)
+
  X_train, X_test, y_train, y_test = '''train_test_split'''(X, y, test_size=0.2, random_state=42)
  
 
Импорт ''XGBoost'' и создание необходимых объектов.
 
Импорт ''XGBoost'' и создание необходимых объектов.
  import xgboost as xgb
+
  '''import''' xgboost as xgb
  dtrain = xgb.DMatrix(X_train, label=y_train)
+
  dtrain = xgb.'''DMatrix'''(X_train, label=y_train)
  dtest = xgb.DMatrix(X_test, label=y_test)
+
  dtest = xgb.'''DMatrix'''(X_test, label=y_test)
  
 
Задание параметров модели.
 
Задание параметров модели.
Строка 105: Строка 111:
  
 
Обучение.
 
Обучение.
  bst = xgb.train(param, dtrain, num_round)
+
  bst = xgb.'''train'''(param, dtrain, num_round)
  preds = bst.predict(dtest)
+
  preds = bst.'''predict'''(dtest)
  
 
Определение качества модели на тестовой выборке.
 
Определение качества модели на тестовой выборке.
  import numpy as np
+
  '''import''' numpy '''as''' np
  from sklearn.metrics import precision_score
+
  '''from''' sklearn.metrics '''import''' precision_score
 
  best_preds = np.asarray([np.argmax(line) for line in preds])
 
  best_preds = np.asarray([np.argmax(line) for line in preds])
  print precision_score(y_test, best_preds, average='macro')
+
  '''print''' precision_score(y_test, best_preds, average='macro')
  
 
==См. также==
 
==См. также==
Строка 127: Строка 133:
  
 
[[Категория: Машинное обучение]]
 
[[Категория: Машинное обучение]]
 +
[[Категория: Ансамбли]]

Версия 13:59, 28 сентября 2021

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

История

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

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

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

В основе XGBoost лежит алгоритм градиентного бустинга деревьев решений. Градиентный бустинг — это техника машинного обучения для задач классификации и регрессии, которая строит модель предсказания в форме ансамбля слабых предсказывающих моделей, обычно деревьев решений. Обучение ансамбля проводится последовательно в отличие, например от бэггинга. На каждой итерации вычисляются отклонения предсказаний уже обученного ансамбля на обучающей выборке. Следующая модель, которая будет добавлена в ансамбль будет предсказывать эти отклонения. Таким образом, добавив предсказания нового дерева к предсказаниям обученного ансамбля мы можем уменьшить среднее отклонение модели, которое является таргетом оптимизационной задачи. Новые деревья добавляются в ансамбль до тех пор, пока ошибка уменьшается, либо пока не выполняется одно из правил "ранней остановки".

Рассмотрим иллюстрацию бустинга. На ней рассматривается поведение модели на одной точке абстрактной задачи линейной регрессии. Предположим, что первая модель ансамбля [math]F[/math] всегда выдает выборочное среднее предсказываемой величины [math]f_0[/math]. Такое предсказание довольно грубое, поэтому среднеквадратичное отклонение на выбранной нами точке будет довольно большим. Мы попробуем это исправить обучив модель [math]\Delta_1[/math], которая будет "корректировать" предсказание предыдущего ансамбля [math]F_0[/math]. Таким образом мы получим ансамбль [math]F_1[/math], предсказание которого будет суммироваться из предсказаний моделей [math]f_0[/math] и [math]\Delta_1[/math]. Продолжая такую последовательность мы приходим к ансамблю [math]F_4[/math] предсказание которого суммируется из предсказаний [math]f_0[/math], [math]\Delta_1[/math], [math]\Delta_2[/math], [math]\Delta_3[/math], [math]\Delta_4[/math] и предсказывает в точности значение заданного таргета.

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

[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)}[/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

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

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

  • Стандартный градиентный бустинг с возможностью изменения скорости обучения(learning rate).
  • Стохастический градиентный бустинг[8] с возможностью семплирования по строкам и колонкам датасета.
  • Регуляризованный градиентный бустинг[9] с L1 и L2 регуляризацией.

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

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

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

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

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

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

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

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

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

Поддерживаемые интерфейсы

  • Интерфейс командной строки (CLI).
  • C++ (язык, на котором написана библиотека).
  • Интерфейс Python, а также модель в Scikit-Learn.
  • R интерфейс, а также модель в пакете карета.
  • Julia.
  • JVM языки, такие как Java, Scala, и платформы, такие как Hadoop.

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

Импорт XGBoost и создание необходимых объектов.

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')

См. также

Примечания

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