サポートベクターマシン（ハードマージン）（２） - 機械学習に詳しくなりたいブログ

$\displaystyle \frac{1}{2}\|\mathbf{w}\|^{2} \tag{1}$

を、

$t_n(\mathbf{w}^{T}\phi(\mathbf{x}_n)+b) \ge 1 \quad\quad (n=1,\cdots,N) \tag{2}$

という2次計画問題となることを確認しました。この問題を解きやすい形にするため、2次計画における双対問題の手順に沿って双対問題を導出します。手順は、

ラグランジュ関数を作る
$\displaystyle \frac{\partial L}{\partial \mathbf{w}}=0$ 、 $\displaystyle \frac{\partial L}{\partial b}=0$ を求める
求めた $\mathbf{w},b$ を使って、ラグランジュ関数から $\mathbf{w},b$ を消去する
双対問題が完成。もとのラグランジュ関数に比べ、制約条件が少なく、解くのが簡単になる。

です。まず手順１。不等式制約におけるラグランジュの未定乗数法（KKT条件）より、ラグランジュ乗数 $a_n$ を用いれば、ラグランジュ関数は

$\displaystyle L(\mathbf{w},b,\mathbf{a}) = \frac{1}{2} \| \mathbf{w} \|^{2} - \sum_{n=1}^{N} a_n ( t_n (\mathbf{w}^{T} \phi(\mathbf{x}_n)+b)-1) \,\,\,\,\,\,\,\, (a_n\ge0)\tag{3}$

と書けます。

次に手順２。 $\displaystyle \frac{\partial L}{\partial \mathbf{w}}=0$ 、 $\displaystyle \frac{\partial L}{\partial b}=0$ を計算すれば*1、

$\begin{eqnarray*} \displaystyle \frac{\partial L}{\partial \mathbf{w}}=\mathbf{w} - \sum_{n=1}^{N}a_n t_n \phi(\mathbf{x}_n) &=& 0 \tag{4} \\ \mathbf{w} &=& \sum_{n=1}^{N}a_n t_n \phi(\mathbf{x}_n) \tag{5} \end{eqnarray*}$

$\displaystyle \frac{\partial L}{\partial b} = \sum_{n=1}^{N}a_n t_n = 0 \tag{6}$

です。

次に手順３・４。式(5)、(6)を、式(3)のラグランジュ関数に代入して $\mathbf{w},b$ を消去して双対問題 $\tilde{L}$ を作ります。まずそのまま代入すれば、

$\begin{equation*} \begin{split} \displaystyle \tilde{L}(\mathbf{a})&= \frac{1}{2} \left( \sum_{n=1}^{N}a_n t_n \phi(\mathbf{x}_n) \right)^{T} \left( \sum_{n=1}^{N}a_n t_n \phi(\mathbf{x}_n)\right) \\ &- \sum_{n=1}^{N}a_n t_n \left( \sum_{m=1}^{N}a_m t_m \phi(\mathbf{x}_m) \right)^{T} \phi(\mathbf{x}_n) +\sum_{n=1}^{N}a_n \end{split} \end{equation*} \tag{7}$

です。式(7)右辺の１番目の項は、カーネル関数を用いて $k(\mathbf{x}_i,\mathbf{x}_j) = \phi^{T}(\mathbf{x}_i)\phi(\mathbf{x}_j)$ とすれば、

$\displaystyle \frac{1}{2} \sum_{n=1}^{N}\sum_{m=1}^{N} a_n t_n a_m t_m k(\mathbf{x}_n,\mathbf{x}_m) \tag{8}$

と書けます。同様に式(7)右辺の2番目の項も計算すれば、

$\displaystyle - \sum_{n=1}^{N}\sum_{m=1}^{N} a_n t_n a_m t_m k(\mathbf{x}_n,\mathbf{x}_m) \tag{9}$

です。したがって、双対問題は

$\displaystyle \tilde{L}(\mathbf{a}) = \sum_{n=1}^{N}a_n -\frac{1}{2} \sum_{n=1}^{N}\sum_{m=1}^{N} a_n t_n a_m t_m k(\mathbf{x}_n,\mathbf{x}_m) \tag{10}$