オンライン学習でキャッシュを実装してみた
手持ちのオンライン学習器で訓練データをメモリに載せず処理するモードがオンメモリで処理するモードに比べて5倍ぐらい遅いのが気になったので，Vowpal Wabbit みたく訓練データをキャッシュしてみることにした．まず準備として，Simple-9 と Variable byte code (vByte)，さらに binary でそのまま保存する場合 (Raw) に，訓練データの符号化（入出力込み）／復号化 (入力のみ込み) の性能を比較してみた．普段使っている訓練データをx100倍したもの (約3000万訓練例, 819,841,000 integers) を入力．Disk Cache の扱いがいい加減だったので，再実験した．さらに，Group Varint Encoding の結果も追加した．
素性番号を適当につけた場合 (5952MiB)
| Simple-9 | vByte |Group vInt| Raw | ------------------------------------------------------------------| Encode | 81.066s | 68.853s | 70.527s | 81.601s | Decode w/o Disk Cache | 8.316s | 8.357s | 8.348s | 21.274s | Decode w/ Disk Cache | 5.153s | 6.947s | 5.645s | 5.875s | Cache Size | 1264MiB | 1110MiB | 1269MiB | 3354MiB |
頻度順につけて密にした場合（素性ベクトルを表現する差分リストで，前半の多くの差分値が1になる; 3924 MiB）
| Simple-9 | vByte |Group vInt| Raw | ------------------------------------------------------------------| Encode | 58.743s | 56.112s | 58.878s | 72.033s | Decode w/o Disk Cache | 5.932s | 6.798s | 7.973s | 20.139s | Decode w/ Disk Cache | 4.141s | 5.143s | 5.697s | 5.909s | Cache Size | 679MiB | 959MiB | 1134MiB | 3354MiB |
実験に使ったのは 32GBのメモリを積んだ 3.2Ghz の Mac OS X サーバ．
Simple-9 は素性番号のつけ方で大きく性能が変わるので（符号化方法の選択戦略にもよるかもしれないが），この用途だとやや使いにくいか．この分だと，PFor系 も駄目かも．vByte は Raw に比べてキャッシュサイズが 1/3-1/4 程度で済むようだったので（Raw のキャッシュは svm-light 形式の元データの6割程度のサイズ），実装の手間を考えると，この中では vByte が良いな（Vowpal Wabbit のキャッシュの実装も確か vByte だった気がするが）．後は，Group Varint Encoding とかか（特許が気になるけど）．
で，学習器に vByte で符号化するキャッシュを実装してみたら，オンメモリ版の2倍弱の時間で学習ができるようになった（学習前に purge して Disk Cache をキャッシュ）．多項式カーネルを用いた学習は，I/O がそもそもボトルネックじゃないのでほとんど学習時間は変わらず（素性番号を密にマップするのが高速化に大きく寄与するため，最初に訓練データを符号化してディスクに保存しつつ素性番号のマップを作り，一回目の繰り返しは，訓練データを変換して再保存しつつ学習するようにした）．
上で I/O の観点で大きく不利な Raw が一番デコードが速かったことから分かるが，復号部の速度をいかに速くするかが今回は大事だったようで，前の実装が遅かったのは，要するにテキストデータから素性ベクトルへの変換（低速な I/O 含む）にボトルネックがあったということのようだ． これは追記で載せた SSD な LINUX マシンでの結果．ディスクキャッシュに載らないほどのサイズのデータを使うときは，やはり何らかの符号化を試すべき（その方がディスクキャッシュも効きやすくなるだろうし）．
あとは，オンメモリ版とオンディスク版でシャッフリングを同じようにできないのが気になるところ．以前オンディスク版のシャッフリングは考えたことがあるが，オンメモリ版で一番素直な random_shuffle と同じシャッフリングをするのはちょっと難しいので，オンメモリ版の方をオンディスク版のアルゴリズムに合わせるのが良いのかな．
[追記] ボトルネックは，Disk への出力を伴う Encode 部（キャッシュを Disk に保存するところ）にあるようなので，繰り返し回数が極端に多くない限りは vByte で十分そうだ．ちなみに，256GBのメモリを積んだ SSD な LINUX サーバで実験すると，結果の傾向が大きく変わる (purge の代わりに sudo sysctl -w vm.drop_caches=3 で Disk Cache をクリア)．
素性番号を適当につけた場合 (5952MiB)
| Simple-9 | vByte |Group vInt| Raw | ------------------------------------------------------------------| Encode | 51.690s | 43.290s | 45.210s | 49.172s | Decode w/o Disk Cache | 4.547s | 6.817s | 4.804s | 6.404s | Decode w/ Disk Cache | 4.304s | 6.840s | 4.721s | 3.473s |
頻度順につけて密にした場合（素性ベクトルを表現する差分リストで，前半の多くの差分値が1になる; 3924 MiB）
| Simple-9 | vByte |Group vInt| Raw | ------------------------------------------------------------------| Encode | 36.375s | 32.750s | 35.072s | 40.403s | Decode w/o Disk Cache | 4.079s | 5.307s | 6.033s | 5.865s | Decode w/ Disk Cache | 3.748s | 4.985s | 5.069s | 3.509s |
興味深いのは Disk Cache が効いている状況で Raw が最速になっていることと，Disk Cache の有無の影響があまりないこと（SSD ＋メモリの性能差のためか）．
[追記] Group Varint + vByte (Group vInt) の結果を足してみた．大体 Information Retrieval – Addenda: Index Compression と一緒の結果．Group Varint は，キャッシュサイズが大きくなる関係で，訓練データをメモリに載せないような状況（Disk Cache が使えず，Disk I/O がボトルネックになるような状況）では，vByte より必ずしも良いとは言えなさそう．Simple-9（あるいは PFor）の Encode がもう少し速ければなあ（転置インデクスの文脈では，この部分の時間は重要視されないのだよな）
最後に，その他幾つか注意しないといけないことをメモ
- Simple-9（あるいは PFor）だと扱える素性数に上限 (Simple-9 だと 28bit) ができる
- Group Varint Encoding だとマシンのバイトオーダに依存しないコードを書くのが難しそう
