XGBoost は、アンサンブル学習の一種であるブースティングを利用した手法及び実装です。
アンサンブル学習とは、複数のモデル（弱学習器）を組み合わせて、より強力なモデルを作る手法のことです。
XGBoost は、性能的にも優れており、たびたびコンペの上位入賞者が使う手法です。
多数のハイパーパラメーターを持ち、調整するためにはある程度手法について知っている必要があります。
そこで、このページでは、XGBoost のパラメーターの意味を理解できることを目標に、仕組みをまとめます。
なお、このページでは弱学習器に木を使う場合を主に説明します。

参考情報

仕組みについて

公式ドキュメント: https://xgboost.readthedocs.io/en/latest/tutorials/model.html
論文(arXiv): https://arxiv.org/abs/1603.02754
作者による説明スライド: https://homes.cs.washington.edu/~tqchen/pdf/BoostedTree.pdf

パラメーターについて

公式ドキュメント: https://xgboost.readthedocs.io/en/latest/parameter.html

仕組み

XGBoost はブースティングを木と組み合わせた GBDT (Gradient Boosted Descision Tree) と呼ばれる手法の一種です。
（XGBoost 自体は、木以外と組み合わせて使うこともできるのですが、性能的に木と組み合わせて使われることが多いようです。）
以下では、ブースティングの基本から仕組みを説明していきます。

ほぼ公式ドキュメントの内容を踏襲するものになっていますが、一部数式は、わかりやすそうな等価な式に変えたりしています。（わかりやすいかは主観によりますが。。。）

ブースティングの基本

XGBoost がブースティングを利用した手法であることをすでに説明したので、ブースティングの基本からまとめていきます。
ブースティングは、その時点までに学習済みのモデルを生かして次の弱学習器を作っていくような手法を指します。
これを繰り返すことで性能改善を図ります。

具体的な例を下記に示します。

ある入力 ${ x_i }$ に対して、 ${ y_i }$ を予測することを考えてみましょう。
まず最初に、１つモデル ${ f_1 }$ を作ります。
このモデルの出力を ${ y_i }$ に対する予想値 ${ \hat{y}_i ^1 }$ とします。

${ \begin{align} \hat{y}_i^1 = f_1 (x_i) \end{align} }$

モデルが予想した結果と実際の ${ y_i }$ の差が発生します。

${ \begin{align} err_i^1 = y_i - \hat{y}_i^1 \end{align} }$

もし、ここで ${ err_i ^1 }$ を出力するようなモデル ${ f_2 }$ を作ることを考えます。
${ f_2 }$ がある程度 ${ err_i ^1 }$ にフィットしているのなら、以下の予想値は、 ${ \hat{y}_i ^1 }$ よりも良い予想となるはずです。

${ \begin{align} \hat{y}_i^2 = \hat{y}_i^1 + f_2 (x_i) = f_1 (x_i) + f_2 (x_i) \end{align} }$

さらに、 ${ \hat{y}_i ^2 }$ 　と ${ y_i }$ の残差を予想するモデル ${ f_3 }$ を作ることもできます。
これを繰り返していけば、モデルの性能はあげられそうです。
このように、その時点までに学習済みのモデルにより得られた知識を使って次のモデルを構築していくというのがブースティングの基本となります。

目的関数の導入

ここまで見てきた手法は、わかりやすいものの柔軟性にはかけます。
つまり、残差を減らすということしか考慮できておらず、任意の目的関数に対して最適化をできるわけではありません。

例えば、MSE (平均二乗誤差) でモデルを学習させたいとしましょう。
しかし、上の方法では、たしかに残差は減るものの直接 MSE を最適化しているわけではありません。

タスクごとに適切な目的関数は異なるため、任意の目的関数を考慮した最適化がができればより便利になります。
そこで、以下では任意の目的関数に対してブースティングを適用する方法を考えて行きます。

まず、各ステップでモデルを作成し、それらを足し合わせて予想とするという基本的な考え方は変わりません。

${ \begin{split}\hat{y}_i^{(0)} &= 0\\ \hat{y}_i^{(1)} &= f_1(x_i) = \hat{y}_i^{(0)} + f_1(x_i)\\ \hat{y}_i^{(2)} &= f_1(x_i) + f_2(x_i)= \hat{y}_i^{(1)} + f_2(x_i)\\ &\dots\\ \hat{y}_i^{(t)} &= \sum_{k=1}^t f_k(x_i)= \hat{y}_i^{(t-1)} + f_t(x_i) \end{split} }$

目的関数は、一般的に以下の形をとります。

${ \begin{align} \text{obj}^{(t)} = \sum_{i=1}^n l(y_i, \hat{y}_i^{(t)}) + \sum_{i=1}^t\Omega(f_i) \\ \end{align} }$

ここで、右辺の第一項は損失関数、第二項は正則化項です。
${ f_{t-1} }$ までのモデルはすでに作っていて、次の ${ f_t }$ を作ることを考えます。
目的関数を少し変形します。

${ \begin{align} \text{obj}^{(t)} &= \sum_{i=1}^n l(y_i, \hat{y}_i^{(t)}) + \sum_{i=1}^t\Omega(f_i) \\ &= \sum_{i=1}^n l(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)) + \Omega(f_t) + \sum_{i=1}^{t-1}\Omega(f_i) \end{align} }$

目的関数を考慮してブースティングするためには、この式を最小化させるような ${ f_t }$ を作ればよいことになります。
このままでは、任意の損失関数に対してモデルを求めにくいため、テイラー展開の 2 次の項までの求めます。

${ \begin{align} \text{obj}^{(t)} \approx \sum_{i=1}^n [l(y_i, \hat{y}_i^{(t-1)}) + g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i)] + \Omega(f_t) + \sum_{i=1}^{t-1}\Omega(f_i) \end{align} }$

${ \begin{align} g_i &= \left.\frac{\partial}{\partial \hat{y}_i} l(y_i, \hat{y}_i) \right|_{\hat{y}_i=\hat{y}_i^{(t-1)}}\\ h_i &= \left.\frac{\partial^2}{(\partial \hat{y}_i)^2} l(y_i, \hat{y}_i) \right|_{\hat{y}_i=\hat{y}_i^{(t-1)}}\\ \end{align} }$

${ f_{t-1} }$ まではすでに決まっているので、結局下記の式を最小化する ${ f_t }$ を求めることで目的関数に対してブースティングを適用することができます。

${ \begin{align} \sum_{i=1}^n [g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i)] + \Omega(f_t) \end{align} }$

ここまで、 ${ f_t }$ に具体的にどのようなモデルを使うかに立ち入ることなく議論を進めている点に注意して下さい。
ブースティング手法は、木と組み合わせて使われることが多いですが、他のモデルにも適用することが可能となっています。

木に適用することを考える

ここから具体的に木に対して適用することを考えます。
ここでは、CART (classification and regression trees) という形式の木を考えます。
CART は各葉にスコアが割り当てられており、入力に対して、葉に割り当てた値を返すような木です。
CART については、こちらの図がわかりやすいです。

これを踏まえると CART は以下のように表現できます。

${ \begin{align} f_t(x) = w_{q(x)}, w \in R^T, q:R^d\rightarrow \{1,2,\cdots,T\} \end{align} }$

ここで記号は、

${T}$ は、葉の数
${w = \{w_i\}}$ は、各葉の値を表す T 次元ベクトル
${q}$ は、CART への入力(x) を受取り分類される葉の番号を返す関数

をそれぞれあらわしています。

また、正則化項を下記のように定義します。

${ \begin{align} \Omega(f) = \gamma T + \frac{1}{2}\lambda \sum_{j=1}^T w_j^2 \end{align} }$

正則化項はこれが唯一の定義というわけではありません。
実際に、XGBoost でもハイパーパラメーターを指定すると L1 正則化項が追加できたりもします。

構築済みの木にスコアを割り当てる

次に、すでに構築済みの木にスコアを割り当てることを考えましょう。（どうやって木の構造を学習するかは一旦おいておきます。）
これまでの議論をまとめると、以下の式を最小化する ${ w }$ を各葉に割り当てれば良いことになります。

${ \begin{align} \text{obj}^{(t)} & \approx \sum_{i=1}^n [g_i w_{q(x_i)} + \frac{1}{2} h_i w_{q(x_i)}^2] + \gamma T + \frac{1}{2}\lambda \sum_{j=1}^T w_j^2\\ &= \sum^T_{j=1} [(\sum_{i\in I_j} g_i) w_j + \frac{1}{2} (\sum_{i\in I_j} h_i + \lambda) w_j^2 ] + \gamma T\\ &= \sum^T_{j=1} [G_jw_j + \frac{1}{2} (H_j+\lambda) w_j^2] +\gamma T \end{align} }$

${ \begin{align} G_j &= \sum_{i\in I_j} g_i\\ H_j &= \sum_{i\in I_j} h_i \end{align} }$

${ I_j }$ は j 番目に割り振られるデータのインデックスの集合です ${ I_j = \{i|q(x_i)=j\} }$
各 ${ w_j }$ が独立だとすれば、最良値 ${ w_j^{\ast} }$ は微分から簡単に求めることができて、下記のようになります。

${ \begin{align} w_j^\ast = -\frac{G_j}{H_j+\lambda} \end{align} }$

つまり木がすでに構築されていれば、上の値を各葉の値として割り当てれば、目的関数の最良値が得られるというわけです。

${ \begin{align} \text{obj}^\ast &= -\frac{1}{2} \sum_{j=1}^T \frac{G_j^2}{H_j+\lambda} + \gamma T \end{align} }$

どうやって木を構築するか

構築済みの木にスコアを割り当てる方法はわかったので、あとはどのように木を構築するかを決められればすべて解決です。

理想的には、全ての可能な木を構築してそれぞれに対して ${\text{obj}^\ast}$ を計算し、最も小さい値を与える木を採用すれば良いでしょう。
でも、変数が多くなればこれは困難です。

そこで、枝を一つ分岐させるごとに考えることにします。
すなわち、一つ木の枝を分岐させると、目的関数の最良値 ${\text{obj}^\ast }$ は以下の値だけ減少します。

${ \begin{align} Gain = \frac{1}{2} \left[\frac{G_L^2}{H_L+\lambda}+\frac{G_R^2}{H_R+\lambda}-\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}\right] - \gamma \end{align} }$

${ \begin{align} G_R : 右の葉に対して g_i を足し合わせたもの\\ G_L : 左の葉に対して g_i を足し合わせたもの\\ H_R : 右の葉に対して h_i を足し合わせたもの\\ H_L : 左の葉に対して h_i を足し合わせたもの\\ \end{align} }$

つまり、各説明変数に対して分割候補を作成し、最も大きい Gain を与えるものを採用します。
これを繰り返すことで木を構築していきます。
もし、Gain > 0 となるような分割候補がなければ分割は行わないことにします。（損失の減少分が　 ${\gamma}$ よりも小さいと分岐が行われないことになります。）

このようにして、木を構築することができます。
（この方法で得られた木が最良のものであるという保証はありませんが、なんとなく良さそうな木がこの方法で学習できます。）

XGBoost のパラメーター

ここからは、上記の仕組みを踏まえてパラメーターについて説明します。基本的に公式ドキュメントの内容ですが、適宜論文などからも補足をしています。

XGBoost のパラメーターは、大きく下記の 4 種類にわけられています。

General parameters：共通の動作に関するパラメーター
Booster parameters：弱学習器の種類に依存するパラメーター
Learning task parameters：学習についてのパラメーター
Command line parameters：コマンドラインからのパラメーター

Booster parameters については、このページでは弱学習器に木を使ったパラメーターのみについて説明します。
また、Command line parameters も説明は省略します。

General parameters

booster [default= gbtree ]
弱学習器として何を使うか
silent [default=0] [Deprecated]
ログに関する制御
現在は非推奨なので、verbosity を使うこと
verbosity [default=1]
ログに関する制御
0 (silent), 1 (warning), 2 (info), 3 (debug)
nthread [default to maximum number of threads available if not set]
スレッド数
デフォルトでは CPU スレッド数
disable_default_eval_metric [default=0]
Set to >0 to disable.
num_pbuffer [set automatically by XGBoost, no need to be set by user]
予想値を保存するバッファのサイズ
XGBoost が自動で設定するので指定不要
num_feature [set automatically by XGBoost, no need to be set by user]
特徴量の数
XGBoost が自動で設定するので指定不要

Booster parameters (for Tree Booster)

eta [default=0.3, alias: learning_rate]
上の説明では、単純にモデルを足し合わせることで予想値を作りましたが、実際には、作成したモデルの効果に係数 ${\eta}$ をかけて弱めるということが行われます。
range: [0,1]
式で書くとこんな感じ

${ \begin{align} \hat{y}_i^{(t)} &= \hat{y}_i^{(t-1)} + \eta f_t(x_i) \end{align} }$

gamma [default=0, alias: min_split_loss]
正則化項に出てきた ${\gamma}$
range: [0,∞]
max_depth [default=6]
木の深さの最大値
range: [0,∞] (0 is only accepted in lossguided growing policy when tree_method is set as hist)
min_child_weight [default=1]
葉に割り当てるスコア ${ w_i }$ の合計の最小値
これを下回った場合、それ以上の分割を行わない
range: [0,∞]
max_delta_step [default=0]
葉に関する制約らしいのですが、ちょっと正確な意味がわかりませんでした。
クラス間に極端な不均衡（多い・少ない）がある場合に使われるパラメーターとのこと。
range: [0,∞]
subsample [default=1]
木を構築する前にデータのサブサンプリングを行う比率
1 なら全部のデータを使うし、0.5 なら半分のデータを使う
range: (0,1]
colsample_bytree, colsample_bylevel, colsample_bynode [default=1]
列のサブサンプリングを行う比率
2 つ以上を指定した場合は累計的に機能する
たとえば、64の特徴量があった場合、{'colsample_bytree':0.5, 'colsample_bylevel':0.5, 'colsample_bynode':0.5} では、各分割で 8 つの特徴量が使われる
range of (0, 1]
サブサンプリングを行うタイミングごとに別れている
- colsample_bytree : 各木を構築する前に行われる (木ごとに一回のみ)
- colsample_bylevel : 木の深さごとに1回づつ行われる
- colsample_bynode : ノードごとに1回づつ行われる
lambda [default=1, alias: reg_lambda]
L2 正則化項の係数として出てきた ${\lambda}$
alpha [default=0, alias: reg_alpha]
L1 正則化項の係数
上の説明では L2 正則化項しか記載していませんでしたが、このパラメーターを設定することで、目的関数に L1 正則化項を追加することができます。
tree_method string [default= auto]
ツリー構築アルゴリズム
上の説明では木の構築する際に、すべての変数で可能な分割を調べて行くと簡単に書きましたが、実際にこれを行おうとするとデータ数や変数の数によっては時間が多くかかる場合もあります。そのため、いくつかのアルゴリズムが用意されています。
詳しくは論文の「3. SPLIT FINDING ALGORITHMS]」に記載されています。
sketch_eps [default=0.03]
tree_method=approx の場合にのみ使われる変数
range: (0, 1)
scale_pos_weight [default=1]
正と負の ${w}$ のバランスを制御します。正負のデータ数に違いがある場合に役立つ
典型的には、(負例の数) / (正例の数) などを指定
updater [default= grow_colmaker,prune]
木のアップデーター
これは高度なパラメータで、通常は他のパラメータに応じて自動的に設定される
refresh_leaf [default=1]
updater に refresh を指定した場合に使われる値
process_type [default= default]
ブースティングプロセスの種類
grow_policy [default= depthwise]
新しいノードをツリーに追加する方法を制御
tree_method=hist の場合にのみサポート
max_leaves [default=0]
葉の最大数
max_bin, [default=256]
ビンの最大数
tree_method=hist の場合にのみ有効
predictor, [default=cpu_predictor]
予想を行う際のアルゴリズム (CPU で実行するか、GPU で実行するか)
num_parallel_tree, [default=1]
各ブーストステップで構築される木の数
各ステップでランダムフォレストを使う場合は 1 より大きな値

Learning Task Parameters

objective [default=reg:squarederror]
目的関数
base_score [default=0.5]
予想の初期値
eval_metric [default according to objective]
評価指標
特に指定しなかった場合、objective と同じ指標が使われます
seed [default=0]
乱数シード

以上が、木を使った XGBoost の全パラメーターです。かなり数が多いですね。。。

パラメーターチューニング

実際に使うためにはこのように多くのパラメーターを調整する必要がありますが、ここについては、タスクごとに試してみないことにはなんとも言えないというところだそうです。

web で検索すると、XGBoost のパラメーターチューニングについて書かれている記事もたくさんありますので、こういったページを参考にさせていただきつつ、いろんなパラメーターの組み合わせで試すしかないみたいです。

taka5hi’s blog

統計と機械学習の話題をメインに記事を書いています。

機械学習アルゴリズム：XGBoost の仕組みとパラメーター