「確率的機械学習入門編II」を読む　～第18章木，森，バギング，ブースティング ③ブースティング・その1～

はじめに

持橋大地・鈴木大慈監訳「確率的機械学習入門編II」は，世界的に評価の高いK.P.Murphy著 "Probabilistic Machine Learning (Book1)" の和訳であり，確率モデルに基づく機械学習，深層学習といった基礎が丁寧に整理されている。

本記事は，「第18章木，森，バギング，ブースティング」における，ブースティングに関する読書メモである。

18.5　ブースティング

木のアンサンブルは，

$\begin{align} f(\mathbfit{x} ; \mathbfit{\theta}) = \sum_{m=1}^M \beta_m F_m(\mathbfit{x} ; \mathbfit{\theta}_m) \\ \\ \end{align}$

という形をしている。

ブースティング(boosting)は，逐次的に加法的モデルをフィットさせる手法である。
それぞれのモデル $F_m$ が二値分類器であるとして，

$F_1$ を学習データにフィットさせる。
$F_1$ の分類器によるエラーの分だけ重みを付ける(誤ったら重みを大きくする)。
$F_2$ は，重み付きデータにフィットさせる。
このような手続きを $M$ 回繰り返す。

という手順で行なう。

下図に，スパム電子メールデータセットの分類問題の例を示す。
横軸は用いた木の本数，縦軸はテストデータの予測誤差である。手法は，バギング・ランダムフォレスト・ブースティングを使用している。
これらの手法のうち，ブースティングが最もテスト誤差が小さい。

https://github.com/probml/pml-book/releases/latest/download/book1.pdf のFigure 18.5から引用

18.5.1　段階的加法モデル

本項では，段階的加法モデル(forward stagewise additive model)を導入する。

これは $m$ 段目において，

$\begin{align} (\beta_m, \mathbfit{\theta}_m) = \operatorname*{argmin}_{\beta, \mathbfit{\theta}} \sum_{n=1}^N l(y_i, f_{m-1}(\mathbfit{x}_i) + \beta F(\mathbfit{x}_i ; \mathbfit{\theta})) \\ \\ \end{align}$

という最適化を行なう。
このとき損失は，1つ前で得られた分類器 $f_{m-1}(\mathbfit{x})$ と，新たに加えた分類器 $F(\mathbfit{x}_i; \mathbfit{\theta})$ によって計算される。

また， $f_m$ は以下のように定める。

$\begin{align} f_m(\mathbfit{x}) = f_{m-1}(\mathbfit{x}) + \beta_m F(\mathbfit{x}; \mathbfit{\theta}_m) = f_{m-1}(\mathbfit{x}) + \beta_m F_m(\mathbfit{x}) \\ \\ \end{align}$

このように， $m$ よりも前に得られている加法モデルのパラメータについては動かさないことが重要である。

18.5.2　二乗損失と最小二乗ブースティング

本項では，回帰問題の損失 $l(y, \hat{y}) = (y - \hat{y})^2$ で与えられる損失について考える。

データ $i$ に対応する $m$ 段目の損失関数は次の通りとなる。

$\begin{align} l(y_i, f_{m-1}(\mathbfit{x}_i) + \beta F(\mathbfit{x}_i ; \mathbfit{\theta})) &= (y_i - f_{m-1}(\mathbfit{x}_i) - \beta F(\mathbfit{x}_i ; \mathbfit{\theta}))^2 \\ \\ &= (r_{im} - \beta F(\mathbfit{x}_i ; \mathbfit{\theta}))^2 \\ \\ \end{align}$

この式からブースティングでは，残差 $r_{im} = y_i - f_{m-1}(\mathbfit{x}_i)$ に対してフィッティングしていることが分かる。
この方法は，最小二乗ブースティングと呼ばれる。

下図に，ブースティングによる回帰を行なった例を示す。左側が残差，右側が予測結果を示す。
図に示すように，残差が徐々に低減されて言っていることが分かる。

https://github.com/probml/pml-book/releases/latest/download/book1.pdf のFigure 18.6から引用

18.5.3　指数損失とアダブースト

二値分類，すなわち $\tilde{y}_i \in \{ -1, 1 \}$ の予測を行なうことを考える。

指数損失

弱学習器は，以下の予測の計算を行なうとする。

$\begin{align} p(y=1 \mid \mathbfit{x}) = \frac{e^{F(\mathbfit{x})}}{ e^{-F(\mathbfit{x})} + e^{F(\mathbfit{x})}} = \frac{1}{1 + e^{-2F(\mathbfit{x})}} \\ \\ \end{align}$

この式より，負の対数尤度は以下のようになる。

$\begin{align} l(\tilde{y}, F(\mathbfit{x})) = \log (1 + e^{-2\tilde{y} F(\mathbfit{x})}) \\ \\ \end{align}$

また，別の損失として，指数損失を考えることもできる。

$\begin{align} l(\tilde{y}, F(\mathbfit{x})) = \exp (-\tilde{y} F(\mathbfit{x})) \\ \\ \end{align}$

対数損失・指数損失を含む各種損失を下図に示す。縦軸は損失の大きさ，横軸はマージン $m(\mathbfit{x}) = \tilde{y} F(\mathbfit{x})$ である。
対数損失も指数損失も，既に正しく分類できている領域(マージンが正の領域)は損失が小さいことがわかる。

https://github.com/probml/pml-book/releases/latest/download/book1.pdf のFigure 18.7から引用

ブースティングにおいては，指数損失の方が最適化しやすい。

アダブースト

指数損失を使った場合，二値分類のラベルを返すアルゴリズムは離散アダブースト，確率値を返すようなアルゴリズムは実数アダブーストと呼ばれる。

実数アダブーストにおける損失関数は以下のようになる。

$\begin{align} L_m(F) = \sum_{i=1}^N \exp [ -\tilde{y}_i (f_{m-1}(\mathbfit{x}) + \beta F(\mathbfit{x}_i) ) ] = \sum_{i=1}^N \omega_{i,m} \exp(- \beta \tilde{y}_i F(\mathbfit{x}_i)) \\ \\ \end{align}$