サポートベクターマシンのソースを表示

{{Machine learning bar}}
'''サポートベクターマシン'''（{{lang-en-short|support-vector machine}}, '''SVM'''）は、[[教師あり学習]]を用いる[[パターン認識]]モデルの1つである。[[分類 (統計学)|分類]]や[[回帰分析|回帰]]へ適用できる。[[1963年]]に[[ウラジーミル・ヴァプニク]]とAlexey Ya. Chervonenkisが線形サポートベクターマシンを発表し<ref>V. Vapnik and A. Lerner. Pattern recognition using generalized portrait method. Automation and Remote Control, 24, 1963.</ref>、[[1992年]]にBernhard E. Boser、Isabelle M. Guyon、ヴァプニクが非線形へと拡張した。

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

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

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

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

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

==概念的特長==
次のような学習データ集合<math>\mathcal{D}</math>が与えられた場合を考える。
:<math>\mathcal{D} = \{ (\boldsymbol{x}_i, y_i) \mid \boldsymbol{x}_{i}\in\mathbb{R}^p,\, y_{i}\in\{-1,1\} \}_{i=1}^n</math>
<math>y_i</math>は1もしくは−1の値を持つ変数で<math>\boldsymbol{x}_i</math>が属したクラスを意味する。<math>\boldsymbol{x}_i</math>は<math>p</math>次元の特徴ベクトルである。
[[Image:Svm_separating_hyperplanes.png|thumb|right|H3は2つのクラスのいくつかの点を正しく分類していない。H1とH2は2つのクラスのいくつかの点を分類するのに、H2がH1よりもっと大きいマージンを持って分類することを確認することができる。]]
[[ニューラルネットワーク]]を含む多くの学習アルゴリズムは、このような学習データが与えられた時<math>y_i=1</math>であるいくつかの点と<math>y_i=-1</math>であるいくつかの点とを分離する超平面をさがすのが共通の目標である。SVMが他のアルゴリズムと差別化される特徴は、ただいくつかの点を分離する超平面を捜すことで終わるのではなく、いくつかの点を分離することができる幾多の候補平面の中でマージンが最大になる超平面 (maximum-margin hyperplane) を探す点にある。ここでマージンとは、超平面から各いくつかの点に至る距離の最小値を言い、このマージンを最大にしながらいくつかの点を2つのクラスで分類しようとすると、結局クラス1に属するいくつかの点との距離の中の最小値とクラス−1に属するいくつかの点との距離の中の最小値とが等しくなるように超平面が位置しなければならず、このような超平面をマージン最大の超平面という。結論として、SVMは2つのクラスに属しているいくつかの点を分類する幾多の超平面の中で、最大限に2つのクラスのいくつかの点と距離を維持するものを探すアルゴリズムといえる。

== 線形 SVM ==
[[File:SVM margin.png|thumb|2クラスのサンプルで学習したSVMの最大マージン超平面とマージン。マージン上のサンプルはサポートベクターと呼ばれる。|alt=|300x300px]]

以下のような形式の <math>n</math> 個のトレーニング・データセットが与えられる。

:<math> (\boldsymbol{x}_1, y_1), \ldots, (\boldsymbol{x}_n, y_n),</math>

<math>y_i</math>は1または−1であり、それぞれ、点<math>\boldsymbol{x}_i </math>が属するクラスを示す。<math>\boldsymbol{x}_i</math>は<math>p</math>-次元の実数ベクトルである。<math>y_i = 1</math>となる点<math>\boldsymbol{x}_i </math>のグループと<math>y_i = -1</math>となる点<math>\boldsymbol{x}_i </math>のグループとを分ける「最大マージン超平面」を求めたい。この超平面は、超平面と各グループのもっとも近い点<math>\boldsymbol{x}_i</math>との距離が最大になるように定義される。

超平面は下記を満たす点<math>\boldsymbol{x}</math>の集合として記述できる。

:<math>\boldsymbol{w}^T \boldsymbol{x} - b = 0,</math>

ここで、<math>\boldsymbol{w}</math>は超平面への法線ベクトルである。ヘッセ正規形とよく似ているが、<math>\boldsymbol{w}</math>は単位ベクトルとは限らない。原点から超平面までの法線ベクトルに沿った距離は、<math>b/\|\boldsymbol{w}\|</math>で求められる。

=== ハードマージン ===
学習データが[[線形分離可能]]であるとき、なるべくその距離が大きくなるように、2つのクラスのデータを分離するような、2つの平行な超平面を選択することができる。2つの超平面の間はマージン、2つの超平面の中間に位置する超平面は最大マージン超平面と呼ばれる。

正規化ないし標準化されたデータセットでは、これらの超平面は次の式で表される。

: <math>\boldsymbol{w}^T \boldsymbol{x} - b = 1</math>（この境界以上の点は、全てラベル1）
と
: <math>\boldsymbol{w}^T \boldsymbol{x} - b = -1</math>（この境界以下の点は、全てラベル−1）

この2つの超平面の間の距離は、幾何学的には、{{仮リンク|点と平面の距離|en|distance from a point to a plane}}の公式を用いて、<math>2/\|\boldsymbol{w}\|</math>となる<ref>{{cite web |url=https://math.stackexchange.com/q/1305925/168764 |title=Why is the SVM margin equal to <math>\frac{2}{\|\boldsymbol{w}\|}</math> |author= |accessdate=20150530 |website=Mathematics Stack Exchange}}</ref>。だから、超平面の間の距離を最大化するためには、<math>\|\boldsymbol{w}\|</math> を最小化したい。

点がマージンに入らず、正しい側にいるための制約条件は、全ての<math>i</math>に対し、以下の式が成立することである。

:<math>
\begin{cases}
\boldsymbol{w}^T \boldsymbol{x}_i - b \ge 1 & \text{if} \quad y_i = 1 \\
\boldsymbol{w}^T \boldsymbol{x}_i - b \le -1 & \text{if} \quad y_i = -1
\end{cases}
</math>

つまり、全て<math>i</math>に対し、次のようになる。

: <math>y_i(\boldsymbol{w}^T \boldsymbol{x}_i - b) \ge 1 \qquad\cdots\cdots\,(1)</math>

以上をまとめると、次の最適化問題が得られる。

: "Minimize <math>\|\boldsymbol{w}\|</math> subject to <math>y_i(\boldsymbol{w}^T \boldsymbol{x}_i - b) \ge 1</math> for <math>i = 1, \ldots, n</math>."

これを解いて得られる<math>\boldsymbol{w}</math>と<math>b</math>を用いて、分類器<math>\boldsymbol{x} \mapsto \sgn(\boldsymbol{w}^T \boldsymbol{x} - b)</math>を決定することができる。ここで、<math>\sgn(\cdot)</math>は[[符号関数]]である。

この幾何学的記述から、最大マージン超平面は、それと最も近い位置にある<math>\boldsymbol{x}_i</math>によって定まるという重要な帰結が得られる。<math>\boldsymbol{x}_i</math>をサポートベクターと呼ぶ。

=== ソフトマージン ===
SVMを拡張して線形分離可能ではないデータを扱えるようにするためには、{{仮リンク|ヒンジ損失|en|Hinge loss}}関数が有用である。

: <math>\max\left(0, 1 - y_i(\boldsymbol{w}^T \boldsymbol{x}_i - b)\right).</math>

ここで、<math>y_i</math>は<math>i</math>番目のターゲット（すなわち、1または−1）であり、<math>\boldsymbol{w}^T \boldsymbol{x}_i - b</math>は<math>i</math>番目の出力である。

この関数の値は、(1) の制約が満たされている場合、つまり、<math>\boldsymbol{x}_i</math>がマージンの正しい側にある場合にはゼロとなる。マージンの反対側にあるデータに対しては、関数の値はマージンからの距離に比例する。

最適化の目的は、以下を最小化することである。

: <math>\left[\frac 1 n \sum_{i=1}^n \max\left(0, 1 - y_i(\boldsymbol{w}^T \boldsymbol{x}_i - b)\right) \right] + \lambda\lVert \boldsymbol{w} \rVert^2,</math>

パラメータ<math>\lambda</math>は、マージンサイズを大きくすることと、<math>\boldsymbol{x}_i</math>がマージンの正しい側にあることとのトレードオフを決定する。<math>\lambda</math>が充分に小さいとき、損失関数の第2項は無視可能になり、ハードマージンSVMと同様の振る舞いをする。

== 線形分離不可能な問題への適用 ==
1963年にウラジーミル・ヴァプニク、Alexey Ya. Chervonenkis が発表した初期のサポートベクターマシンは、[[線形分類器]]にしか適用できなかった。しかし、[[再生核ヒルベルト空間]]の理論を取り入れた{{仮リンク|カーネル関数|en|Positive-definite kernel|redirect=1}}を用いてパターンを有限もしくは無限次元の{{仮リンク|特徴空間|en|Feature space}}へ写像し、特徴空間上で線形分離を行う手法が 1992年にBernhard E. Boser、Isabelle M. Guyon、ヴァプニクらによって提案された。これにより、[[非線形]]分類問題にも優れた性能を発揮することがわかり、近年特に注目を集めている。

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

主に下記のカーネル関数がよく使われていてLIBSVMでも実装されている。
* 線形
* [[多項式]]
* [[放射基底関数]]
* [[シグモイド関数]]

== SVM分類器の計算 ==
ソフトマージンSVM分類器の計算は、次のような式を最小化することになる

: <math>\left[\frac 1 n \sum_{i=1}^n \max\left(0, 1 - y_i(\boldsymbol{w}^T \boldsymbol{x}_i - b)\right) \right] + \lambda \|\boldsymbol{w}\|^2 \qquad\cdots\cdots\,(2)</math>

線形分離可能な入力データに対して、<math>\lambda</math>の値を充分に小さく取るとハードマージン分類器が得られる。以下に詳述する古典的なアプローチは、(2) を [[二次計画法]]問題に帰着するものである。

=== 主形式 ===
(2) の最小化問題は、微分可能な目的関数を持つ制約付き最適化問題に書き換えることができる。

<math>i \in \{1,\,\ldots,\,n\}</math>のそれぞれに対して変数<math> \zeta_i = \max\left(0, 1 - y_i(\boldsymbol{w}^T \boldsymbol{x}_i - b)\right)</math>を定義する。なお、<math> \zeta_i</math>は <math> y_i(\boldsymbol{w}^T \boldsymbol{x}_i - b) \geq 1 - \zeta_i</math>を満たす最小の非負の数である。

したがって、最適化問題を次のように書き換えることができる。

: <math> \text{minimize } \frac 1 n \sum_{i=1}^n \zeta_i + \lambda \|\boldsymbol{w}\|^2 </math>
: <math> \text{subject to } y_i(\boldsymbol{w}^T \boldsymbol{x}_i - b) \geq 1 - \zeta_i \, \text{ and } \, \zeta_i \geq 0,\, \text{for all } i.</math>

=== 双対形式 ===
次のような双対形式に帰着することができる。

: <math> \text{maximize}\,\, f(c_1 \ldots c_n) =  \sum_{i=1}^n c_i - \frac 1 2 \sum_{i=1}^n\sum_{j=1}^n y_ic_i(\boldsymbol{x}_i^T \boldsymbol{x}_j)y_jc_j,</math>
: <math> \text{subject to } \sum_{i=1}^n c_iy_i = 0,\,\text{and } 0 \leq c_i \leq \frac{1}{2n\lambda}\;\text{for all }i.</math>

双対形式の最大化問題は、線形制約を前提とした<math> c_i</math>の二次関数であり、[[二次計画法]]のアルゴリズムで効率的に解くことができる。

ここで、<math> c_i</math>は次のように定義される。

: <math> \boldsymbol{w} = \sum_{i=1}^n c_iy_i \boldsymbol{x}_i</math>.

さらに、<math> \boldsymbol{x}_i</math>が正しい側にあるときは<math> c_i = 0</math>であり、<math> \boldsymbol{x}_i</math>がマージン境界にあるときは<math> 0 < c_i <(2n\lambda)^{-1}</math>である。このことから、<math>\boldsymbol{w}</math>はサポートベクターの線形結合として書くことができる。

オフセット<math>b</math>は、マージン境界上に<math>\boldsymbol{x}_i</math>を見つけ、次の式を解くことで復元することができる。

: <math> y_i(\boldsymbol{w}^T \boldsymbol{x}_i - b) = 1 \iff b = \boldsymbol{w}^T \boldsymbol{x}_i - y_i .</math>

ここで、<math>y_i = \pm 1</math>なので<math>y_i ^ {-1} = y_i</math>となることを利用した。

== 構造化SVM ==
[[2005年]]にIoannis Tsochantaridisらが{{仮リンク|構造化SVM|en|Structured support vector machine}}を発表した<ref>{{cite journal
 |title=Large Margin Methods for Structured and Interdependent Output Variables
 |author=Ioannis Tsochantaridis
 |author2=Thorsten Joachims
 |author3=Thomas Hofmann
 |author4=Yasemin Altun
 |url=http://www.jmlr.org/papers/volume6/tsochantaridis05a/tsochantaridis05a.pdf
 |year=2005
 |journal=The Journal of Machine Learning Research
 |volume=6
 |issue=9
 |pages=1453-1484
}}</ref>。任意のデータ構造を扱えるように拡張したものである。

通常の二値分類SVMは以下の値で分類する。
: <math>\hat{y}(x; w) = \text{sign} \langle w, x \rangle</math>
これは、このようにも書ける。
: <math>\hat{y}(x; w) = \underset{y \in \{-1, 1\}}{\operatorname{arg\,max}}\ \langle w, y x \rangle</math>
その上で、これを二値から一般の値に拡張する。<math>\Psi</math> は入出力から特徴量を作り出す実数ベクトルを返す関数。問題ごとに定義する。
: <math>\hat{y}(x; w) = \underset{y \in \mathcal{Y}}{\operatorname{arg\,max}}\ \langle w, \Psi(x, y) \rangle</math>
そして、下記の損失関数を最小化するように、[[最適化問題]]を解く。ここではL2[[正則化]]を付けている。<math>C</math>は正則化の強さを表す定数。
<math>\Delta</math>は出力の類似度を表す実数を返す関数。問題ごとに定義する。<math>\Delta(y, y) = 0</math>であり、異なる値同士なら0よりも大きくなるように設計する。
: <math>E(w) = \| w \|^2 + C \sum_{i = 1}^n \Delta(y_i, \hat{y}(x_i; w))</math>
上記の最適化問題を解くには工夫が必要であり、その後も提案が続いているが、2005年に提案された方法は下記のように上界となる関数<math>L_i(w)</math>を作る。
: <math>\Delta(y_i, \hat{y}(x_i; w)) \le L_i(w)</math>
その上で、下記の最適化問題を解く。
: <math>E(w) = \| w \|^2 + C \sum_{i = 1}^n L_i(w)</math>
<math>L_i(w)</math> の作り方として2通りが提案された。
; マージンリスケーリング
: <math>L_i(w) = \sup_{y \in \mathcal{Y}} \Delta(y_i, y) + \langle w, \Psi(x_i, y) \rangle - \langle w, \Psi(x_i, y_i) \rangle</math>
; スラックリスケーリング
: <math>L_i(w) = \sup_{y \in \mathcal{Y}} \Delta(y_i, y) \left( 1 + \langle w, \Psi(x_i, y) \rangle - \langle w, \Psi(x_i, y_i) \rangle \right)</math>

== 参照 ==
{{reflist}}

== 教科書 ==
* 阿部重夫：「パターン認識のためのサポートベクトルマシン入門」、森北出版、ISBN 978-4-627-84921-1 (2011年4月).
* 竹内一郎、鳥山昌幸：「サポートベクトルマシン」、講談社サイエンティフィク、ISBN 978-4-06-152906-9 (2015年8月7日).
* 田村孝廣：「やさしく学べる　サポートベクトルマシン：数学の基礎とPythonによる実践」、オーム社、ISBN 978-4-274-22967-1 (2022年11月30日).

== 関連項目 ==
*[[カーネル法]]
*[[逐次最小問題最適化法]] (SMO)
*[[人工知能]]
*[[パターン認識]]
*[[放射基底関数]]
*[[線形分類器]]
*実装
**[[LIBSVM]]（一般）、LIBLINEAR（線形）
**[[scikit-learn]]（LIBSVM、LIBLINEARのPythonラッパーを含む）

{{統計学}}
{{Tech-stub}}

{{Normdaten}}
{{DEFAULTSORT:さほおとへくたあましん}}
[[Category:サポートベクターマシン|*]]
[[Category:分類アルゴリズム]]
[[Category:教師あり学習]]
[[Category:機械学習]]
[[Category:人工知能]]