サポートベクターマシン

サポートベクターマシン（, SVM）は、教師あり学習を用いるパターン認識モデルの1つである。分類や回帰へ適用できる。1963年にとAlexey Ya. Chervonenkisが線形サポートベクターマシンを発表し、1992年にBernhard E. Boser、Isabelle M. Guyon、ウラジミール・ヴァプニクが非線形へと拡張した。
サポートベクターマシンは、現在知られている手法の中でも認識性能が優れた学習モデルの1つである。サポートベクターマシンが優れた認識性能を発揮することができる理由は、未学習データに対して高い識別性能を得るための工夫があるためである。
基本的な考え方.
サポートベクターマシンは、線形入力素子を利用して2クラスのパターン識別器を構成する手法である。訓練サンプルから、各データ点との距離が最大となるマージン最大化超平面を求めるという基準（超平面分離定理）で線形入力素子のパラメータを学習する。
最も簡単な場合である、与えられたデータを線形に分離することが可能な（例えば、3次元のデータを2次元平面で完全に区切ることができる）場合を考えよう。
このとき、SVMは与えられた学習用サンプルを、もっとも大胆に区切る境目を学習する。学習の結果得られた超平面は、境界に最も近いサンプルとの距離（マージン）が最大となるパーセプトロン（マージン識別器）で定義される。すなわち、そのようなパーセプトロンの重みベクトル formula_1 を用いて、超平面は formula_2 で表される。
学習過程はラグランジュの未定乗数法とKKT条件を用いることにより、最適化問題の一種である凸二次計画問題で定式化される。ただし、学習サンプル数が増えると急速に計算量が増大するため、分割統治法の考え方を用いた手法なども提案されている。
概念的特長.
次のような学習データ集合formula_3が与えられた場合を考える。
formula_5は1もしくは−1の値を持つ変数でformula_6が属したクラスを意味する。formula_6はformula_8次元の特徴ベクトルである。
ニューラルネットワークを含む多くの学習アルゴリズムは、このような学習データが与えられた時formula_9であるいくつかの点とformula_10であるいくつかの点とを分離する超平面をさがすのが共通の目標である。SVMが他のアルゴリズムと差別化される特徴は、ただいくつかの点を分離する超平面を捜すことで終わるのではなく、いくつかの点を分離することができる幾多の候補平面の中でマージンが最大になる超平面 (maximum-margin hyperplane) を探す点にある。ここでマージンとは、超平面から各いくつかの点に至る距離の最小値を言い、このマージンを最大にしながらいくつかの点を2つのクラスで分類しようとすると、結局クラス1に属するいくつかの点との距離の中の最小値とクラス−1に属するいくつかの点との距離の中の最小値とが等しくなるように超平面が位置しなければならず、このような超平面をマージン最大の超平面という。結論として、SVMは2つのクラスに属しているいくつかの点を分類する幾多の超平面の中で、最大限に2つのクラスのいくつかの点と距離を維持するものを探すアルゴリズムといえる。
線形 SVM.
以下のような形式の formula_11 個のトレーニング・データセットが与えられる。
formula_5は1または−1であり、それぞれ、点formula_14が属するクラスを示す。formula_6はformula_8-次元の実数ベクトルである。formula_17となる点formula_14のグループとformula_19となる点formula_14のグループとを分ける「最大マージン超平面」を求めたい。この超平面は、超平面と各グループのもっとも近い点formula_6との距離が最大になるように定義される。
超平面は下記を満たす点formula_22の集合として記述できる。
ここで、formula_24は超平面への法線ベクトルである。ヘッセ正規形とよく似ているが、formula_24は単位ベクトルとは限らない。原点から超平面までの法線ベクトルに沿った距離は、formula_26で求められる。
ハードマージン.
学習データが線形分離可能であるとき、なるべくその距離が大きくなるように、2つのクラスのデータを分離するような、2つの平行な超平面を選択することができる。2つの超平面の間はマージン、2つの超平面の中間に位置する超平面は最大マージン超平面と呼ばれる。
正規化ないし標準化されたデータセットでは、これらの超平面は次の式で表される。
と
この2つの超平面の間の距離は、幾何学的には、の公式を用いて、formula_29となる。だから、超平面の間の距離を最大化するためには、formula_30 を最小化したい。
点がマージンに入らず、正しい側にいるための制約条件は、全てのformula_31に対し、以下の式が成立することである。
つまり、全てformula_31に対し、次のようになる。
以上をまとめると、次の最適化問題が得られる。
これを解いて得られるformula_24とformula_39を用いて、分類器formula_40を決定することができる。ここで、formula_41は符号関数である。
この幾何学的記述から、最大マージン超平面は、それと最も近い位置にあるformula_6によって定まるという重要な帰結が得られる。formula_6をサポートベクターと呼ぶ。
ソフトマージン.
SVMを拡張して線形分離可能ではないデータを扱えるようにするためには、関数が有用である。
ここで、formula_5はformula_31番目のターゲット（すなわち、1または−1）であり、formula_47はformula_31番目の出力である。
この関数の値は、(1) の制約が満たされている場合、つまり、formula_6がマージンの正しい側にある場合にはゼロとなる。マージンの反対側にあるデータに対しては、関数の値はマージンからの距離に比例する。
最適化の目的は、以下を最小化することである。
パラメータformula_51は、マージンサイズを大きくすることと、formula_6がマージンの正しい側にあることとのトレードオフを決定する。formula_51が充分に小さいとき、損失関数の第2項は無視可能になり、ハードマージンSVMと同様の振る舞いをする。
線形分離不可能な問題への適用.
1963年に、Alexey Ya. Chervonenkis が発表した初期のサポートベクターマシンは、線形分類器にしか適用できなかった。しかし、の理論を取り入れたを用いてパターンを有限もしくは無限次元のへ写像し、特徴空間上で線形分離を行う手法が 1992年にBernhard E. Boser、Isabelle M. Guyon、らによって提案された。これにより、非線形分類問題にも優れた性能を発揮することがわかり、近年特に注目を集めている。
なお、カーネル関数を取り入れた一連の手法では、どのような写像が行われるか知らずに計算できることから、カーネルトリック (Kernel Trick) と呼ばれている。
主に下記のカーネル関数がよく使われていてLIBSVMでも実装されている。
SVM分類器の計算.
ソフトマージンSVM分類器の計算は、次のような式を最小化することになる
線形分離可能な入力データに対して、formula_51の値を充分に小さく取るとハードマージン分類器が得られる。以下に詳述する古典的なアプローチは、(2) を 二次計画法問題に帰着するものである。
主形式.
(2) の最小化問題は、微分可能な目的関数を持つ制約付き最適化問題に書き換えることができる。
formula_56のそれぞれに対して変数formula_57を定義する。なお、formula_58は formula_59を満たす最小の非負の数である。
したがって、最適化問題を次のように書き換えることができる。
双対形式.
次のような双対形式に帰着することができる。
双対形式の最大化問題は、線形制約を前提としたformula_64の二次関数であり、二次計画法のアルゴリズムで効率的に解くことができる。
ここで、formula_64は次のように定義される。
さらに、formula_67が正しい側にあるときはformula_68であり、formula_67がマージン境界にあるときはformula_70である。このことから、formula_24はサポートベクターの線形結合として書くことができる。
オフセットformula_39は、マージン境界上にformula_6を見つけ、次の式を解くことで復元することができる。
ここで、formula_75なのでformula_76となることを利用した。
構造化SVM.
2005年にIoannis Tsochantaridisらがを発表した。任意のデータ構造を扱えるように拡張したものである。
通常の二値分類SVMは以下の値で分類する。
これは、このようにも書ける。
その上で、これを二値から一般の値に拡張する。formula_79 は入出力から特徴量を作り出す実数ベクトルを返す関数。問題ごとに定義する。
そして、下記の損失関数を最小化するように、最適化問題を解く。ここではL2正則化を付けている。formula_81は正則化の強さを表す定数。
formula_82は出力の類似度を表す実数を返す関数。問題ごとに定義する。formula_83であり、異なる値同士なら0よりも大きくなるように設計する。
上記の最適化問題を解くには工夫が必要であり、その後も提案が続いているが、2005年に提案された方法は下記のように上界となる関数formula_85を作る。
その上で、下記の最適化問題を解く。
formula_85 の作り方として2通りが提案された。