AdaBoost
AdaBoost学習者に人気のYouTube動画がある。
Extracted from Alexander Ihler's youtube video
誤分類したデータの重みを大きくして、次の学習器用のデータにする、という手法。
なので、直列処理になる。
最終的な出力$H(x)$は以下.
(各xが正例に分類されるか、負例に分類されるかの2値分類)
{H(x) = sign(\sum_{m=1}^{M}α_my_m(x))}
where:
- $_m$ ： m番目の学習器であることを示す添え字
- $y_m$ ： 各弱学習器の出力ラベル(予測値)
- $a_m$ ： 各弱学習器の重み（信頼度）
- $sign(x)$ ： 符号関数
sign(x) = \left\{
\begin{array}{ll}
1 & (x \geq 0) \\
-1 & (x \lt 0)
\end{array}
\right.
モデル完成までの流れ
1.各データに「データ重み」を与える
2.学習器作成（予測外れデータ個数×各重みの和を最小化）
3.各「学習器重み」(信頼度)を評価（正解率に重みを考慮し、logした関数）
4.各「データ重み」を更新
5.1〜4を繰り返し、学習器を沢山作る
6.予測：各学習器の予測値に、「学習器重み」を与えて多数決
※3では、実装上は、誤差関数で重み付き外れ量を計算済み（最小化した値）なので、これを全重みで正規化した「重み付き外れ率」を使う
出てくる評価式一覧
振り返り用。どのタイミングで何を考慮するかを見返すために羅列した。
予測値の出力：$H(x)$
{H(x) = sign(\sum_{m=1}^{M}α_my_m(x))}
誤差関数:$E_m$
E_m = \sum_{k=1}^{n}w_k^{(m)}I(y_m(x_k)\neq t_k)
学習器重み（信頼度）：$\alpha_m$ (mはイテレーション数（m番目のモデル作成）)
（正解率が高いほど重みが大きい。ロジット関数の符号逆転）
\alpha_m = \frac{1}{2}log \bigl(\frac{1-\epsilon_m}{\epsilon_m} \bigr)
データ重み付き外れ率:$\epsilon$
\epsilon_m = \frac{\sum_{k=1}^{n}w_k^{(m)}I(y_m(x_k)\neq t_k)}{\sum_{k=1}^{n}w_k^{(m)}}
（ただし、実装上データ重みを正規化する（つまり$\sum_k^n w_k^{(m)}=1$）ので分母は不要となり、誤差関数に等しい値でデータ重み付き外れ率を計算できる！）
データの重み : $w_k^{(m)}$
w_k^{(m + 1)} = w_k^{(m)}exp \bigl(-\alpha_m \cdot y_m(x_k) \cdot t_k) \bigr)
その後、総和が1になるように正規化
データの重み正規化：
w_k^{(m + 1)} \leftarrow \frac{w_k^{(m)+1}}{\sum_k^n w_k^{(m+1)}}
支持関数:I():
I()の中身に条件式を与え、Trueなら1,Falseなら0を返す関数。
データ重み
最初に扱うのは、「データ重み」。
以下の図の、データ重みを定式化することに相当。
データを$\mathbb{X}={x_1,x_2,\cdots,x_k,\cdots,x_n}$
とする。
データ重みは、$\mathbb{W}^{(m)}={w_1^{(m)},w_1^{(m)},\cdots,w_k^{(m)},\cdots,w_n^{(m)}}$
とする。mは、m個目の学習器におけるデータ重みを表す。
最初の1個目の学習器では、$w_k^{1}$は全点共通で$\frac{1}{n}$。
ニュートラルな重みは1としたくなるが、$\frac{1}{n}$である点に注意。正規化のため。
2個目以降の学習器では、直前の結果からデータ重みを計算して与える。誤分類した点ほど重みを強くすることになる。
誤差関数
誤差関数は、誤分類の数を数えることを基本とする。
ただし、重みを考慮したいので以下の式で表現する。
E_m = \sum_{k=1}^{n}w_k^{(m)}I(y_m(x_k)\neq t_k)
各データの予測が外れていたら、そのデータの重み分を加算していく。
これを最小化することで学習器を作成する。
学習器重み（信頼度）の計算
学習器重み（信頼度）を以下で算出する。
\alpha_m = \frac{1}{2}
\log (\frac{1-\epsilon_m}{\epsilon_m})
logをとっているので、正解率が高いほど学習器重みは強くなる。
$\epsilon_m$は誤差関数。処理の過程で正規化されている（すべて外れで1、全て正解で0）。
適当に、「データ重み付き外れ率」と名付けた。
（ただし、毎回データ重みを正規化する場合には$E_m$が既に$\epsilon$に等しいので、この計算は不要。一般に、実装上では毎回データ重みを正規化する。）
データ重み付き外れ率:$\epsilon$
\epsilon_m = \frac{\sum_{k=1}^{n}w_k^{(m)}I(y_m(x_k)\neq t_k)}{\sum_{k=1}^{n}w_k^{(m)}} = \frac{E_m}{\sum_{k=1}^{n}w_k^{(m)}}
学習器重み$\alpha_m$は、$\epsilon_m=0.5$を0として正負の値を取ることになる。
正解率（重み付きだが）が0.5を下回るとは、ランダムな正誤判定の期待値より低いという事になるので、基本的に起こらない。
（万一そうなった場合、正負を反転させると正解数の方が多いことになるので、多くの実装では反転する処理をする。）
データ重みの更新
データ重み$w_k^{(m+1)}$
w_k^{(m + 1)} = w_k^{(m)}exp \bigl(-\alpha_m \cdot y_m(x_k) \cdot t_k) \bigr)
ただし、正解ラベル$t_k$は正例で1,負例で-1を取ることとし、同様に予測値も正例予測で1、負例予測で-1を取ることとする。
つまり、予測が正解だった場合、 $y_m(x_k) \cdot t_k=1$, 外れだった場合 $y_m(x_k) \cdot t_k = -1$
$w_k^{(m)}$に、予測値が正解か外れかで $exp{(-\alpha)}$ か $exp{(\alpha)}$ を掛ける。
正解した場合は$exp(-\alpha)$ (<1 の値) を掛けるので重みは小さくなり、外れの場合はその逆で重みは大きくなる。
$\alpha_m$ は正確な学習器では値が大きく、不正確な学習器では値が小さい。
最終的な予測値（再掲）
学習器をたくさん作ったら、それらの多数決を取り予測値を出力する。
予測値は以下で算出。
{H(x) = sign(\sum_{m=1}^{M}α_my_m(x))}
where:
- $_m$ ： m番目の学習器であることを示す添え字
- $y_m$ ： 各弱学習器の出力ラベル(予測値)
- $a_m$ ： 各弱学習器の重み
- $sign(x)$ ： 符号関数
sign(x) = \left\{
\begin{array}{ll}
1 & (x \geq 0) \\
-1 & (x \lt 0)
\end{array}
\right.
各学習器の予測値に重みを掛けたものを総和。
総和して正の値ならTrue、負の値になるならFalseとして出力する。
AdaBoostまとめ
m番目の学習器において、予測外れ（重み考慮）が最も少なくなるように学習器を作成する。
予測の外れ率（データ重みを考慮）から学習器の重み（信頼度）$\alpha_m$を算出する。
正解だったデータの重みに$\exp{(-\alpha_m)}$を掛け、不正解だったデータの重みに$\exp{(\alpha_m)}$を掛けてデータ重みを更新する。
これを繰り返して作成したたくさんの学習器を用いて予測を行う。
予測結果は、各学習器の予測値に重みを付けて総和を取る、「重み付き多数決」を予測値として用いる。
1.各データに「データ重み」を与える
2.学習器作成（予測外れデータ個数×各重みの和を最小化）
3.各「学習器重み」(信頼度)を評価（正解率に重みを考慮し、logした関数）
4.各「データ重み」を更新
5.1〜4を繰り返し、学習器を沢山作る
6.予測：各学習器の予測値に、「学習器重み」を与えて多数決
予測値の出力：$H(x)$
{H(x) = sign(\sum_{m=1}^{M}α_my_m(x))}
誤差関数:$E_m$
E_m = \sum_{k=1}^{n}w_k^{(m)}I(y_m(x_k)\neq t_k)
学習器重み（信頼度）：$\alpha_m$
\alpha_m = \frac{1}{2}log \bigl(\frac{1-\epsilon_m}{\epsilon_m} \bigr)
データ重み付き外れ率:$\epsilon$
\epsilon_m = \frac{\sum_{k=1}^{n}w_k^{(m)}I(y_m(x_k)\neq t_k)}{\sum_{k=1}^{n}w_k^{(m)}}
（実装上重みは正規化、$\sum_k^n w_k^{(m)}=1$、とすることが多いので、事実上誤差関数と同じ)
データの重み : $w_k^{(m)}$
w_k^{(m + 1)} = w_k^{(m)}exp \bigl(-\alpha_m \cdot y_m(x_k) \cdot t_k) \bigr)
その後、総和が1になるように正規化
データの重み正規化：
w_k^{(m + 1)} \leftarrow \frac{w_k^{(m)+1}}{\sum_k^n w_k^{(m+1)}}
支持関数:I():
I()の中身に条件式を与え、Trueなら1,Falseなら0を返す関数。