双対形式
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/05 23:41 UTC 版)
「サポートベクターマシン」の記事における「双対形式」の解説
次のような双対形式に帰着することができる。 maximize f ( c 1 … c n ) = ∑ i = 1 n c i − 1 2 ∑ i = 1 n ∑ j = 1 n y i c i ( x i T x j ) y j c j , {\displaystyle {\text{maximize}}\,\,f(c_{1}\ldots c_{n})=\sum _{i=1}^{n}c_{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}c_{i}(\mathbf {x} _{i}^{T}\mathbf {x} _{j})y_{j}c_{j},} subject to ∑ i = 1 n c i y i = 0 , and 0 ≤ c i ≤ 1 2 n λ for all i . {\displaystyle {\text{subject to }}\sum _{i=1}^{n}c_{i}y_{i}=0,\,{\text{and }}0\leq c_{i}\leq {\frac {1}{2n\lambda }}\;{\text{for all }}i.} 双対形式の最大化問題は、線形制約を前提とした c i {\displaystyle c_{i}} の二次関数であり、二次計画法のアルゴリズムで効率的に解くことができる。 ここで、 c i {\displaystyle c_{i}} は次のように定義される。 w = ∑ i = 1 n c i y i x i {\displaystyle \mathbf {w} =\sum _{i=1}^{n}c_{i}y_{i}\mathbf {x} _{i}} . さらに、 x i {\displaystyle \mathbf {x} _{i}} が正しい側にあるときは c i = 0 {\displaystyle c_{i}=0} であり、 x i {\displaystyle \mathbf {x} _{i}} がマージン境界にあるときは 0 < c i < ( 2 n λ ) − 1 {\displaystyle 0<c_{i}<(2n\lambda )^{-1}} である。このことから、 w {\displaystyle \mathbf {w} } はサポートベクターの線形結合として書くことができる。 オフセット b {\displaystyle b} は、マージン境界上に x i {\displaystyle \mathbf {x} _{i}} を見つけ、次の式を解くことで復元することができる。 y i ( w T x i − b ) = 1 ⟺ b = w T x i − y i . {\displaystyle y_{i}(\mathbf {w} ^{T}\mathbf {x} _{i}-b)=1\iff b=\mathbf {w} ^{T}\mathbf {x} _{i}-y_{i}.} ここで、 y i = ± 1 {\displaystyle y_{i}=\pm 1} なので y i − 1 = y i {\displaystyle y_{i}^{-1}=y_{i}} となることを利用した。
※この「双対形式」の解説は、「サポートベクターマシン」の解説の一部です。
「双対形式」を含む「サポートベクターマシン」の記事については、「サポートベクターマシン」の概要を参照ください。
- 双対形式のページへのリンク
