« 国際会議WWW2009論文感想その6 | トップページ | クラスタリング アルゴリズムの評価 »

AdaBoost アルゴリズム (ブースティング)

近年,機械学習の研究分野において,ブースティングと呼ばれるアルゴリズムが注目を集めています.アルゴリズムと書きましたが,正確には教師あり学習を実行するための機械学習のメタアルゴリズムであります.すなわち,一般の(任意の)機械学習アルゴリズムをもっと賢く実行するためのフレームワークと言えます.弱い学習機をまとめて,重みを付けてその結果を足し合わせることで,強い学習機を生成することを目指します.

核となる機械学習アルゴリズムに何を用いるかは,制限されておりません.弱い分類器は,学習の正確さ(あるいは汎用性?)に基づいて,重み付けされます.「分類器をいくつも作成する」と言っても,どう作成するのかが分からないと思いますが,実際には,元のデータに重み付けをし直して(何度も重みづけを行い),それにより共通の機械学習アルゴリズムで学習し,複数の分類器を作ります.一般には,誤分類される例(サンプル)は重みを増し,正しく分類される例は重みを減らします.

代表的かつ人気のあるブースティングアルゴリズムとして,AdaBoost(「エイダブースト」「アダブースト」と呼ぶ)があります.以下,AdaBoostのアルゴリズムの概要と本質について説明します.

概要

1.サンプル(特徴ベクトルと教師信号であるクラスの組)への重みは,最初は1/N (Nはサンプル数)で初期化します.

2.T個弱識別器を作るとします.

3.(まずは,1つ目の)弱識別器tを作ります.弱識別器tの作り方は,重み付きのサンプルを利用して,一般的な機械学習アルゴリズムを利用して学習します.

4.弱識別器tの誤り率を求めます.誤り率は,各サンプルを見たときに,サンプルのクラスと弱識別器の出力クラスが一致しないサンプルの重みを足し合わせたものになります.

5.誤り率から弱識別器tの信頼度を求めます.具体的には,誤り率が小さいほど,信頼度が大きくなるようにします.

6.サンプルへの重みを更新します.サンプルへの重みは,弱識別器tが正しく識別できたサンプルは重みが低くなるように更新します.弱識別器tが間違って識別したサンプルは重みが高くなるように更新します.

7.サンプルの重みの和が1になるように正規化します.

8.3.に戻って,t+1個目の弱識別器を作ります.T個作れたら,アルゴリズム終了です.

9.最終的な識別は,全ての弱識別器を信頼度で重みづけして多数決を取ります.

本質

ブースティングの本質は,弱い機械学習アルゴリズムを用いて,過学習の状態を作り出すことにあると考えます.サンプルに重みをつけずに機械学習したものは,もっとも一般的な識別を行う識別器と考えてよいでしょう.その識別器が誤ったものの重みを大きくして学習するということは,特異例を識別するための特異な識別器を作ることになります.ブースティングでは,順に識別器を作っていきますが,汎用的な識別器から順に特異例に対する識別器を,深く掘り下げて作っていくイメージになります.

このように元の学習データは同じで,それを何度も繰り返し学習を行いますので,見た目的には少ない学習データから効率的に学習していることになります.学習データは,ユーザプロファイリングなどにおいては,多くは期待できませんので,そのようなモデルの学習には,ブースティングは期待されております.

ただし,本当に効率的かどうかは結果をみないとわかりません.本当に賢い識別器を作るか,過学習の識別器を作るかは,非常にセンシティブであると言えます.学習データが少ないから使うというモチベーションは分かりますが,作成された識別器の汎用性は十分に考慮する必要があると思います.

なお,アルゴリズムの特質上,もともと強い学習器を弱識別器の学習に用いると,過学習の上に過学習を塗り重ねる可能性がありますので,注意が必要です.SVMなどの高性能な機械学習アルゴリズムを用いるよりは,ロジスティック回帰などの古典的なアルゴリズムを用いる方が良いように思います.

|

« 国際会議WWW2009論文感想その6 | トップページ | クラスタリング アルゴリズムの評価 »

Web研究」カテゴリの記事