『はじめてのパターン認識』（平井 有三）の8.1 SVMを丁寧に読んだのでメモ。
線形分離可能な時、適当な$\boldsymbol{w},b$を選ぶことで、(8.2)式
\begin{align}
t_i=+1 \ の場合 \quad \boldsymbol{w}^T \boldsymbol{x}_i +b \geq +1 \\
t_i=-1 \ の場合 \quad \boldsymbol{w}^T \boldsymbol{x}_i +b \leq -1
\end{align}
を満たすようにできる。
これは、図8.1をイメージすれば分かる。というのも、
\boldsymbol{w}^T \boldsymbol{x}_i +b = 0
は平面を表すからである。
マージンがノンゼロなら$\boldsymbol{w},b$を何倍かすれば、必ず式(8.2) のようにできる。
特に、境界平面からの距離が最も近い点が$\boldsymbol{w}^T \boldsymbol{x}_i +b =\pm 1$ を満たすようにする。すると、クラス間マージンは(8.4)式
\rho (\boldsymbol{w},b) = 2/ || \boldsymbol{w}||
のようになる。
これの導出方法としては、点と直線の距離
d = \frac{|ax_1+by_1+c|}{\sqrt{a^2+b^2}}
の一般次元バージョン
d = \frac{|\boldsymbol{w}^T \boldsymbol{x}_1 + b|}{||\boldsymbol{w}||}
を用いても導出できる。
8.1.2 KKT条件
不等式制約条件つきのLagrange 未定乗数法を知らないので調べたら、Princetonのスライド
https://www.cs.princeton.edu/courses/archive/spring16/cos495/slides/ML_basics_lecture5_SVM_II.pdf
が一番わかりやすかった。
ロジックがややこしいので、自分なりに解釈。
式(8.7)
\tilde{L}_p(\boldsymbol{w},b,\boldsymbol{\alpha}) = \frac{1}{2} \boldsymbol{w}^T \boldsymbol{w} - \sum_{i=1}^N \alpha_i ( t_i (\boldsymbol{w}^T \boldsymbol{x}_i +b) -1 )
を$\boldsymbol{\alpha}$ に関して最大化して、$\boldsymbol{w},b$に関して最小化すること、つまり
\min_{\boldsymbol{w},b} \max_{\boldsymbol{\alpha}} \tilde{L}_p(\boldsymbol{w},b,\boldsymbol{\alpha})
が、主問題、つまり不等式制約条件
t_i ( \boldsymbol{w}^T \boldsymbol{x}_i + b ) \geq 1
を満たしつつ評価関数
L_p(\boldsymbol{w}) = \frac{1}{2} \boldsymbol{w}^T \boldsymbol{w}
を最小化することと等価。
なぜなら、
\begin{align}
\max_{\boldsymbol{\alpha}} \tilde{L}_p(\boldsymbol{w},b,\boldsymbol{\alpha}) =
\left\{
\begin{array}{ll}
L_p(\boldsymbol{w}), & \text{if} \quad \boldsymbol{w} が制約条件を満たす \\
\infty, & \text{if} \quad \boldsymbol{w} が制約条件を満たさない
\end{array}
\right.
\end{align}
だからである。
そしてこの問題はの解となる$\boldsymbol{w},b,\alpha$は(1)~(5) の KKT条件を満たす。(KKT条件から一意に決まるか、つまりKKT条件とこの問題との等価性は知らない。あと、KKT条件を満たすのは、凸性とかアフィン変換とかの条件を満たす場合だけ。)
双対問題[1] は制約条件として$\alpha_i>0$ が残っていることに注意。
あと、ロジック的には、$\boldsymbol{\alpha}^T \boldsymbol{t} =0$ は課さなくても、評価関数の最大化をすれば得られるように思えるけど、違うのか？
# コメント
Princetonのスライドを見たら、Lagurange dualityのprimal problem, dual problemと言っているのは、
\min_{\boldsymbol{w},b} \max_{\boldsymbol{\alpha}} \tilde{L}_p(\boldsymbol{w},b,\boldsymbol{\alpha})
に対する、
\max_{\boldsymbol{\alpha}} \min_{\boldsymbol{w},b} \tilde{L}_p(\boldsymbol{w},b,\boldsymbol{\alpha})
だから、微妙に本と言ってること違う。あと、日本語の本ってやっぱり行間が空いていて自分で埋めるタイプが多いよね。というかKKT条件は自分で埋められる行間になってない。外国の本の、全部行間埋まっているものとセットで読むのが一番いい気がする。