はじめに
XGBoostやLightGBMなどの勾配ブースティングがkaggleなどでも欠かせないモデルとなっていますが、ブースティングが何をやっているのかよく理解していなかったので、改めて勉強したので備忘録としてこのブログを書こうと思います。
まず、アダブースト(AdaBoost)を例にブースティングについて説明した後、XGBoostの概要について説明します。
まず、ブースティングとは？
ブースティングは複数のモデルを組み合わせるアンサンブル学習の手法の1つです。他にはバギングやスタッキングなどもよく利用されるアンサンブル手法として挙げられます。
ブースティングは下図の様に学習を順番に行っていき複数のモデルを作成する手法です。その際、前回の学習で間違えたデータを重視して次の学習を行います。
最終的に複数得られたモデルをそれぞれ重み付けし、多数決で最終結果を計算します。
重みはどうやって計算するの？
前節ではブースティングのイメージについて説明しました。では具体的にはどのように重みを計算するのかアダブーストM1というアルゴリズムを例に見ていきましょう。
１と−１を分類する2値分類問題を考えます。
G_mはm番目のモデルで１か−１の値を取ります。
アダブーストM1のアルゴリズム
1. 重みをw_i = 1/Nで初期化
2. for m=1 to M:
(a) 重みw_iを用いてm番目のモデルG_mを学習
(b) 次の計算を行うerr_m = \frac{\sum_{i=1}^N w_i I(y_i \neq G_m(x_i))}{\sum_{i=1}^Nw_i}
(c) モデルの重み\alpha_mを計算する\alpha_m = \log ((1-err_m)/err_m)
(d) 各データの重みを計算するw_iw_i = w_i\cdot\exp(\alpha_m I(y_i \neq G_m(x_i)))
3. 最終的にG(x) = \rm {sign}(\alpha_mG_m(x))をモデルとする。
(注1)I(x)はxが成り立つとき１、それ以外のとき０になる指示関数。
(注2)\rm{sign}(x)はx>0のとき１、x\leq0のとき−１となる関数
これは、前回の学習で誤分類したデータにe^{\alpha_m}の重みをつけるアルゴリズムになっています。
最終的には\alpha_mで各モデルを重み付けし多数決を行っています。
アダブーストと指数損失
前節までで、ブースティングがどうやって学習を進めていくかイメージが掴めたと思います。この節ではより詳細にアダブーストの説明をしていきます。
加法的モデル
f(x) = \sum_{m=1}^M\beta_m b_m(x)というように複数のモデルb_m(x)を重み付けし足されたモデルを加法的モデルといいます。
学習の目標は損失関数をL(y,\hat{y})としたとき、
\sum_{i=1}^N L(y_i,f(x_i)) = L(y_i,\sum_{m=1}^M\beta_m b_m(x_i))を最小とする\beta_m,b_mを求めることになります。
しかし、損失関数を最小にするモデルと重みを求めることは簡単ではありません。そこで次に紹介する方法などの近似法が利用されます。
前向き段階的加法的モデリング
加法的モデルを近似する方法として前向き段階的加法的モデリングを紹介します。
前向き段階的加法的モデリング
1. f_0(x) = 0で初期化
2. for m=1 to M:
(a) \beta_m,b_m = \argmin_{\beta,b} \sum_{i=1}^N L(y_i,f_{m-1}(x_i) + \beta b(x_i))
(b) f_m = f_{m-1}(x)+\beta_mb_m(x)
これは過去のモデルは固定して新たにモデルを加えていく手法になります。
指数損失とアダブーストの関係
ここまでで、加法的モデルと前向き段階的加法的モデリングという近似手法を紹介しました。
アダブーストM1は加法的モデルで損失関数として指数損失
L(y,f(x)) = exp(-yf(x))
を利用し、近似手法として前向き段階的加法的モデリングを用いた場合と等価であることが証明できます。(今回は証明は割愛します)
ブースティングが加法的モデルを最適化する問題と等価であることについて、アダブーストと指数損失を例に説明しました。では、いよいよXGBoostについて説明していきます。
XGBoostは何をしているの？
XGBoostはkaggleで上位に入賞するモデルとして使われたりしていて、いかにも難しそうに思えますが、基本的な考え方はこれまでに説明したことで理解できます。
モデルは前節で紹介した加法的モデルf(x) = \sum_{m=1}^M\beta_m b_m(x)です。XGBoostは勾配ブースティング木と言われるようにb_m(x)として決定木を利用します。
損失関数は正則化項を加えた次のものを利用します。
L(y,f(x)) = \sum_{i=1}^N l(f(x_i),y_i) + \Omega(f)
\Omega(f) = \gamma T + \frac{1}{2}\sum_{t=1}^T w_t^2
l(y,f(x))は微分可能な損失関数であれば利用することができます。
Tは決定木の終端頂点の数で、w_tは各終端頂点の持つ値です。
つまり、頂点の数が増えることと各頂点の値が大きくなることを抑制する正則化項が加えられていることになります。
XGBoostは以上の設定で最適化を行うだけ、ということになります。まとめると意外と簡単ですよね。
加法的モデルの近似方法としては前向き段階的加法的モデリングを行います。また、L(y,f(x))を最小化するモデルを見つけるのではなく、L(y,f(x))を2次近似したものを最小化するモデルを見つけます。
2次近似は次のように得られます。
L(y,f(x))\simeq\sum_{i=1}^N [l(y_i,f_{m-1}(x_i)) + g_ib_m(x_i) + \frac{1}{2}h_ib_m^2(x_i)] + \Omega(b_m)
g_i = \partial_{f_{m-1}}l(y_i,f_{m-1}(x_i)),h_i = \partial_{f_{m-1}}^2l(y_i,f_{m-1}(x_i))
実際にはこの後、決定木を求めるアルゴリズムや計算速度を向上させる工夫などがありますが、今回はXGBoostがどんなことをしているかの紹介にとどめたいと思います。
ブースティングやXGBoostなどがちょっとでもわかってもらえれば嬉しいです。
参考文献
『統計的学習の基礎 データマイニング・推論・予測』共立出版
Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In Proceedings of the 22Nd ACM SIGKDD International
Conference on Knowledge Discovery and Data Mining, pages 785–794. ACM, 2016.
