二値素性でのオンライン学習の実験まとめ

研究

複数のオンライン学習のライブラリについて，線形学習と多項式カーネルの学習の詳細な実験結果（構文解析タスクと関係抽出タスク）を学習器の公開ページに追加した．今までの実験のまとめ的な内容になっている．オンライン学習は，訓練例を shuffling をするように統一して実験したら，ライブラリ間の速度差が少し縮まった．分類時間にはモデルの読み込み時間も入っているが，多項式カーネルではモデルの読み込みに時間がかかる分（と言っても100msec.とかだけど），特にテスト例数が少ない関係抽出タスクの実験セットで（線形学習に比べて）やや不利となっている．
幾つか分かったこと

  • PA-I は averaging すると，繰り返し数を固定した場合の C の最適値が変わって，より少ないサポートベクタ数で同程度以上の分類精度が出せる．SVM よりサポートベクタ数が多くなりがちな PA-I にとっては良い特性だと思われる．
  • averaged PA-I（繰り返し20回）と SVM が最高精度を競い合っている感じ．L1 正則化系の学習は大体精度が劣化する．有効素性数が減っても平均発火素性数が減るとは限らないので，分類は大して速くならないことが多い．L1 正則化を使わなくても，例えば省メモリでモデルを学習／テストする方法はあるしで，個人的には L1 正則化自体にあまりメリットを感じないのだけど．Representor Theorem によりカーネル化可能な L2 正則化だけでいいのではないかと．
  • CW は全然ダメ（特に構文解析タスクでは），AROW は少しましで，関係抽出タスクの方では Averaged Perceptron に勝っている．CW は訓練例にノイズが多くなると精度が劣化しやすいようだけど，よりアノテーションのノイズが多そうな関係抽出タスクの方で差が小さいのは不思議だ．共分散行列を対角に近似した実装のみと比較したのだけど，構文解析タスクでは素性間の依存関係が強いのでこの近似があまり良くないのかも知れない．しかし，素性数が多いドメインだと，そもそも近似しないとメモリ的に苦しくなりそうなので，実際に動かすには少し工夫が要りそうだなぁ．Transition-Based Parsing with Confidence-Weighted Classification でも同じような結果が出ているが，他言語では CW~SVM となっている．ただ，中の人に聞いた限りでは，SVM は学習が重いのであまりパラメタチューニング出来なかったと言っていたので，世の中の人が言うほど CW 万歳ではないのかもしれない．
  • 二値分類向けの最適化は大事．内積取るのに浮動小数点数の演算が入らなくなったり，カーネル関数の結果をキャッシュできたり，データサイズが減ってキャッシュが効きやすくなったりと，あちこちでボディブローのように効いてくる（学習器の場合，体感で2倍以上は差が出る）．古典的な TinySVM が（載せてないけど）SVMlight や LIBSVM より速いのは，二値素性向けの最適化が効いているからだと思う．
  • 線形学習だと，（昔言ったのと逆の言い方だけど）LIBLINEAR が精度の安定性や速度面で強過ぎて半端なオンライン学習を実装してもあまり意味が無いかも知れない（というか，オンライン学習を，単に高速な学習手法としてでなく，モデルの追加更新など，バッチ学習自体が出来ない状況で使っている人ってどれぐらいいるのだろうか）．LIBLINEAR-poly2 の実験も入れようと思ったけど，素性数が多いデータでは，訓練データ中の素性番号を密にして，さらに配列の添字を 64bit に書き換えないといけなかったり（そして密にしても 16G とかメモリを食う）で取り敢えず棚上げ．CW の共分散行列の実装とも関係するけど，機械学習畑の人って，素性数が極端に少ないか，極端に多いか，二つの状況しか想定していないような気もするなぁ．
  • Averaged Perceptron はパラメタが繰り返し数のみで，かつ安定して動き，収束も速いので，一家に一台は持つべき．シンプルと言えば，Winnow とかもあるけど，どうなのかな．
  • 最後に．IO を侮るなかれ．アルゴリズムの計算量ばかりが頭にあると，痛い目に会う（会った）．C++ で STL 使うなら，手元のコンパイラの実装ぐらいは，さらっと目を通しておいても良いと思う．

さて，と．次いくか．
[追記] LIBLINEAR-POLY2 と SVMlin を結果に追加した．LIBLINEAR-POLY2 は以前の結果とほぼ同様の結果．素性数が30万の訓練データでは動かなかった（400GBぐらいメモリがいるはずなので仕方ないが）．SVMlin は LiBLINEAR の10倍程度遅いぐらいだけど，半教師あり学習などをサポートしているのは良い感じ．libcvm は Windows しかサポートせず（なんだそれ），と．
[追記] libarow を結果に追加した．モデルを保存しないでテストする割り切った仕様．分類結果を出力しないので，分類結果を利用したい人は少しハックする必要はあるけど，オンライン学習系のライブラリでは（今回自分が公開したもの以外では）一番速そうだ（というか，Random Feature Mixing が入っている関係で，モデルを保存すること自体が微妙という話も）．素性番号の代わりに文字列を使えて，さらに Random Feature Mixing でメモリを節約できるのは使い勝手が良さそう．文字列→素性へのマップには，MurmurHash 2.0 を使っているようだ．ハッシュ値を引くのは速そうだけどハッシュ値が散らばり過ぎてキャッシュが効きにくくなるような気がする（以前自分のライブラリで試したときは FNV-1a に比べて遅くなった）．