C++0xで10行で書けるマージンパーセプトロン
C++0xの練習として，マージンパーセプトロンを書きました．データ読み込みやコマンドライン処理を含めてもperceptron_binary.cppという90行にみたない1ファイルだけで済ませてあり，一応，コピペなどで気軽に使えることを意識しています．
ソースコードと使い方
上の「ソースコード」や「使い方」のリンク先にもかいてありますが，gcc4.6さえ入っていれば，下記のように打てば使えます．基本的には，perceptron_binary.cppをコンパイルするだけです．gcc4.6が必要なのは，range-based forを使っているからです．
% g++ -std=c++0x -O2 perceptron_binary.cpp -o perceptron_binary % g++ -O2 mknews20.cpp -o mknews20 % wget http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/binary/news20.binary.bz2 % bzip2 -dc news20.binary.bz2|./mknews20 % ./perceptron_binary news20.train news20.test 10 0.6 Accuracy: 4819/4996=0.964572 Zerofication rate: 334121/1355194=0.246548
10行，というのはこちらの記事にインスパイアされました．
直接の参考にしたのは，kisa12012さんのこの記事や輪講発表資料です．
最初，パーセプトロンを実装していたところ，id:sleepy_yoshi さんのTokyoNLP #5で発表された資料でマージンパーセプトロンも簡単に出来ることを知り，ついでにやってみたという感じです．
プログラムの解説
主要なマージンパーセプトロンの部分は，以下の10行です．
struct perceptron_t{ weight_t weight; val_t margin; perceptron_t(int size, val_t margin_=0.0): weight(size), margin(margin_) {} inline clabel_t classify(const datum_t& datum) const{ return weight*datum>0.0?1:-1; } inline void train (const datum_t& datum){ if(((val_t)datum.first)*(weight*datum)<=margin) for(const auto& p : datum.second) weight[p.first] += ((val_t)datum.first)*p.second; } };
10行で書ける…というのは，class perceptron_tが10行ということです．すみません，さすがにc++でデータ読み込みまで含めて10行というのは無理です（汗 仕掛けはweight*datumにあります．weight_t型のoperator*をオーバーロードすることによって，重みベクトルと特徴量ベクトルの内積をweight*datumで書けるようにしました．id:sleepy_yoshi さんや id:kisa12012 さんの資料に出てくるパーセプトロンのifをほとんどそのままの形で表せています．
数式：
- if
プログラム：
if(((val_t)datum.first)*(weight*datum)<=margin) for(const auto& p : datum.second) weight[p.first] += ((val_t)datum.first)*p.second;
一方，更新式はプログラムっぽい形になってしまいました．これも，vectorのoperator +とoperator =をオーバーロードすれば数式っぽくかけると思うのですが，ナイーブに書くと途中でvectorのコピーが発生したり，データ中に現れる特徴だけではなくて，全ての特徴に対してforがかかったりしそうで，パフォーマンスが低下しそうです．プログラムで書けば2行ですむものにそこまで労力をかける気にもなりませんでした．
データフォーマットは，libsvmやliblinear，ollその他，みんなが使っている，1行1データで各行が"ラベル 特徴量ID:特徴量 特徴量ID:特徴量 ... 特徴量ID:特徴量"という形式です．
datum_tはpair<ラベル,vector
weight_tはvector
C++0xのRange-based forをfor(const auto& p : datum.second)で使ってますが，これ，この部分だけなら普通のC++でも書けますね．for(data_t::iterator it = datum.second.begin(); it!=datum.second.end();++it)みたいに．なので，分かりにくくなりますが，一応C++でも10行で書けます．C++0xのもうひとつの本領はラムダ式で，制度を求めるときに使ってます（後述）．
C++0xの機能
Range-based for
今までC++でループを回すためには，for(int i=0;i
auto
先程のfor(c_t::iteratort it...のところのc::iteratorを書くのは，cがvector
ラムダ式
今までも，operator()をオーバーロードすることによる関数オブジェクトは定義すれば作ることが出来ましたが，いちいち定義しなければならず，その場で作ることができませんでした．一方，Pythonでは，lambda x:x**2のように，その場で関数を作成する事ができます．C++でも，その場で関数オブジェクトを作成することができるようになりました．
今回は，集計のところで本領を発揮してくれています．
printrate("Accuracy: ", count_if(test_data.begin(), test_data.end(), [&p](const datum_t& t){return p.classify(t)==t.first;}), test_data.size()); printrate("Zerofication rate: ", count_if(p.weight.begin(), p.weight.end(), [](const val_t& w_i ){return (bool)(w_i==0.0);}) , (int)maxfid+1);
pがperceptron_t型で，パーセプトロンそのものです．printrate(文字列,int a, int b)は，文字列を表示した後，a,bをfloatに直して率を表示するだけの関数です．
ラムダ式はtest_dataに対するcount_ifの中で使っています．count_ifは，指定されたコンテナ（test_data）中の各要素について，渡されたpredicateを実行し，trueが返って時だけカウントするというものです．
[&p](const datum_t& t){return p.classify(t)==t.first;}という形をしています．t.firstには，正解が入っています．[&p]は現在のスコープからpという変数を使用できるという指定です．
実験設定
実験は，news20.binaryで行いました．これは，既にBag-of-words形式で特徴量ベクトルになっている新聞記事を２つに分類する問題です．news20.binaryは，@hillbig さん作のollというオンライン学習ライブラリのマニュアルに書かれている実験で使われています．
この実験データの作り方は，id:n_shuyo さんも以前，書かれています．この実験でも，この記事と同じデータの作り方をしています．
が，困ったことに，行の順番をランダムに並び替えるsort -Rが自分の環境にはなかったので，この際news20.binaryから上記事のnews20.trainとnews20.testを作成するmknews20という簡単なプログラムを作成しました．使い方は簡単でコンパイルして，bzip2 -dc news20.binary.bz2|./mknews20で，news20.trainとnews20.testが作成できます．上のgithubのREADME.mdに書いてあります．
実験結果
まず，普通のパーセプトロンです．10はイテレーション回数で，0.0がマージンです．biasはデフォルトでは入りません．毎イテレーションでデータをrandom_shuffleしています．
$ ./perceptron_binary news20.train news20.test 10 0.0 Accuracy: 4768/4996=0.954363 Zerofication rate: 1025984/1355194=0.757075
Zerofication rate（ゼロ化率）は，重みベクトル中の0の要素の数/重みベクトルの次元（＝素性の次元）です．精度はそこそこですが，高いゼロ化率を達成できています．
マージンをあげると，ゼロ化率は急激に下がりますが，精度は1%ほど上がります．
$ ./perceptron_binary news20.train news20.test 10 1.0 Accuracy: 4820/4996=0.964772 Zerofication rate: 680830/1355194=0.502386
マージンを上げることによって，しばらく精度が上がるが，3.0ぐらいをピークにどんどんゆっくりと精度が下がっていく．一方，ゼロ化率はマージンを上げることで急激に下がっていく．
$ ./perceptron_binary news20.train news20.test 10 2.0 Accuracy: 4825/4996=0.965773 Zerofication rate: 557335/1355194=0.411258 $ ./perceptron_binary news20.train news20.test 10 3.0 Accuracy: 4827/4996=0.966173 Zerofication rate: 483274/1355194=0.356609 $ ./perceptron_binary news20.train news20.test 10 4.0 Accuracy: 4825/4996=0.965773 Zerofication rate: 423173/1355194=0.31226 $ ./perceptron_binary news20.train news20.test 10 5.0 Accuracy: 4824/4996=0.965572 Zerofication rate: 379253/1355194=0.279851 $ ./perceptron_binary news20.train news20.test 10 6.0 Accuracy: 4819/4996=0.964572 Zerofication rate: 334121/1355194=0.246548 $ ./perceptron_binary news20.train news20.test 10 7.0 Accuracy: 4818/4996=0.964372 Zerofication rate: 312279/1355194=0.230431 $ ./perceptron_binary news20.train news20.test 10 8.0 Accuracy: 4817/4996=0.964171 Zerofication rate: 286297/1355194=0.211259
マージンパーセプトロンは，マージンがとても大きい場合は，ほとんど常に更新するので，マージンが十分に大きいところでは確率的勾配降下法(SGD)と同じ更新をする．ただし，今回は学習率は1.0で固定であるが，SGDは段々学習率をイテレーション回数に反比例する形で減衰させることが普通である．しかも，SGDでは重みベクトルを0に引き戻す作用をする正則化項を入れることも通常行われるが，今回はいれていない．
$ ./perceptron_binary news20.train news20.test 10 100.0 Accuracy: 4472/4996=0.895116 Zerofication rate: 67953/1355194=0.0501426 $ ./perceptron_binary news20.train news20.test 10 1000.0 Accuracy: 3958/4996=0.792234 Zerofication rate: 68017/1355194=0.0501899
失敗する場合だけでなく，正解した場合も常に重みベクトルを更新すると，このように，精度ががた落ちになり，しかも，ゼロ化率も低くなってしまうことが分かる．
