title-icon
Яндекс.Метрика

XGBoost

26.10.2022


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 {displaystyle {(x_{i},y_{i})}_{i=1}^{N}} , дифференцируемая функция потерь L ( y , F ( x ) ) {displaystyle L(y,F(x))} , число слабых обучающихся M {displaystyle M} и скорость обучения α {displaystyle alpha } .

Алгоритм:

  • Инициализировать модель постоянным значением: f ^ ( 0 ) ( x ) = arg ⁡ min θ ∑ i = 1 N L ( y i , θ ) . {displaystyle {hat {f}}_{(0)}(x)={underset { heta }{arg min }}sum _{i=1}^{N}L(y_{i}, heta ).}
  • Для m = от 1 до M:
  • Вычислите "градиенты" и "гессианы": g ^ m ( x i ) = [ ∂ L ( y i , f ( x i ) ) ∂ f ( x i ) ] f ( x ) = f ^ ( m − 1 ) ( x ) . {displaystyle {hat {g}}_{m}(x_{i})=left[{frac {partial L(y_{i},f(x_{i}))}{partial f(x_{i})}} ight]_{f(x)={hat {f}}_{(m-1)}(x)}.} h ^ m ( x i ) = [ ∂ 2 L ( y i , f ( x i ) ) ∂ f ( x i ) 2 ] f ( x ) = f ^ ( m − 1 ) ( x ) . {displaystyle {hat {h}}_{m}(x_{i})=left[{frac {partial ^{2}L(y_{i},f(x_{i}))}{partial f(x_{i})^{2}}} ight]_{f(x)={hat {f}}_{(m-1)}(x)}.}
  • Подогнать базового/слабого обучающегося, используя обучающее множество { x i , − g ^ m ( x i ) h ^ m ( x i ) } i = 1 N {displaystyle displaystyle left{x_{i},-{frac {{hat {g}}_{m}(x_{i})}{{hat {h}}_{m}(x_{i})}} ight}_{i=1}^{N}} , решив следующую оптимизационную задачу: ϕ ^ m = arg ⁡ min ϕ ∈ Φ ∑ i = 1 N 1 2 h ^ m ( x i ) [ − g ^ m ( x i ) h ^ m ( x i ) − ϕ ( x i ) ] 2 . {displaystyle {hat {phi }}_{m}={underset {phi in mathbf {Phi } }{arg min }}sum _{i=1}^{N}{frac {1}{2}}{hat {h}}_{m}(x_{i})left[-{frac {{hat {g}}_{m}(x_{i})}{{hat {h}}_{m}(x_{i})}}-phi (x_{i}) ight]^{2}.} f ^ m ( x ) = α ϕ ^ m ( x ) . {displaystyle {hat {f}}_{m}(x)=alpha {hat {phi }}_{m}(x).}
  • Обновление модели: f ^ ( m ) ( x ) = f ^ ( m − 1 ) ( x ) + f ^ m ( x ) . {displaystyle {hat {f}}_{(m)}(x)={hat {f}}_{(m-1)}(x)+{hat {f}}_{m}(x).}
  • Результат: f ^ ( x ) = f ^ ( M ) ( x ) = ∑ m = 0 M f ^ m ( x ) . {displaystyle {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)