サポートベクターマシン

提供: testwiki
ナビゲーションに移動 検索に移動

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

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

基本的な考え方

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

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

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

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

概念的特長

次のような学習データ集合𝒟が与えられた場合を考える。

𝒟={(𝒙i,yi)∣𝒙i∈ℝp,yi∈{−1,1}}i=1n

yiは1もしくは−1の値を持つ変数で𝒙iが属したクラスを意味する。𝒙iはp次元の特徴ベクトルである。

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

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

線形 SVM

2クラスのサンプルで学習したSVMの最大マージン超平面とマージン。マージン上のサンプルはサポートベクターと呼ばれる。

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

(𝒙1,y1),…,(𝒙n,yn),

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

超平面は下記を満たす点𝒙の集合として記述できる。

𝒘T𝒙−b=0,

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

ハードマージン

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

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

𝒘T𝒙−b=1（この境界以上の点は、全てラベル1）

と

𝒘T𝒙−b=−1（この境界以下の点は、全てラベル−1）

この2つの超平面の間の距離は、幾何学的には、テンプレート:仮リンクの公式を用いて、2/‖𝒘‖となる[2]。だから、超平面の間の距離を最大化するためには、‖𝒘‖ を最小化したい。

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

{𝒘T𝒙i−b≥1ifyi=1𝒘T𝒙i−b≤−1ifyi=−1

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

yi(𝒘T𝒙i−b)≥1⋯⋯(1)

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

"Minimize ‖𝒘‖ subject to yi(𝒘T𝒙i−b)≥1 for i=1,…,n."

これを解いて得られる𝒘とbを用いて、分類器𝒙↦sgn⁡(𝒘T𝒙−b)を決定することができる。ここで、sgn⁡(⋅)は符号関数である。

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

ソフトマージン

SVMを拡張して線形分離可能ではないデータを扱えるようにするためには、テンプレート:仮リンク関数が有用である。

max⁡(0,1−yi(𝒘T𝒙i−b)).

ここで、yiはi番目のターゲット（すなわち、1または−1）であり、𝒘T𝒙i−bはi番目の出力である。

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

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

[1n∑i=1nmax⁡(0,1−yi(𝒘T𝒙i−b))]+λ‖𝒘‖2,

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

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

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

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

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

SVM分類器の計算

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

[1n∑i=1nmax⁡(0,1−yi(𝒘T𝒙i−b))]+λ‖𝒘‖2⋯⋯(2)

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

主形式

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

i∈{1,…,n}のそれぞれに対して変数ζi=max⁡(0,1−yi(𝒘T𝒙i−b))を定義する。なお、ζiは yi(𝒘T𝒙i−b)≥1−ζiを満たす最小の非負の数である。

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

minimize 1n∑i=1nζi+λ‖𝒘‖2
subject to yi(𝒘T𝒙i−b)≥1−ζi and ζi≥0,for all i.

双対形式

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

maximizef(c1…cn)=∑i=1nci−12∑i=1n∑j=1nyici(𝒙iT𝒙j)yjcj,
subject to ∑i=1nciyi=0,and 0≤ci≤12nλfor all i.

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

ここで、ciは次のように定義される。

𝒘=∑i=1nciyi𝒙i.

さらに、𝒙iが正しい側にあるときはci=0であり、𝒙iがマージン境界にあるときは0<ci<(2nλ)−1である。このことから、𝒘はサポートベクターの線形結合として書くことができる。

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

yi(𝒘T𝒙i−b)=1⟺b=𝒘T𝒙i−yi.

ここで、yi=±1なのでyi−1=yiとなることを利用した。

構造化SVM

2005年にIoannis Tsochantaridisらがテンプレート:仮リンクを発表した[3]。任意のデータ構造を扱えるように拡張したものである。

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

y^(x;w)=sign⟨w,x⟩

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

y^(x;w)=argmaxy∈{−1,1} ⟨w,yx⟩

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

y^(x;w)=argmaxy∈𝒴 ⟨w,Ψ(x,y)⟩

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

E(w)=‖w‖2+C∑i=1nΔ(yi,y^(xi;w))

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

Δ(yi,y^(xi;w))≤Li(w)

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

E(w)=‖w‖2+C∑i=1nLi(w)

Li(w) の作り方として2通りが提案された。

マージンリスケーリング
Li(w)=supy∈𝒴Δ(yi,y)+⟨w,Ψ(xi,y)⟩−⟨w,Ψ(xi,yi)⟩
スラックリスケーリング
Li(w)=supy∈𝒴Δ(yi,y)(1+⟨w,Ψ(xi,y)⟩−⟨w,Ψ(xi,yi)⟩)

参照

テンプレート: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日).

関連項目

テンプレート:統計学 テンプレート:Tech-stub

テンプレート:Normdaten

  1. ↑ V. Vapnik and A. Lerner. Pattern recognition using generalized portrait method. Automation and Remote Control, 24, 1963.
  2. ↑ テンプレート:Cite web
  3. ↑ テンプレート:Cite journal
「https://ja.wiki.beta.math.wmflabs.org/w/index.php?title=サポートベクターマシン&oldid=1363」から取得