前回はSVMについての導入を行いました。
bananarian.hatenablog.com
しかし、前回の記事では肝心の最適化問題を解く部分は長くなるのでカットしていました。そういうわけで今回はSVMに関係する部分だけピックアップして説明していきます。
KKT条件についてもう少し知りたいって人は、とりあえずここのpdf見れば大丈夫です。
http://www.cit.nihon-u.ac.jp/kouendata/No.42/7_sujo/7-047.pdf
スポンサーリンク
前回の復習
とにもかくにも次のような最適化問題を解きたいということでした。
制約 の下で
を最小化したい。
まず、もう少し制約の部分をスタイリッシュに書いてみましょう。
ですね。
そういうわけで今回考えたい問題は
制約 の下で、
を最小化したい。
という問題になります。
KKT条件
さて、このように制約に不等式があるような問題の場合用いられるのがKKT条件です。
http://www.cit.nihon-u.ac.jp/kouendata/No.42/7_sujo/7-047.pdfの最初のページに詳細は書いてあります。
まず、pdfの表記に揃えるために、次のように置くことにします。
さらに、ラグランジュ乗数を導入することで次のようなラグランジュ関数を得られます。
そこでラグランジュ関数に対して次の条件を満たすようなを考えてやるわけです。
(1)
(2)
(3)←全てのiで成り立つ
(4)←全てのiで成り立つ
これでが出てきます。しかし、なんか大変そうですね。別にこれでも出来るんですが、双対問題という問題に変換することでより、簡単に解くことが出来ます。
KKT条件は何をやっているのか
一般的な話をしていると、とてもじゃないけど一つの記事におさまらないので、今回は変形過程を説明することにとどめます。でもまあ結構自然に変換していけるのでほとんど違和感はないかなあとは思います。
まず、さっきまで考えていた問題はこうでした。
を最小化したいわけですが、
まず、(4)からわかる通り、に適当な値を入れた後でのは元の目的関数になっていると言うことに注意してください。つまりこの問題は結局ゴリゴリ条件を加えただけで、最小化したい目的関数は元のままなのです。
次に、(1)から(4)の条件は一旦忘れて、を適当な値に止めて置いて、よくよくを眺めながらを色々な値に動かしてみてほしいんですけど、
もし何れかのでが成り立っていたら、を大きくすればするほどいくらでもを小さくすることが出来ます。つまりこの時最小値はになってしまうわけです。
しかし、全てのでが成り立つ限りにおいて、の最小値はしっかり元の目的関数の最小値に一致します。これはでないと、元の関数に変な値が足されて大きくなるのでわかりますね。
整理すると次のようになります。
の時、
つまり、私たちはの場合の最小値は興味がないわけです。元の目的関数の最小値と一致する場合だけ知りたいわけです。
というわけで、を固定した下でを動かし、最小値の挙動を上のように調べた後は、をはじく為に、a,hについて最大化する必要があるのです。
つまり、こういうことです。
こうすることで、となった段階で大きい方、つまりが選ばれます。
これを言葉で説明せずに数式で簡潔に示すと先ほどの(1)~(4)となります。
双対問題
ところで、双対問題とはなんでしょう。先ほどのは双対問題に対して主問題と呼びますが、双対問題は次のようになります。
主問題のをひっくり返しただけですね。
これは必ず次のような関係があります。
これはどういうことかというと、
まず左の項を見るととりあえずを動かしてを最も大きくしています。
次に右の項ですが、一旦を動かして制約をつけてから、更にを動かして最も大きなを見つけています。
つまり、の点から見ると左は純粋にの点の中で最も大きくなるようなものを見つけている一方、右は一旦制約を与えてからの点の中で最も大きくなるようなものを見つけています。
制約がかかっている以上、右の項は左の項と同じ値かそれより小さくなるのは当然ですね。ちなみに同じ話をで見てみてもしっかり成り立っています。
強双対定理
最後に強双対定理です。
これは今回のように不等式線形制約しかなくて、目的関数が凸である場合には先ほどの関係
の不等号部分>が外れて、必ず等号が成り立ちますよという定理です。
まとめ
以上より、少なくともこのSVMのケースでは主問題ではなく双対問題でを求めても良いと言うことになります。
主問題でも解けますが、この場合、ちょっと条件が多いので強双対定理は重宝します。