XGBoost

Шаблон:Infobox software XGBoost (eXtreme Gradient Boosting) — это библиотека с открытым исходным кодом, используемая в машинном обучении и предоставляющая функциональность для решения задач, связанных с регуляризацией градиентного бустинга. Библиотека поддерживается языками программирования C++, Java, Python, R, Julia, Perl и Scala. Библиотека работает под ОС Linux, Windows, и macOS. Она работает как на одной машине, так и на системах распределенной обработки Apache Hadoop, Apache Spark и Apache Flink.

В последнее время эта библиотека приобрела большую популярность и привлекла внимание как выбор многих команд-победителей соревнований по машинному обучению.

История

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

Вскоре XGBoost был интегрирован с рядом других пакетов, что упростило его использование в соответствующих сообществах. Сейчас он интегрирован в scikit-learn для пользователей Python и в пакет caret для пользователей R. Он также может быть интегрирован в такие фреймворки Data Flow, как Apache Spark, Apache Hadoop и Apache Flink с помощью абстрактного Rabit и XGBoost4J. XGBoost также доступен на OpenCL для ПЛИС. Эффективная, масштабируемая реализация XGBoost была опубликована Чэн Тяньци и Карлосом Густрином.

Хотя модель XGBoost часто достигает более высокой точности, чем одно дерево решений, она жертвует присущей деревьям решений интерпретируемостью. Например, проследить путь, по которому дерево решений принимает решение, тривиально и самообъяснимо, но проследить пути сотен или тысяч деревьев гораздо сложнее. Для достижения производительности и интерпретируемости некоторые методы сжатия моделей позволяют преобразовать XGBoost в одно "перерожденное" дерево решений, которое аппроксимирует ту же функцию принятия решений.

Функционал

Основные особенности XGBoost, отличающие его от других алгоритмов градиентного бустинга, включают:.

• Умная штрафовка деревьев
• Пропорциональное уменьшение узлов листьев
• Метод Ньютона в оптимизации
• Дополнительный параметр рандомизации
• Реализация на одиночных, распределенных системах и out-of-core вычислениях
• Автоматический отбор признаков

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

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

Общий вид нерегуляризованного алгоритма XGBoost: Шаблон:Начало коробки Вход: обучающее множество $\{(x_i,y_i){\}}_{i=1}^N$, дифференцируемая функция потерь $L(y,F(x))$, число слабых обучающихся $M$ и скорость обучения $\alpha$.

Алгоритм:

1. Инициализировать модель постоянным значением:

   ${\hat{f}}_{(0)}(x)=\underset{\theta }{\arg \min }\sum _{i=1}^{N}L(y_i,\theta ).$

2. Для Шаблон:Mvar = от 1 до Шаблон:Mvar:
   1. Вычислите "градиенты" и "гессианы":

      ${\hat{g}}_m(x_i)={\left[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}\right]}_{f(x)={\hat{f}}_{(m-1)}(x)}.$

      ${\hat{h}}_m(x_i)={\left[\frac{{\partial }^{2}L(y_i,f(x_i))}{\partial f(x_i{)}^2}\right]}_{f(x)={\hat{f}}_{(m-1)}(x)}.$

   2. Подогнать базового/слабого обучающегося, используя обучающее множество ${\{x_i,-\frac{{\hat{g}}_m(x_i)}{{\hat{h}}_m(x_i)}\}}_{i=1}^N$, решив следующую оптимизационную задачу:

      ${\hat{\varphi }}_m=\underset{\varphi \in \mathrm{\Phi }}{\arg \min }\sum _{i=1}^N\frac{1}{2}{\hat{h}}_m(x_i){[-\frac{{\hat{g}}_m(x_i)}{{\hat{h}}_m(x_i)}-\varphi (x_i)]}^2.$

      ${\hat{f}}_m(x)=\alpha {\hat{\varphi }}_m(x).$

   3. Обновление модели:

      ${\hat{f}}_{(m)}(x)={\hat{f}}_{(m-1)}(x)+{\hat{f}}_m(x).$

3. Результат: $\hat{f}(x)={\hat{f}}_{(M)}(x)=\sum _{m=0}^M{\hat{f}}_m(x).$

Награды

• Премия John Chambers (2016)
• Премия High Energy Physics meets Machine Learning award (HEP meets ML) (2016)