SVMは２次最適化問題になるので、それを勉強してみてはということだったのですが、SVMに特化したSMO(Sequential Minimal Optimisation)アルゴリズムがあるということなので、そちらをやってみました。
SVMの制約条件に
というのがあって、yiは正例なら1、負例なら-1となる値なのですが、そうすると、ようするにこの条件は、正例のαの合計と負例のαの合計が等しくなるということを示してるわけです。
この条件をつかうと、ひとつαを操作したときには、ほかのαを操作して、正例と負例のバランスを取る必要があることがわかります。
で、このことを利用して、同時に２つのαを操作することにすると、解析的に一つ目のαが求められて、２つ目のαはそこから足し算引き算で求められてお徳かも、というのがSMOの考え方です。
問題は、いかに効率よく更新する２つのαを決めるかということになります。
で、サポートベクターマシン入門に書いてある通りに実装してみたのですが、あんまりうまくいってない。線形分離可能なほうでは、うまくいったりいかなかったりします。線形分離不可能なほうは、実行するたびに同じ分離面が出るのですが、これ、もっと速く計算できていいはず。じゃないとSMOの意味ない。
ひとつ、etaが0以下のときの処理を行っていないので、それが敗因でしょうか。
とりあえずは、ソースを。
実行にはid:nowokay:20080327のGraph.java、id:nowokay:20080326のLerningMachine.javaが必要です。
