【機械学習】ブースト(boost・AdaBoost）の原理・計算式

機械学習で識別器の作成などに使われるブースト(boost・AdaBoost）のアルゴリズムや計算についてまとめました。

【boostとは】AdaBoost
【アルゴリズム】AdaBoostの学習手順
参考文献

【boostとは】AdaBoost

boost(ブースト)とは、多くの弱識別器を組み合わせて強識別器を作成することです。
識別器を強化することから「boost(ブースト)」と呼ばれます。

AdaBoostは、Adaptive Boosting（適応型ブースティング）の略で1995年にY.Freundらによって考案された学習アルゴリズムです。
AdaBoostでは、学習過程で弱識別器に対して適応的に重み付けを行います。
そして、重みが大きい弱識別器を重点的に組み合わせて識別器の能力を高めていき、強識別器を作ります。

【特徴】
・計算時間が短い（処理が高速）
・事前のチューニングが不要
・ノイズや外れ値の影響を受けやすい

【アルゴリズム】AdaBoostの学習手順

AdaBoostのアルゴリズムの大まかな処理手順は以下の通りです。

–	内容
1	訓練データ(正解・非正解データ、教師データ)と弱識別器を多数用意します。
2	訓練データの重み $D_1$ を初期化します。（正解・非正解それぞれ均等にします。重みの合計はそれぞれ0.5）
3	学習をT回繰り返します。( $t=1,2, \hdots ,T$ )
3.1	各弱識別器に訓練データを与えて判別を行います。そして、訓練データの重み $D_t$ を元に誤検出率を計算します。
3.2	誤検出率が最小になった弱識別器 $h_t$ を取り出します。
3.3	誤検出率を元に、取り出した弱識別器の重み $\alpha_t$ を計算します。
3.4	取り出した弱識別器が判別を誤った訓練データの重み $D_t$ を大きくします。
3.5	訓練データの重み $D_t$ を合計1になるよう正規化します。
4	取り出した弱識別器の重み付き和により強識別器を構築します。

※訓練データと弱識別器の重みを混同しないよう注意

ポイント

エラー率が最小になった弱識別器は、他の弱識別器よりも優れています。
そのため、学習を繰り返す毎に取り出していき、強識別器の作成に使用します。
また、取り出した弱識別器が判別を誤った訓練データは重要なので、重みを大きくします。

強識別器は、学習回数の分だけ取り出した弱識別器とその重み（手順3.3で算出）により求められる重み付き和で構成されます。

参考文献

[1] Y.Freund and R.Schapire,”Experiments with a New Boosting Algorithm”(1996)
http://www.cis.upenn.edu/~mkearns/teaching/COLT/boostingexperiments.pdf

[2] Y.Freund and R.Schapire,”A Decision-Theoretic Generalization of On-Line Learning and an Application to Bosting”(1997)
http://face-rec.org/algorithms/Boosting-Ensemble/decision-theoretic_generalization.pdf