サポートベクターマシン
以下のような形式の n {\displaystyle n} 個のトレーニング・データセットが与えられる。
( x 1 , y 1 ) , ... , ( x n , y n ) , {\displaystyle ({\boldsymbol {x}}_{1},y_{1}),\ldots ,({\boldsymbol {x}}_{n},y_{n}),}
y i {\displaystyle y_{i}} は1または−1であり、それぞれ、点 x i {\displaystyle {\boldsymbol {x}}_{i}} が属するクラスを示す。 x i {\displaystyle {\boldsymbol {x}}_{i}} は p {\displaystyle p} -次元の実数ベクトルである。 y i = 1 {\displaystyle y_{i}=1} となる点 x i {\displaystyle {\boldsymbol {x}}_{i}} のグループと y i = − 1 {\displaystyle y_{i}=-1} となる点 x i {\displaystyle {\boldsymbol {x}}_{i}} のグループとを分ける「最大マージン超平面」を求めたい。
2005年にIoannis Tsochantaridisらが構造化SVM(英語版)を発表した。任意のデータ構造を扱えるように拡張したものである。
通常の二値分類SVMは以下の値で分類する。
y ^ ( x ; w ) = sign ⟨ w , x ⟩ {\displaystyle {\hat {y}}(x;w)={\text{sign}}\langle w,x\rangle }
これは、このようにも書ける。
y ^ ( x ; w ) = a r g m a x y ∈ { − 1 , 1 } ⟨ w , y x ⟩ {\displaystyle {\hat {y}}(x;w)={\underset {y\in \{-1,1\}}{\operatorname {arg\,max} }}\ \langle w,yx\rangle }
その上で、これを二値から一般の値に拡張する。 Ψ {\displaystyle \Psi } は入出力から特徴量を作り出す実数ベクトルを返す関数。問題ごとに定義する。
y ^ ( x ; w ) = a r g m a x y ∈ Y ⟨ w , Ψ ( x , y ) ⟩ {\displaystyle {\hat {y}}(x;w)={\underset {y\in {\mathcal {Y}}}{\operatorname {arg\,max} }}\ \langle w,\Psi (x,y)\rangle }
そして、下記の損失関数を最小化するように、最適化問題を解く。ここではL2正則化を付けている。