Zenn
Open2

XGBoost

機械学習
xgboost
haru256haru256

XGBoost

ロス

Gradient Tree Boostingの場合、t番目の木のロス関数は以下の通りで、このロスを最小化するような木を構築する。

\mathcal{L}^{(t)}=\sum_{i=1}^n l\left(y_i, \hat{y}_i^{(t-1)}+f_t\left(\mathbf{x}_i\right)\right)+\Omega\left(f_t\right)

ここで、\Omega\left(f_t\right)は以下のような正則化項。

\Omega\left(f_t\right) = \gamma T + \frac{1}{2} \lambda \| w \|^2

XGBoostでは、上記損失関数ではなく、以下の2次のテイラー展開で近似した損失関数を最小化する（ニュートン法）。

\mathcal{L}^{(t)} \simeq \sum_{i=1}^n\left[l\left(y_i, \hat{y}^{(t-1)}\right)+g_i f_t\left(\mathbf{x}_i\right)+\frac{1}{2} h_i f_t^2\left(\mathbf{x}_i\right)\right]+\Omega\left(f_t\right)

t番目の木を構築する際、上式のl\left(y_i, \hat{y}^{(t-1)}\right)は定数項のため、t番目の木で考える損失関数は以下のとおりとなる。

\tilde{\mathcal{L}}^{(t)} = \sum_{i=1}^n\left[g_i f_t\left(\mathbf{x}_i\right)+\frac{1}{2} h_i f_t^2\left(\mathbf{x}_i\right)\right]+\Omega\left(f_t\right)

Structure Score

回帰のXGBoostでは、回帰木を連ねていくが、split点の選定に独自のスコアを使用する。Structure Score or Similarity Scoreと呼ばれる。Scoreといっているが、本家の定式化では小さいほうがより良い値で、Gini Impurityのような意味を持つ。

まず、ある木構造qのStructure Scoreを以下で定義する。ここで、Tはleafノードの数、\lambdaはL2正則化パラメータであり、\gammaはリーフ数に対する抑制パラメータ、g_i, h_iは実際の値 y_i と予測値 \hat{y}_i の微分可能なloss l(\hat{y}_i, y_i) の1階微分・2階微分を表す。

\tilde{\mathcal{L}}^{(t)}(q)=-\frac{1}{2} \sum_{j=1}^T \frac{\left(\sum_{i \in I_j} g_i\right)^2}{\sum_{i \in I_j} h_i+\lambda}+\gamma T

split点は、以下のStructure Scoreの減少幅が最も大きい点をsplit点とする。I_L, I_Rはそれぞれleft nodeとright nodeを表し、I = I_L \cup I_R は分割対象のnodeを意味する。また、上式の第一項部はgainと呼ばれる。

\mathcal{L}_{\text {split }}=\frac{1}{2}\left[\frac{\left(\sum_{i \in I_L} g_i\right)^2}{\sum_{i \in I_L} h_i+\lambda}+\frac{\left(\sum_{i \in I_R} g_i\right)^2}{\sum_{i \in I_R} h_i+\lambda}-\frac{\left(\sum_{i \in I} g_i\right)^2}{\sum_{i \in I} h_i+\lambda}\right]-\gamma

最終的なleaf j の出力値は以下の値とする。論文では w_j をleaf weightやleaf scoreと読んでいる。

w_j^*=-\frac{\sum_{i \in I_j} g_i}{\sum_{i \in I_j} h_i+\lambda}

Pruning

ハイパーパラメータ\gammaを導入し、gain が\gamma未満であればその分割をpruningする。
つまり、 Structure Scoreの減少幅 \mathcal{L}_{\text {split }}が負になれば、その分割をpruningする。

L2正則化パラメータ

L2正則化パラメータ \lambda は値が大きいほど Structure Score \tilde{\mathcal{L}}^{(t)}(q) の値は小さくなり、Structure Scoreの減少幅 \mathcal{L}_{\text {split }} は小さくなる。そのため、pruningが引き起こされやすくなり、結果として深さが浅い木ができあがる。
ただし、L2正則化パラメータを0に設定してもpruning が発生することはある。

cover