Gradient Boosting（勾配ブースティング）とは

最近、Kaggleだとかその周辺では、XGboostだとかcatboostだとか、Gradient Boosting（勾配ブースティング）の手法が流行っているらしい。最終的にcatboostを勉強する目的で、その前段階として勾配ブースティングをひととおり勉強したので、そのメモ。

■Boosting（ブースティング）とは？

ブースティングとはアンサンブル学習の一種で、弱学習機を「積み重ねる」ことで精度を上げようとするもの。下の図がわかりやすいが、バギングは複数の弱学習機を並列に並べてそれぞれの学習機の結果を平均したり投票したりして最終的な結果を出力するもので、Random Forestが代表的な例。一方でブースティングは複数の弱学習機を「直列」に並べてモデルを強化してあげようという思想のもの。具体的な例としてはLS_boostingが挙げられる。この手法は１つ目の弱学習機での回帰残差を２つめの弱学習機で最小化するようにし、さらにその結果の残差を３つめの弱学習機で最小化するようにし・・・・、というふうに学習機を繋いでいく。

ブースティングのアルゴリズムには幾つか種類があり、代表的なのはAdaboostや今回のトピックである勾配ブースティング。

Source

■勾配ブースティングの概要

勾配ブースティングは、超ざっくりでいうと「前の学習機の誤差を埋めるように次の弱学習機を学習させる」ことをしている。

勾配ブースティングアルゴリズムの疑似コードは以下のようなものだ。

ここで、\(L\)は回帰や分類のLoss関数、\(h\)は個別の弱学習器、\(F_m\)は各弱学習器を統合した（つまり繋いだ）加法モデルを示している。

• ３行目：それぞれのサンプル(\(i\)）についてのLossをその時点（の１つ前）の加法モデルの偏微分（\(F\)を微小変化させた時の\(L\)の変化量）のマイナスを\(\tilde{y}_i\)と計算している。つまりこれはLossを最小にするための勾配降下の方向を示している。
• ４行目：３行目で求めた勾配降下の方向に最も近くなる修正を加える弱学習器を学習させる。
• ５行目：４行目で求めた弱学習機をその時点の加法モデルに加える時のパラメータ（学習レート？）を学習。
• ６行目：４行目と５行目の結果から、加法モデルを決定。

というプロセスを繰り返すアルゴリズムとなっている。

ここで、勾配効果の方向にむけて弱学習器を学習させていくことから「勾配」ブースティングという名前がついているのだ。

■勾配ブースティングの具体例

勾配ブースティング自体は一般的なアルゴリズムのため、そのアルゴリズムの中で利用するLossの種類などは様々なバリエーションが存在する。

最もシンプルな具体的なLossを回帰の二乗誤差とするもので、LS_boosting。

Lossを二乗誤差、つまり\(L(y_i, F(\boldsymbol{x}_i))=\frac{1}{2}(y_i - F(\boldsymbol{x}_i))^2\)としたときに、３行目の偏微分は

\[\tilde{y}_i= - \left[\frac{\partial L}{\partial F}\right] _{F=F_{m-1}}= - \left[\frac{\partial \frac{1}{2}(y_i - F)^2}{\partial F}\right] _{F=F_{m-1}} = y_i - F_{m-1}\]

となり、一つ前のイタレーションで作成した加法モデルと実測との残差になる。そのため前述したようにLS_boostingはこの残差を最小化するように次の弱学習器を作成するということになる。

■参考

https://www.st-hakky-blog.com/entry/2017/08/08/092031

https://ticc-econometrics.hatenablog.com/entry/gbdt2#fn-6241a4a1