Passive Aggressive と多項式カーネル
Passive Aggressive で陽に多項式カーネルを展開した場合 (explicit) の速度劣化について調べてみた。訓練データ約30万例、平均発火素性数27ほどのタスクで20回ほど学習のループを回すと、
d | C | PKI | explicit | speed-up | |SV| (PKI) ---------------------------------------------------------------- 0 | 0.005 | NA | 1.09s | | 1 | 0.005 | 11684.02s | 7.75s | x 1444.8 | 107354 (107390) 2 | 0.0001 | 10067.15s | 91.35s | x 110.2 | 94490 (94480) 3 | 0.000005 | 9106.61s | 1247.02s | x 7.3 | 89032 (89072) on core2 3.2Ghz; compiled with gcc (4.5.0) -O2 -march=core2
なお、計算方法によってサポートベクタの数が僅かにずれるのは丸め誤差のため。等価なサポートベクタは重複して追加されないようにチェックしたり、内積の値→カーネル関数の計算を配列で持っておくなどの自明な最適化は適用済み。メモリは PKI で 100M、explicit の d=3 で 1.3G ほど消費。このタスクでは C を小さくとって繰り返しを増やすことで、実際には精度をバッチ学習より高くできるのだが、繰り返し回数を揃えた関係で d=2,3 は SVM より 0.1% ほど精度が低くなっている。ちなみに explicit (d>=1) では、重みベクトルの保存／更新に std::tr1::unordered_hash (FNV-1) を使っている関係でキーへのアクセスが最低二回発生してしまうが、これを一度で済む動的ダブル配列などに変えれば、速度を2倍、メモリを1/3ぐらいには出来そうだ。
バッチ学習だと SVM (~implicit)で約数日、ME (~explicit) で約1日かかるので、カーネルを直接使った場合でもまだ速いのだけど、メモリが少なくて済む利点はあるとは言え、ME の10倍しか速くないし、d=0 に対して目に見えて速度劣化しているのでなんとか速くしたいところ。というわけで速くなって良かった。
その他、任意のカーネルに対して高速化するなら、キャッシュを使うという手もある。例えば
カーネルキャッシュ: 各 example と各サポートベクタの内積の値(または上のカーネル関数の適用結果)を保持しておく。重複するサポートベクタをまとめた際に重みが変わっても適用できるのは良いが、学習データが大きいと全てキャッシュするのは厳しいか。仮に全てキャッシュできれば素性ベクトルの長さ倍ほど高速化できることになる。学習データのサイズに比べて、素性ベクトルの長さが長いときには有効かも。上のタスクだと、学習データが多過ぎて10G以上メモリを消費する上にメモリ確保のコストが大き過ぎて現実的ではないが、学習データが10000件ぐらいだと結構速くなる感じであった。forgetron や randomized budget perceptron など軽めの budget 系のアルゴリズムでサポートベクタ数を抑えれば動くかな？
マージンキャッシュ: 各ループでの example のマージンを、前回のループのときのマージンと以後追加されたサポートベクタに対するマージンの和で計算する。各ループで誤分類する(Passive Aggressive なら十分なマージンの無い場合も) example が劇的に減っていく場合には有効だけど、これは C で重みをバウンドされるサポートベクタが多いときにはあまり期待できない。重複するサポートベクタをまとめられないのでメモリ効率的に痛いし、PKI と組み合わせるときは二分探索のオーバーヘッドもかかる。実際、上のタスクで実際やってみると以下のような感じでそれほど速くならない。
d | C | PKI | + mcache | speed-up | |SV| -------------------------------------------------------- 1 | 0.005 | 11684.02s | 7923.78s | x 1.5 | 1586415 2 | 0.0001 | 10067.15s | 4943.27s | x 2.0 | 1135350 3 | 0.000005 | 9106.61s | 4306.30s | x 2.1 | 997658
メモリはサポートベクタの重複を取らないのが大きく 200M ほど消費。
[追記] 参考のため、Perceptron だとどうなるか調べてみた。上と同じ条件で試した場合。
d | PKI | + mcache | explicit | speed-up | |SV| (PKI, + mcache) ------------------------------------------------------------------- 0 | | | 1.09s | | NA 1 | 9607.51s | 3947.32s | 6.28s | x 1529.9 | 99996 (99996, 786730) 2 | 6218.44s | 1701.63s | 69.70s | x 89.2 | 77419 (77419, 358670) 3 | 6648.55s | 1093.32s | 944.02s | x 6.6 | 72322 (72255, 228353)
新規に追加されるサポートベクタが少ない関係で、マージンキャッシュの効果が上がっているものの、3次でもまだ展開する方が速い。explicit と PKI でサポートベクタの数があまりずれないのは、重みを -1, +1 で更新するため丸め誤差の影響をほぼ受けないから(3次でずれている理由は良く分からないが)。projectron++ を実装した関係で 0.03s ほど変数の初期化の overhead が増えています。
