NLP2011に参加してきました - 射撃しつつ前転改

　もう一ヶ月以上も前の話になりますが、2011年の言語処理学会年次大会で、かな漢字変換について発表をしてきました。
　日本語入力についてのテーマセッションが用意されているということで、発表申し込みをしようかどうか迷った挙句、仕事が忙しいからあきらめたのですが、〆切前日にG社の方から「明日が〆切なのでよろしく」的なメールが来て、そんなに申し込みが少ないなら出すか…ということで発表してきました。蓋を開けてみたら2セッション分の発表があって割と大人気だった訳ですが、こんな機会がないとなかなか会わないような人にたくさん会えたので、結果的には行ってきて良かったです。
　発表に関しては会社ブログの方に既に資料を上げたので、こちらでは実装の細かいところの話をちょっと書いてみたいと思います。
　資料にも書きましたが、構造化SVMをFOBOSで最適化する場合、

正解パスへはペナルティを与えつつ現在のパラメーターで変換してみる
変換できたら何もしない、変換できなかったらパラメーターを更新する

　という手順になります。学習の速度のことを考えると、実際に変換してみるというところがボトルネックで、つまり、秒間に何文ぐらい変換できるか、というのが非常に重要な数字になってきます。結論から書くと、今回の実装ではいろいろ頑張りすぎたせいで、850文/secぐらいの速度で変換できるようになりました。Sandy Bridgeなら1000文/secぐらいはいけると思います。京大コーパスには結構長い文も含まれていますから、これはなかなかの速度だと考えています。
　変換の際にはビタビアルゴリズムを使うことになりますが、その中で、バイグラムコストを求めてくるところが計算量的には一番重いところです。プロファイルをとってみると一発でボトルネックなのがわかるぐらいで、だいたい8割以上の時間がここに費やされます。今回は単語バイグラム素性を使ったので、特に問題でした。
　バイグラムコストを求めるとは言うものの、実際にはなにかその場で計算をする訳ではなく、データ構造に突っ込んでおいたコストの値を取ってくるだけなので、問題としてはどういうデータ構造が速いのか、というものになります。
　単語バイグラムを素性として使う場合、バイグラムの時点で既に素性空間が広くなりすぎるので、二次元の配列で持つというのは現実的ではありません。いや、最近のハイスペックマシンだと結構現実的だったりしますが、今回はそこまでメモリが潤沢には使えませんでした。
　そうなると、残りの選択肢としては、ハッシュテーブルに突っ込むか、もしくは動的ダブルアレイに突っ込むか、私の技術力的にはこの2つに絞られます。
　動的ダブルアレイはバグったときにデバッグが大変（過去に体験して非常に辛いことがありました…）なので、〆切までのスケジュールがタイトな今回はハッシュテーブルを使うことにしました。
　ハッシュテーブルは、まずはglib付属のg_hash_tableを使っていたのですが、あんまり速くないし改造も面倒な感じだったので、他のものをいくつか当たってみることにしました。
　次にあたったのはC++のtr/unordred_mapでしたが、これはglibより遅く、論外でした。stringじゃなくてchar*を使えばよかったのかもしれませんが、そうするとメモリ管理がまたずいぶんと面倒になってしまうので、それ以上の改良は断念しました。
　次に、libghthashというハッシュテーブルを使ってみました。これはハッシュ関数が取り替えられたりできるし、glibと違って改造しやすかったので、こちらを使うことにしました。
　いろいろ試行錯誤をしたのですが、最終的には以下のような改造をしたlibghthashを使っています。

ハッシュ関数はone at a time hashをベースに、削っても大丈夫そうなところを削ってみたオリジナルの適当関数を採用
ハッシュテーブルから値を取り出すところは、すべての関数をヘッダファイルに移してインライン化
テーブルの空き領域を増やして、探索失敗を高速化

　ハッシュ関数はFNVとかmurmurハッシュとか試してみましたが、最終的には適当な奴が一番早い、という結果に落ち着きました。あまりシンプルなハッシュ関数にし過ぎると衝突確率が上がって却って遅くなるといったトレードオフあり、興味深い体験でした。
　インライン化は非常に重要で、これで20〜30%ぐらいは速度が稼げます。二重ループの中で呼び出すので仕方ないですが、抽象化と高速化は時に両立しない、というやや残念な結果になってしまいました。
　その他、ハッシュテーブルを2重にするといった実験もしてみましたが、あまり良い結果を得られませんでした。もっとも、これに関してはあまり追求していないので、もしかしたらうまく高速できたかもしれません。
　また、姑息な高速化として、IDが小さい部分に関しては二次元配列に値を保存するという工夫を入れたところ、数百MBのメモリと引換に、そこそこ高速化ができました。10%ぐらいだったかな？
　論文にはさらっと「学習時間は8分30秒程度であった」と書いてありますが、その影にはこのような苦労があったわけです。しかし、学習が10分程度で終わるのであれば、そもそもここまでシビアに高速化を行う必要はありません。特に改良をせずとも、当初のナイーブな実装で、おそらく30分以内ぐらいに学習は終わっていたでしょう。
　これにはおまぬけな事情があります。実は、バグによって変換時間がすごく長くなっており、その本質に気づかなかったせいで、ある意味では無駄な努力を高速化につぎ込んでいたのです。ビタビアルゴリズムではゴールまでたどり着く経路が一つ以上は必要ですから、グラフの構築時に入力文字そのままのノードをオンザフライで追加していたのですが、関数呼び出しのフラグを間違えていて、このオンザフライのノードを辞書にまで追加してしまっていたのでした。しかも辞書エントリに重複が許されていたものですからひらがなが辞書に大量に追加され、結果として辞書まわりの操作コストすべてが急上昇していたのでした。このバグの効果は劇的で、コーパスに対して1回の学習ループを回すために3日間以上の時間が必要でした。変換結果そのものには影響がでないので、どこにバグがあるのかがわかりづらく、厄介でした。
　その他、実装でつまづいたを細々と点を挙げておきます。
　今回は、素性を抽象化して扱いたかったので、ハッシュテーブルのキーとしては64bitの整数を使うことにし、その上位4bitを素性の種別として使い、残りの60bitを素性IDとして使うことにしました。これは最初に実装する方法としては、あまり良いやり方ではありませんでした。結局、この素性の抽象化の部分ではバグはなかったのですが、うまく動かないときにはこの抽象化の部分も疑わざるを得ず、しかも正しく動いていることを確認するのが難しいので、無駄に手間を取られてしまいました。後知恵ですが、まずはもっと分かりやすく、素性は分かりやすい文字列で表現すべきでした。そちらで正しく動くことが確認できてから、高速化実装を作ったほうが、結果的には早く実装を終わらせられたでしょう。
　また、メモリ管理が非常に面倒でした。グラフ構築時にひらがなの経路を追加していたわけですが、このために辞書が返すメモリ領域がフリーしてはいけないものとフリーしないといけないものの2種類があり、原理的にはその2つはコードパスで区別でき、うまく処理できるはずだったのですが、ダブルポインタ、トリプルポインタが乱舞するようになると自分の管理能力を超えてしまい、うまく動きませんでした。結局、変換時に一時的に確保するメモリは変換終了後に一気に開放できるようにバッファクラスを作って、メモリはそちらで管理するようにしたのですが、これはよく考えてみたらメモリプールそのもので、自分で作らずにaprとか使えばよかったなと、これも後知恵で思いました。
　高速化自体は楽しい作業ではありましたが、予稿提出の一週間前はまだまともな数字が出せていないという状態で、正直なところ気が気ではありませんでした。間に合って本当に良かった。