XGBoost

XGBoostは、 C++、Java、Python、R、Julia、Perl 、Scala用の正則化勾配ブースティングフレームワークを提供するオープンソースソフトウェアライブラリ。 Linux、Windows、macOSで動作する。 プロジェクトの説明によると、「スケーラブルでポータブルな分散型勾配ブースティング（GBM、GBRT、GBDT）ライブラリ」を提供することを目的としている。 単一のマシンだけでなく、分散処理フレームワークであるApache Hadoop、Apache Spark、Apache Flink、Daskでも動作する。

機械学習コンテストの優勝チームの多くが選択するアルゴリズムとして、人気と注目を集めている。

同様に勾配ブースティングに基づくアルゴリズムとして、LightGBMとCatBoostが存在する。

歴史

XGBoostは、Distrubuted (Deep) Machine Learning Community (DMLC) グループの一員であるTianqi Chen氏の研究プロジェクトとしてスタートした。当初は、libsvmの設定ファイルで設定可能なターミナル・アプリケーションだった。 Higgs Machine Learning Challenge で優勝した際に使用されたことで、機械学習コンテストの世界で広く知られるようになった。その後すぐにPythonとRのパッケージが作られ、Java、Scala、Julia、Perl、その他の言語のパッケージ実装ができた。これにより、XGBoost はより多くの開発者に利用されるようになり、Kaggleコミュニティでも人気を博し、多くのコンペティションで利用されている。

すぐに他の多くのパッケージと統合され、それぞれのコミュニティでの使用が容易になった。 Pythonユーザーにはscikit-learn、Rユーザーにはcaretパッケージと統合された。 また、抽象化されたRabitとXGBoost4Jを使って、Apache Spark、 Apache Hadoop、Apache FLINK などのデータフローフレームワークに統合することもできる。XGBoostは、OpenCL for FPGAでも利用できる 。 XGBoostの効率的でスケーラブルな実装は、Tianqi ChenとCarlos Guestrinによって発表された。

特徴

XGBoostは、他の勾配ブースティングアルゴリズムとは異なる、以下の様な特徴を持っている。

• Clever penalization of trees
• A proportional shrinking of leaf nodes
• Newton Boosting
• Extra randomization parameter
• Implementation on single, distributed systems and out-of-core computation
• Automatic Feature selection

アルゴリズム

XGBoostは、関数空間でニュートンラフソンとして動作する。関数空間で勾配降下法として機能する勾配ブースティングとは異なり、損失関数に2次テイラー近似を使用してニュートンラフソン法との関連性を持たせている。

一般的な非正則化 XGBoost アルゴリズムは次の通り。テンプレート:枠の始まり Input: training set $\{(x_i,y_i){\}}_{i=1}^N$, a differentiable loss function $L(y,F(x))$, a number of weak learners $M$ and a learning rate $\alpha$.

Algorithm:

1. Initialize model with a constant value:

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

2. For テンプレート:Mvar = 1 to テンプレート:Mvar:
   1. Compute the 'gradients' and 'hessians':

      ${\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. Fit a base learner (or weak learner, e.g. tree) using the training set $\{x_i,-\frac{{\hat{g}}_m(x_i)}{{\hat{h}}_m(x_i)}{\}}_{i=1}^N$ by solving the optimization problem below:

      ${\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. Update the model:

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

3. Output $\hat{f}(x)={\hat{f}}_{(M)}(x)=\sum _{m=0}^M{\hat{f}}_m(x).$

賞

2006年

• ジョン・チェンバース賞
• High Energy Physics Meets Machine Learning Award（HEP Meets ML

関連項目

• 勾配ブースティング
• LightGBM
• CatBoost

外部リンク

• テンプレート:Official website
• テンプレート:GitHub
• XGBoost Documentation