勾配ブースティング - yuuk1's Digital Garden

# 勾配ブースティング ## 定義勾配ブースティング(Gradient Boosting、実装名としてMART/GBM)は、弱学習器(通常は浅い決定木)を**前向き段階的加法モデリング(forward stagewise additive modeling)**の枠組みで逐次追加し、任意の微分可能な損失関数を最小化する手法である。各段で、現在のモデル $f_{m-1}(x)$ の損失に対する負の勾配(擬似残差)に新しい木を最小二乗で当てはめ、縮小率 $\nu$ でスケールしてモデルに加える。AdaBoostは指数損失を用いる特殊ケースとしてこの枠組みに包含される(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 10 Boosting and Additive Trees]] §10.2-10.4, §10.10)。 ### AdaBoostと指数損失 AdaBoost.M1は、基底関数を個々の分類器 $G_m(x)\in\{-1,1\}$、損失関数を指数損失 $\exp(-yf(x))$ とした前向き段階的加法モデリングと数学的に等価である。観測重み $w_i^{(m)}=\exp(-y_if_{m-1}(x_i))$ を使った加重誤り率最小化が、AdaBoostの分類器重み $\alpha_m=\log((1-\mathrm{err}_m)/\mathrm{err}_m)$ と重み更新則をちょうど導く。この等価性はAdaBoost発表(1997)から5年後に発見された(Source: 同上 §10.4)。 ### 損失関数の頑健性指数損失と二項逸脱度(交差エントロピー)は母集団最小化子(対数オッズの半分)を共有するが、有限データでは負のマージンへの罰則の増え方が異なる。指数損失は負のマージンが大きいほど指数的に影響力を増すのに対し、二項逸脱度は線形にしか増えない。したがって二項逸脱度はノイズの多い設定や誤ラベルに対しAdaBoostより頑健である。回帰でも同様に、二乗誤差は外れ値に脆弱で、絶対誤差やHuber損失(零点近傍は二乗誤差、それ以外は線形)がより頑健な代替になる(Source: 同上 §10.5-10.6)。 ### 数値最適化としての一般化損失 $L(f)=\sum_i L(y_i,f(x_i))$ を $f\in\mathbb{R}^N$ の関数とみなすと、最急降下法は負の勾配 $g_{im}=[\partial L(y_i,f(x_i))/\partial f(x_i)]_{f=f_{m-1}}$ の方向に更新する。木ブースティングはこの最急降下法の制約付き(木の予測という形に限定された)近似とみなせる。勾配ブースティングは各反復で負の勾配に最も近い回帰木を最小二乗で当てはめることで、指数損失や二乗誤差以外の任意の微分可能な損失関数(Huber損失・多項逸脱度など)にも同じ枠組みを適用できるようにする(Source: 同上 §10.10)。 ### 調整パラメータ木のサイズ $J$(終端ノード数)は表現できる交互作用の最大次数を $J-1$ に制限する(ANOVA分解に基づく)。$J=2$(切り株)は主効果のみのモデルを生み、実務的には $4\le J\le 8$、既定 $J\simeq 6$ が推奨される。縮小率 $\nu$(各木の寄与のスケール)を小さく(0.1未満)し反復回数 $M$ を検証サンプルでの早期停止により選ぶ戦略が最も良いテスト誤差を与える。部分標本抽出(各反復で訓練データの一部を非復元抽出して木を育てる、典型的に割合0.5)は縮小と併用すると精度と計算効率を両方改善するが、縮小なしでは効果が薄い(Source: 同上 §10.11-10.12)。 ## 横断的知見 - **部分標本抽出(stochastic gradient boosting)の分散削減メカニズムは、ランダムフォレストの脱相関(de-correlation)と同根であることがESL第15章の文献ノートから確認できる**: 第10章は勾配ブースティングの部分標本抽出(各反復で訓練データの一部を非復元抽出して木を育てる)が縮小と併用すると精度と計算効率を改善すると述べるにとどまるが、第15章の文献ノート(Friedman and Hall, 2007)は、サイズ $N/2$ の標本で木を育てて平均する操作がバイアス・分散の観点でバギングとほぼ同値であり、$N$ に対する抽出割合をさらに小さくすると脱相関を通じて分散がいっそう減ることを示す。すなわち勾配ブースティングの部分標本抽出とランダムフォレストの分割候補変数のランダム化は、どちらも「木どうしの相関を下げることでバギングされた推定量の分散公式 $\rho\sigma^2+\frac{1-\rho}{B}\sigma^2$(式15.1)の $\rho\sigma^2$ 項を削る」という同一の分散削減メカニズムの異なる実装であるとみなせる。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 10 Boosting and Additive Trees]] §10.12, [[@2009__Springer__The Elements of Statistical Learning - Chapter 15 Random Forests]] Bibliographic Notes) - **縮小(shrinkage)とL1正則化(lasso)の関係は、ESL第16章が木を基底とする巨大な辞書上の正則化パスとして精密化する**: 第10章の縮小(式10.41、学習率 $\nu$)は経験的に「小さい $\nu$ ほど良いテスト誤差を与える」という現象として導入されるにとどまるが、第16章§16.2.1はこれを次のように理論づける。木の辞書 $\mathcal T=\{T_k\}$ を基底とする線形モデル $f(x)=\sum_k\alpha_kT_k(x)$(式16.1)に対し、罰則 $J(\alpha)=\sum_k|\alpha_k|$(lassoペナルティ、式16.4)を課した罰則付き最小二乗(式16.2)を考えると、この厳密解は辞書が巨大すぎて計算不可能だが、前向き段階的線形回帰(Algorithm 16.1: 現在の残差に最もよく適合する木を選び、その係数を微小量 $\varepsilon$ だけ更新する)がその効果を近似する。木ブースティング(縮小率 $\nu$)はAlgorithm 16.1の $\varepsilon$ に対応する学習率として、この単調ill-posed回帰の実用近似とみなせる。基底が無相関、または係数 $\hat\alpha_k(\lambda)$ が $\lambda$ の単調関数であれば、$\varepsilon\downarrow0,\ M\uparrow\infty,\ M\varepsilon\to t$ の極限でAlgorithm 16.1はlassoの解パスと厳密に一致する(Efron et al., 2004によりこの極限での解パスは区分線形であることが示され、LARSアルゴリズムでの効率計算につながる)。すなわち「$\nu$ を小さくして反復回数を検証データで早期停止する」という縮小の実務的成功は、lassoの正則化パス上で最適な複雑さの点を選ぶ操作の近似という理論的裏付けを持つ。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 10 Boosting and Additive Trees]] §10.12, [[@2009__Springer__The Elements of Statistical Learning - Chapter 16 Ensemble Learning]] §16.2.1) ## 未解決の問い - AdaBoostが誤ラベルに弱いという指摘は経験的観察として述べられるが(§10.6)、二項逸脱度ベースの勾配ブースティングがどの程度の誤ラベル率まで頑健であるかの定量的な目安は本章の記述だけでは読み取れない。 - 決定木を弱学習器として使う場合、単木のようなコスト複雑度枝刈りではなく固定サイズ $J$ を使う設計判断がされている(§10.11)。この設計判断は決定木単体の枝刈り理論(ESL第9章)とどう関係し、なぜ枝刈りでなく固定サイズが選ばれるのか、両者の理論的な接続はESL内では明示されていない。 - ランダムフォレストは非適応的(木を独立に育てて平均する)、勾配ブースティングは適応的(前の木の誤りを次の木が補正する)というESL第15章の対比は、両者の実務上の性能差(バイアスを削れるブースティングの方が一般に強いが、チューニングが難しい)とどう定量的に対応するか。ESL第15章・第10章の個別記述だけでは、この非適応性/適応性の違いがどのような問題設定でどちらに有利に働くかの一般則までは読み取れない。 ## 関連 - ソース: [[@2009__Springer__The Elements of Statistical Learning - Chapter 10 Boosting and Additive Trees]] / [[@2009__Springer__The Elements of Statistical Learning - Chapter 15 Random Forests]] / [[@2009__Springer__The Elements of Statistical Learning - Chapter 16 Ensemble Learning]] - 概念: [[決定木]] / [[アンサンブル学習]] / [[縮小推定]] - 関連 MOC: (該当なし) ## 出典 - [[@2009__Springer__The Elements of Statistical Learning - Chapter 10 Boosting and Additive Trees]](§10.1-10.13 Boosting and Additive Trees) - [[@2009__Springer__The Elements of Statistical Learning - Chapter 15 Random Forests]](§15.2, Bibliographic Notes) - [[@2009__Springer__The Elements of Statistical Learning - Chapter 16 Ensemble Learning]](§16.2.1 Penalized Regression)