サポートベクターマシン 線形 SVM

ウィキペディア

サポートベクターマシン

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/22 06:20 UTC 版)

線形 SVM

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

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

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

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

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

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

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

ハードマージン

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

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

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

と

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

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

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

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

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

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

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

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

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

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

ソフトマージン

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

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

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

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

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

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

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