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

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

boost

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

AdaBoostとは

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

【関連記事】
【画像処理入門】アルゴリズム&プログラミング

シェア&フォローお願いします!