基本、個人的に勉強した内容を書き留めていくつもりです。間違っている箇所があれば指摘して頂けると、とてもうれしいです。
1. Boostingとは何ぞや
Boostingとは弱学習器をたくさん集めて強学習器を作ろうという話が出発点で、PAC Learningと呼ばれています（PAC Learning:強学習器が存在するとき弱学習器は必ず存在するが、弱学習器のアンサンブルが存在する場合、強学習器と同性能の学習器を作れるかという話です）。他方、J.H.Friedma先生[1]が損失関数を最小化する枠組みでも議論できるんでない？という（おそらく）疑問から、なんと機械学習の枠組みでBoostingを説明してしまいました。損失関数を最小化する問題として再定義し、損失を最小化する方向を探すのに勾配情報を使っているので、Gradient Boostingと呼ばれています。
で、この方法が昨今のデータコンペで猛威を振るっています（今更、言われなくてもおわかりだと思いますが）。そろそろ応用問題にも機械学習を適用してみようかと思っていたので、勉強してみました。
2. Boostingの歴史
Boostingが猛威を振るっている疑問として、なんでそんなに上手くいくの？というです。素人でも不思議なのですが、機械学習の理論の先生方もおそらくまだわかっていないはず（実用性というより汎化誤差の上限バウンドの話です）で、個人的には密かなフロンティアなのではないかと注目しています。
流れとしては、Adaboost -> Gradient Boosting -> Stochastic Gradient Boosting -> Stochastic Parallel Gradient Boosting かなと思ってます。最初はPAC Learningの枠組みで理解され、現代では機械学習の枠組みで定式化されている流れ。
肝心の疑問ですが、ここに歴史を感じるのです。AdaboostからGradient Boostingに移行するまで、経験的に性能が高かったBoostingの汎化誤差について深く議論されています[2]。Adaboostにかぎらず、Boostingは訓練データに思いっきりfittingしていきますので、汎化誤差は悪いんでないの？と思っていて、多くの方が同様に考えていたはず[3]です。しかし、経験的には汎化誤差があまり悪化しないのです。
そこで、理論の先生が考えました。答えはL1-Marginです。SVNはMarginという量を最大化する問題で、このMarginはL2-Margin
\begin{eqnarray}
||\overrightarrow{\rm x}||_2^{2}
\end{eqnarray}
でした。つまり、Marginをユークリッド距離として解釈できたわけです。他方、Boostingは式をよく見るとL1-Marginと考えられることに先生が気づきました([2]のP18-19)。あ～Marginか～と多分先生は思いついて定式化し、理論的な汎化誤差を導出[3]しました。
しかし、経験的に達成される汎化誤差と理論的に導出される汎化誤差には大きな乖離があるようで、依然、謎のままのようです（このあたり、理解が間違っていたらご指摘をお願いします）。
3. AdaboostとGradient Boosting
2章で書きましたが、大学で勉強する多くがAdaboostなのではないでしょうか。PAC Learningの枠組みで教科書も書かれています。これをGrdient Boostingの枠組みで理解すると、AdaboostはExponential Lossで理解できます。その他、Logit-Boost(Logistic Loss)、L2-Boost(Square Loss)などが有名どころです。
4. 勾配情報は何に使われるのか
詳細は5章に書きますが、ここでは、勾配情報とアンサンブル学習の関連性は何なんだという話です。答えは損失関数を最も下げる様に、弱学習器を追加する[1]という話です。
Boostingは加法モデルと呼ばれる手法で、時刻t-1までに学習したアンサンブルに、時刻tにさらに弱学習器を追加するモデルです。
5. Gradient Boostingのアルゴリズム
アルゴリズムの概要です。図は[1]から引用しました。順に書いていきますと
- 1行目:損失関数(プサイ)の初期化
- 2行目:mが弱学習器の添え字.
- 3行目:これポイントです。損失関数を前回(m-1)までのアンサンブル学習器の予測で偏微分しています。yチルダは予測ではなく、サンプルデータiに関するnegative gradientです。
- 4行目:hが弱学習器なのですが、4で述べた通り、追加する弱学習器は損失関数を最も下げる様に振舞ってほしいのです。そこで、negative gradient(yチルダ)を正解データとして弱学習器(h)を最小二乗近似し、弱学習器hのパラメータaを求めています。
- 5行目:3-4行目で求めたのは、勾配を下げる弱学習器で、学習率は別途求める必要があり、それをline searchで求めている。
- 6行目:m-1までのアンサンブル学習器に3-5行目で求めた弱学習器を追加。
6. Gradient Boosting Decision Tree（GBDT）
非常に長くなってきました。やっと流行っているGBDTです。決定木がどこで使われるかといえば、追加する弱学習器を決定木にしています。
7. 次回以降
以上がBoostingの概要です。次回以降は具体的な実験をscikit-learnでやってみたり、正則化の話、最後に滅茶苦茶はやっているXgboostについてコメントしてみたいと思います。
いきなりネタバレしておきますと、boostingの正則化はいわゆる正則化の理論でいう正則化ではなく、学習率をいじっているだけです。結果、boostingでは学習率の数列の優劣で汎化誤差が良くなったり悪くなったりしています。しかし、Xgboost[4]は損失関数を2次の項までテイラー展開しているよう（実際のコードを確認していませんが、[4]ではそのようになっています）です。正則化といえばL1・L2ですから、2次の項まで解析的に求まれば、従来の意味で正則化可能なのです。だから、Xgboostの予測精度がよいのではないかと思っています。
8. 参考文献
[1] J.H.Friedma, Greedy Function Approximation_A Gradient Boosting Machine
[2] M.Mohri, Introduction to Machine Learning Lecture 11
[3] L1-Marginの導出論文忘れた・・・
[4] Tianqi Chen, Introduction to Boosted Trees https://homes.cs.washington.edu/~tqchen/pdf/BoostedTree.pdf