やっと出たのか

1月に試した liblinear-poly2 の論文 Training and Testing Low-degree Polynomial Data Mappings via Linear SVM が JMLR でも公開されてた．少し内容が変わってる？気のせいか．
liblinear-poly2 は組み合わせ素性の重みが配列で実装されている関係で，素性数が多いデータで実験するとえらいことになる．論文ではハッシュを使う方法を提案してるけど，良いハッシュ関数を使うほど完全なランダムアクセスになるので，「ちゃんと実装した」動的ダブル配列を使った方が良い（頻度降順で素性番号をバイトコーディングしてループで組み合わせ素性を列挙すると，ほとんどキャッシュに載った配列アクセスと同じになるため）．また全展開してしまうと，ハッシュを使っても，3次（以上）で動かすのは大変．この問題を解決した論文（今年の某全国大会）を出したときにこの論文を参照しておけば良かったかな．
[追記] 配列 v.s. (静的/動的)ダブル配列 v.s. ハッシュ（トライ）
2次の組合せ素性の列挙で実験してみた．配列 (0.222s) < (静的)ダブル配列 (0.326s) < (動的)ダブル配列 (0.370s; 0.385s; 0.395s; 0.417s) < ハッシュ（トライ） (0.543s; 0.673s; 0.724s; 0.788s) だった．ただし，重みDBの構築時間は含んでおらず，値を取得するだけで追加／更新はなし，また(静的)ダブル配列は darts-clone (0.32f-rc2) で列挙に別コード（分類器のライブラリ）を利用．キャッシュ効率を改善するために，動的ダブル配列とハッシュ（トライ）では最初に列挙する素性ごとに別のトライを作った場合 (|f|~2^16)，16 のトライに振り分けた場合 (ceil log_2 f)，3つのトライに振り分けた場合 (ceil (log_128 f)) の結果も載せた（一つ目，二つ目，三つ目の結果）．しかし配列速いな〜．