サポートベクターマシン
C {\displaystyle C} は正則化の強さを表す定数。 Δ {\displaystyle \Delta } は出力の類似度を表す実数を返す関数。問題ごとに定義する。 Δ ( y , y ) = 0 {\displaystyle \Delta (y,y)=0} であり、異なる値同士なら0よりも大きくなるように設計する。
E ( w ) = ‖ w ‖ 2 + C ∑ i = 1 n Δ ( y i , y ^ ( x i ; w ) ) {\displaystyle E(w)=\|w\|^{2}+C\sum _{i=1}^{n}\Delta (y_{i},{\hat {y}}(x_{i};w))}
上記の最適化問題を解くには工夫が必要であり、その後も提案が続いているが、2005年に提案された方法は下記のように上界となる関数 L i ( w ) {\displaystyle L_{i}(w)} を作る。
Δ ( y i , y ^ ( x i ; w ) ) ≤ L i ( w ) {\displaystyle \Delta (y_{i},{\hat {y}}(x_{i};w))\leq L_{i}(w)}
その上で、下記の最適化問題を解く。
E ( w ) = ‖ w ‖ 2 + C ∑ i = 1 n L i ( w ) {\displaystyle E(w)=\|w\|^{2}+C\sum _{i=1}^{n}L_{i}(w)}
L i ( w ) {\displaystyle L_{i}(w)} の作り方として2通りが提案された。
この超平面は、超平面と各グループのもっとも近い点 x i {\displaystyle {\boldsymbol {x}}_{i}} との距離が最大になるように定義される。
超平面は下記を満たす点 x {\displaystyle {\boldsymbol {x}}} の集合として記述できる。
w T x − b = 0 , {\displaystyle {\boldsymbol {w}}^{T}{\boldsymbol {x}}-b=0,}
ここで、 w {\displaystyle {\boldsymbol {w}}} は超平面への法線ベクトルである。ヘッセ正規形とよく似ているが、 w {\displaystyle {\boldsymbol {w}}} は単位ベクトルとは限らない。原点から超平面までの法線ベクトルに沿った距離は、 b / ‖ w ‖ {\displaystyle b/\|{\boldsymbol {w}}\|} で求められる。
最適化の目的は、以下を最小化することである。
[ 1 n ∑ i = 1 n max ( 0 , 1 − y i ( w T x i − b ) ) ] + λ ‖ w ‖ 2 , {\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 } は、マージンサイズを大きくすることと、 x i {\displaystyle {\boldsymbol {x}}_{i}} がマージンの正しい側にあることとのトレードオフを決定する。 λ {\displaystyle \lambda } が充分に小さいとき、損失関数の第2項は無視可能になり、ハードマージンSVMと同様の振る舞いをする。