　前回の記事の続きです．前回導出した SVM の双対問題を導出します．

導入

　前回の記事では，ハードマージンSVMが解く最適化問題を求めました．

$\displaystyle{ \min _ {w \in \mathbb R ^ d, b \in \mathbb R} \frac 1 2 \| w \| _ 2 ^ 2 \quad \text{subject to} \quad y_i(w \cdot x_i + b) \geq 1, \; \forall i \in \{ 1, \ldots, m \} }$

これは $d$ 変数，制約は $m$ 個の最適化問題です．今回はこの問題の双対問題を考えてみようと思います．

双対形の導出

　まずは，ラグランジュ乗数 $\alpha \in \mathbb R ^ m _ +$ を導入してラグランジュ関数 $L( w, b ; \alpha )$ を定義します（ $w$ ， $b$ は主問題の変数， $\alpha$ は双対問題の変数なのでセミコロンで区切りました）．

$\displaystyle{ L( w, b; \alpha ) = \frac 1 2 \| w \| _ 2 ^ 2 + \sum_{i = 1} ^ m \left\{ 1 - y_i(w \cdot x_i + b) \right \} }$

この関数を主問題の変数 $w$ ， $b$ について最小化します．

$\displaystyle{ \begin{align} &\min_{w, b} L( w, b; \alpha ) \\ =& \min_{w, b} \frac 1 2 \| w \| _ 2 ^ 2 + \sum_{i = 1} ^ m \alpha _ i \left\{ 1 - y_i(w \cdot x_i + b) \right \} \\ =& \min _ w \frac 1 2 \| w \| _ 2 ^ 2 - w \cdot \left( \sum_{i=1} ^ m y_i \alpha _ i x_i \right) + \min _ b b \sum_{i = 1} ^ m \alpha _ i y_i + \sum _ {i=1} ^ m \alpha _ i \end{align} }$

明らかに $L$ は凸関数ですので，最小値が存在します．主問題の変数で偏微分すると

$\displaystyle{ \begin{align} \nabla _ w L( w, b; \alpha ) &= w - \sum_{i=1} ^ m \alpha _ i y_i x_i = 0 & & \Leftrightarrow w = \sum_{i=1} ^ m \alpha _ i y_i x_i \\ \nabla _ b L( w, b; \alpha ) &= \sum_{i = 1} ^ m \alpha _ i y_i = 0 & & \Leftrightarrow \sum_{i = 1} ^ m \alpha _ i y_i = 0 \end{align} }$

となるので，これらを $L$ に代入すると

$\displaystyle{ \begin{align} &\min_{w, b} L( w, b; \alpha ) \\ =& \frac 1 2 \left\| \sum_{i=1} ^ m \alpha _ i y_i x_i \right\| ^ 2 - \sum _ {i=1} ^ m \sum _ {j=1} ^ m \alpha _ i \alpha _ j y _ i y _ j (x _ i \cdot x _ j) - b \sum _{i=1}^m \alpha _ i y _ i + \sum_{i=1} ^ m \alpha _ i \\ =& \sum_{i=1} ^ m \alpha _ i - \frac 1 2 \left\| \sum_{i=1} ^ m \alpha _ i y_i x_i \right\| ^ 2 \end{align} }$

となり，双対形の目的関数が得られます．

　以上より，SVM の双対問題は

$\displaystyle{ \begin{align} \max _ {\alpha} \sum_{i=1} ^ m \alpha _ i & - \frac 1 2 \left\| \sum_{i=1} ^ m \alpha _ i y_i x_i \right\| ^ 2 \\ \text{subject to} & \sum _ {i=1} ^ m \alpha _ i y _ i = 0 \\ & \alpha _ i \geq 0, \quad \forall i \in \{ 1, \ldots, m \} \end{align} }$

となります．双対問題は $m$ 変数，制約は $1$ 個です．

　ここで，

$\displaystyle{ Q := \sum _ {i=1} ^ m (y _ i x _ i) (y _ i x _ i) ^ \top }$

とすれば $Q$ はグラム行列と呼ばれる半正定値行列ですので，目的関数

$\displaystyle{ \sum _ {i=1} ^ m \alpha _ i - \frac 1 2 \alpha ^ \top Q \alpha }$

は上に凸な二次関数（Quadratic function）であることがわかりやすくなります．

主問題と双対問題の関係

　また，KKT条件から主問題の最適解 $w ^ \ast$ と双対問題の最適解 $\alpha ^ \ast$ に対して

$\displaystyle{ w ^ * = \sum _ {i=1} ^ m \alpha ^ * _ i y _ i x _ i }$

が成り立つので，双対問題の最適解 $\alpha ^ \ast$ から主問題の最適解 $w ^ \ast$ を構築できます．主問題の最適解 $b$ に関しては，次の考察からわかります．

サポートベクター

　さて，相補正条件から得られる主問題の最適解 $w ^ \ast$ と双対問題の最適解 $\alpha ^ *$ の関係式

$\displaystyle{ \forall i \in \{ 1, \ldots, m\}, \quad \alpha ^ * _ i \left( 1 - y _ i ( w ^ * \cdot x _ i + b ) \right) = 0 }$

より，各 $i \in \{ 1, \ldots, m \}$ に対して次が成り立ちます．

$\displaystyle{ \left( \alpha ^ * _ i = 0 \right) \vee \left( y _ i (w ^ * \cdot x _ i + b ) = 1 \right) }$

$L$ を $w$ で偏微分して得られた関係式

$\displaystyle{ w ^ * = \sum _ {i=1} ^ m \alpha ^ * _ i y _ i x _ i }$

が主問題の最適解 $w ^ *$ と双対問題の最適解 $\alpha ^ *$ について成り立つことを思い出すと， 最適解 $w ^ *$ は $\alpha ^ * _ i \neq 0$ となるような $y _ i x _ i$ を組み合わせて構成されることがわかります． $\alpha ^ * _ i \neq 0$ のとき，相補正条件の式から $y _ i ( w \cdot x _ i + b ) = 1$ が成り立つので，

$y _ i = + 1$ のとき．
　 $w \cdot x _ i + b = 1$ となるので，訓練例 $x _ i$ は 超平面の正例側で，超平面との距離が最小（ $= 1$ ）となるような例であることがわかります．
$y _ i = - 1$ のとき．
　 $w \cdot x _ i + b = -1$ となるので，訓練例 $x _ i$ は 超平面の負例側で，超平面との距離が最小（ $= 1$ ）となるような例であることがわかります．

　このような， $\alpha _ i \neq 0$ となる $x _ i$ のことをサポートベクター（Support Vector）と呼びます．

f:id:OCELOT:20200607145153p:plain — サポートベクター

$w$ は一意に定まりますが， $w$ を構成する $(x _ i, y _ i)$ の組み合わせは必ずしも一意には定まりませんので注意が必要です．

　また，各サポートベクター $x _ i$ に関しては，相補性条件より $w \cdot x _ i + b = 1$ が成り立つので

$\displaystyle{ \begin{align} b &= 1 - w \cdot x _ i \\ &= 1 - \left( \sum _ {j=1} ^ m \alpha _ j y _ j x _ j \right) \cdot x _ i \end{align} }$

得られます．従って最適な $\alpha ^ \ast$ が求まれば，最適な $w ^ \ast$ が求まり，それから $b$ も双対問題の最適解を使って構築できることがわかります．

　以上より，主問題の代わりに双対問題を解けば良いこともわかります．

おわりに

　さて，これまでの式変形でハードマージンSVM で扱う最適化問題と，その双対問題を求めました．しかし，一般にはデータは超平面でラベルが+1のデータと-1のデータを分離できません（言い換えると，線形分離可能でないということです）．そういう場合には，これまで展開してきた話の仮定が崩れることになりますので，定式化をやり直す必要があります．こうして新たに定式化し直されたSVMを ソフトマージンSVM と呼びます．

　次の記事では，ソフトマージンSVMについて話をし，余力があればハードマージンSVM，ソフトマージンSVMの汎化誤差の保証について話をしたいと思います．

学習理論の学習

統計的学習理論を学習してるときに思ったこととか

SVM（Support Vector Machine，サポートベクターマシーン）その２

導入

双対形の導出

主問題と双対問題の関係

サポートベクター

おわりに