サポートベクターマシン

サポートベクターマシン(英: support vector machine、SVM)は、教師あり学習を用いるパターン認識モデルの一つである。識別や回帰分析へ適用できる。

サポートベクターマシンは、現在知られている手法の中でも認識性能が優れた学習モデルの一つである。サポートベクターマシンが優れた認識性能を発揮することができる理由は、未学習データに対して高い識別性能を得るための工夫があるためである。

基本的な考え方

サポートベクターマシンは、線形入力素子を利用して 2 クラスのパターン識別器を構成する手法である。訓練サンプルから、各データ点との距離が最大となるマージン最大化超平面を求めるという基準（超平面分離定理）で線形入力素子のパラメータを学習する。

最も簡単な場合である、与えられたデータを線形に分離することが可能な（例えば、3次元のデータを2次元平面で完全に区切ることができる）場合を考えよう。

このとき、SVMは与えられた学習用サンプルを、もっとも大胆に区切る境目を学習する。 学習の結果得られた超平面は、境界に最も近いサンプルとの距離（マージン）が最大となるパーセプトロン（Margin classifier）で定義される。 すなわち、そのようなパーセプトロンの重みベクトル $\boldsymbol{w}\in\mathbb{R}^p$ を用いて、超平面は $\{\boldsymbol{x}\in\mathbb{R}^p\mid\boldsymbol{x}\cdot\boldsymbol{w}=0\}$ で表される。

学習過程はラグランジュの未定乗数法とKKT条件を用いることにより、最適化問題の一種である凸二次計画問題で定式化される。 ただし、学習サンプル数が増えると急速に計算量が増大するため、分割統治法の考え方を用いた手法なども提案されている。

概念的特長

次のような学習データ集合 $\mathcal{D}$ が与えられた場合を考える。

$\mathcal{D} = \{ (\boldsymbol{x}_i, y_i) \mid \boldsymbol{x}_{i}\in\mathbb{R}^p,\, y_{i}\in\{-1,1\} \}_{i=1}^n$

$y_i$ は 1 もしくは -1 の値を持つ変数で $\boldsymbol{x}_i$ が属したクラスを意味する。 $\boldsymbol{x}_i$ は $p$ 次元の特徴ベクトルである。

H3は二つのクラスのいくつかの点を正しく分類していない。H1 と H2 は二つのクラスのいくつかの点を分類するのに、H2 が H1 よりもっと大きいマージンを持って分類することを確認することができる。

ニューラルネットワークを含む多くの学習アルゴリズムは、このような学習データが与えられた時 $y_i=1$ であるいくつかの点と $y_i=-1$ であるいくつかの点とを分離する超平面をさがすのが共通の目標であるが、SVMが他のアルゴリズムと差別化される特徴はただいくつかの点を分離する超平面を捜すことで終わるのではなく、いくつかの点を分離することができる幾多の候補平面の中でマージンが最大になる超平面 (maximum-margin hyperplane) を探す点にある。ここでマージンとは、超平面から各いくつかの点に至る距離の最小値を言い、このマージンを最大にしながらいくつかの点を二つのクラスで分類しようとすると、結局クラス 1 に属するいくつかの点との距離の中の最小値とクラス -1 に属するいくつかの点との距離の中の最小値とが等しくなるように超平面が位置しなければならず、このような超平面をマージン最大の超平面という。結論として、SVMは二つのクラスに属しているいくつかの点を分類する幾多の超平面の中で、最大限に二つのクラスのいくつかの点と距離を維持するものを探すアルゴリズムといえる。

線形分離不可能な問題への適用

1963年にウラジミール・ヴァプニク が発表した初期のサポートベクターマシンは、線形分類器にしか適用できなかった。 しかし、再生核ヒルベルト空間の理論を取り入れたカーネル関数を用いてパターンを有限もしくは無限次元の特徴空間へ写像し、特徴空間上で線形分離を行う手法が 1992年に ヴァプニクらによって提案された。 これにより、非線形分類問題にも優れた性能を発揮することがわかり、近年特に注目を集めている。

なお、カーネル関数を取り入れた一連の手法では、どのような写像が行われるか知らずに計算できることから、カーネルトリック (Kernel Trick) と呼ばれている。

関連項目

• カーネル法
• 逐次最小問題最適化法 (SMO)
• 人工知能
• パターン認識
• 放射基底関数
• 線形分類器
• 実装
  • LIBSVM
  • scikit-learn

翻訳元

en:Support vector machine 2009-3-26 01:13 UTC から「概念的特長」の項を翻訳。