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++あまりかけないのでコードが汚いけど仕方ない。
ガウスカーネルを使って適当に作ったデータを分類したら以下の画像のようになった。一応成功してるみたい。
本当はSparseLUを用いて逆行列を求めたかったのだけど、謎のエラーが出て結局あきらめてSparseQRを用いた。エラーメッセージでググってもヘッダファイルしか出てこないのがいけなかった。