読者です 読者をやめる 読者になる 読者になる

何らかのブログ

日記とか備忘録

2次計画問題のソルバを作ってC-SVMを作る

大学の課題で機械学習をやることになったので、2次計画問題の解法のひとつである主双対内点法をパス追跡法で実装して、それを用いて非線形ソフトマージンサポートベクタ―マシンを実装した。

以下のサイトを参考にした。

二次計画用の内点法(Interior Point Method)をC++で書きました。 - ニートがプログラミングするブログ

Quadratic programming problems - a review on algorithms and applications

制約付大規模最適化問題に対する主双対内点法について

カーネル法

二次計画法のアルゴリズム - MATLAB & Simulink - MathWorks 日本

後で調べたら大規模密行列ではIPMは高速らしいが、大規模疎行列ではActive Set Method(有効制約法)の方が有利らしい。SVMで使うために疎行列を扱いたかったので完全に失敗したけど、今度ASMで書き直したい。

 C++あまりかけないのでコードが汚いけど仕方ない。

IPM

ガウスカーネルを使って適当に作ったデータを分類したら以下の画像のようになった。一応成功してるみたい。

f:id:censored:20150609160508p:plain

本当はSparseLUを用いて逆行列を求めたかったのだけど、謎のエラーが出て結局あきらめてSparseQRを用いた。エラーメッセージでググってもヘッダファイルしか出てこないのがいけなかった。