LIBLINEAR と oll

最近よく使われているのを見かける LIBLINEAR と oll (PA-I) を比べてみた．いつものタスク，学習サンプル数: 296,776，平均発火素性数: 27.6, 学習データサイズ: 62,412,806 bytes, 二値素性のみ．テストサンプル数: 60,766, 平均発火素性数: 27.6, テストデータサイズ: 12,789,886 bytes.
LIBLINEAR は全てのパラメタ推定法 (s=0-6)，oll は繰り返し回数 (I) 20回と50回で試してみた．LIBLINEAR / oll とも c = 1.0, 0.5, ..., 0.005, 0.001 辺りを試して，一番分類精度の高かった c を利用．その他のパラメタはデフォルト (データは事前にランダムシャッフルし，テストでは LIBLINEAR に合わせて label か margin をファイルに出力するようにした)．pa (手元のPA-I実装) のみ，c を下げて繰り返しを増やした結果を載せておく*1．LIBLINEAR は最も高速だったパラメタ推定法と，得られたモデルが最も高精度だったパラメタ推定法の結果をそれぞれ載せた (各 s について c を変えて，最高精度の得られた c で，速度／精度を比較)．

(12/05 18:30 再実験)
             |LIBLINEAR c=0.5|  oll c=0.005  |   pa c=0.005    c=0.001
             |  s=5     s=3  |  I=20   I=50  |  I=20    I=50   I=250 
-------------+---------------+---------------+-------------------------
ACCURACY (%) | 90.78 | 91.05 | 90.85 | 90.88 | 90.85 | 90.88 | 91.05
TRAIN (sec.) |  4.39 | 11.91 | 15.16 | 16.44 |  1.14 |  1.79 |  6.09
TEST  (sec.) |  0.38 |  0.39 |  3.12 |  3.12 |  0.13 |  0.13 |  0.13

on Intel core2 3.2Ghz; compiled pa with gcc (4.5.0 200091126) -g -O2

oll と pa で I=20 と I=50 の学習時間の差をとると，繰り返し部分に約2倍の速度差があるが，これは単に pa が二値素性専用の実装になっているから (なので，pa はちょっとズル)で，後は IO の差．この辺りを考慮して，oll と pa の IO を入れ替えてみれば，LIBLINEAR は SVM としては確かに速いけど，同程度の精度のオンライン学習ほどではないし (この速度のレンジだと速いも遅いも無いけど)，精度も変わらないので，このタスクでは特にメリットは無さげ．SVM はカーネルがあってこそという気もするし，LIBLINEAR の立ち位置はそもそもやや微妙な感じがする．

あとは，log-linear model を SGD (Stochastic Gradient Descent) で学習するというのもあるけど，SGD を使う時点でバッチ学習が持つ安心感は薄れるので，L1 正則化を使える (有効素性数を減らせる) ぐらいのメリットしか無い・・・*2．

*1:PA-I は，学習速度／分類精度の制御が比較的容易なので便利．c は update の上限として使われるので，(ものすごくおおざっぱに言えば) I=10 ぐらいで c をチューニングして，その後 c を 1/n にして，I を n 倍にすれば，簡単に高精度化できる．多項式カーネルを使う場合は，c を高次写像空間での発火素性数に反比例するようにスケーリングすれば大体 ok (ただし，素性ベクトルのノルムや，カーネル関数の値を正規化しない場合)．LIBSVM の c は，PA の c に繰り返し回数をかけた値が目安になる．

*2:ちなみに同じ学習データを用いて OWLQN と SGD で L1 正則化 log-linear model を学習すると，得られたモデルは有効素性数は同程度なものの，平均有効素性数は後者が前者に比べてかなり少なくなる傾向があり，分類速度という点でメリットがある感じだった．何でこうなるの．