多クラス Passive Aggressive アルゴリズムの平均化
先日実装した多クラス Passive Aggressive アルゴリズムに平均化を実装してみた．コードは
を参照．実装したと言っても大したものではなく，本質的には追加したのは4行（USE_AVERAGING で囲われたところ）．平均化すると，収束を待つ必要がなくなるので，繰り返し回数を 20->5 に変更して実験．
# MacBook Air (Mid 2011); Intel Core i7 1.7 Ghz CPU, 4 GB Memory
> g++ -DUSE_AVERAGING -std=c++0x -Wall -O2 spa.cc -o spaa
# covtype
> run spaa PA1 covtype.train covtype.test 0.1 5
read: 0.827s
train: .....0.965s
test: 0.073s
class 1 2 3 4 5 6 7 precision
1 12720 4460 0 0 2 0 713 17895 (0.711)
2 5084 19477 338 0 784 372 11 26066 (0.747)
3 6 319 2663 131 24 797 0 3940 (0.676)
4 0 1 41 83 0 9 0 134 (0.619)
5 0 16 0 0 4 0 0 20 (0.200)
6 4 81 130 19 1 279 0 514 (0.543)
7 392 27 0 0 0 0 1012 1431 (0.707)
18206 24381 3172 233 815 1457 1736 50000
recall (0.699) (0.799) (0.840) (0.356) (0.005) (0.191) (0.583) (0.725)
elapsed (real): 2.209s; RSS=123.3M
# mnist
> run spaa PA1 mnist.train mnist.test 0.005 5
read: 1.143s
train: .....0.700s
test: 0.186s
class 0 1 2 3 4 5 6 7 8 9 precision
0 966 0 5 2 1 10 10 2 5 10 1011 (0.955)
1 0 1115 7 0 2 2 3 5 8 6 1148 (0.971)
2 0 3 930 19 3 2 3 24 5 1 990 (0.939)
3 1 2 14 925 2 32 2 8 17 9 1012 (0.914)
4 0 0 8 0 914 10 9 6 9 26 982 (0.931)
5 1 1 4 20 0 771 17 1 28 9 852 (0.905)
6 7 4 13 3 13 16 910 0 10 0 976 (0.932)
7 2 2 9 12 3 8 2 953 10 19 1020 (0.934)
8 3 8 37 21 10 35 2 4 877 9 1006 (0.872)
9 0 0 5 8 34 6 0 25 5 920 1003 (0.917)
980 1135 1032 1010 982 892 958 1028 974 1009 10000
recall (0.986) (0.982) (0.901) (0.916) (0.931) (0.864) (0.950) (0.927) (0.900) (0.912) (0.928)
elapsed (real): 2.135s; RSS=156.8Mcovtype の方では顕著に分類精度（0.716 -> 0.725; liblinear 1.8: 0.722）が上がった．mnist の方は上がっていないが，そもそもパラメタのチューニングがズル（テストでチューニング）なので，あまり議論しても仕方がない．
Passive Aggressive では（学習されるモデルの）分類精度という観点では平均化は（Perceptron におけるそれほど）必須ではない*1が，収束を待つ必要がなくなり訓練時間を削減できるという旨みの他に，ハイパーパラメタの影響が小さくなったりと，結果のモデルを「鈍らす」効果があるので，トータルの実験時間を減らしたい場合は基本使うようすると良いと思う．
IO がボトルネックなのは見ての通り．標準の訓練データのフォーマット
label(?: feature_index:feature_value)*\n
から読み込む限り，これ以上大きく速度を改善するのは難しい（少しはできる）．なので，ハイパーパラメタを変えて何度も学習を繰り返す場合には，
のように，訓練データをバイナリ，あるいは符号化してディスクに保存して使う方が良いだろう．
