【初心者向け】KKT条件を使ってSVMの計画問題を解く

前回はSVMについての導入を行いました。
bananarian.hatenablog.com

しかし、前回の記事では肝心の最適化問題を解く部分は長くなるのでカットしていました。そういうわけで今回はSVMに関係する部分だけピックアップして説明していきます。

KKT条件についてもう少し知りたいって人は、とりあえずここのpdf見れば大丈夫です。
http://www.cit.nihon-u.ac.jp/kouendata/No.42/7_sujo/7-047.pdf

前回の復習

とにもかくにも次のような最適化問題を解きたいということでした。

制約　 $y_i=1の時は(aX_i-h)≧1であり、y_i=-1の時は(aX_i-h)≦-1$ 　の下で

$||a||^2$ を最小化したい。

まず、もう少し制約の部分をスタイリッシュに書いてみましょう。

$y_i(aX_i-h)≧1$

ですね。

そういうわけで今回考えたい問題は

制約　 $y_i(aX_i-h)≧1$ 　の下で、
$||a||^2$ を最小化したい。

という問題になります。

KKT条件

さて、このように制約に不等式があるような問題の場合用いられるのがKKT条件です。
http://www.cit.nihon-u.ac.jp/kouendata/No.42/7_sujo/7-047.pdfの最初のページに詳細は書いてあります。

まず、pdfの表記に揃えるために、次のように置くことにします。

$f(a,h)=||a||^2$
$g_i(a,h)=y_i(aX_i-h)-1$

さらに、ラグランジュ乗数 $\lambda≧0$ を導入することで次のようなラグランジュ関数 $L(a,h,\lambda)$ を得られます。

$L(a,h,\lambda)=||a||^2-\sum_{i=1}^{n}\lambda_i(y_i(aX_i-h)-1)$

そこでラグランジュ関数に対して次の条件を満たすような $a,h$ を考えてやるわけです。

(1) $\frac{\partial L(a,h,\lambda)}{\partial a}=0$
(2) $\frac{\partial L(a,h,\lambda)}{\partial h}=0$
(3) $\frac{\partial L(a,h,\lambda)}{\partial \lambda_i}≦0$ ←全てのiで成り立つ
(4) $\lambda_i g_i(a,h)=0$ ←全てのiで成り立つ

これで $a,h$ が出てきます。しかし、なんか大変そうですね。別にこれでも出来るんですが、双対問題という問題に変換することでより、簡単に解くことが出来ます。

KKT条件は何をやっているのか

一般的な話をしていると、とてもじゃないけど一つの記事におさまらないので、今回は変形過程を説明することにとどめます。でもまあ結構自然に変換していけるのでほとんど違和感はないかなあとは思います。

まず、さっきまで考えていた問題はこうでした。

$L(a,h,\lambda)=||a||^2-\sum_{i=1}^{n}\lambda_i g_i(a,h)$ を最小化したいわけですが、

まず、(4)からわかる通り、 $a,h$ に適当な値を入れた後での $L(a,h,\lambda)$ は元の目的関数 $||a||^2$ になっていると言うことに注意してください。つまりこの問題は結局ゴリゴリ条件を加えただけで、最小化したい目的関数は元のままなのです。

次に、(1)から(4)の条件は一旦忘れて、 $a,h$ を適当な値に止めて置いて、よくよく $L(a,h,\lambda)$ を眺めながら $\lambda$ を色々な値に動かしてみてほしいんですけど、

もし何れかの $g_i$ で $g_i(a,h)≧0$ が成り立っていたら、 $\lambda$ を大きくすればするほどいくらでも $L$ を小さくすることが出来ます。つまりこの時最小値は $-\infty$ になってしまうわけです。

しかし、全ての $g_i$ で $g_i(a,h)＜0$ が成り立つ限りにおいて、 $L(a,h,\lambda)$ の最小値はしっかり元の目的関数の最小値に一致します。これは $\lambda=0$ でないと、元の関数に変な値が足されて大きくなるのでわかりますね。

整理すると次のようになります。

$g_i(a,h)＜0$ の時、
$\min_{\lambda} L(a,h,\lambda)=||a||^2$

$g_i(a,h)≧0$ の時、
$\min_{\lambda} L(a,h,\lambda)=-\infty$

つまり、私たちは $g_i(a,h)≧0$ の場合の最小値は興味がないわけです。元の目的関数の最小値と一致する場合だけ知りたいわけです。

というわけで、 $a,h$ を固定した下で $\lambda$ を動かし、最小値の挙動を上のように調べた後は、 $-\infty$ をはじく為に、a,hについて最大化する必要があるのです。

つまり、こういうことです。

$\max_{a,h}\min_{\lambda} L(a,h,\lambda)$

こうすることで、 $-\inftyか||a||^2か$ となった段階で大きい方、つまり $||a||^2$ が選ばれます。

これを言葉で説明せずに数式で簡潔に示すと先ほどの(1)~(4)となります。

双対問題

ところで、双対問題とはなんでしょう。先ほどの $\max_{a,h}\min_{\lambda} L(a,h,\lambda)$ は双対問題に対して主問題と呼びますが、双対問題は次のようになります。

$\min_{\lambda} \max_{a,h} L(a,h,\lambda)$

主問題の $\minと\max$ をひっくり返しただけですね。

これは必ず次のような関係があります。
$\min_{\lambda} \max_{a,h} L(a,h,\lambda)≧\max_{a,h}\min_{\lambda} L(a,h,\lambda)$

これはどういうことかというと、
まず左の項を見るととりあえず $a,h$ を動かして $L(a,h,\lambda)$ を最も大きくしています。

次に右の項ですが、一旦 $\lambda$ を動かして制約をつけてから、更に $a,h$ を動かして最も大きな $L(a,h,\lambda)$ を見つけています。

つまり、 $a,h$ の点から見ると左は純粋に $a,h$ の点の中で最も大きくなるようなものを見つけている一方、右は一旦制約を与えてから $a,h$ の点の中で最も大きくなるようなものを見つけています。

制約がかかっている以上、右の項は左の項と同じ値かそれより小さくなるのは当然ですね。ちなみに同じ話を $\lambda$ で見てみてもしっかり成り立っています。

強双対定理

最後に強双対定理です。

これは今回のように不等式線形制約しかなくて、目的関数が凸である場合には先ほどの関係

$\min_{\lambda} \max_{a,h} L(a,h,\lambda)≧\max_{a,h}\min_{\lambda} L(a,h,\lambda)$

の不等号部分＞が外れて、必ず等号が成り立ちますよという定理です。

まとめ

以上より、少なくともこのSVMのケースでは主問題ではなく双対問題で $a,h$ を求めても良いと言うことになります。
主問題でも解けますが、この場合、ちょっと条件が多いので強双対定理は重宝します。