Gradient Boosting Machine ¶ 複数の関数に重みをかけて足し合わせた関数
の形で予測モデルを構築することを考える。ここでθ 0 , … , θ M \theta_0, \dots, \theta_M θ 0 , … , θ M
このモデルはβ 1 , β 2 , … , β M \beta_1, \beta_2, \dots, \beta_M β 1 , β 2 , … , β M θ 0 , θ 1 , … , θ M \theta_0, \theta_1, \dots, \theta_M θ 0 , θ 1 , … , θ M β m f m ( x ; θ m ) \beta_m f_m(x; \theta_m) β m f m ( x ; θ m )
前向き段階的加法モデリング（forward stagewise additive modeling）
f 0 ( x ) = 0 f_0(x) = 0 f 0 ( x ) = 0
m = 1 m = 1 m = 1 M M M
パラメータを推定する：( β m , θ m ) = arg min β , θ ∑ i = 1 N L ( y i , f m − 1 ( x i ) + β f ( x i ; θ ) ) (\beta_m, \theta_m) = \argmin_{\beta, \theta} \sum^N_{i=1} L(y_i, f_{m-1}(x_i) + \beta f(x_i; \theta)) ( β m , θ m ) = arg min β , θ ∑ i = 1 N L ( y i , f m − 1 ( x i ) + β f ( x i ; θ ))
新たなモデルを足す：f m ( x ) = f m − 1 ( x ) + β m f ( x ; θ m ) f_m(x) = f_{m-1}(x) + \beta_m f(x; \theta_m) f m ( x ) = f m − 1 ( x ) + β m f ( x ; θ m )
これを前向き段階的加法モデリング（forward stagewise additive
modeling）という。ブースティングはこの方法でアンサンブル学習を行う。
誤差関数が二乗誤差L ( y , f ( x ) ) = ( y − f ( x ) ) 2 L(y, f(x)) = (y - f(x))^2 L ( y , f ( x )) = ( y − f ( x ) ) 2
L ( y i , f m − 1 ( x i ) + β f ( x i ; θ ) ) = ( y i − f m − 1 ( x i ) − β f ( x i ; θ ) ) 2 = ( residual i , m − 1 − β f ( x i ; θ ) ) 2 \begin{align}
L(y_i, f_{m-1}(x_i) + \beta f(x_i; \theta))
&= (y_i - f_{m-1}(x_i) - \beta f(x_i; \theta))^2 \\
&= (\text{residual}_{i,m-1} - \beta f(x_i; \theta))^2
\end{align} L ( y i , f m − 1 ( x i ) + β f ( x i ; θ )) = ( y i − f m − 1 ( x i ) − β f ( x i ; θ ) ) 2 = ( residual i , m − 1 − β f ( x i ; θ ) ) 2 となり、m − 1 m-1 m − 1 residual i , m − 1 = y i − f m − 1 ( x i ) \text{residual}_{i,m-1} = y_i - f_{m-1}(x_i) residual i , m − 1 = y i − f m − 1 ( x i ) m m m β f ( x i ; θ ) \beta f(x_i; \theta) β f ( x i ; θ )
最適化の観点からの説明 ¶ 勾配降下法 ¶ 数理最適化において関数の最小化問題
を解く方法のひとつに勾配降下法 （gradient descent method）あるいは最急降下法 （steepest descent method）と呼ばれるものがある。これは目的関数の微分のベクトルである勾配
を用いて
という値の更新を何度も繰り返して最適化を行っていく。ここでα \alpha α
最終的にM M M x ∗ x^* x ∗
x ∗ = x 0 − α 1 ∂ f ( x 1 ) ∂ x 1 − α 2 ∂ f ( x 2 ) ∂ x 2 − ⋯ − α M ∂ f ( x M ) ∂ x M x^* = x_0
- \alpha_1 \frac{\partial f(x_{1})}{\partial x_{1}}
- \alpha_2 \frac{\partial f(x_{2})}{\partial x_{2}}
- \cdots
- \alpha_M \frac{\partial f(x_{M})}{\partial x_{M}} x ∗ = x 0 − α 1 ∂ x 1 ∂ f ( x 1 ) − α 2 ∂ x 2 ∂ f ( x 2 ) − ⋯ − α M ∂ x M ∂ f ( x M ) となり、ブースティングにより得られる予測モデル
f ( x ) = f 0 ( x ; θ 0 ) + β 1 f 1 ( x ; θ 1 ) + ⋯ + β M f M ( x ; θ M ) f(x) = f_0(x; \theta_0) + \beta_1 f_1(x; \theta_1) + \cdots + \beta_M f_M(x; \theta_M) f ( x ) = f 0 ( x ; θ 0 ) + β 1 f 1 ( x ; θ 1 ) + ⋯ + β M f M ( x ; θ M ) と同様に重み付き和の形になる。
ブースティング ¶ ブースティングは勾配降下法を機械学習で行っていると捉えることができる。
機械学習においては予測値f ( x ) f(x) f ( x ) y y y
min f ( x ) L ( y , f ( x ) ) \min_{f(x)} L(y, f(x)) f ( x ) min L ( y , f ( x )) を解きたいため、勾配は誤差関数の予測モデルによる微分∂ L ( y , f ( x ) ) ∂ f ( x ) \frac{ \partial L(y, f(x)) }{ \partial f(x) } ∂ f ( x ) ∂ L ( y , f ( x ))
二乗誤差L ( y , f ( x ) ) = 1 2 ( y − f ( x ) ) 2 L(y, f(x)) = \frac{1}{2} (y - f(x))^2 L ( y , f ( x )) = 2 1 ( y − f ( x ) ) 2
− ∂ L ( y , f ( x ) ) ∂ f ( x ) = y − f ( x ) = residual - \frac{ \partial L(y, f(x)) }{ \partial f(x) } = y - f(x) = \text{residual} − ∂ f ( x ) ∂ L ( y , f ( x )) = y − f ( x ) = residual 前向き段階的加法モデルの節で「二乗誤差の場合は残差を近似するように学習している」と述べた。
L ( y i , f m − 1 ( x i ) + β f ( x i ; θ ) ) = ( residual i , m − 1 − β f ( x i ; θ ) ) 2 L(y_i, f_{m-1}(x_i) + \beta f(x_i; \theta)) = (\text{residual}_{i,m-1} - \beta f(x_i; \theta))^2 L ( y i , f m − 1 ( x i ) + β f ( x i ; θ )) = ( residual i , m − 1 − β f ( x i ; θ ) ) 2 これにより、学習されるモデルβ f ( x ; θ ) \beta f(x; \theta) β f ( x ; θ )
正則化つきGBDT ¶ n n n m m m
D = { ( x i , y i ) } , ∣ D ∣ = n , x i ∈ R m , y ∈ R \mathcal{D} = \{ (x_i, y_i) \}, |D| = n, x_i \in \mathbb{R}^m, y \in \mathbb{R} D = {( x i , y i )} , ∣ D ∣ = n , x i ∈ R m , y ∈ R 勾配ブースティング決定木のモデルは次のように表される
y ^ i = ϕ ( x i ) = ∑ k = 1 K f k ( x i ) \hat{y}_i = \phi(x_i) = \sum^K_{k=1} f_k(x_i) y ^ i = ϕ ( x i ) = k = 1 ∑ K f k ( x i ) ここで
学習の際は正則化付き誤差関数
L ( ϕ ) = ∑ i = 1 n l ( y ^ , y i ) + ∑ k Ω ( f k ) \mathcal{L}(\phi) = \sum^n_{i=1} l(\hat{y}, y_i) + \sum_k \Omega(f_k) L ( ϕ ) = i = 1 ∑ n l ( y ^ , y i ) + k ∑ Ω ( f k ) を最小化する。ここでl l l Ω \Omega Ω
Ω ( f ) = γ T + 1 2 λ ∣ ∣ w ∣ ∣ 2 \Omega(f) = \gamma T + \frac{1}{2} \lambda ||w||^2 Ω ( f ) = γ T + 2 1 λ ∣∣ w ∣ ∣ 2 学習は加法的に行うためt t t
L ( t ) ( ϕ ) = ∑ i = 1 n l ( y i , y ^ ( t − 1 ) + f t ( x i ) ) + Ω ( f t ) \mathcal{L}^{(t)}(\phi) = \sum^n_{i=1} l(y_i, \hat{y}^{(t-1)} + f_t(x_i)) + \Omega(f_t) L ( t ) ( ϕ ) = i = 1 ∑ n l ( y i , y ^ ( t − 1 ) + f t ( x i )) + Ω ( f t ) テイラー展開による近似 ¶ この誤差を二次近似したものを使うことで計算量を削減することもできることが知られている（Friedman et al., 2000
L ( t ) ≈ ∑ i = 1 n [ l ( y i , y ^ ( t − 1 ) ) + g i f t ( x i ) + 1 2 h i f t 2 ( x i ) ] + Ω ( f t ) \mathcal{L}^{(t)} \approx
\sum^n_{i=1} [
l(y_i, \hat{y}^{(t-1)})
+ g_i f_t(x_i)
+ \frac{1}{2} h_i f_t^2(x_i)
]
+ \Omega(f_t) L ( t ) ≈ i = 1 ∑ n [ l ( y i , y ^ ( t − 1 ) ) + g i f t ( x i ) + 2 1 h i f t 2 ( x i )] + Ω ( f t ) ここで
g i = ∂ l ( y i , y ^ ( t − 1 ) ) ∂ y ^ ( t − 1 ) h i = ∂ 2 l ( y i , y ^ ( t − 1 ) ) ∂ ( y ^ ( t − 1 ) ) 2 g_i = \frac{ \partial l(y_i, \hat{y}^{(t-1)}) }{\partial \hat{y}^{(t-1)} }\\
h_i = \frac{ \partial^2 l(y_i, \hat{y}^{(t-1)}) }{\partial (\hat{y}^{(t-1)})^2 } g i = ∂ y ^ ( t − 1 ) ∂ l ( y i , y ^ ( t − 1 ) ) h i = ∂ ( y ^ ( t − 1 ) ) 2 ∂ 2 l ( y i , y ^ ( t − 1 ) ) 定数項を省略すると
L ~ ( t ) = ∑ i = 1 n [ g i f t ( x i ) + 1 2 h i f t 2 ( x i ) ] + Ω ( f t ) \tilde{\mathcal{L}}^{(t)} =
\sum^n_{i=1} [
g_i f_t(x_i)
+ \frac{1}{2} h_i f_t^2(x_i)
]
+ \Omega(f_t) L ~ ( t ) = i = 1 ∑ n [ g i f t ( x i ) + 2 1 h i f t 2 ( x i )] + Ω ( f t ) 葉j j j I j = { i ∣ q ( x i ) = j } I_j = \{i|q(x_i) = j\} I j = { i ∣ q ( x i ) = j }
L ~ ( t ) = ∑ i = 1 n [ g i f t ( x i ) + 1 2 h i f t 2 ( x i ) ] + γ T + 1 2 λ ∑ j = 1 T w j 2 = ∑ j = 1 T [ ( ∑ i ∈ I j g i ) w j + 1 2 ( ∑ i ∈ I j h i + λ ) w j 2 ] + γ T \begin{align}
\tilde{\mathcal{L}}^{(t)}
&= \sum^n_{i=1} [
g_i f_t(x_i)
+ \frac{1}{2} h_i f_t^2(x_i)
] + \gamma T + \frac{1}{2} \lambda \sum^T_{j=1} 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^2_j
] + \gamma T
\end{align} L ~ ( t ) = i = 1 ∑ n [ g i f t ( x i ) + 2 1 h i f t 2 ( x i )] + γ T + 2 1 λ j = 1 ∑ T w j 2 = j = 1 ∑ T [( i ∈ I j ∑ g i ) w j + 2 1 ( i ∈ I j ∑ h i + λ ) w j 2 ] + γ T 固定した木の構造q ( x ) q(x) q ( x ) j j j
w j ∗ = − ∑ i ∈ I j g i ∑ i ∈ I j h i + λ w^*_j = -\frac{ \sum_{i\in I_j} g_i }{ \sum_{i \in I_j} h_i + \lambda } w j ∗ = − ∑ i ∈ I j h i + λ ∑ i ∈ I j g i となる。
葉j j j
∂ L ~ j ( t ) ∂ w j = ∑ i ∈ I j g i + ( ∑ i ∈ I j h i + λ ) w j = 0 ⟹ ( ∑ i ∈ I j h i + λ ) w j = − ∑ i ∈ I j g i ⟹ w j = − ∑ i ∈ I j g i ∑ i ∈ I j h i + λ = w j ∗ \frac{ \partial \tilde{\mathcal{L}}^{(t)}_j }{\partial w_j }
= \sum_{i\in I_j} g_i + (\sum_{i\in I_j} h_i + \lambda ) w_j
= 0
\\
\implies
(\sum_{i\in I_j} h_i + \lambda ) w_j
= -\sum_{i\in I_j} g_i
\\
\implies
w_j = -\frac{ \sum_{i\in I_j} g_i }{ \sum_{i\in I_j} h_i + \lambda } = w_j^* ∂ w j ∂ L ~ j ( t ) = i ∈ I j ∑ g i + ( i ∈ I j ∑ h i + λ ) w j = 0 ⟹ ( i ∈ I j ∑ h i + λ ) w j = − i ∈ I j ∑ g i ⟹ w j = − ∑ i ∈ I j h i + λ ∑ i ∈ I j g i = w j ∗ L1の場合
L ~ ( t ) = ∑ i = 1 n [ g i f t ( x i ) + 1 2 h i f t 2 ( x i ) ] + γ T + 1 2 λ ∑ j = 1 T w j 2 + α ∑ j = 1 T ∣ w j ∣ = ∑ j = 1 T [ ( ∑ i ∈ I j g i ) w j + 1 2 ( ∑ i ∈ I j h i + λ ) w j 2 ] + γ T \begin{align}
\tilde{\mathcal{L}}^{(t)}
&= \sum^n_{i=1} [
g_i f_t(x_i)
+ \frac{1}{2} h_i f_t^2(x_i)
]
+ \gamma T + \frac{1}{2} \lambda \sum^T_{j=1} w_j^2
+ \alpha \sum^T_{j=1} |w_j|
\\
&= \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^2_j
] + \gamma T
\end{align} L ~ ( t ) = i = 1 ∑ n [ g i f t ( x i ) + 2 1 h i f t 2 ( x i )] + γ T + 2 1 λ j = 1 ∑ T w j 2 + α j = 1 ∑ T ∣ w j ∣ = j = 1 ∑ T [( i ∈ I j ∑ g i ) w j + 2 1 ( i ∈ I j ∑ h i + λ ) w j 2 ] + γ T L1の場合
L ~ ( t ) = ∑ i = 1 n [ g i f t ( x i ) + 1 2 h i f t 2 ( x i ) ] + γ T + 1 2 λ ∑ j = 1 T w j 2 + α ∑ j = 1 T ∣ w j ∣ = ∑ j = 1 T [ ( ∑ i ∈ I j g i ) w j + α ∣ w j ∣ + 1 2 ( ∑ i ∈ I j h i + λ ) w j 2 ] + γ T \begin{align}
\tilde{\mathcal{L}}^{(t)}
&= \sum^n_{i=1} [
g_i f_t(x_i)
+ \frac{1}{2} h_i f_t^2(x_i)
]
+ \gamma T + \frac{1}{2} \lambda \sum^T_{j=1} w_j^2
+ \alpha \sum^T_{j=1} |w_j|
\\
&= \sum^T_{j=1} [
(\sum_{i\in I_j} g_i) w_j
+ \alpha |w_j|
+ \frac{1}{2} (\sum_{i\in I_j} h_i + \lambda ) w^2_j
] + \gamma T
\end{align} L ~ ( t ) = i = 1 ∑ n [ g i f t ( x i ) + 2 1 h i f t 2 ( x i )] + γ T + 2 1 λ j = 1 ∑ T w j 2 + α j = 1 ∑ T ∣ w j ∣ = j = 1 ∑ T [( i ∈ I j ∑ g i ) w j + α ∣ w j ∣ + 2 1 ( i ∈ I j ∑ h i + λ ) w j 2 ] + γ T ∑ j = 1 T [ ⋅ ] \sum^T_{j=1} [\cdot] ∑ j = 1 T [ ⋅ ]
w j ∗ = − ∑ i ∈ I j g i ± α ∑ i ∈ I j h i + λ w^*_j = -\frac
{ \sum_{i\in I_j} g_i \pm \alpha }
{ \sum_{i \in I_j} h_i + \lambda } w j ∗ = − ∑ i ∈ I j h i + λ ∑ i ∈ I j g i ± α 最適な重みw j ∗ w_j^* w j ∗
L ~ ( t ) ( q ) = − 1 2 ∑ j = 1 T ( ∑ i ∈ I j g i ) 2 ∑ i ∈ I j h i + λ + γ T \tilde{\mathcal{L}}^{(t)}(q)
= -\frac{1}{2} \sum^T_{j=1}
\frac{ (\sum_{i\in I_j} g_i)^2 }
{ \sum_{i\in I_j} h_i + \lambda }
+ \gamma T L ~ ( t ) ( q ) = − 2 1 j = 1 ∑ T ∑ i ∈ I j h i + λ ( ∑ i ∈ I j g i ) 2 + γ T となり、これ木の構造q q q
L ~ ( t ) = ∑ j = 1 T [ ( ∑ i ∈ I j g i ) ( − ∑ i ∈ I j g i ∑ i ∈ I j h i + λ ) + 1 2 ( ∑ i ∈ I j h i + λ ) ( − ∑ i ∈ I j g i ∑ i ∈ I j h i + λ ) 2 ] + γ T = ∑ j = 1 T [ − ( ∑ i ∈ I j g i ) 2 ∑ i ∈ I j h i + λ + 1 2 ( ∑ i ∈ I j g i ) 2 ∑ i ∈ I j h i + λ ] + γ T = ∑ j = 1 T [ − 1 2 ( ∑ i ∈ I j g i ) 2 ∑ i ∈ I j h i + λ ] + γ T \begin{align}
\tilde{\mathcal{L}}^{(t)}
&= \sum^T_{j=1} [
(\sum_{i\in I_j} g_i)
(-\frac{ \sum_{i\in I_j} g_i }{ \sum_{i \in I_j} h_i + \lambda })
+ \frac{1}{2} (\sum_{i\in I_j} h_i + \lambda )
(-\frac{ \sum_{i\in I_j} g_i }{ \sum_{i \in I_j} h_i + \lambda })^2
] + \gamma T
\\
&= \sum^T_{j=1} [
-\frac{ (\sum_{i\in I_j} g_i)^2 }{ \sum_{i \in I_j} h_i + \lambda }
+ \frac{1}{2} \frac{ (\sum_{i\in I_j} g_i)^2 }{ \sum_{i \in I_j} h_i + \lambda }
] + \gamma T
\\
&= \sum^T_{j=1} [
- \frac{1}{2} \frac{ (\sum_{i\in I_j} g_i)^2 }{ \sum_{i \in I_j} h_i + \lambda }
] + \gamma T
\end{align} L ~ ( t ) = j = 1 ∑ T [( i ∈ I j ∑ g i ) ( − ∑ i ∈ I j h i + λ ∑ i ∈ I j g i ) + 2 1 ( i ∈ I j ∑ h i + λ ) ( − ∑ i ∈ I j h i + λ ∑ i ∈ I j g i ) 2 ] + γ T = j = 1 ∑ T [ − ∑ i ∈ I j h i + λ ( ∑ i ∈ I j g i ) 2 + 2 1 ∑ i ∈ I j h i + λ ( ∑ i ∈ I j g i ) 2 ] + γ T = j = 1 ∑ T [ − 2 1 ∑ i ∈ I j h i + λ ( ∑ i ∈ I j g i ) 2 ] + γ T Schapire, R. E. (1990). The strength of weak learnability. Machine learning, 5, 197-227.
Friedman, J., Hastie, T., & Tibshirani, R. (2000). Additive logistic regression: a statistical view of boosting (with discussion and a rejoinder by the authors). The annals of statistics, 28(2), 337-407.
GBDTの応用のガイドライン
Boldini, D., Grisoni, F., Kuhn, D., Friedrich, L., & Sieber, S. A. (2023). Practical guidelines for the use of gradient boosting for molecular property prediction. Journal of Cheminformatics, 15(1), 73.
XGBoost, CatBoost, LightGBMの解説と化学分野の分子抑制予測タスクにおける比較