PRML勉強会で発表する気分になってみる@自宅

爆弾低気圧から身を守るため勉強会は延期となってしまいましたが、資料をUPします。（爆弾ならしょうがないですね＞＜）

Prml revenge7.1.1

ソフトマージンSVM

今回の自分の担当範囲では、ソフトマージンSVMが登場します。
今回、予習するうえで最も時間がかかったのは、資料の中でさらっと流してる感じのWorking Set Selection(WSS) の部分です。SVMは、結局のところ二次計画問題を解くという話になるのですが、時間的・空間的リソースの観点から、汎用のQPソルバー*1では問題があります(変数がM個の二次計画問題を解くには、一般に $O(M^3)$ の時間がかかることが知られています)。そこで、効率的な計算手法が必要となります。例えば、SVMの有名な実装であるlibsvmではSMOという手法が使われているのですが、SMOのパフォーマンスを決めるための重要なコンポーネントがWSSです。libsvmの開発ドキュメントではWSSについて詳細な解説があり、がんばって読んだのですが、結局自分の頭では今日までに理解することはできませんでした（泣）
余力があれば、今後リベンジしたいです。

参考にしたドキュメント・サイトなど

LIBSVM: A Library for Support Vector Machines　http://www.csie.ntu.edu.tw/~cjlin/papers/libsvm.pdf
- libsvmの開発ドキュメントです。
Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines http://www.bradblock.com/Sequential_Minimal_Optimization_A_Fast_Algorithm_for_Training_Support_Vector_Machine.pdf
- SMOを初めて提案したPlattによるドキュメントです。
ソフトマージンSVMを書いてみた　http://sucrose.hatenablog.com/entry/20111015/p1
- @Scaled_Wurmさんによる、ソフトマージンSVMの実装例です。最適化には汎用のQPソルバーを使っているようです。実装例ではデータサイズが10で問題なく動きますが、データを増やすとやはりリソース的に厳しい感じでした。

*1:QPはquadratic programming の略です