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

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

サポートベクターマシン（SVM）

本来，サポートベクターマシン（SVM）は，（ある意味で）最適な二値（2クラス）分類器を作るためのテクニックであったが，その後，このテクニックは回帰およびクラスタリング問題に拡張されてきた． SVM はカーネルベースな手法の一つである．この手法はカーネル関数を用いて特徴ベクトルを高次元空間にマップし，この空間における最適な線形分離関数（あるいは学習データに適合する最適な超平面）を形成する． SVMの場合，高次元空間へのマッピングが陽に定義されない代わりに，超空間における二点間距離，すなわちそれを計算するカーネルの定義が必要となる．

この手法は，両クラス（2クラス分類器の場合）の分割超平面に最も近い特徴ベクトルのマージンが最大である，という意味において最適となる．超平面に最も近い特徴ベクトルは「サポートベクター」と呼ばれ，これは，その他のベクトルの位置が超平面（決定関数）に影響を及ぼさないという事を意味している．

SVMに関する優れたリファレンスは数多く存在する．ここでは数冊を紹介するにとどめる．

[Burges98] C. Burges. "A tutorial on support vector machines for pattern recognition", Knowledge Discovery and Data Mining 2(2), 1998.
（オンラインでも入手可能 http://citeseer.ist.psu.edu/burges98tutorial.html）．
LIBSVM - A Library for Support Vector Machines. By Chih-Chung Chang and Chih-Jen Lin
(http://www.csie.ntu.edu.tw/~cjlin/libsvm/)

CvSVM

サポートベクターマシンクラス

class CvSVM : public CvStatModel
{
public:
    // SVM の種類
    enum { C_SVC=100, NU_SVC=101, ONE_CLASS=102, EPS_SVR=103, NU_SVR=104 };

    // SVM カーネルの種類
    enum { LINEAR=0, POLY=1, RBF=2, SIGMOID=3 };

    // SVM パラメータの種類
    enum { C=0, GAMMA=1, P=2, NU=3, COEF=4, DEGREE=5 };
    
    CvSVM();
    virtual ~CvSVM();

    CvSVM( const CvMat* _train_data, const CvMat* _responses,
           const CvMat* _var_idx=0, const CvMat* _sample_idx=0,
           CvSVMParams _params=CvSVMParams() );

    virtual bool train( const CvMat* _train_data, const CvMat* _responses,
                        const CvMat* _var_idx=0, const CvMat* _sample_idx=0,
                        CvSVMParams _params=CvSVMParams() );

    virtual bool train_auto( const CvMat* _train_data, const CvMat* _responses,
        const CvMat* _var_idx, const CvMat* _sample_idx, CvSVMParams _params,
        int k_fold = 10,
        CvParamGrid C_grid      = get_default_grid(CvSVM::C),
        CvParamGrid gamma_grid  = get_default_grid(CvSVM::GAMMA),
        CvParamGrid p_grid      = get_default_grid(CvSVM::P),
        CvParamGrid nu_grid     = get_default_grid(CvSVM::NU),
        CvParamGrid coef_grid   = get_default_grid(CvSVM::COEF),
        CvParamGrid degree_grid = get_default_grid(CvSVM::DEGREE) );
			
    virtual float predict( const CvMat* _sample ) const;
    virtual int get_support_vector_count() const;
    virtual const float* get_support_vector(int i) const;
    virtual CvSVMParams get_params() const { return params; };
    virtual void clear();

    static CvParamGrid get_default_grid( int param_id );
    
    virtual void save( const char* filename, const char* name=0 );
    virtual void load( const char* filename, const char* name=0 );

    virtual void write( CvFileStorage* storage, const char* name );
    virtual void read( CvFileStorage* storage, CvFileNode* node );
    int get_var_count() const { return var_idx ? var_idx->cols : var_all; }

protected:
    ...
};

CvSVMParams

SVM 学習パラメータ

struct CvSVMParams
{
    CvSVMParams();
    CvSVMParams( int _svm_type, int _kernel_type,
                 double _degree, double _gamma, double _coef0,
                 double _C, double _nu, double _p,
                 CvMat* _class_weights, CvTermCriteria _term_crit );

    int         svm_type;
    int         kernel_type;
    double      degree; // poly 用
    double      gamma;  // poly/rbf/sigmoid 用
    double      coef0;  // poly/sigmoid 用

    double      C;  // CV_SVM_C_SVC, CV_SVM_EPS_SVR, CV_SVM_NU_SVR 用
    double      nu; // CV_SVM_NU_SVC, CV_SVM_ONE_CLASS, CV_SVM_NU_SVR 用
    double      p;  // CV_SVM_EPS_SVR 用
    CvMat*      class_weights; // CV_SVM_C_SVC 用
    CvTermCriteria term_crit;  // 終了条件
};

svm_type: SVM の種類．以下のうち一つ．
CvSVM::C_SVC - はずれ値に対するペナルティ乗数 C を持ち，不完全な分離を許容する n-クラス分類（n>=2）．
CvSVM::NU_SVC - 不完全な分離となる可能性がある n-クラス分類． C の代わりにパラメータ nu （0..1 の範囲，大きい値ほど滑らかな判断境界を表す）が用いられる．
CvSVM::ONE_CLASS - 1-クラス SVM．全学習データは同じクラスから得られ，SVMはそのクラスを特徴空間の他のクラスから分離する境界を求める．
CvSVM::EPS_SVR - 回帰．学習集合の特徴ベクトルと超平面との距離が p よりも短くなければならない．はずれ値に対してはペナルティ乗数 C が用いられる．
CvSVM::NU_SVR - 回帰．p の代わりにnu が用いられる．
kernel_type: カーネルの種類．以下のうち一つ．
CvSVM::LINEAR - マッピングは行われない．もとの特徴空間内で，線形分離（あるいは回帰）が行われる．最も高速なオプション．d(x,y) = x•y == (x,y)
CvSVM::POLY - 多項式カーネル： d(x,y) = (gamma*(x•y)+coef0)^degree
CvSVM::RBF - 動径基底関数カーネル．ほとんどの場合，適切に動作する： d(x,y) = exp(-gamma*|x-y|²)
CvSVM::SIGMOID - シグモイド関数がカーネルとして用いられる．d(x,y) = tanh(gamma*(x•y)+coef0)
degree, gamma, coef0: カーネルのパラメータ．上述の式を参照．
C, nu, p: 一般化 SVM の最適化問題におけるパラメータ．
class_weights: 特定のクラスに割り当てられる任意の重み．これに C が乗算され，それが異なるクラスに対する分類失敗ペナルティとして作用する．重みが大きくなるほど，対応するクラスに属するデータの分類失敗に対して大きなペナルティが課せられる．
term_crit: SVM の反復学習手続きに対する終了条件（これは制約条件付き二次最適化問題のいくつかを解決する）．

この構造体は初期化される必要があり，その後 CvSVM の学習メソッドに渡される．

CvSVM::train

SVM を学習する

bool CvSVM::train(const CvMat* _train_data, const CvMat* _responses,
                   const CvMat* _var_idx=0, const CvMat* _sample_idx=0,
                   CvSVMParams _params=CvSVMParams() );

このメソッドはSVM モデルを学習する．これは以下の制限のもと，一般的なtrain「メソッド」の仕様に従う． CV_ROW_SAMPLE データレイアウトだけがサポートされる．入力変数は全て連続変数である．出力変数はカテゴリ変数（_params.svm_type=CvSVM::C_SVC や _params.svm_type=CvSVM::NU_SVC）か，連続変数（_params.svm_type=CvSVM::EPS_SVR や　_params.svm_type=CvSVM::NU_SVR），あるいは全く要求されない（_params.svm_type=CvSVM::ONE_CLASS），のいずれかである．データ欠損はサポートされない．

他の全てのパラメータは構造体CvSVMParams に集められる．

CvSVM::train_auto

SVM を最適なパラメータで学習する

bool CvSVM::train_auto( const CvMat* _train_data, const CvMat* _responses,
        const CvMat* _var_idx, const CvMat* _sample_idx,
        CvSVMParams params, int k_fold = 10,
        CvParamGrid C_grid      = get_default_grid(CvSVM::C),
        CvParamGrid gamma_grid  = get_default_grid(CvSVM::GAMMA),
        CvParamGrid p_grid      = get_default_grid(CvSVM::P),
        CvParamGrid nu_grid     = get_default_grid(CvSVM::NU),
        CvParamGrid coef_grid   = get_default_grid(CvSVM::COEF),
        CvParamGrid degree_grid = get_default_grid(CvSVM::DEGREE) );

k_fold: 交差検定（Cross-validation）パラメータ．学習集合は，k_foldの部分集合に分割され，一つの部分集合がモデルの学習に用いられ，その他の部分集合はテスト集合となる．つまり，SVM アルゴリズムは，k_fold回実行される

このメソッドは， CvSVMParams から最適なパラメータ C，gamma，p，nu，coef0， degree を選択して，自動的に SVM モデルを学習する．この最適性は，テスト集合に対する交差検定推定の誤差が最小となる事を意味する．パラメータの選択は，対数グリッド単位で繰り返される．例えば，パラメータ gamma は，次の集合から値をとる． {gamma_grid.min_val, gamma_grid.min_val*gamma_grid.step, gamma_grid.min_val*gamma_grid.step²,..., gamma_grid.min_val*gamma_grid.stepⁿ}．ここで，n は， gamma_grid.min_val*gamma_grid.stepⁿ < gamma_grid.max_val を満たす，最大のインデックス．つまり，step は，常に 1 よりも大きくなければならない．

もし，いくつかのパラメータで最適化が必要なければ，そのグリッドステップは，1 以下の任意の値に設定されるべきである．例えば，gamma の最適化を避けるためには， gamma_grid.step = 0，また，gamma_grid.min_val と gamma_grid.max_val は任意の値に設定される．この場合，params.gamma の値が gamma として用いられる．

そして，いくつかのパラメータにおいて最適化が必要であるが，そのグリッドが全く不明な場合，関数 CvSVM::get_default_grid が呼び出される．グリッドを生成するために，例えば，gamma の場合， CvSVM::get_default_grid(CvSVM::GAMMA) を呼び出す．

この関数は，回帰（params.svm_type=CvSVM::EPS_SVR や params.svm_type=CvSVM::NU_SVR）と同様に，分類（params.svm_type=CvSVM::C_SVC や params.svm_type=CvSVM::NU_SVC）の場合でも動作する． params.svm_type=CvSVM::ONE_CLASS の場合，最適化は行われず，params で指定されたパラメータを与えられた通常の SVM が実行される．

CvSVM::get_default_grid

SVM パラメータのためのグリッドを生成する

CvParamGrid CvSVM::get_default_grid( int param_id );

param_id: 次の値のうちのいずれか一つ： CvSVM::C, CvSVM::GAMMA, CvSVM::P, CvSVM::NU, CvSVM::COEF, CvSVM::DEGREE. このIDで指定されたパラメータのグリッドが生成される．

この関数は，指定された SVMアルゴリズムのパラメータのグリッドを生成する．そのグリッドは，関数 CvSVM::train_auto に渡されることになる．

CvSVM::get_params

現在の SVM パラメータを返す

CvSVMParams CvSVM::get_params() const;

この関数は，自動学習CvSVM::train_auto で獲得された最適パラメータを取得するために用いられる．

CvSVM::get_support_vector*

サポートベクターの個数と，特定のサポートベクターを取得する

int CvSVM::get_support_vector_count() const;
const float* CvSVM::get_support_vector(int i) const;

このメソッドは，サポートベクターの集合を取得するために使われる．

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

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