Gradirnt Boosting Decision Treeの勉強をした。
動機
Kaggleなどで話題となっているLightGBMなどのことを知るためにまず、勾配ブースティング決定木の勉強をした。
\[\DeclareMathOperator{\mathrm{argmin}}{arg\,min}\]決定木とは
決定木では特徴量 $x$ を元に排反な $J$ 個の分割領域 $\{R_j\}_{j=1}^J$ を構成し、
$x \in R_j$ のとき、予測値 $f(x)=\gamma_j$ を返す。
これをまとめて表現すると、$\Theta := \{R_j, \gamma_j \}_{j=1}^J$ として、
\[f(x) = T(x; \Theta) := \sum_{j=1}^J \gamma_j I(x\in R_j)\]とかける。
ブースティング木
ブースティング木とは決定木をたくさん用意した予測モデルです。つまり
\[F_M(x;\{\Theta_k\}_{k=1}^M) = \sum_{k=1}^M T(x;\Theta_k)\]で予測するようなモデルです。Adaboostの記事 でやったように$F$ を逐次最適化してみましょう。
つまり、各 $\Theta_m$ を推定するときに
\[\hat{\Theta}_1,\hat{\Theta}_2,\dots,\hat{\Theta}_{m-1}\]は得られているものとして(固定して)、
\[\hat{\Theta}_m = \underset{\Theta_m}{\mathrm{argmin}} \sum_{i=1}^N L(y_i, F_M(x;\{\hat{\Theta}\}_{k=1}^{m-1})(x_i)+ T(x_i;\Theta_m))\]で推定してやろうということです。$L$は適当な損失関数です。
最急降下法
いま、関数$f$を使って予測したときの 損失関数の$x$についての条件付き期待値
\[\Phi(f) = \mathbb{E}_{y,x} \left[L(y, f(x))\right]\]がわかっているとします。
$\Phi(f)$ を最小にするような予測関数 $f^\ast(x):=\mathrm{argmin}_f \Phi(f)$ がいま得たいものです。
これを、
\[F_M(x;\{f_k\}_{k=1}^M)=\sum_{k=1}^M f_m(x)\]の形で得ることを考えます。$f_1, f_2, f_3$ と少しづつ $f_i$ を増やして近似していくというイメージです。
$f_i$ 一つ一つが弱学習器だと思ってください。
いま、$f_1,\ldots,f_{m-1}$ まで得られているとします。
いま、最急降下法を使って $f_m$ を計算することを考えます。$\Phi(f)$の$f$についての関数微分(functional gradient)を
\[g_m := \left.\frac{\partial \Phi}{\partial f}\right|_{f=F_{m-1}}\]と置くと、最急降下法によってもとまる $f_m$ は
\[f_m(x) = f_{m-1}(x) - \rho_m g_m(x)\]となります。$\rho_m$ は $\Phi(F_{m})$ が最小となるようにとります。
つまり、
\[\rho_m :=\mathrm{argmin}_{\rho}\Phi(F_{m-1}-\rho g_m)\]で定めます。
\[\Phi(f) = \mathbb{E}_x[\mathbb{E}_y[L(y,f(x))|x]]\]と書き直すことができて、
\[\phi(f(x))=\mathbb{E}_y[L(y,f(x))|x]\]と置くと、
\[\Phi(f) = \mathbb{E}_x[\phi(x)]\]と書き直す事ができます。$\phi$を使うと、$g_m(x)$を
\[g_m(x) = \left.\frac{\partial \phi(f(x))}{\partial f(x)}\right|_{f(x)=F(x;\{f_k\}_{k=1}^{m-1})}\]と書き直せます。これをもう少し書き換えると
\[\begin{align} g_m(x) &= \left.\frac{\partial \phi(f(x))}{\partial f(x)}\right|_{f(x)=F(x;\{f_k\}_{k=1}^{m-1})} \\ &= \mathbb{E}_y\left[\left.\frac{\partial L(y,f(x)|x)}{\partial f(x)}\right|_{f(x)=F(x;\{f_k\}_{k=1}^{m-1})}\right] (\text{微分と積分を入れ替えた}) \end{align}\]となります。これを用いて、先程の$\rho_m$の最適化の式を書き直すと
\[\rho_m = \mathrm{argmin}_{\rho}\mathbb{E}_{y,x}L(y, F_{m-1}-\rho g_m(x))\]とかける。
勾配ブースティングとは
実際は $(x,y)$ の分布は未知であり、有限の訓練データ $\{(x_i,y_i)\}_{i=1}^N$ しか持っていません。
なので、$g_m(x)$ の値は訓練データ点のところしかわかりません。よって、$\hat{\Theta}_m$ を推定するような問題を考えるとき、この方法は直接は使えません。
次善の策を考えます。
つまり有限個の最急勾配の値 $\{-g_m(x_i)\}_{i=1}^N$ と $\{T(x_i;\Theta)\}$ が訓練データ点においてだけでも近くなるように
\[\tilde{\Theta}_m :=\underset{\Theta}{\mathrm{argmin}}\sum_{i=1}^N (-g_m(x_i)-T(x_i;\Theta))^2\]で定めるという策です。
勾配ブースティング決定木
以上を踏まえて勾配ブースティング決定木の最適化アルゴリズムは次のようになります。
(b)の部分が勾配情報との近くなるようにしている部分です。
勾配ブースティング決定木のアルゴリズム (カステラ本のp361より引用)