SVMの双対問題について

SVMの復習してるのでメモ。

双対問題の導出で、だいたいどの参考書やウェブ上の資料見ても「ラグランジュの未定乗数法使えばいいよ！」というとこまでは書いてあるが、
wとbを消してラグランジュ乗数αのみで表したラグランジュ関数(Lagrangian)の最大化がなぜ双対問題になるのか、
よくわからなかったのでまとめました。

私が以前学習したときも、ラグランジュ関数の導出だけで「すげーｗ」と思考停止していた。

【ラグランジュ関数】
以下の非線形計画問題を考える。

$\min_{\bf x} \;\; f({\bf x})$
$\mbox{subject to} \;\; g_i({\bf x}) \leq 0 (i=1,\dots,m)$

この問題のラグランジュ関数 $L$ は次のように定義される。

$L({\bf x},{\bf \lambda}) = f({\bf x}) + \sum_{i=1}^m \lambda_i g_i({\bf x})$

【元関数とラグランジュ関数】
ラグランジュ関数に対し、 ${\bf x} = \tilde{\bf x}$ と固定したとき

$\max_{\bf \lambda} \;\; L(\tilde{\bf x}, {\bf \lambda})$
$\mbox{subject to} \;\; \lambda_i \geq 0$

なる最適化問題を考える。 $g_i(\tilde{\bf x}) > 0$ となる $i$ が存在すれば
$\lambda_i \rightarrow \infty$ ととることで $\delta(\tilde{\bf x}) \rightarrow \infty$ となる。
一方全ての $i$ に対して $g_i(\tilde{\bf x}) \leq 0$ であれば、 ${\bf \lambda} = {\bf 0}$ のとき最適値 $f(\tilde{\bf x})$ を得る。

このようにこの問題の最適値は $\tilde{\bf x}$ に依存するのでこれを $F(\tilde{\bf x})$ とおくと

$F(\tilde{\bf x}) = f(\tilde{\bf x}) \;\;(\mbox{if} \;g_i(\tilde{\bf x}) \leq 0, \; i=1,\dots,m)$
$\;\;\;\;\;\;\; = \infty \;\; (\mbox{else})$

と表せ、 $F(\tilde{\bf x})$ の $\tilde{\bf x}$ に関する最小値は初めの問題の最適値に等しいことになる。

【max-minとmin-max】
ここで、以下の等式は常に成り立つ。

$\min_{\bf x} \; \max_{{\bf \lambda} \geq 0 } L({\bf x},{\bf \lambda}) \; \geq \; \max_{{\bf \lambda} \geq 0 } \; \min_{\bf x} L({\bf x},{\bf \lambda})$

（左辺の $\min$ を無視して考えれば当然）

これを用いると

$\min_{\bf x} \; F({\bf x}) = \min_{\bf x} \; \max _{{\bf \lambda} \geq 0 } L({\bf x},{\bf \lambda}) \; \geq \; \max_{{\bf \lambda} \geq 0 } \; \min_{\bf x} L({\bf x},{\bf \lambda})$

が成立する。このとき最右辺の最大化をラグランジュ双対問題（または単に双対問題）と呼ぶ。
この最右辺は、 $L$ を ${\bf x}$ に関して最小化した関数を ${\bf \lambda}$ に関して最大化した値。
SVMでいうと $L$ を ${\bf w}, b$ に関して最小化して ${\bf \alpha}$ に関して最大化。
$L$ の ${\bf w}, b$ に関する最小値はすなわちラグランジュの未定乗数法で求めた $L({\bf \alpha})$ 。
つまりこの $L({\bf \alpha})$ を最大化する問題がここで登場するわけだ。
最後に残った不等号は、強双対性定理を用いて外す。

【強双対性定理】
定義域 $\Omega \subseteq \mathrm{R}^n$ における凸最適化問題
$\min \;\; {\bf w}, \; {\bf w} \in \Omega$
$\mbox{subject to}\;\; g_i({\bf w})\geq 0 \; (i=1,\dots,m)$
では、主問題と双対問題の最適値は一致する。ただし $f$ は連続で集合 $\Omega$ の各点で微分可能であり、
その微分が連続である凸関数とする。また $g_i$ はアファイン関数とする。

【つまり？】
強双対性定理から、
$f({\bf w}^*, b^*) = \min_{\bf x}\; F({\bf w}, b) \; = \; \max_{{\bf \alpha} \geq 0 }\; L({\bf \alpha})$
が得られ、 $L({\bf \alpha})$ を最大化したときの ${\bf \alpha}$ を用いて得られる ${\bf w}, b$ は主問題の最適解となるのである。
ちなみにここで $f$ は
$f({\bf w}, b) = \frac{1}{2} \| {\bf w} \|^2 + C \sum_i \xi_i$
すなわちSVMの主問題。
ただし双対問題の制約条件は途中の計算で増える。

【というわけで】
いいはず……
主問題と双対問題の間に $F({\bf x})$ を挟んでいるところが意外と重要かもしれない。
つまり本当の双対関係にあるわけではないようだ。

Cristianini，Shawe-Taylor著，大北訳の「サポートベクターマシン入門」（共立出版）、
小野田著の「サポートベクターマシン」（オーム社）、
田村，村松著の「最適化法」（共立出版）
を参考にしました。