サポートベクターマシンの理論
データを \(\{\boldsymbol{x}_i\in\mathbb{R}^d\}_{i=1}^N\) とします。
このデータを2つのクラス \(K_1,K_2\) に分類することを考えます。
分類方法は、超平面 \(\boldsymbol{w}^\top\boldsymbol{x}+b=0\) を境に分けて
\[
\boldsymbol{x}_i\in K_1 \Longleftrightarrow \boldsymbol{w}^\top\boldsymbol{x}_i+b \gt 0
\]
\[
\boldsymbol{x}_i\in K_2 \Longleftrightarrow \boldsymbol{w}^\top\boldsymbol{x}_i+b \lt 0
\]
とします。
また、ラベル変数を次のように定めます。
\[
y_i=
\begin{cases}
1 & (\boldsymbol{x}_i\in K_1) \\
-1 & (\boldsymbol{x}_i\in K_2)
\end{cases}
\]
各データ点 \(\boldsymbol{x}_i\) と超平面 \(\boldsymbol{w}^\top\boldsymbol{x}+b=0\) の符号付き距離は
\[
\frac{\boldsymbol{w}^\top\boldsymbol{x}_i+b}{\|\boldsymbol{w}\|}
\]
と表せます。
これにラベル変数 \(y_i\) を掛けたもの
\[
\frac{y_i(\boldsymbol{w}^\top\boldsymbol{x}_i+b)}{\|\boldsymbol{w}\|}
\]
は、正しく分類された \(\boldsymbol{x}_i\) に対しては正の距離、誤って分類された \(\boldsymbol{x}_i\) に対しては負の距離を表します。
ハードマージンSVMでは、すべてのデータ点 \(\boldsymbol{x}_i\) は線形分離可能であるという仮定で考えるので、常に
\[
\frac{y_i(\boldsymbol{w}^\top\boldsymbol{x}_i+b)}{\|\boldsymbol{w}\|} \gt 0
\]
が成り立ちます。
よって、このうち最小となるもの
\[
\min_{i} \frac{y_i(\boldsymbol{w}^\top\boldsymbol{x}_i+b)}{\|\boldsymbol{w}\|} \quad (i=1,2,\cdots,N)
\]
をパラメータ \(\boldsymbol{w},b\) のもとで最大化すればよく、考える問題は次のようになります。
最適化問題（マージン最大化）
\[
\max_{\boldsymbol{w},b} \left\{ \min_{i} \frac{y_i(\boldsymbol{w}^\top\boldsymbol{x}_i+b)}{\|\boldsymbol{w}\|} \right\} \quad (i=1,2,\cdots,N)
\]
この問題を変形して簡単にします。
\[
\begin{align}
&\max_{\boldsymbol{w},b} \left\{ \min_{i} \frac{y_i(\boldsymbol{w}^\top\boldsymbol{x}_i+b)}{\|\boldsymbol{w}\|} \right\} \\
\\
&\Longleftrightarrow \max_{\boldsymbol{w},b} \left[ \frac{1}{\|\boldsymbol{w}\|} \left\{ \min_{i} y_i(\boldsymbol{w}^\top\boldsymbol{x}_i+b) \right\} \right] \\
\\
&\Longleftrightarrow \max_{\boldsymbol{w},b,m} \frac{m}{\|\boldsymbol{w}\|} \quad \text{s.t.} \quad y_i(\boldsymbol{w}^\top\boldsymbol{x}_i+b) \ge m \\
\\
&\Longleftrightarrow \max_{\boldsymbol{w},b,m} \frac{m}{\|\boldsymbol{w}\|} \quad \text{s.t.} \quad y_i\left(\frac{\boldsymbol{w}^\top}{m}\boldsymbol{x}_i+\frac{b}{m}\right) \ge 1 \\
\\
&\Longleftrightarrow \begin{cases}
\displaystyle \max_{\boldsymbol{w},b,m} \frac{m}{\|\boldsymbol{w}\|} \quad \text{s.t.} \quad y_i\left(\frac{\boldsymbol{w}^\top}{m}\boldsymbol{x}_i+\frac{b}{m}\right) \ge 1 \\
\displaystyle \tilde{\boldsymbol{w}}=\frac{\boldsymbol{w}}{m},~\tilde{b}=\frac{b}{m}
\end{cases} \\
\\
&\Longleftrightarrow \max_{\tilde{\boldsymbol{w}},\tilde{b},m} \frac{m}{\|m\tilde{\boldsymbol{w}}\|} \quad \text{s.t.} \quad y_i(\tilde{\boldsymbol{w}}^\top\boldsymbol{x}_i+\tilde{b}) \ge 1 \\
\\
&\Longleftrightarrow \max_{\tilde{\boldsymbol{w}},\tilde{b}} \frac{1}{\|\tilde{\boldsymbol{w}}\|} \quad \text{s.t.} \quad y_i(\tilde{\boldsymbol{w}}^\top\boldsymbol{x}_i+\tilde{b}) \ge 1 \\
\\
&\Longleftrightarrow \min_{\tilde{\boldsymbol{w}},\tilde{b}} \|\tilde{\boldsymbol{w}}\| \quad \text{s.t.} \quad y_i(\tilde{\boldsymbol{w}}^\top\boldsymbol{x}_i+\tilde{b}) \ge 1
\end{align}
\]
計算しやすくするために少し書き換えると、次のようになります。
最適化問題（マージン最大化）
\[
\begin{align}
&\min_{\boldsymbol{w},b}\frac{1}{2}\|\boldsymbol{w}\|^2\\
&\text{s.t.}\quad y_i(\boldsymbol{w}^\top\boldsymbol{x}_i+b)\ge1 \quad (i=1,\cdots,N)
\end{align}
\]
この問題を解くために、ラグランジュの未定乗数法を適用します。
ラグランジュ関数は次のようになります。
\[
\mathcal{L}(\boldsymbol{w},b,\boldsymbol{\alpha})
=\frac{1}{2}\|\boldsymbol{w}\|^2+\sum_{i=1}^N\alpha_i\{1-y_i(\boldsymbol{w}^\top\boldsymbol{x}_i+b)\}
\]
このとき、最適解の必要十分条件は次のようになります。
\[
\frac{\partial\mathcal{L}}{\partial\boldsymbol{w}}=\boldsymbol{0}
,~
\frac{\partial\mathcal{L}}{\partial b}=0
,~
\frac{\partial\mathcal{L}}{\partial \alpha_i} \le 0
,~
\alpha_i \ge 0
~~ (i=1,\cdots,N)
\]
\[
\begin{align}
\frac{\partial\mathcal{L}}{\partial\boldsymbol{w}}=\boldsymbol{0}
&\Longleftrightarrow \boldsymbol{w}-\sum_{i=1}^N\alpha_iy_i\boldsymbol{x}_i=\boldsymbol{0} \\
&\Longleftrightarrow \boldsymbol{w}=\sum_{i=1}^N\alpha_iy_i\boldsymbol{x}_i
\end{align}
\]
\[
\begin{align}
\frac{\partial\mathcal{L}}{\partial b}=0
&\Longleftrightarrow -\sum_{i=1}^N\alpha_iy_i=0 \\
&\Longleftrightarrow \sum_{i=1}^N\alpha_iy_i=0
\end{align}
\]
\[
\begin{align}
\frac{\partial\mathcal{L}}{\partial \alpha_i} \le 0
&\Longleftrightarrow 1-y_i(\boldsymbol{w}^\top\boldsymbol{x}_i+b) \le 0 \\
&\Longleftrightarrow y_i(\boldsymbol{w}^\top\boldsymbol{x}_i+b) \ge 1
\end{align}
\]
よって、\(\displaystyle\boldsymbol{w}=\sum_{i=1}^N\alpha_iy_i\boldsymbol{x}_i,~\sum_{i=1}^N\alpha_iy_i=0\) を \(\mathcal{L}\) に代入すると
\[
\begin{align}
\mathcal{L}
&=\frac{1}{2}\left(\sum_{i=1}^N\alpha_iy_i\boldsymbol{x}_i\right)^\top\left(\sum_{j=1}^N\alpha_jy_j\boldsymbol{x}_j\right) + \sum_{i=1}^N\alpha_i\left[1-y_i\left\{\left(\sum_{j=1}^N\alpha_jy_j\boldsymbol{x}_j\right)^\top\boldsymbol{x}_i+b\right\}\right] \\
&=\frac{1}{2}\left(\sum_{i=1}^N\alpha_iy_i\boldsymbol{x}_i^\top\right)\left(\sum_{j=1}^N\alpha_jy_j\boldsymbol{x}_j\right) + \sum_{i=1}^N\alpha_i\left[1-y_i\left\{\left(\sum_{j=1}^N\alpha_jy_j\boldsymbol{x}_j^\top\right)\boldsymbol{x}_i+b\right\}\right] \\
&=\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j\boldsymbol{x}_i^\top\boldsymbol{x}_j + \sum_{i=1}^N\alpha_i\left(1-\sum_{j=1}^N\alpha_jy_jy_i\boldsymbol{x}_j^\top\boldsymbol{x}_i+by_i\right) \\
&=\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j\boldsymbol{x}_i^\top\boldsymbol{x}_j + \sum_{i=1}^N\alpha_i-\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_jy_i\boldsymbol{x}_j^\top\boldsymbol{x}_i+b\sum_{i=1}^N\alpha_iy_i \\
&=-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j\boldsymbol{x}_i^\top\boldsymbol{x}_j + \sum_{i=1}^N\alpha_i
\end{align}
\]
最適化問題（ハードマージンSVM：双対問題）
\[
\begin{align}
&\max_{\boldsymbol{\alpha}}\left(-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j\boldsymbol{x}_i^\top\boldsymbol{x}_j + \sum_{i=1}^N\alpha_i\right)\\
&\text{s.t.}\quad \alpha_i\ge0,~\sum_{i=1}^N\alpha_iy_i=0 \quad (i=1,\cdots,N)
\end{align}
\]