Adaboostは、ある学習器から新しい学習器を繰り返し改良しながら作っていき、それら全ての学習器から多数決で判定するアルゴリズムです。
各学習器は「弱学習器」と呼びます。弱学習機はランダムな判定よりも高い精度をもつものとします。つまり正解率は$\frac{1}{2}$よりも大きいものとします。
#仮定
・（入力データ）Ｎ個とし、i番目のデータを$x_i$とする。
・（教師データ）$i$番目データ$x_i$に対応する教師データを$y_i$として、$y_i$は1か-1のどちらかをとるとする。
・（学習結果）弱学習器をＴ回作ると設定する。t回目（t=1～T）の弱学習器でデータ$x_i$に対する予想結果を$f^{t}(x_i)$と表し、1か-1のみをとるとする。
・（弱学習器での重み）t回目の弱学習器で算出されたi番目のデータの重みを$w_i(t)$とする。
#アルゴリズム
１．（初期化）１つめの弱学習器の重みは均等とします。つまり$w_i(1)=\frac{1}{N}$です。
以下２～５までを$Ｔ$回繰り返す
-ループ開始-
２．（学習）$ε(t)=\sum_{i=1}^{N}w_i(t)[f^t(x_i)≠y_i]$が最小になる弱学習器$f^{t}$を作ります。
ここで$[f^t(x_i)≠y_i]$は$f^t(x_i)$と$y_i$が一致しないときに$1$、一致するときに$0$をとるものとします。
この式から$ε(t)$は重み$w(t)$による弱学習器の誤分類率を表しています。
特にループ1回目のとき、つまり$ε(1)$は予測を間違えた割合となります。
３．（誤分類率の判定）もし誤分類率$ε(t)$が$0.5$を超えたらループから抜ける。$0.5$を超えると$α(t)$がマイナスになり、下記５の部分が機能しなくなるためです。
４．（信頼度の計算）$α(t)=\frac{1}{2}\ln\frac{1-ε(t)}{ε(t)}$を計算する。$ε(t)$が小さくなると$α(t)$が増えるので、$α(t)$は弱学習器の信頼度を意味します。
※なぜ$\frac{1}{2}$をつけるのかは厳密な計算で出てくるのでここでは割愛します。特に気にしなくて大丈夫です。
上記３と４により、$α(t)>0$となることに注意。
５．（次の弱学習器の重みを更新）$w_i(t+1)=w_i(t)\exp{(-α(t)f^{t}(x_i)y_i)}$
$α(t)>0$、$w_i(t)$の更新の仕方から$w_i(t)>0$となることに注意すると、
・$f^t(x_i)$の予測が外れたときには$w_i(t+1)=w_i(t)×（１より大きい数値）$となり重みを増やしています。一方で$f^t(x_i)$の予測が当たったときには
・$w_i(t+1)=w_i(t)×（１より小さい数値）$となり重みを減らしています。
$x_i$で予測が外れたとする→データの重み$w_i(t)$が大きくなる→次の弱学習器を作る時に、誤分類率$ε(t)$を小さくするためには優先して$x_i$を正解させなければならなくなる。これで$x_i$が次正解しやすくなるように学習させているということです。
６．（重みの正規化）$w_i(t+1)⇐\frac{w_i(t+1)}{\sum_{i=1}^{N}w_i(t+1)}$
これで重みの和$\sum_{i=1}^{N}w_i(t+1)$を$1$に合わせます。誤分類率を最小化するにあたり、$w_i(t)$が相対的に他の$w_i$たちと比べて大きいか小さいかが重要だからです。
-ループ終了-
７．（多数決）最終予測$H(x_i)=sign(\sum_{t=1}^{T}α(t)f^{t}(x_i))$
弱学習器での予想結果である$f(x_i)$に、信頼度$α(t)$で重み付けた加重平均が正となれば最終予測$H(x_i)$は$1$となり、負であれば$-1$となります。信頼度の高い弱学習器の予測結果が最終結果に反映しやすいようになっています。単純な多数決ではなく、信頼度に応じた多数決といえます。
参考・引用
http://www.iip.ist.i.kyoto-u.ac.jp/member/keisuke/resources/11adaboost.pdf