AdaBoostは頑固者

タイトルはネタです。
前回，Gradient Boostingについてまとめました。
Gradient Boostingの視点からAdaBoostを導出してみようと思ったら，以外に素直じゃなかったので
こんな変なタイトルにしてみました。

あとは，AdaBoost関連のBoostingアルゴリズムにGentle AdaBoostがあるので。
Gentleも何もつかないAdaBoostはGentleじゃ無いんだろうなーという意味もあります¹。

Gradient Boostingのおさらい

前回の説明の通り，Gradient Boostingは2つの操作

1. 弱学習器を選択する
2. 勾配降下のステップ幅を決定する
   を繰り返します。

とりあえず勾配が計算できる損失関数があれば分類問題，回帰問題，ランキング学習なんでもOK！な汎用的なアルゴリズムです。
アルゴリズム的には2つの操作のうち1の弱学習器選択が重要でしょうか。

今回は分類問題を考えると損失関数は${\cal R}[f] = \sum_{i=1}^N L(y_i, f(\boldsymbol{x}_i))$という形式です。
さらに，この${\cal R}$の$f = f_t$における勾配$g_t$は
$$
g_t(\boldsymbol{x}) = \left.\frac{\partial L(y, f(\boldsymbol{x}))}{\partial f(\boldsymbol{x})}\right|_{f(\boldsymbol{x})=f_t(\boldsymbol{x})}
$$
で表現されます。Gradient Boostingでは負の勾配$-g_t(\boldsymbol{x}_i), i=1, \ldots, N$に対して弱学習器$h$を回帰させていくことでadditive modelを成長させていくのです。
つまり
$$
h_{t+1} = \mathrm{argmin}_{h \in {\cal H}} \frac{1}{N} \sum_{i=1}^N \left((-g_t(\boldsymbol{x}_i)) - h(\boldsymbol{x}_i)\right)^2
$$
というように，回帰問題を解いて弱学習器を選別します。

ここまでが大雑把な振り返りですが，このGradient BoostingはたくさんのBoostingアルゴリズムに派生していきます。
その中でも最も有名なのがAdaBoostです。

AdaBoost

Gradient Boostingでは負の勾配$-g_t(\boldsymbol{x}_i), i=1, \ldots, N$に対して弱学習器$h$を回帰させます。
とりあえず，AdaBoostの$g_t$を計算してみましょう！

AdaBoostでは損失関数にexponential関数を使います。
$L(y, f(\boldsymbol{x})) = \exp(-yf(\boldsymbol{x}))$です。
この勾配計算は簡単で

$$
\begin{align}
g_t(\boldsymbol{x}) &= \left.\frac{\partial L(y, f(\boldsymbol{x}))}{\partial f(\boldsymbol{x})}\right|_{f(\boldsymbol{x})=f_t(\boldsymbol{x})} \\
&= -y \exp\left(-y f_t(\boldsymbol{x})\right)
\end{align}
$$

となります。
つまり$-g_t(\boldsymbol{x}) = y \exp\left(-y f_t(\boldsymbol{x})\right) \in \mathbb{R}$に対して$h(\boldsymbol{x})$を回帰させればよいのですが，AdaBoostでは$h(\boldsymbol{x}) \in {-1, +1}$という制限をかけてしまっています！
なぜなんだ…　素直に$h(\boldsymbol{x}) \in \mathbb{R}$にしてくれれば簡単なのに…

この流れから分かるようにAdaBoostは敢えてハードモードで問題を解く頑固なやつです。どうやって解きましょう？

じつは前回のGradient Boosting導出過程で出てきた内積表現を使うとAdaBoostを一気に解釈できるようになります。

弱学習器の訓練

Gradient Boostingでは損失${\cal R}[f]$の負の変分(汎関数の微分)である$-D{\cal R}[f](h)$が最大になるように$h$を決定します。
$$
\begin{align}
h_{t+1} &= \mathrm{argmax}_{h \in {\cal H}} (-1) D{\cal R}[f](h) \\
&= \mathrm{argmax}_{h \in {\cal H}} \sum_{i=1}^N \left(-g_t(\boldsymbol{x}_i)\right)h(\boldsymbol{x}_i) \\
&= \mathrm{argmin}_{h \in {\cal H}} \sum_{i=1}^N \left(\left(-g_t(\boldsymbol{x}_i)\right) - h(\boldsymbol{x}_i)\right)^2
\end{align}
$$

通常のGradient Boostingは回帰問題に帰着させるのですが，AdaBoostは上式二段目の内積表現を使います。
$-g_t(\boldsymbol{x}_i) = y_i\exp(-y_i f_t(\boldsymbol{x}_i)$をそのまま内積表現に代入してみると，

$$
\begin{align}
h_{t+1} &= \mathrm{argmax}_{h \in {\cal H}} \sum_{i=1}^N \left(-g_t(\boldsymbol{x}_i)\right)h(\boldsymbol{x}_i) \\
&= \mathrm{argmax}_{h \in {\cal H}} \sum_{i=1}^N y_i \exp\left(-y_i f_t(\boldsymbol{x}_i)\right) h(\boldsymbol{x})
\end{align}
$$

となります。ここで$w_i := \exp\left(-y_i f_t(\boldsymbol{x}_i)\right)$とおくと

$$
\begin{align}
h_{t+1} &= \mathrm{argmax}_{h \in {\cal H}} \sum_{i=1}^N w_i y_i h(\boldsymbol{x}_i)
\end{align}
$$

です。さらに，$y_i \in \{-1, +1\}$かつ$h(\boldsymbol{x}_i) \in \{-1, +1\}$であることに注意すると,
$y_i = h(\boldsymbol{x}_i)$になる$i$が多いほど$\sum_i w_i y_i h(\boldsymbol{x}_i)$の値は大きくなります。
したがって，

$$
\begin{align}
h_{t+1} &= \mathrm{argmax}_{h \in {\cal H}} \sum_{i=1}^N w_i \mbox{1}\hspace{-0.25em}\mbox{l} \left( y_i = h(\boldsymbol{x}_i) \right)
\end{align}
$$

となります。これは各サンプルに重み$w_i$をつけて正解率を最大化していることに他なりません！

あと，意味は変わりませんが，こちらの誤り率最小化で表現しているものも多いですね。
$$
\begin{align}
h_{t+1} &= \mathrm{argmin}_{h \in {\cal H}} \sum_{i=1}^N w_i \mbox{1}\hspace{-0.25em}\mbox{l} \left( y_i \neq h(\boldsymbol{x}_i) \right)
\end{align}
$$
以上でAdaBoostにおける弱学習器の決定方法が導出できました！

弱学習器の信頼度の決定

勾配降下の方向$h_{t+1}$が決まったら，後はどの程度降下するかを決定します。
$$
\alpha_{t+1} = \mathrm{argmin}_{\alpha} {\cal R}[f_t + \alpha h_{t+1}]
$$

${\cal R}(\alpha) := {\cal R}[f_t + \alpha h_{t+1}]$と置くと，一変数の最小化問題であり，通常はline searchで最適化されますが，AdaBoostの場合は$\alpha$を解析的に導出することができます。
基本的には$\left.\frac{\partial {\cal R}}{\partial \alpha}\right|_{\alpha=\alpha_t} = 0$なる$\alpha_t$を導出するという方針です。

では実際に計算してみましょう！

$$
\begin{align}
\frac{\partial {\cal R}}{\partial \alpha} &= \frac{\partial}{\partial \alpha} \sum_{i=1}^N \exp\left(-y_i \left(f_{t}(\boldsymbol{x}_i) + \alpha h_{t+1}(\boldsymbol{x}_i)\right)\right) \\
&= \sum_{i=1}^N \exp\left(-y_i f_t(\boldsymbol{x}_i)\right) \frac{\partial}{\partial \alpha} \exp\left(-y_i \alpha h_{t+1}(\boldsymbol{x}_i)\right) \\
&= \sum_{i=1}^N w_i \left(-y_i h_{t+1}(\boldsymbol{x}_i)\right) \exp\left(-y_i \alpha h_{t+1}(\boldsymbol{x}_i)\right)
\end{align}
$$

この値が0になる$\alpha$を求めたいわけです。ここで一工夫します。訓練データのインデックス$i$を正解・不正解でグループ分けします。
$I_{correct} := \{i | y_i = h_{t+1}(\boldsymbol{x}_i)\}$, $I_{incorrect} := \{i | y_i \neq h_{t+1}(\boldsymbol{x}_i)\}$とすると， $j \in I_{correct}$に関しては$y_j h_{t+1}(\boldsymbol{x}_j) = +1$, $k \in I_{incorrect}$に関しては$y_k h_{t+1}(\boldsymbol{x}_k) = -1$となり，見通しが立てやすくなります。

$$
\begin{align}
\frac{\partial {\cal R}}{\partial \alpha}
&= \sum_{i=1}^N w_i \left(-y_i h_{t+1}(\boldsymbol{x}_i)\right) \exp\left(-y_i \alpha h_{t+1}(\boldsymbol{x}_i)\right) \\
&= \sum_{j \in I_{correct}} (-w_j)\exp\left(-\alpha\right) + \sum_{k \in I_{incorrect}} (+w_k)\exp\left(+\alpha\right) \\
&= -\exp(-\alpha) \sum_{j \in I_{correct}} w_j + \exp(+\alpha) \sum_{k \in I_{incorrect}} w_k
\end{align}
$$

これでかなりスッキリしました。あとは$\left.\frac{\partial {\cal R}}{\partial \alpha}\right|_{\alpha=\alpha_t} = 0$を解くだけです。
すなわち

$$
\begin{align}
\left.\frac{\partial {\cal R}}{\partial \alpha}\right|_{\alpha = \alpha_t}
&= -\exp(-\alpha_t) \sum_{j \in I_{correct}} w_j + \exp(+\alpha_t) \sum_{k \in I_{incorrect}} w_k = 0
\end{align}
$$
であり，これを解くと

$$
\alpha_t = \frac{1}{2} \ln \frac{\sum_{j \in I_{correct}} w_j}{\sum_{k \in I_{incorrect}} w_k}
$$

これで終わりで良いのですが，$\hat{w}_i := \frac{w_j}{\sum_{i=1}^N w_j}$のように$w_i$が$[0, 1]$の範囲に収まるように正規化をすると重み付き誤り率$\epsilon_t := \sum_{k \in I_{incorrect}} \hat{w}_k$を用いて

$$
\alpha_t = \frac{1}{2} \ln \frac{1 - \epsilon_t}{\epsilon_t}
$$
と表記できます。これでよく見るAdaBoostの信頼度が導出できました！

まとめ

Gradient Boostingが理解できればAdaBoostは損失関数を決めるだけと思っていた時期が私にもありました。

ただ，タイトルでAdaBoostは頑固者とか書きましたが，別に頑固ではないですね。
単純に$-D{\cal R}[f](h)$を最大にしようとすると内積表現のほうがstraightforwardですし。

AdaBoostの解説なんてネット上にいくらでもあると思いますが，誰かの理解の一助になればと思います。

1. gentleの対義語が頑固かと言われると違う気がしますが，細かいことは気にしないということで ↩