機械学習リファレンスマニュアル

最終変更者: 怡土順一, 最終変更リビジョン: 467, 最終変更日時: 2009-06-23 14:23:34 +0900 (火, 23 6月 2009)

ブースティング（Boosting）

一般的な機械学習のタスクは，次のような教師あり学習である．入力と出力の学習データ集合が与えられたときに，未観測の入力サンプル xに対する出力 y を予測する．つまり，入力 x と出力 y の間の関係を表す関数F: y = F(x) を学習することが目的である．定性的な出力予測が分類と呼ばれるのに対して，定量的な出力予測は回帰と呼ばれる．

ブースティングは教師あり分類の学習タスクを解決する強力な学習概念であり，たくさんの「弱い」分類器の能力を結合することで，強力な「コミッティ」[HTF01] を構成する．弱い分類器は，偶然よりもましな性能を持っていれば良いため，非常にシンプルで計算コストの小さいものである．しかし，これらの多くを上手く結合することで，強力な分類器が構成できる．これは，SVM やニューラルネットワーク等の「一つの」強力な分類器よりも良い性能を示すことも多い．

決定木は，ブースティングの枠組みに用いられる最も有名な弱い分類器である．一つの木に一つの分類ノードしかない，最も単純な決定木（stump と呼ばれる）で十分な場合が多い．

ブーストされたモデルの学習は，N 個の学習サンプル {(x_i,y_i,)}1N（ここで，x_i ∈ R^K， y_i ∈ {−1, +1}）に基づいている． x_i は，K 個の成分をもつベクトルである．それぞれの弱い分類器（コンポーネント）は，現在の学習タスクに関連する特徴をエンコードする．目的の二つのクラスは，−1 と +1 にエンコードされる．

ブースティングの変形として，Discrete Adaboost，Real AdaBoost，LogitBoost，Gentle AdaBoost[FHT98] などが知られている．これらは全て，全体的な構造が非常に似ているので，以下で説明する標準的な2クラスの Discrete AdaBoost についてのみ見ることにする．初期状態では，各サンプルに対して同一の重みが与えられる（step 2）．次に，弱い分類器 f_m(x) が重み付き学習データを用いて学習される（step 3-1）．重み付き学習誤差とスケーリングファクター c_mが計算される（step 3-2）．分類に失敗した学習サンプルの重みが増加する（step 3-3）．そして，重みが正規化され，次の弱い分類器を求める処理がまた M-1 回繰り返される．最終的な分類器 F(x) は，個々の弱い分類器出力の重み付き和の符号を出力とする（step 4）．

N 個のサンプルが与えられる {(x_i,y_i)}1N with x_i ∈ R^K, y_i ∈ {−1, +1}.
重みを付ける w_i = 1/N, i = 1,…,N．
繰り返し m = 1,2,…,M:
1. 分類器 f_m(x) ∈ {−1,1}を重み w_i 付きの学習データを用いて学習する．
2. err_m = E_w [1_{(y ≠ f_m(x))}], c_m = log((1 − err_m)/err_m) を計算する．
3. w_i ← w_i exp[c_m 1_{(y_i ≠
  f_m(x_i))}]， i = 1,2,…,N, となるように各重みを設定し，さらに ∑i w_i = 1 となるように再び正規化する．
分類器の出力 [∑ m = 1M c_m f_m(x)] の符号．

2クラスの Discrete AdaBoost アルゴリズム：学習（step 1 から 3）と分類（step 4）

注釈： 古典的ブースティング手法と同様に，現在の実装でも2クラス分類器だけをサポートしている． M>2 のクラスに対しては，[FHT98] で述べられる AdaBoost.MH アルゴリズムが存在する．これは，かなり多くの学習データ集合が必要ではあるものの，問題を2クラス問題に帰着する．

精度を大きく下げることなくブーストモデルの計算時間を減らすために，影響力を考慮したトリミング（influence trimming technique）が用いられることがある．学習アルゴリズムが進むにつれて集合の決定木の数が増加すると，多くの学習サンプルが正しく分類されて信頼度が増す．その結果，それらのサンプルは以降の繰り返し計算において小さい重みが付けられる．相対的な重みが非常に小さいサンプルは，弱い学習器の学習においてほとんど影響を与えない．よって，このようなサンプルは弱い学習器の学習中に排除されるが，最終的に生成される分類器にあまり影響を与えない．この処理は，パラメータ weight_trim_rate によりコントロールされる．全重みに対して上位 weight_trim_rate の割合を占める重みをもつサンプルだけが，弱い分類器の学習に利用される．全ての学習サンプルに対する重みは，各学習の反復毎に再計算される事に注意する．ある繰り返しにおいて削除されたサンプルも，別の弱い学習器の学習においては再利用されるかもしれない [FHT98]．

[HTF01] Hastie, T., Tibshirani, R., Friedman, J. H. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer Series in Statistics. 2001.

[FHT98] Friedman, J. H., Hastie, T. and Tibshirani, R. Additive Logistic Regression: a Statistical View of Boosting. Technical Report, Dept. of Statistics, Stanford University, 1998.

CvBoostParams

ブースティングの学習パラメータ

struct CvBoostParams : public CvDTreeParams
{
    int boost_type;
    int weak_count;
    int split_criteria;
    double weight_trim_rate;

    CvBoostParams();
    CvBoostParams( int boost_type, int weak_count, double weight_trim_rate,
                   int max_depth, bool use_surrogates, const float* priors );
};

boost_type: ブースティングの種類．は以下のいずれかである．
CvBoost::DISCRETE - Discrete AdaBoost
CvBoost::REAL - Real AdaBoost
CvBoost::LOGIT - LogitBoost
CvBoost::GENTLE - Gentle AdaBoost
この内，よく利用されるのが Gentle AdaBoost と Real AdaBoost である．
weak_count: 構築する弱い分類器の個数．
split_criteria: 弱い木を構築するときの最適分岐を選択する際に用いられる分岐規則．
CvBoost::DEFAULT - 個々のブースティング手法におけるデフォルト規則（後述）を用いる．
CvBoost::GINI - ジニ指標（Gini index）を用いる．これはReal AdaBoost のデフォルトオプションである．Discrete AdaBoost でも用いられることがある．
CvBoost::MISCLASS - 誤判別率を用いる．これはDiscrete AdaBoost のデフォルトオプションである．Real AdaBoost でも用いられることがある．
CvBoost::SQERR - 最小二乗基準を用いる．これは LogitBoost および Gentle AdaBoost で用いられるデフォルトかつ唯一のオプションである．
weight_trim_rate: トリミング重み比率．0..1 の範囲内．前述の注釈を参照．もしこのパラメータが ≤0 あるいは >1 の場合，トリミングは行われず，全てのサンプルが各繰り返し計算で用いられる．デフォルト値は 0.95 である．

この構造体は，CvDTreeParams から派生するが，全ての決定木パラメータがサポートされるわけではない．具体的には，交差検証法がサポートされていない．

CvBoostTree

弱い決定木クラス

class CvBoostTree: public CvDTree
{
public:
    CvBoostTree();
    virtual ~CvBoostTree();

    virtual bool train( CvDTreeTrainData* _train_data,
                        const CvMat* subsample_idx, CvBoost* ensemble );
    virtual void scale( double s );
    virtual void read( CvFileStorage* fs, CvFileNode* node,
                       CvBoost* ensemble, CvDTreeTrainData* _data );
    virtual void clear();

protected:
    ...
    CvBoost* ensemble;
};

ブーストされた分類器 CvBoost の要素である弱い決定木（弱い分類器）は，CvDTree から派生する．通常，弱い決定木をユーザが直接使う必要はないが，シーケンス CvBoost::weak の要素としてのアクセスや， CvBoost::get_weak_predictorsによる取り出しが可能である．

LogitBoost および Gentle AdaBoost の場合，それぞれの弱い決定木は，分類木ではなく回帰木となることに注意する． Discrete AdaBoost と Real AdaBoost の場合でも，戻り値（CvBoostTree::predict）は出力クラスラベルではない．クラス番号 0 に対しては，正の値が「投票」され，クラス番号 1 に対しては負の値が投票される．そして，その投票に重み付けがなされる．個々の木の重みは，CvBoostTree::scale メソッドにより増減される． method CvBoostTree::scale.

CvBoost

ブーストされた分類器クラス

class CvBoost : public CvStatModel
{
public:
    // ブースティングの種類
    enum { DISCRETE=0, REAL=1, LOGIT=2, GENTLE=3 };

    // 分割基準
    enum { DEFAULT=0, GINI=1, MISCLASS=3, SQERR=4 };

    CvBoost();
    virtual ~CvBoost();

    CvBoost( const CvMat* _train_data, int _tflag,
             const CvMat* _responses, const CvMat* _var_idx=0,
             const CvMat* _sample_idx=0, const CvMat* _var_type=0,
             const CvMat* _missing_mask=0,
             CvBoostParams params=CvBoostParams() );

    virtual bool train( const CvMat* _train_data, int _tflag,
             const CvMat* _responses, const CvMat* _var_idx=0,
             const CvMat* _sample_idx=0, const CvMat* _var_type=0,
             const CvMat* _missing_mask=0,
             CvBoostParams params=CvBoostParams(),
             bool update=false );

    virtual float predict( const CvMat* _sample, const CvMat* _missing=0,
                           CvMat* weak_responses=0, CvSlice slice=CV_WHOLE_SEQ,
                           bool raw_mode=false ) const;

    virtual void prune( CvSlice slice );

    virtual void clear();

    virtual void write( CvFileStorage* storage, const char* name );
    virtual void read( CvFileStorage* storage, CvFileNode* node );

    CvSeq* get_weak_predictors();
    const CvBoostParams& get_params() const;
    ...

protected:
    virtual bool set_params( const CvBoostParams& _params );
    virtual void update_weights( CvBoostTree* tree );
    virtual void trim_weights();
    virtual void write_params( CvFileStorage* fs );
    virtual void read_params( CvFileStorage* fs, CvFileNode* node );

    CvDTreeTrainData* data;
    CvBoostParams params;
    CvSeq* weak;
    ...
};

CvBoost::train

ブーストされた分類器の学習

bool CvBoost::train(const CvMat* _train_data, int _tflag,
             const CvMat* _responses, const CvMat* _var_idx=0,
             const CvMat* _sample_idx=0, const CvMat* _var_type=0,
             const CvMat* _missing_mask=0,
             CvBoostParams params=CvBoostParams(),
             bool update=false );

このTrainメソッドは共通のテンプレートに従い，最後のパラメータ update は，その分類器をアップデートする必要がある（つまり，新しい弱い分類木が既にある集合に加えられる）か，あるいは，その分類器を最初から作り直すかを指定する．応答は，カテゴリ変数でなければならず，二つのクラスが存在するべきである．つまり，ブーストされた分類器は，回帰にはつかえない．

CvBoost::predict

入力サンプルに対する応答を予測する

float CvBoost::predict(const CvMat* sample, const CvMat* missing=0,
                        CvMat* weak_responses=0, CvSlice slice=CV_WHOLE_SEQ,
                        bool raw_mode=false ) const;

sample: 入力サンプル．
missing: データ欠損マスク（オプション）．データ欠損を扱うためには，弱い決定木が代理分岐を含まなければならない（CvDTreeParams::use_surrogates を参照）．
weak_responses: 個々の弱い決定木からの応答の出力パラメータ（オプション）で，これは浮動小数点型ベクトルである．ベクトルの要素数は，slice 長と等しくなければならない．
slice: 予測に用いられる弱い決定木シーケンスの連続的部分集合（スライス）．デフォルトでは，全ての弱い分類器が用いられる．
raw_mode: CvDTree::predict と同じ意味．通常は false となるべきである．

メソッド CvBoost::predict は，決定木の集合にサンプルを入力し，重み付き投票に基づく出力クラスラベルを返す．

CvBoost::prune

指定された弱い決定木を削除する

void CvBoost::prune(CvSlice slice );

このメソッドは指定された弱い決定木をシーケンスから削除する．個々の決定木における刈り込み（これは現在サポートされていない）と混同しないように注意すること．

CvBoost::get_weak_predictors

弱い分類器のシーケンスを返す

CvSeq* CvBoost::get_weak_predictors();

このメソッドは弱い分類木のシーケンスを返す．シーケンスの各要素は CvBoostTree クラス（あるいはその派生クラス）へのポインタである．

機械学習 リファレンス マニュアル

機械学習リファレンスマニュアル