サポートベクターマシン
ソフトマージンSVM分類器の計算は、次のような式を最小化することになる
[ 1 n ∑ i = 1 n max ( 0 , 1 − y i ( w T x i − b ) ) ] + λ ‖ w ‖ 2 ⋯ ⋯ ( 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 \|{\boldsymbol {w}}\|^{2}\qquad \cdots \cdots \,(2)}
線形分離可能な入力データに対して、 λ {\displaystyle \lambda } の値を充分に小さく取るとハードマージン分類器が得られる。以下に詳述する古典的なアプローチは、(2) を 二次計画法問題に帰着するものである。
(2) の最小化問題は、微分可能な目的関数を持つ制約付き最適化問題に書き換えることができる。
i ∈ { 1 , ... , n } {\displaystyle i\in \{1,\,\ldots ,\,n\}} のそれぞれに対して変数 ζ i = max ( 0 , 1 − y i ( w T x i − b ) ) {\displaystyle \zeta _{i}=\max \left(0,1-y_{i}({\boldsymbol {w}}^{T}{\boldsymbol {x}}_{i}-b)\right)} を定義する。なお、 ζ i {\displaystyle \zeta _{i}} は y i ( w T x i − b ) ≥ 1 − ζ i {\displaystyle y_{i}({\boldsymbol {w}}^{T}{\boldsymbol {x}}_{i}-b)\geq 1-\zeta _{i}} を満たす最小の非負の数である。