Adaboostは指数損失を最小化している。
Adaboostとは
Adaboostは単純な分類器(弱学習器)をたくさん集めて、分類モデルを学習するときのアルゴリズムの一つです。
いま、$Y\in\{-1,1\}$ を正解ラベル、$X\in\mathcal{X}$ を特徴量とする2値分類問題を考えます。
$G_m:\mathcal{X}\to\{-1,1\}$ となる分類器を$M$個(m=1,2,\ldots,M)用意します。
これらを用いて分類器 $G(x)$ を
\[G(x)=\mathrm{sign}\left(\sum_{m=1}^M \alpha_mG_m(x)\right)\]で作ることを考えます。
訓練データ ${x_i,y_i}_{i=1}^N\subset \{-1,1\}\times\mathcal{X}$ が得られているとします。
このとき、$\{G_m\}{m=1}^M, \{\alpha_m\}{m=1}^M$ を学習するのが目標です。
Adaboostは次のようなアルゴリズムです。
Adaboostのアルゴリズム(カステラ本p339より引用)
Adaboostでは各訓練データに対して重み$w_i$を $m$ について逐次更新します。各 $m$ で $w_i$ に従った重み付きのフィッティングを行い $G_m$ を決定します。
イメージとしては、前回で誤分類したデータに対しては重みを重く、正解したデータに対しては重みは変えないというような感じで $w_i$ を決定しています。
$\alpha_m$ の根拠
$w_i$ を更新する際に $\exp(\alpha_m\cdot I(y_i\neq G_m(x_i)))$ 倍していますがこれにはどんな根拠があるのでしょうか。実は指数損失の最小化を考えると、自然とこの値が導かれるというのが今日これから書く内容です。
指数損失の最小化から $\alpha_m$ を出す
指数損失とは
\[\exp(-yG(x))\]で定義される損失です。
いま
\[f_m(x) := \sum_{i=1}^m \beta_i G_i(x)\]と定めて、各 $m$ に対して、
\[(\beta_m, G_m) := \mathrm{argmin}_{\beta, G} \sum_{i=1}^N \exp(-y_i(f_{m-1}(x_i)+\beta G(x_i)))\]で逐次的に $(\beta_m, G_m)$ を決定していくことを考えます。
$w_i^{(m)}:=\exp(-y_if_{m-1}(x_i))$ と置くと、
\[(\beta_m, G_m) := \mathrm{argmin}_{\beta, G} \sum_{i=1}^N w_i^{(m)}\exp(-y_i\beta G(x_i))\]と書き換える事ができます。$(\beta_m, G_m)$ は指数損失の重み付き和を最小にするように決定しようというわけです。
ここで指数損失の重み付き和について次のような書き換えを行います。
これより $G_m$は $\sum_{i=1}^N w_i^{(m)}I(y_i\neq G_m(x_i))$ を最小にするように決めれば良いことがわかります。そのように決定した $G_m$ を代入し、それを $\beta$ について最小化するような $\beta$ を求めれば $\beta_m$ も決定します。
上の式を $\beta$ について偏微分して整理すると
\[e^{2\beta} = \frac{\sum_{i=1}^N w_i^{(m)}(1-I(y_i\neq G_m(x_i)))}{\sum_{i=1}^N w_i^{(m)}I(y_i\neq G_m(x_i))}\]となります。いま重み付き誤差率 $\mathrm{err}_m$ を
\[\mathrm{err}_m = \frac{\sum_{i=1}^N w_i^{(m)}I(y_i\neq G_m(x_i))}{\sum_{i=1}^N w_i^{(m)}}\]で定めると
\[\begin{align} &e^{2\beta} = \frac{1-\mathrm{err}_m}{\mathrm{err}_m}\\ &\therefore \beta_m = \frac{1}{2} \log\left( \frac{1-\mathrm{err}_m}{\mathrm{err}_m}\right) \end{align}\]となります。$\alpha = 2\beta_m$ と置けば、Adaboostの $\alpha_m$ が出てきました。