XGBoost: A Scalable Tree Boosting System

March 26, 2022

XGBoostは、キャッシュやシャーディングによる高速な勾配ブースティングのライブラリであり、スパースなデータもあつかえる。 情報利得を最大化する分岐をもとめてノードからのばすときは、ノードにあるサンプルで分岐の条件を決定する。 このとき、欠損のない特徴の値のみをつかい、欠損のないサンプル数の線形オーダまで計算量を削減する。 情報利得の最大値をもとめるときは、分岐条件になる特徴が欠損しているときに左右どちらに分岐させるべきかを計算する。

訓練データ\(\mathcal{D}=\{(\boldsymbol{\rm x}_i, y_i)\}(\mid \mathcal{D} \mid = n, \boldsymbol{\rm x}_i\in \mathbb{R}^m, y_i\in \mathbb{R})\)があるとき、決定木を弱識別器にするアンサンブルモデルの出力関数は次の式をとる。 $$ \hat{y}_i=\phi(\boldsymbol{\rm x}_i)=\sum^K_{k=1}f_k(\mathcal{\rm x}_i), f_k \in \mathcal{F} $$ ただし、\(F=\{f(\boldsymbol{\rm x})=w_{q(\boldsymbol{\rm x})}\}(q: \mathbb{R}^m \rightarrow T, w\in \mathbb{R}^T)\)は決定木の集合、\(T\)は葉の数、\(q\)はサンプルを葉に写像する決定木の関数、\(w\)は葉の重みである。

この出力関数の正則化項をふくむ損失関数は $$ \mathcal{L}(\phi) = \sum_i l(\hat{y_i}, y_i) + \sum_k \left(\gamma T + \frac{1}{2}\lambda \mid\mid w \mid\mid^2 \right) $$ である。\(l\)は微分可能な凸関数である。

\(t\)をくりかえしの回数として、\(g_i = \partial_{\hat{y}^{(t-1)}}l(y_i, \hat{y}^{(t-1)})\), \(h_i = \partial^2_{\hat{y}^{(t-1)}}l(y_i,\hat{y}^{(t-1)})\)とすると損失関数は、 $$ \mathcal{\tilde{L}}^{(t)}(q) = -\frac{1}{2}\sum^T_{j=1}\frac{\left(\sum_{i\in I_j}g_i\right)^2}{\sum_{i\in I_j}h_i + \lambda} + \gamma T $$ で近似的にもとめられる。

損失関数で最適な決定木がわかるが、とりえるすべての決定木を構築し損失関数で評価することは計算量上できない。 そこで、勾配ブースティングは、以下のアルゴリズムで1つのノードから徐々に枝をのばして決定木を構築する。 greedy

XGBoostは、スパースなデータであれば、以下のアルゴリズムによって、欠損データをつかわずに情報利得を最大化できる分岐をもとめる。 アルゴリズムの中では、欠損したデータがあるときに、左右どちらに分岐するほうがいいかを比較する。 sparse

論文をこちらからダウンロードできます。 画像は論文から引用しています。