SIMD で線形分類器を省メモリ・高速化
公開している構文解析器と線形分類器のコードを更新した．（論文にするほどではないが）幾つか面白い結果が得られたのでメモ（どちらかというと構文解析器の更新が主だけれど，良いタイトルが思いつかなかったので線形分類器の更新内容をタイトルにした）．
構文解析器の実装は C++ に慣れる前に書き始めたもので，効率重視で継ぎ接ぎの変更を繰り返して，色々と見苦しいことになっている．幸い，全体で 2000行足らずと身動きが取れないほどのサイズでもないので，効率を落とさないよう注意しつつ，リファクタリング（というかコードの短縮化）を繰り返してきた．今回の更新では，if-else だらけで読み難い素性抽出のコードを書き直して条件分岐の数を大幅に削減した．変更については長くなるので末尾．
コードも整理されたので，気分転換に素性選択を一日ほどしてみた．標準的なデータセットにおける一回の学習・テストが MacBook Air (Mid 2011) 上で1分を切っているので，網羅的な素性選択も気軽にできる．公開している構文解析器は精度だけでなく速度も売りなので，闇雲に素性を追加するのはやめて，開発データで精度向上／速度低下の観点で最も割の良い素性セットを探索*1．開発データの解析結果を眺めていたら，簡単な並列句の解析を失敗する例が目についたので，局所的な並列句を同定する素性を3つ入れてそれらを含めて素性の取捨選択をしたところ，最終的に 10% 程度の速度低下で精度を 0.2%（文正解率で 0.5%）ほど上げることに成功．この精度についてはいずれどこかで報告しておいた方が良いような気もする．
もう一つ大きな変更として，注釈のみで公開されている某新聞コーパスから元テキスト無しでも学習できるようにした．注釈だけといっても読みはついているので表層文字列の代わりに読みを素性に使って素性抽出．解析精度に大きく影響するのは機能語の表層なので読みだけでも良いモデルが学習できるだろうとは思っていたが，精度が（表層から学習したモデルと） 文節区切りでも係り受け同定でも 0.1% 程度しか変わらなかったのには軽く驚いた*2．しかし，この学習で得られたモデルのライセンスはどうなるのだろうか．有償の元データを学習に使っていないので得られたモデルの使用上の制限は少ない感じはするが，いまいちよく分からない．いずれにせよモデルの配布は話が色々とややこしそうなので，配布はせずコンパイル時に学習するようにしているのだけど，誰か詳しい人教えてくれないかなぁ．例えば，有償のコーパスを使って学習したモデルで解析したテキストから再学習したらそのモデルのライセンスはどうなるのだろうか？
今回の素性選択で少し発火素性数が増えた関係で，3次の多項式カーネルを用いた場合の学習時間が8分→10分と増加してしまったので，線形分類器の方も何とか高速化できないか考えてみた．以下
で SIMD 試してみたいなと思っていたところだったので，ちょっと思案して
を参考に，高頻度・密な素性ベクトル*3の内積を SSE4.2 の POPCNT 命令（なければ table 引き）を利用して行うようにしたところ，学習時間は10分→7分と素性選択前より短くなった．一方で分類器の方は速度を落とさずメモリ消費を減らすことができるようになって，一挙両得．論文になるかどうかはともかく，今後さらに高速化するためには SIMD （というか SSE）は避けられないように感じた．深い沼があるような感じで，研究者としては上手につき合いたいが・・・
[追記]実装の一部を最適化したら，さらに 25% ほど速くなった．
[余談]素性抽出のコードを整理している途中で，
#include <iostream> class M { private: int val_; public: M () : val_ (0) {} int val () { return this ? this->val_ : -1; } }; class B { private: M* m_; public: B () : m_ (new M) {} M* m () { return this ? this->m_ : 0; } // * }; int main () { B* b0; std::cerr << b0->m ()->val () << std::endl; return 0; }
こんなコードを書いたのだけど，これは C++ の規格では結果は不定となるらしい (gcc-4.8 -O2 では意図通り動くが clang-3.2 -O2 だとコケる)．
仕方がないので，* で 0 の代わりに M m0; なる例外用のインスタンスを返すようにした．
*1:構文解析は精度向上だけに集中すれば（例えば解析器をスタッキングするとか） 精度を1%以上上げることもできるけど，解析器のスタッキングは長所だけでなく短所も組み合わせることになり実用的には魅力を感じない（今の場合は，速度が「劇的に」低下する）．
*2:この読みは既存の形態素解析器で自動付与したものであてにならないと聞くが，素性として使う分には学習時と解析時で素性（の抽出源）に一貫性があれば，その抽出源に誤りがあるかどうかは必ずしも問題にはならない．余談ながら，構文解析のような問題を部分問題にバラしてパイプラインで解くのは，前段の解析結果の誤りが伝搬するから良くない（だから同時に解くのが良い）と主張する研究者が結構いるのだけど，出力に直接関与するところ（文節区切り）を除けばこれは必ずしも正しくないと感じている．テスト時も学習時もどちらも前段の解析結果から素性抽出すべきところで，学習時のみ人間がつけた注釈から素性抽出していては精度が下がるのもある意味当然．人間が恣意的に作ったタグ付け基準の観点からみて誤りがあったとしても，そこから分類上役に立つ素性が抽出できないということには必ずしもならない（例えば，クラスタ素性などを考えてみると良い．自分の分野では，実際に解く問題に関する注釈以外にも多様な注釈がついている場合が多く，良くも悪くもみんなそこに引っ張られて研究をしている印象．注釈は手段）．そういう意味で誤りを含む読みから素性を抽出して学習した構文解析器も，その読みを自動付与した形態素解析器と組み合わせる限りにおいては，問題なく使えるのではないかな．
*3:素性を頻度順に並び替えてIDを振り直しているため，全体としては疎だが部分的に密になっている．
