サポートベクターマシン
次のような学習データ集合 D {\displaystyle {\mathcal {D}}} が与えられた場合を考える。
D = { ( x i , y i ) ∣ x i ∈ R p , y i ∈ { − 1 , 1 } } i = 1 n {\displaystyle {\mathcal {D}}=\{({\boldsymbol {x}}_{i},y_{i})\mid {\boldsymbol {x}}_{i}\in \mathbb {R} ^{p},\,y_{i}\in \{-1,1\}\}_{i=1}^{n}}
y i {\displaystyle y_{i}} は1もしくは−1の値を持つ変数で x i {\displaystyle {\boldsymbol {x}}_{i}} が属したクラスを意味する。 x i {\displaystyle {\boldsymbol {x}}_{i}} は p {\displaystyle p} 次元の特徴ベクトルである。
したがって、最適化問題を次のように書き換えることができる。
minimize 1 n ∑ i = 1 n ζ i + λ ‖ w ‖ 2 {\displaystyle {\text{minimize }}{\frac {1}{n}}\sum _{i=1}^{n}\zeta _{i}+\lambda \|{\boldsymbol {w}}\|^{2}}
subject to y i ( w T x i − b ) ≥ 1 − ζ i and ζ i ≥ 0 , for all i . {\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.}
さらに、 x i {\displaystyle {\boldsymbol {x}}_{i}} が正しい側にあるときは c i = 0 {\displaystyle c_{i}=0} であり、 x i {\displaystyle {\boldsymbol {x}}_{i}} がマージン境界にあるときは 0 < c i < ( 2 n λ ) − 1 {\displaystyle 0<c_{i}<(2n\lambda )^{-1}} である。このことから、 w {\displaystyle {\boldsymbol {w}}} はサポートベクターの線形結合として書くことができる。
オフセット b {\displaystyle b} は、マージン境界上に x i {\displaystyle {\boldsymbol {x}}_{i}} を見つけ、次の式を解くことで復元することができる。
y i ( w T x i − b ) = 1 ⟺ b = w T x i − y i . {\displaystyle y_{i}({\boldsymbol {w}}^{T}{\boldsymbol {x}}_{i}-b)=1\iff b={\boldsymbol {w}}^{T}{\boldsymbol {x}}_{i}-y_{i}.}
ここで、 y i = ± 1 {\displaystyle y_{i}=\pm 1} なので y i − 1 = y i {\displaystyle y_{i}^{-1}=y_{i}} となることを利用した。