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$より小さい値であり、非復元抽出した学習データをつかって弱識別器を学習する。

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