XGBoostをある程度理解しました。いずれ、XGBoostと再度向き合ったときに思い出しやすいように今回の記事を書きました。参考リンクにも書きましたが既に素晴らしい記事も多いので、個人的な備忘録の意味合いが強いです。
基本的なアルゴリズムは以下で記載した前進逐次加法モデリングと同じ。
多くの数式は以下のブログ記事抜粋です(素晴らしい)。
計算順序
以下の計算手順です。
- 出力関数と損失関数
- 出力関数と損失関数の漸化式化
- リーフノードの最適化
- リーフノード最適解を損失関数に埋め込み
- 損失関数を使ったリーフノード増減判断
計算手順
1. 出力関数と損失関数
最終的な出力
説明変数$x_i$に対する決定木全体の出力。
$f_k(x)$: 決定木kの出力関数。
\hat{y_i} = \sum_{k=1}^{K} f_k(x_i) \tag{1}
損失関数
L2正則化項付き損失関数。γは葉ノードに対する正則化項、λは重みに対する正則化項。
\mathcal L(\phi)=\sum_i \mathcal l(\hat{y_i}, y_i) + \sum_k \Omega(f_k) \\
where \ \ \Omega(f)= \gamma T + \frac{1}{2} \lambda w^2 \tag{2} \\
L1正則化だと以下になるはず(少し自信なし)。
\ \ \Omega(f)= \gamma T + \alpha ||w|| \tag{3}
2. 出力関数と損失関数の漸化式化
出力関数(漸化式)
tは木の数。出力関数を漸化式として表現。
前進逐次加法モデリングなので漸化式として表現可能。
\hat{y_i}^{(t)} = \hat{y_i}^{(t-1)} + f_t(x_i) \tag{4}
損失関数(漸化式)
漸化式での損失関数。
正則化項$\Omega (f_k)$から$\sum_k$が消えたのは、この時点で訓練対象ではなく定数項扱いだから。
{\begin{align}
\mathcal L^{(t)} &= \sum_i^{n} \mathcal l\,(y_i^{(t)}, \hat{y_i}^{(t)}) + \Omega (f_k) \\
&= \sum_i^{n} \mathcal l\,(y_i^{(t)}, \hat{y_i}^{(t-1)} + f_t(x_i)) + \Omega (f_k)
\end{align}
} \tag{5}
漸化式の損失関数を2次の項までのテイラー展開で近似値にします。関数$l$の$\hat{y_i}^{t-1}$周辺でテイラー展開です。
{\begin{align}
\mathcal L^{(t)} &= \sum_i^{n} l\,(y_i^{(t)}, \hat{y_i}^{(t-1)} + f_t(x_i)) + \Omega (f_k) \\
&= \sum_i^{n} [l\,(y_i^{(t)}, \hat{y_i}^{(t-1)}) + l'(y_i^{(t)}, \hat{y_i}^{(t-1)})\, f_t(x_i)
+ \frac{1}{2!} l''\,(y_i^{(t)}, \hat{y_i}^{(t-1)})\, (f_t(x_i))^2]
+ \Omega (f_k) \\
&= \sum_i^{n} [l\,(y_i^{(t)}, \hat{y_i}^{(t-1)}) + \frac{\partial }{\partial \hat{y_i}^{(t-1)}} \,l\,(y_i^{(t)}, \hat{y_i}^{(t-1)})\, f_t(x_i)
+ \frac{1}{2} \frac{\partial^2}{(\partial \hat{y_i}^{(t-1)})^2}\,l\,(y_i^{(t)}, \hat{y_i}^{(t-1)})\, (f_t(x_i))^2]
+ \Omega (f_k) \\
&= \sum_i^{n} [l\,(y_i^{(t)}, \hat{y_i}^{(t-1)}) + g_i \, f_t(x_i)
+ \frac{1}{2} h_i \, f^2_t(x_i)]
+ \Omega (f_k) \\
\end{align}
} \tag{6}
{\begin{align}
where \quad g_i &= \frac{\partial }{\partial \hat{y_i}^{(t-1)}} \,l\,(y_i^{(t)}, \hat{y_i}^{(t-1)}) \\
h_i &= \frac{\partial^2}{(\partial \hat{y_i}^{(t-1)})^2}(l\,(y_i^{(t)}, \hat{y_i}^{(t-1)}) \\
f_t^2(x_i) &= (f_t(x_i))^2
\end{align}
} \tag{7}
ここで定数項$l(y_i^{(t)}, \hat{y_i}^{(t-1)})$を除去して、正則化項を元に戻します。
※$l(y_i^{(t)}, \hat{y_i}^{(t-1)})$は$f_t(x_i)$に依存しない、確定した木の情報なので定数項。
{\begin{align}
\tilde{\mathcal {L}}^{(t)} &= \sum_i^{n} [g_i \, f_t(x_i)
+ \frac{1}{2} h_i \, f^2_t(x_i)] + \Omega (f_k) \\
&= \sum_i^{n} [g_i \, f_t(x_i)
+ \frac{1}{2} h_i \, f^2_t(x_i)]
+ \gamma T + \frac{1}{2} \lambda \sum_{j=1}^{T}w_j^2 \\
\end{align}
} \tag{8}
3. リーフノードの最適化
リーフノードの最適化
j番目のリーフノード$w_j$の最適解を求めます。
第1項の$\sum_i^n$を第3項の$\sum_{j=1}^T$に揃えます。つまり、データの総和からリーフノードの総和に変換です。
※$\sum_{i \in I_j}$: 実際に出力されたノードのみの総和
{\begin{align}
\tilde{\mathcal {L}}^{(t)} &=
\sum_i^{n} [g_i \, f_t(x_i) + \frac{1}{2} h_i \, f^2_t(x_i)]
+ \gamma T + \frac{1}{2} \lambda \sum_{j=1}^{T}w_j^2 \\
&= \sum_{j=1}^T \sum_{i \in I_j} [g_i \, f_t(x_i)
+ \frac{1}{2} h_i \, f^2_t(x_i)]
+ \gamma T + \frac{1}{2} \lambda \sum_{j=1}^{T}w_j^2\\
&=\sum_{j=1}^T [(\sum_{i \in I_j} g_i) \, w_j
+ \frac{1}{2} (\sum_{i \in I_j} h_i) \, w_j^2]
+ \gamma T + \frac{1}{2} \lambda \sum_{j=1}^{T}w_j^2 \ \ \because f_t(x_i)=w_j\\
&= \sum_{j=1}^T [( \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
\end{align}
} \tag{8}
$x_i$に対して対応する葉ノードが変化しない場合の、j番目の葉ノードの最適解を求めます。
損失関数である(8)の式を$w_j$で微分をします。
{\begin{align}
\frac{\partial \tilde{\mathcal L}^{(t)}}{\partial w_j} &= \frac{\partial}{\partial w_j}(
\sum_{j=1}^T [( \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_{i \in I_j}g_i) + (\sum_{i \in I_j} h_i + \lambda) w_j \\
&= 0 \\
\end{align}
} \tag{9}
これで$w_j$の最適解が求まりました。
w_j^* = - \frac{\sum_{i \in I_j} g_i}{\sum_{i \in I_j} h_i + \lambda} \tag{10}
4. リーフノード最適解を損失関数に埋め込み
損失関数の式(8)にリーフノードの最適解$w_j$を代入。
{\begin{align}
\tilde{\mathcal {L}}^{(t)} &= \sum_{j=1}^T [( \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_{j=1}^T \left[\left( \sum_{i \in I_j} g_i\right) \, \left(- \frac{\sum_{i \in I_j} g_i}{\sum_{i \in I_j} h_i + \lambda}\right)
+ \frac{1}{2} \left( \sum_{i \in I_j} h_i + \lambda\right) \left(- \frac{\sum_{i \in I_j} g_i}{\sum_{i \in I_j} h_i + \lambda} \right)^2\right]
+ \gamma T \\
&= \sum_{j=1}^T \left[\left(- \frac{(\sum_{i \in I_j} g_i)^2}{\sum_{i \in I_j} h_i + \lambda}\right)
+ \frac{1}{2} \left(- \frac{(\sum_{i \in I_j} g_i)^2}{\sum_{i \in I_j} h_i + \lambda} \right)\right]
+ \gamma T \\
&= - \frac{1}{2} \sum_{j=1}^{T} \frac{(\sum_{i \in I_j}g_i)^2}{\sum_{i \in I_j}(h_i + \lambda)} + \gamma T\\
\end{align}
} \tag{11}
これで、固定した構造での損失関数の最小値が出ました。この損失関数を使ってリーフノードを増やすかを判断します。
5. 損失関数を使ったリーフノード増減判断
リーフノード増減判断
以下の前提でリーフノード増減を判断します。正の場合は、損失が減っているのでリーフノードを増やしたほうがいい。
- $\mathcal L$: 分割しなかった場合の損失関数
- $\mathcal L_L$: 分割後の左側リーフノードの損失関数
- $\mathcal L_R$: 分割後の右側リーフノードの損失関数
- $\mathcal L_{split}$: 分割前後の損失関数の差
リーフノードが1増える(1減って2増える)ので、最後の正則化項は-γとなります(リーフノードを増やさないようにするためのペナルティ)。
{\begin{align}
\mathcal L_{split} &= \mathcal L - (\mathcal L_L + \mathcal L_R) \\
&= - \frac{1}{2}[\frac{(\sum_{i \in I} g_i)^2}{\sum_{i \in I}h_i + \lambda}
- \frac{(\sum_{i \in I_L} g_i)^2}{\sum_{i \in I_L}h_i + \lambda}
- \frac{(\sum_{i \in I_R} g_i)^2}{\sum_{i \in I_R}h_i + \lambda} ] - \gamma\\
&= \frac{1}{2}[\frac{(\sum_{i \in I_L} g_i)^2}{\sum_{i \in I_L}h_i + \lambda}
+ \frac{(\sum_{i \in I_R} g_i)^2}{\sum_{i \in I_R}h_i + \lambda}
- \frac{(\sum_{i \in I} g_i)^2}{\sum_{i \in I}h_i + \lambda}] - \gamma\\
\end{align}
} \tag{12}
参考リンク
以下を参考に理解