Adaboost
つぎはAdaboostです。昨日のGradientBoostingでは、各段階ではずれのみを学習していました。Adaboost系統では各段階で間違ったサンプルは重みを大きくし、その後に続くモデルでのそれらのサンプルの寄与を大きくすることで精度が改善されます。
アルゴリズム
また、回帰から見てみます。
Regression
論文はこちらです。3ページ目から記載があります。もともとは分類のアルゴリズムが提案されその後に回帰用のアルゴリズムが提案されました。
学習
- 各サンプルの重み$w_i$でN個サンプル（のインデックス）を取得（初期化は同じ値）
- 抽出したサンプルでモデルを学習
- 学習済みモデルに全サンプルを適用し、予測値$\tilde{y}_i$をすべて取得
- 損失$L_i$を計算。
- $L_i = |\tilde{y}_i - y_i|^2 /D$ ここで、$D = max|\tilde{y}_i - y_i|^2 \hspace{10pt} i=1,\cdots, N$
- 平均損失を計算 $\bar{L} = \sum_{i=1}^N L_i p_i$
- 信頼度を計算（大きいほど現在学習しているモデルは予測を外している）$\beta = \bar{L} / (1 - \bar{L})$
- 各サンプルの重みを更新 $w_i = w_i \beta^{1-L_i}$
- M回繰り返していなければ最初に戻る。
予測
予測時には$\beta$も用います。各モデルの重みを$\log (1/\beta)$とした時の重み付き中央値を予測値として用います。
Classification
次に分類です。重みを用いる点は同じですが、サンプリングは実施されず分割を計算する際にのみ用いられます。
学習
- 重みを初期化。$w_i = 1/N$
- 重みとともに学習
- エラーを計算。 $err = (予測が正解した時の重みの総和)/重みの総和$
- 重みの更新具合を計算。$\alpha = (1-err)/err$
- 各サンプルの重みを更新。$w_i = w_i \exp(\alpha * （不正解の場合１、それ以外０）)$
- 重みの総和を１にスケール
- ２～６をM回繰り返す
予測
２値分類でラベルを予測する場合は、
\tilde{y}_i = \text{sign} \left( \sum^M_{i=1} \alpha_i H_i(x_i) \right)
を計算し、その符号が予測ラベルです。ここでは$\pm 1$を正解として与えます。ただしこの時$H_i$はラベルそのものを返します。一方、ラベルの確率は回帰と同じように計算することができるようですが、もう一度確認して追記します。
分類は実装が間に合いませんでした。
上記のものは最初期に提案されたもので現在は非常に様々な派生アルゴリズムが存在します。Adaboost自体もScikit-learnではオリジナルではなくSAMME.Rというもののようです。
以上