勾配ブースティングについてざっくりと説明する

最近xgboostがだいぶ流行っているわけですけど，これはGradient Boosting（勾配ブースティング）の高速なC++実装です．従来使われてたgbtより10倍高速らしいです．そんなxgboostを使うにあたって，はてどういう理屈で動いているものだろうと思っていろいろ文献を読んだのですが，日本語はおろか，英語文献でもそんなに資料がなかったので，ある程度概要を把握するのに結構時間を食いました．

そんなわけで，今回は自分の理解の確認も兼ねて，勾配ブースティングについてざっくりと説明してみようかと思います．とはいえ生理解な部分も結構あるので，マサカリが飛んできそう感が大いにしています．腑に落ちる的な理解を優先しているため，数式は一切出てきません．

勾配ブースティングとは

複数の弱学習器を組み合わせるアンサンブル学習には，いくつかの手法がありますが，ブースティングは逐次的に弱学習器を構築していく手法です．逐次的というのは，弱学習器を1つずつ順番に構築していくという意味です．新しい弱学習器を構築する際に，それまでに構築されたすべての弱学習器の結果を利用します．そのためすべての弱学習器が独立に学習されるバギングと比べると，計算を並列化できず学習に時間がかかります．

ブースティングでは，各ステップごとに弱学習器を構築して損失関数を最小化します．その際に，各学習データの扱いはずっと平等ではありません．各学習データのうち，前のステップで間違って識別されたものへのウェイトを重くして，次のステップで間違ったものをうまく識別できるようにしていきます．

各ステップ内でやることは，ようするに損失関数の最小化問題です．これだけ切り出せば，通常の最適化問題とそれほど大きくは変わりません．最適化問題でよく使われる最急降下法やニュートン法なんかをまとめて，勾配降下法ということができます．勾配ブースティングでやっていることは，各ステップのパラメタ最適化の際に，勾配降下法を用いているというだけのことです．もちろん数学的にはいろいろあるわけですけれども，大枠としてはそれだけです．勾配を求めて学習していく，という形をとるので，損失関数をパラメタ行列で微分してあげるのを繰り返して，所定回数に達したらおしまいです．

このあたり，数式的にしっかり追いたいというのであれば，はじパタの11.4や，統計的学習の基礎の10.10，Introduction to Boosted TreesやFEGさんのKDD Cupまとめあたりを参照してください．

はじめてのパターン認識

統計的学習の基礎 ―データマイニング・推論・予測―

勾配ブースティングのパラメタ

勾配ブースティングでよく使われるのは，弱識別器に決定木をもちいたGBDT(Gradient Boosting Decision Tree)です．xgboostなんかでも，こちらにパラメタ一覧がまとまっています．GBDTの場合，過学習の制御がパラメタ決定の中心になってきます．

例えば各ステップの学習が後続ステップの学習に影響を及ぼしてしまうため，個々のステップの影響を下げて学習速度をゆっくりにするshrinkageと呼ばれるパラメタがあります．shrinkageのパラメタはの値を取ります（xgboostだと，このパラメタはetaで表され，デフォルトは0.3になっています）．ある程度小さいほうが，過学習が抑制されて精度が上がります．過学習に関しては，深層学習によくまとまっています．というのは，ニューラルネットワークは非常に表現力が高い手法であるため，過学習に陥りやすいという特性があります．そこで，いかにして過学習を防ぎながら多層ニューラルの最適値を得るかについて，様々な研究の蓄積があります．

深層学習 (機械学習プロフェッショナルシリーズ)

また個々の弱学習器である，決定木自体の表現力を制御するパラメタとして，木の深さ（xgboostだとmax_depth）や葉の重みの下限（同じくmin_child_weight），葉の追加による損失減少の下限（gamma）といったものがあります．深さが浅いほど，また下限が大きいほど，当然単純な木になりやすいので過学習の抑制に働きます．

あとは各ステップで決定木の構築に用いるデータの割合というパラメタもあります．学習データから非復元抽出したサブサンプルを用いることで，確率的勾配降下法（Stochastic Gradient Descent: SGD）に近い効果が得られると思われます．当然これも過学習抑制で精度向上につながります．SGDについては最近出版されたオンライン機械学習でも詳しく述べられていて，理解の助けになるかと思います．

オンライン機械学習 (機械学習プロフェッショナルシリーズ)

またxgboostにはcolsample_bytreeというパラメタもあり，これは各ステップの決定木ごとに用いる特徴量をサンプリングすることだと思われます．これはランダムフォレストで行われているのと同じで*1，特徴量同士の交互作用を考慮した形のモデリングができるという利点があります．

それ以外にも，木の本数（nrounds）もあります．当然木の本数が多いほうが結果も安定するし精度も上がりますが，その一方で学習に時間がかかってしまいます．先ほども述べたように，ブースティングはパラメタの推定時に前のステップの結果を用いるため，各ステップの推定を同時に行うことができません．そのためステップ数が増えること（＝木の本数が増えること）は，計算時間の増加を招きます．

xgboostパッケージを試してみる

ということで，ようやくですがxgboostを使っていくつかパラメタのシミュレーションをしてみます．データはStackingのときにも使ったバイナリデータです．各パラメタを何段階かで変えてみて，予測率の変化をみてみましょう．

smrmkt.hatenablog.jp

値を変えてみたパラメタ以外のものについては，基本的にデフォルトの値に固定しています．パラメタのデフォルト一覧は以下の通りです*2．

パラメタ	値
nrounds	100*3
eta	0.3
gamma	0
max.depth*4	6
min.child.weight	1
subsumple	1
colsumple.bytree	1

ということで，以下に各パラメタの値を動かしたときに，どの程度正解率が変化するかをまとめてみました．そんなに極端に動くわけではありませんね．

nrounds

nrounds	accuracy
1	82.9%
10	85.1%
100	84.8%
1000	83.1%

eta

eta	accuracy
0.5	83.9%
0.3	84.8%
0.1	85.2%
0.01	84.7%

gamma

gamma	accuracy
0	84.8%
0.1	84.8%
0.3	85.4%
0.5	85.3%

max.depth

max.depth	accuracy
3	85.3%
6	84.8%
10	85.3%
20	84.5%

min.child.weight

min.child.weight	accuracy
0.1	84.6%
1	84.8%
3	85.2%
10	85.4%

subsumple, colsumple.bytree

なぜかこれらについては，パラメタを変えても実際のモデルに変化がなく，何故なのかがよくわからず...

コードは例のごとくgistにあげているので，ご参考までに．

gist.github.com

*1:ランダムフォレストでは，サンプルと特徴量の両方をサンプリングした木を複数作って，その結果の多数決で識別クラスを選びます

*2:max_delta_stepに関しては，このデータ自体が正例か負例に偏りのあるimbalanceなデータではないため，特に検討の対象とはしません

*3:このパラメタにはデフォルトの値がないため，ここでは100にしています．

*4:xgboostのパラメタの_は，R上の変数として使うときは.で置き換えることができるそうです．