1. はじめに
Gradient Boostingについて - 準備編 -( http://goo.gl/C4oGok )で予告した通り、Boostingで使われる正則化テクニックについてまとめてみようと思います。その前に、第2章で正則化とは何か簡単に記述して起き、第3章においてBoostingで正則化といわれる方法についてまとめます。2・3章を踏まえると、Boostingにおける正則化は学習率の数列をスケジューリングしており、本来的な正則化ではない事が分かります（Boostingで正則化の数値実験をしている文献[3]を参考に振舞いを確認してください）。次に、第4章では昨今猛威を振るっているXgboostにおける正則化導入法を記し、Xgboostが正則化の理論でいう正則化を行っている事を示してみたいと思います。
2. 正則化とは
非常に知られている手法がL1・L2・Elastic Netの3つかと思います。釈迦に説法ですのでOverfittingを防ぐ話は省きます。損失関数に正則化項を追加することで汎化誤差を下げる手法のことです。
実は正則化は理論として非常に面白いですが非常に難しいです。詳しくは[2]のChap6・7を読んで頂きたいのですが、メチャメチャ大変です。時間の猶予があるときに一気に読まないと、文鎮化してしま・・・(僕も全部読んでいません)。個人的な趣味として言っておきますと、L1正則化が変数をスクリーニングできる理由は、L1ノルムが分解可能だからです。
平均(L1ノルム)は並列計算できる(分解可能)ものの、分散(L2ノルム)は並列計算できない(分解不可能)であることと同じ理由です。L1ノルムを使うとウェイトは
\begin{eqnarray}
||\overrightarrow{\rm w}||_1 = ||\overrightarrow{\rm w_{in}}||_1 + ||\overrightarrow{\rm w_{out}}||_1
\end{eqnarray}
と分解できます。ただし
\begin{eqnarray}
||\overrightarrow{\rm w}||_2 \neq ||\overrightarrow{\rm w_{in}}||_2 + ||\overrightarrow{\rm w_{out}}||_2
\end{eqnarray}
ですので、L2ノルムは分解できません。
これを踏まえるとGroup Lassoも全く同じ理由で分解可能です。ただし、Group Lassoは集合がオーバーラップする場合に注意が必要です。
3. Classical Boostingにおける正則化
F_m(X) = F_{m-1}(X) + \gamma_{m} h(X,\overrightarrow{\rm a_m}) \\
\text{$F_m$ : Ensemble Learner at iteration m} \\
\text{$X$ : Design Matrix} \\
\text{$\gamma_{m}$ : Learning Rate at iteration m} \\
\text{$\overrightarrow{a_m}$ : Weak Learner's parameter at iteration m} \\
[1]で触れられている通り、Boostingはガンマをスケジューリングすることで汎下誤差を下げています。数値実験は[3]に詳しく乗っています。
4. Xgboostにおける正則化
さて、大変使われているXgboostの話で、これは本来の意味で正則化しているとう点を整理したいと思います。詳細は[4]を参照してください。
Gradient Boostingについて - 準備編 -( http://goo.gl/C4oGok )で書いた通り、Boostingを機械学習の視点で再定義すると目的関数は以下のようになります；
Obj(X;\theta) = L(X;\theta) + \Omega( \theta ) \\
\text{$Obj$ : Object Function} \\
\text{$L$ : Loss Function} \\
\text{$\Omega$ : Regularization Function} \\
\text{$X$ : Design Matrix} \\
\text{$\theta$ : Model Parameter}
で、Boostingに正則化を作用させる場合、正則化項をどの様な関数にしようかと考えるわけです。以下ではGBDTに焦点を当てて考えます。
GBDTの場合、決定木の複雑さを罰則とする方が汎化性能が高まるのは、直感的にわかると思います。決定木自体（Squared Errorで木を作る場合）がデータに過適合しやすい手法ですので、たとえばdepthを深くしていけば訓練誤差は大きく減少すると思いますが、予測誤差は高いと思われるからです。具体的な関数形は[4]のP25を参照してください；
\Omega(f_t) = \gamma T + \frac{1}{2} \lambda \sum_{j=1}^{T} \omega_j^2 \\
\text{T : Number of leaves in a tree} \\
\text{$||w||_2^{2}$ : L2 norm of leaf scores in a tree}
この式が与えられた時、目的関数は以下のようにかけます。
\begin{eqnarray}
Obj^{(t)} &=& \sum_{i=1}^{n} l(y_i, \hat{y}_i^{t-1} + f_t(x_i)) + \Omega(f_t) \\
&=& \sum_{i=1}^{n} l(y_i, y_i^{t-1}) + g_i f_t(x_i) + \frac{1}{2} h_i f_t^{2}(x_i) + \Omega(f_t)
\end{eqnarray}
\text{$\hat{y}_i^{t-1}$ : ensemble learner's prediction made by iteration t-1 and given data} \\
\text{$f_t$ : weak learner} \\
g_i = \partial_{\hat{y}^{t-1}} l(y_i, \hat{y}^{t-1}) \\
h_i = \partial_{\hat{y}^{t-1}}^{2} l(y_i, \hat{y}^{t-1})
さて、目的関数の内、損失関数を二次近似して整理すると上式になります。罰則項は二次形式ですので、この式はL2正則化をしていることと同じことになります。そして、しっかり木の数についての罰則もあり、自然な目的関数といえるのではないでしょうか。boostingの目的関数を2次近似し、L2正則化と木の数の罰則を加えたXgboostは、従来の意味で正則化が作用しているアンサンブル学習器であるといえると思います。
ということで、classical boostingでは学習率の数列の優劣で汎化誤差が良くなったり悪くなったりしていました[3]が、本来はデータをtree表現するアンサンブル学習器自体を正則化したいわけです。その観点ではXgboostは自然に正則化を実現しており、結果、予測性能が高いのではないでしょうか。
5. 参考文献
[1] J.H.Freedman, Greedy Function Approximation_A Gradient Boosting Machine
[2] Bühlmann.P and van de Geer.S Statistics for High-Dimensional Data, Springer 2011
[3] Alexandre.M, Traditional versus Non-Traditional Boosting Algorithms
[4] Tianqi.C, Introduction to Boosted Trees https://homes.cs.washington.edu/~tqchen/pdf/BoostedTree.pdf