Stochastic Gradient Boosting

April 23, 2022

Gradient Boostingは、反復的に、モデルの予測と正解の残差に弱識別器をあてはめ、弱識別器をモデルに追加する。 Stochastic Gradient Boostingは、弱識別器の学習に非復元抽出したデータの部分集合をつかい、精度と学習速度を向上する。

学習データを\(\{y_i, \boldsymbol{\rm x}_i\}_1^N\), 損失関数を\(\Psi\)とする。 ブースティングは、損失関数に学習データを入力したときの出力を最小にする関数を次の加法展開\(F(\boldsymbol{\rm x})\)で近似する。 $$ F(\boldsymbol{\rm x})=\sum^M_{m=0}\beta_mh(\boldsymbol{\rm x};\boldsymbol{\rm a}_m) $$ $$ (\beta_m,\boldsymbol{\rm a}_m) = \underset{\beta, \boldsymbol{\rm a}}{\operatorname{arg min}}\sum^N_{i=1}\Psi(y_i,F_{m-1}(\boldsymbol{\rm x}_i) + \beta h(\boldsymbol{\rm x}_i;\boldsymbol{\rm a})) $$ \(h\)は弱識別器であり、\(\boldsymbol{\rm a}\)はパラメータである。 \(m=0\)であれば、弱識別器は識別器とかわらない。

勾配ブースティングは、\(m\)回目の反復において、ラベルと\(F_{m-1}(\boldsymbol{\rm x})\)の残差の二乗誤差を最小化する弱識別器を学習する。 $$ \boldsymbol{\rm a}_{m} = \underset{\boldsymbol{\rm a},\rho}{\operatorname{arg min}}\sum^N_{i=1}[\tilde{y}_{im}-\rho h(\boldsymbol{\rm x}_i; \boldsymbol{\rm a})]^2 $$ $$ \tilde{y}_{im}=-\left[\frac{\partial\Psi(y_i,F(\boldsymbol{x}_i))}{\partial F(\boldsymbol{x}_i)}\right]_{F(\boldsymbol{x})=F_{m-1}(\boldsymbol{\rm x})} $$ 弱識別器を学習後、その係数を決める。 $$ \beta_m = \underset{\beta}{\operatorname{arg min}}\sum^N_{i=1}\Psi(y_i, F_{m-1}(\boldsymbol{\rm x}_i), +\beta h(\boldsymbol{\rm x}_i;\boldsymbol{\rm a}_m)) $$

\(L\)個の葉をもつ決定木を弱識別器にする勾配ブースティングでは、弱識別器が\(\boldsymbol{\rm x}\)を分ける領域\(\{R_{lm}\}^L_1\)をパラメタにもつ。 決定木は\(\boldsymbol{\rm x}\)の所属する領域によって予測値を決める。 $$ h(\boldsymbol{\rm x}, \{R_{lm}\}^L_1)=\sum^L_{l=1}\bar{y}_{lm}1(\boldsymbol{\rm x}\in R_{lm}) $$ \(\bar{y}_{lm}=\text{mean}_{\boldsymbol{\rm x}_i \in R_{lm}}(\tilde{y}_{im})\)である。 このとき、上の\(\beta_m\)は領域ごとに決まる。 $$ \gamma_{lm}=\underset{\gamma}{\operatorname{arg min}}\sum_{\boldsymbol{\rm x}_i\in R_{lm}}\Psi (y_i, F_{m-1}(\boldsymbol{\rm x}_i)+\gamma) $$

Stochastic gradient boostingは、サンプル数が\(N\)より小さい値であり、非復元抽出した学習データをつかって弱識別器を学習する。

論文をこちらからダウンロードできます。