AdaBoostは頑固者

タイトルはネタです。
[前回](https://qiita.com/hyt-sasaki/items/f4a2a450cfd9f414d54b)，Gradient Boostingについてまとめました。
Gradient Boostingの視点からAdaBoostを導出してみようと思ったら，以外に素直じゃなかったので
こんな変なタイトルにしてみました。

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

[^1]: 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は敢えてハードモードで問題を解く頑固なやつです。どうやって解きましょう？

じつは[前回](https://qiita.com/hyt-sasaki/items/f4a2a450cfd9f414d54b)の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の解説なんてネット上にいくらでもあると思いますが，誰かの理解の一助になればと思います。