初めに

勾配ブースティングの仕組みをできるだけ分かりやすく説明します。
機械学習についてざっくりとした知識がある前提で書いています。
訂正箇所がありましたらご指摘くださいお願いします。

導入

ブースティングについて

機械学習におけるアンサンブル学習のひとつ
(アンサンブル学習とは、単独では精度の高くない学習器(弱学習器)を多数作り、その組み合わせで精度の高い学習器をつくる手法群)

一般的なブースティング(例えばAdaBoost)では、予測精度の悪い分類器(弱学習器)を使い予測を行い間違えた箇所の「重み」を大きくした新しい学習器を作成することを繰り返す。
最終的に作成した弱学習器に重みをつけた多数決を出力結果とする。

H(x)=\operatorname{sign}\left(\sum_{t=1}^{T} \alpha_{t} h_{t}(x)\right)

$H(x)$:モデルの最終出力
$h_t(x)$:弱学習器
$\alpha_{t}$:弱学習器の重み(その弱学習器がどれだけ大切か)
$sign()$:SIGN関数,符号関数(正なら1,負なら-1を返す関数)

勾配ブースティングについて

一方、勾配ブースティングは学習器によって出力された予測値と正解ラベルとの誤差を次第に小さくしていき、弱学習器を強い学習器に更新していく手法
最終的に作成された学習器の出力を出力結果とする。

F_{T}(x)=f_{0}(x)+\sum_{t=1}^{T} \alpha_{t} f_{t}(x)

$F_T(x)$:モデルの最終出力
$f_{0}(x)$:初期学習器
$\alpha_{t}$:ステップサイズ
$f_t(x)$:探索方向($x$ごとの探索方向を返す関数(学習器))

最急降下法(勾配降下法)を使っているのが名前の由来(たぶん)

勾配ブースティングは何に使われている?

GBDT-Gradient Boosting Decision Tree (勾配ブースティング決定木)で使われている手法

Kaggleでよく用いられるXGBoostやLightGBMは、勾配ブースティングを使っていると思われがちだが実はNewton Boostingを使っている。
(最急降下法を使った勾配ブースティングは一次微分までの情報しか使わないが、Newton法を使ったNewton Boostingは二次微分の情報まで活用する)

仕組み

1初期化をする

損失関数$L(y_i,\rho)$が全ての$i$に対して最小になるように$\rho$を計算する
式にすると以下のようになる。

f_0(x)=argmin_{\rho}\sum_{i=1}^NL(y_i,\rho)

例えば、損失関数が二乗誤差とすると

L=\sum_i^N \frac{1}{2}(y_i-\rho)^2

であり、これを最小にするような$\rho$はこの式を$\rho$で微分して(=0)となるものなので

\begin{align}
\frac{\partial}{\partial \rho}L\left(y_{i},\rho\right)
&=\frac{\partial}{\partial \rho}\sum_i^N \frac{1}{2}(y_i-\rho)^2\\\\
&=\sum_{i=1}^Ny_i-N\rho\\\\
\end{align}

\rho=\frac{1}{N}\sum_{i=1}^Ny_i

これより、損失関数が二乗誤差の時の初期値は

f_0(x)=\frac{1}{N}\sum_{i=1}^Ny_i

となる。

2何を繰り返すのか

勾配ブースティングが何を繰り返しているのかというと以下の計算です。
$t$回目の更新では

\begin{align}
F_{t}(x)
&=f_0(x)+\alpha_{1} f_{1}(x)+\alpha_{2} f_{2}(x)+\alpha_{3} f_{3}(x)...+\alpha_{t} f_{t}(x)\\\
&=F_{t-1}(x)+ \alpha_{t} f_{t}(x)
\end{align}

となり、最終的に$T$回目では

\begin{align}F_{T}(x)&=f_{0}(x)+\sum_{t=1}^{T} \alpha_{t} f_{t}(x)\\\\
&=F_{T-1}(x)+ \alpha_{T} f_{T}(x)
\end{align}

となっている。
これより、$t$回目の更新には$\alpha_t$と$f_t(x)$を求める必要があることが分かります。それぞれ名称は
- $\alpha_{t}$:ステップサイズ
- $f_t(x)$:探索方向
という。
縦軸を損失関数L、横軸を関数$F_{t-1}(x_i)$として模式的に図示すると$\alpha_{t}$と$f_t(x_i)$はそれぞれ以下のようになる。(あくまでイメージです)
注意が必要なのはこの図はある$x_i$の時の模式図であり、$x_i$ごとに図の様子は異なると考えてください。

グラフの一番低い最適な解へ向かうために、どちらに進むのかを$f_t(x_i)$がどれぐらい進むのかを$\alpha_{t}$が表している。
数学的には無限個の基底を持つ関数空間内で、ある基底$f_t(x)$に沿って$\alpha_t$だけ降下している。
先に、探索方向を$x_i$ごとに計算し$f_t(x)$を求め、次に求めた$f_t(x)$を用いてステップサイズ$\alpha_{t}$を計算する。
このような手法を直線探索法という。

3探索方向を決めよう

探索方向は$x_i$ごとに異なるため、それぞれ計算する。
探索方向の決め方は先程の図に示してある損失関数を横軸の関数で微分する方法である。

\frac{\partial L\left(y_{i}, F_{t-1}\left(x_{i}\right)\right)}{\partial F_{t-1}\left(x_{i}\right)}

この計算結果の逆符号を$\tilde{y}_{i}$とすると、$\tilde{y}_i$の符号は最適な解$F(x)$のある方向と一致している。

\tilde{y}_i=-\frac{\partial L\left(y_{i}, F_{t-1}\left(x_{i}\right)\right)}{\partial F_{t-1}\left(x_{i}\right)}\\

また$\tilde{y}_i$は$F(x)$の方向の情報以外に、点$x_i$における損失関数の変化の度合いの情報も含んでいる。
しかし、この値は$x_i$ごとに決まる離散的な点の集まりであるため、この点にフィットするような関数(学習器)$f_t(x_i)$を見つける必要がある。この$f_t(x_i)$を見つけるために、以下の損失関数

l=\sum_{i=1}^{N}\left(\tilde{y}_{i}-f_{t}\left(x_{i}\right)\right)^{2}

が最小になる$f_t(x)$をもとめる。(弱学習器$f_t(x)$によってフィッティングする、この弱学習器はもとの学習器と同じである必要はない)
そうすることで、全ての$x_i$の探索方向に関する情報および$x_i$ごとの変化の大きさの情報を持った$f_t(x)$を求めることができます。
これは関数空間で、もっとも勾配の逆符号にフィッティングしたある基底の関数を見つけだす操作に対応している。
このような数学的な手法を勾配降下法(Gradient descent)という。勾配降下法以外にも最適な解の方向を探す方法はある。例えば二次微分まで計算する方法をニュートン法といい、ニュートン法を使ったブースティングをニュートンブースティングという。
LightGBMやXGBoostではニュートンブースティングが採用されている。

4ステップサイズを決めよう

$f_t(x_i)$が求まったので次にステップサイズを求めていこうと思います。
近いうちに書きます...

5関数を更新しよう

3と4で求めた探索方向$f_t(x_i)$と更新幅$\alpha_t$を使いt回目の更新

F_{t}(x)=F_{t-1}(x)+ \alpha_{t} f_{t}(x)

を実行する。$t=T$なら更新を終了し$t\neq T$なら3と4を繰り返す。

上:正解ラベルの点$y$と$F_{t-1}(x)$の図
中央:$\tilde{y}_i$と$f_t(x)$の図
下:正解ラベルの点$y$と$F_t(x)=F_{t-1}(x)+\alpha_{t}f_{t}(x)$の図

更新前の$F_{t-1}(x)$より、更新後の$F_t(x)$の方がよりデータにフィットしていることがわかる。

6最終的な出力

T回の更新が終わり、最終的な出力は

\begin{align}
F_{T}(x)
&=f_0(x)+\alpha_{1} f_{1}(x)+\alpha_{2} f_{2}(x)+\alpha_{3} f_{3}(x)...+\alpha_{T} f_{T}(x)\\\
&=f_{0}(x)+\sum_{t=1}^{T} \alpha_{t} f_{t}(x)\\
\end{align}