構造化SVM
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/06/05 23:41 UTC 版)
「サポートベクターマシン」の記事における「構造化SVM」の解説
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正則化を付けている。 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通りが提案された。 マージンリスケーリング L i ( w ) = sup y ∈ Y Δ ( y i , y ) + ⟨ w , Ψ ( x i , y ) ⟩ − ⟨ w , Ψ ( x i , y i ) ⟩ {\displaystyle L_{i}(w)=\sup _{y\in {\mathcal {Y}}}\Delta (y_{i},y)+\langle w,\Psi (x_{i},y)\rangle -\langle w,\Psi (x_{i},y_{i})\rangle } スラックリスケーリング L i ( w ) = sup y ∈ Y Δ ( y i , y ) ( 1 + ⟨ w , Ψ ( x i , y ) ⟩ − ⟨ w , Ψ ( x i , y i ) ⟩ ) {\displaystyle L_{i}(w)=\sup _{y\in {\mathcal {Y}}}\Delta (y_{i},y)\left(1+\langle w,\Psi (x_{i},y)\rangle -\langle w,\Psi (x_{i},y_{i})\rangle \right)}
※この「構造化SVM」の解説は、「サポートベクターマシン」の解説の一部です。
「構造化SVM」を含む「サポートベクターマシン」の記事については、「サポートベクターマシン」の概要を参照ください。
- 構造化SVMのページへのリンク