サポートベクターマシン

機械学習および データマイニング
問題 分類 クラスタリング 回帰 異常検知 相関ルール（英語版） 強化学習 構造化予測（英語版） 特徴量設計（英語版） 表現学習（英語版） オンライン学習（英語版） 半教師あり学習（英語版） 教師なし学習 ランキング学習（英語版） 文法獲得（英語版）
教師あり学習（分類 • 回帰） 決定木（英語版） アンサンブル （バギング、ブースティング、 ランダムフォレスト） k-NN 線形回帰 単純ベイズ ニューラルネットワーク ロジスティック回帰 パーセプトロン 関連ベクトルマシン (RVM)（英語版） サポートベクトルマシン (SVM)
クラスタリング BIRCH（英語版） 階層的（英語版） k平均法 期待値最大化法 (EM) DBSCAN OPTICS（英語版） 平均値シフト（英語版）
次元削減 因子分析 CCA ICA LDA（英語版） NMF（英語版） PCA t-SNE
構造化予測（英語版） グラフィカルモデル ベイジアンネットワーク CRF HMM
異常検知 k-NN 局所外れ値因子法
ニューラルネットワーク オートエンコーダ ディープラーニング DeepDream 多層パーセプトロン RNN LSTM GRU 制約ボルツマンマシン（英語版） SOM CNN U-Net
強化学習 TD学習 Q学習 SARSA
理論 偏りと分散のトレードオフ 計算論的学習理論（英語版） 経験損失最小化（英語版） オッカム学習（英語版） PAC学習 統計的学習（英語版） VC理論（英語版）
学会・論文誌等 NIPS（英語版） ICML（英語版） ML（英語版） JMLR（英語版） ArXiv:cs.LG
全般 統計学および機械学習の評価指標
Category:機械学習 Category:データマイニング
表 話 編 歴

サポートベクターマシン（英: support-vector machine, SVM）は、教師あり学習を用いるパターン認識モデルの1つである。分類や回帰へ適用できる。1963年にウラジミール・ヴァプニク（英語版）とAlexey Ya. Chervonenkisが線形サポートベクターマシンを発表し^[1]、1992年にBernhard E. Boser、Isabelle M. Guyon、ウラジミール・ヴァプニクが非線形へと拡張した。

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

基本的な考え方[編集]

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

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

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

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

概念的特長[編集]

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

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

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

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

線形 SVM[編集]

以下のような形式の ${\displaystyle n}$ 個のトレーニング・データセットが与えられる。

${\displaystyle ({\boldsymbol {x}}_{1},y_{1}),\ldots ,({\boldsymbol {x}}_{n},y_{n}),}$

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

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

${\displaystyle {\boldsymbol {w}}^{T}{\boldsymbol {x}}-b=0,}$

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

ハードマージン[編集]

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

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

${\displaystyle {\boldsymbol {w}}^{T}{\boldsymbol {x}}-b=1}$（この境界以上の点は、全てラベル1）

と

${\displaystyle {\boldsymbol {w}}^{T}{\boldsymbol {x}}-b=-1}$（この境界以下の点は、全てラベル−1）

この2つの超平面の間の距離は、幾何学的には、点と平面の距離（英語版）の公式を用いて、${\displaystyle 2/\|{\boldsymbol {w}}\|}$となる^[2]。だから、超平面の間の距離を最大化するためには、${\displaystyle \|{\boldsymbol {w}}\|}$ を最小化したい。

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

${\displaystyle {\begin{cases}{\boldsymbol {w}}^{T}{\boldsymbol {x}}_{i}-b\geq 1&{\text{if}}\quad y_{i}=1\\{\boldsymbol {w}}^{T}{\boldsymbol {x}}_{i}-b\leq -1&{\text{if}}\quad y_{i}=-1\end{cases}}}$

つまり、全て${\displaystyle i}$に対し、次のようになる。

${\displaystyle y_{i}({\boldsymbol {w}}^{T}{\boldsymbol {x}}_{i}-b)\geq 1\qquad \cdots \cdots \,(1)}$

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

"Minimize ${\displaystyle \|{\boldsymbol {w}}\|}$ subject to ${\displaystyle y_{i}({\boldsymbol {w}}^{T}{\boldsymbol {x}}_{i}-b)\geq 1}$ for ${\displaystyle i=1,\ldots ,n}$."

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

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

ソフトマージン[編集]

SVMを拡張して線形分離可能ではないデータを扱えるようにするためには、ヒンジ損失（英語版）関数が有用である。

${\displaystyle \max \left(0,1-y_{i}({\boldsymbol {w}}^{T}{\boldsymbol {x}}_{i}-b)\right).}$

ここで、${\displaystyle y_{i}}$は${\displaystyle i}$番目のターゲット（すなわち、1または−1）であり、${\displaystyle {\boldsymbol {w}}^{T}{\boldsymbol {x}}_{i}-b}$は${\displaystyle i}$番目の出力である。

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

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

${\displaystyle \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},}$

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

線形分離不可能な問題への適用[編集]

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

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

主に下記のカーネル関数がよく使われていてLIBSVMでも実装されている。

• 線形
• 多項式
• 放射基底関数
• シグモイド関数

SVM分類器の計算[編集]

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

${\displaystyle \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)}$

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

主形式[編集]

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

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

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

${\displaystyle {\text{minimize }}{\frac {1}{n}}\sum _{i=1}^{n}\zeta _{i}+\lambda \|{\boldsymbol {w}}\|^{2}}$

${\displaystyle {\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.}$

双対形式[編集]

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

${\displaystyle {\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_{i}c_{i}({\boldsymbol {x}}_{i}^{T}{\boldsymbol {x}}_{j})y_{j}c_{j},}$

${\displaystyle {\text{subject to }}\sum _{i=1}^{n}c_{i}y_{i}=0,\,{\text{and }}0\leq c_{i}\leq {\frac {1}{2n\lambda }}\;{\text{for all }}i.}$

双対形式の最大化問題は、線形制約を前提とした${\displaystyle c_{i}}$の二次関数であり、二次計画法のアルゴリズムで効率的に解くことができる。

ここで、${\displaystyle c_{i}}$は次のように定義される。

${\displaystyle {\boldsymbol {w}}=\sum _{i=1}^{n}c_{i}y_{i}{\boldsymbol {x}}_{i}}$.

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

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

${\displaystyle y_{i}({\boldsymbol {w}}^{T}{\boldsymbol {x}}_{i}-b)=1\iff b={\boldsymbol {w}}^{T}{\boldsymbol {x}}_{i}-y_{i}.}$

ここで、${\displaystyle y_{i}=\pm 1}$なので${\displaystyle y_{i}^{-1}=y_{i}}$となることを利用した。

構造化SVM[編集]

2005年にIoannis Tsochantaridisらが構造化SVM（英語版）を発表した^[3]。任意のデータ構造を扱えるように拡張したものである。

通常の二値分類SVMは以下の値で分類する。

${\displaystyle {\hat {y}}(x;w)={\text{sign}}\langle w,x\rangle }$

これは、このようにも書ける。

${\displaystyle {\hat {y}}(x;w)={\underset {y\in \{-1,1\}}{\operatorname {arg\,max} }}\ \langle w,yx\rangle }$

その上で、これを二値から一般の値に拡張する。${\displaystyle \Psi }$ は入出力から特徴量を作り出す実数ベクトルを返す関数。問題ごとに定義する。

${\displaystyle {\hat {y}}(x;w)={\underset {y\in {\mathcal {Y}}}{\operatorname {arg\,max} }}\ \langle w,\Psi (x,y)\rangle }$

そして、下記の損失関数を最小化するように、最適化問題を解く。ここではL2正則化を付けている。${\displaystyle C}$は正則化の強さを表す定数。 ${\displaystyle \Delta }$は出力の類似度を表す実数を返す関数。問題ごとに定義する。${\displaystyle \Delta (y,y)=0}$であり、異なる値同士なら0よりも大きくなるように設計する。

${\displaystyle E(w)=\|w\|^{2}+C\sum _{i=1}^{n}\Delta (y_{i},{\hat {y}}(x_{i};w))}$

上記の最適化問題を解くには工夫が必要であり、その後も提案が続いているが、2005年に提案された方法は下記のように上界となる関数${\displaystyle L_{i}(w)}$を作る。

${\displaystyle \Delta (y_{i},{\hat {y}}(x_{i};w))\leq L_{i}(w)}$

その上で、下記の最適化問題を解く。

${\displaystyle E(w)=\|w\|^{2}+C\sum _{i=1}^{n}L_{i}(w)}$

${\displaystyle L_{i}(w)}$ の作り方として2通りが提案された。

マージンリスケーリング

${\displaystyle 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 }$

スラックリスケーリング

${\displaystyle 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)}$

参照[編集]

関連項目[編集]

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

表 話 編 歴 統計学
標本調査	標本 母集団 無作為抽出 層化抽出法
要約統計量	連続確率分布 位置 平均 算術 幾何 調和 中央値 分位数 順序統計量 最頻値 階級値 分散 範囲 偏差 偏差値 標準偏差 標準誤差 変動係数 決定係数 相関係数 自己相関 共分散 自己共分散 分散共分散行列 百分率 統計的ばらつき モーメント 分散 歪度 尖度 カテゴリデータ 頻度 分割表
推計統計学	仮説検定 パラメトリック t検定 ウェルチのt検定 F検定 Z検定 二項検定 ジャック-ベラ検定 シャピロ–ウィルク検定 分散分析 共分散分析 ノンパラメトリック ウィルコクソンの符号順位検定 マン・ホイットニーのU検定 カイ二乗検定 イェイツのカイ二乗検定 累積カイ二乗検定 フィッシャーの正確確率検定 尤度比検定 G検定 アンダーソン–ダーリング検定 コルモゴロフ–スミルノフ検定 カイパー検定 マンテル検定 コクラン・マンテル・ヘンツェルの統計量 その他 帰無仮説 対立仮説 有意 棄却 区間推定 信頼区間 予測区間 モデル選択基準 AIC BIC WAIC MDL その他 偏り 偏りと分散 過剰適合 推定量 点推定 最尤推定 尤度関数 尤度方程式 最小距離推定 メタアナリシス ブートストラップ法
ベイズ統計学	確率 主観確率 ベイズ確率 事前確率 事後確率 最大事後確率 その他 ベイズ推定 ベイズ因子
相関	交絡 ピアソンの積率相関係数 順位相関（スピアマンの順位相関係数 ・ケンドールの順位相関係数 ）
モデル	一般線形モデル 一般化線形モデル 混合モデル 一般化線形混合モデル
回帰	線形 リッジ回帰 ラッソ回帰 エラスティックネット 非線形 k近傍法 決定木 ランダムフォレスト ニューラルネットワーク サポートベクターマシン 射影追跡回帰 時系列 自己回帰モデル 自己回帰移動平均モデル ARCHモデル 対移動平均比率法 トレンド定常 傾向推定 共和分 構造変化
分類	線形 線形判別分析 ロジスティック回帰 <! -- 名前に回帰とついていますが確率を回帰する分類手法です --> 単純ベイズ分類器 単純パーセプトロン 線形サポートベクターマシン 二次 二次判別分析 非線形 k近傍法 決定木 ランダムフォレスト ニューラルネットワーク サポートベクターマシン ベイジアンネットワーク 隠れマルコフモデル その他 二項分類 多クラス分類 第一種過誤と第二種過誤
教師なし学習	クラスタリング k平均法 （k-means++法 ） DBSCAN 密度推定（英語版） カーネル密度推定 （ カーネル ） その他 主成分分析 独立成分分析 自己組織化写像
統計図表	棒グラフ バイプロット（英語版） 箱ひげ図 管理図 フォレストプロット ヒストグラム 円グラフ Q-Qプロット ランチャート 散布図 幹葉表示 バイオリン図 ドットプロット ヒートマップ 階級区分図
生存分析	生存関数 カプラン＝マイヤー推定量 ログランク検定 故障率 比例ハザードモデル
歴史	統計学の創始者 確率論と統計学の歩み
応用	社会統計学 疫学 生物統計学 系統学 統計力学 計量経済学 機械学習 実験計画法
出版物	統計学に関する学術誌一覧 重要な出版物
全般	統計 頻度主義統計学 統計学および機械学習の評価指標
その他	方向統計学 S言語 R言語 統計検定 社会調査士 JDLA Deep Learning For GENERAL JDLA Deep Learning for ENGINEER 実用数学技能検定 品質管理検定
カテゴリ

この項目は、工学・技術に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（Portal:技術と産業）。

• 表示
• 編集