しかしSVMも最近は速いらしい

　Complement Naive BayesがSVMより速いよーと主張していたので、SVMもなんか最近は速くなってるらしいよ、という事を紹介してみたい。近年はSVMなどの学習を高速に行うという提案が行われており、実装が公開されているものもある。その中の一つにliblinearという機械学習ライブラリがある。ライブラリ名から推測できる通り、liblinearではカーネルを使うことが出来ない。しかし、その分速度が速く、大規模データに適用できるという利点がある。
　liblinearを作っているのはlibsvmと同じ研究グループで、Chih-Jen Linがプロジェクトリーダーであるようだ。libsvmはかなり有名なライブラリで、liblinearにはそういった意味で安心感がある。（liblinearの方は公開されてしばらくは割とバグがあったらしいけど。）
　liblinearにはL1-SVM, L2-SVM, ロジスティック回帰が実装されている。L1-SVM, L2-SVMはcoordinate descent method, ロジスティック回帰はtrust region Newton methodによる最適化を行う。（L2-SVMはtrust region Newton methodも使える。）L1とかL2というのは間違えたときのペナルティをどう定義するかを意味しており、L1だと間違いの絶対値がペナルティとなり、L2だと間違いの2乗した値をペナルティとする。
　liblinearの学習速度は確かに早く、Journal of Machine Learning Researchに掲載された"LIBLINEAR: A library for large linear classification"という論文によると、2万件ぐらいのデータに対して、数秒で学習が収束している。もちろんいろいろな条件によって学習時間は大きく変わるのだろうけど、libsvmよりも速いことは間違いないだろう。
　使われているアルゴリズムの詳細に関してはICML2008の"A dual coordinate descent method for large-scale linear SVM"に書いてあるのでざっと読んでみたが、速いだけでなく実装も比較的簡単なようだ。なんでこれでSVMの最適化ができるのか、証明はちょっとややこしそうだけどね！
　Complement Naive Bayesと比べて速いかどうかはわからない（さすがに遅いだろうと思う）けど、SVMも頑張っているんだよ、ということで。