SVMの双対問題について
SVMの復習してるのでメモ。
双対問題の導出で、だいたいどの参考書やウェブ上の資料見ても「ラグランジュの未定乗数法使えばいいよ!」というとこまでは書いてあるが、
wとbを消してラグランジュ乗数αのみで表したラグランジュ関数(Lagrangian)の最大化がなぜ双対問題になるのか、
よくわからなかったのでまとめました。
私が以前学習したときも、ラグランジュ関数の導出だけで「すげーw」と思考停止していた。
この問題のラグランジュ関数は次のように定義される。
【元関数とラグランジュ関数】
ラグランジュ関数に対し、と固定したとき
なる最適化問題を考える。 となる
が存在すれば
ととることで
となる。
一方全ての に対して
であれば、
のとき最適値
を得る。
このようにこの問題の最適値はに依存するのでこれを
とおくと
と表せ、の
に関する最小値は初めの問題の最適値に等しいことになる。
【max-minとmin-max】
ここで、以下の等式は常に成り立つ。
(左辺のを無視して考えれば当然)
これを用いると
が成立する。このとき最右辺の最大化をラグランジュ双対問題(または単に双対問題)と呼ぶ。
この最右辺は、を
に関して最小化した関数を
に関して最大化した値。
SVMでいうとを
に関して最小化して
に関して最大化。
の
に関する最小値はすなわちラグランジュの未定乗数法で求めた
。
つまりこのを最大化する問題がここで登場するわけだ。
最後に残った不等号は、強双対性定理を用いて外す。
【強双対性定理】
定義域における凸最適化問題
では、主問題と双対問題の最適値は一致する。ただしは連続で集合
の各点で微分可能であり、
その微分が連続である凸関数とする。またはアファイン関数とする。
【つまり?】
強双対性定理から、
が得られ、を最大化したときの
を用いて得られる
は主問題の最適解となるのである。
ちなみにここでは
すなわちSVMの主問題。
ただし双対問題の制約条件は途中の計算で増える。
【というわけで】
いいはず……
主問題と双対問題の間にを挟んでいるところが意外と重要かもしれない。
つまり本当の双対関係にあるわけではないようだ。
Cristianini,Shawe-Taylor著,大北訳の「サポートベクターマシン入門」(共立出版)、
小野田著の「サポートベクターマシン」(オーム社)、
田村,村松著の「最適化法」(共立出版)
を参考にしました。