自然言語処理のコードリーディング

今週は ACL という自然言語処理最大の国際会議がスウェーデンで開催されているのだが、自分は行かない(行けない)ので代わりに今日の勉強会では

を読んでみる。

CRF というのは形態素解析(分かち書き、品詞タグづけ)や固有表現抽出でよく使われるアルゴリズムで、タグをつけるために使う情報(素性)を柔軟に設計できたり、それまでの理論の発展系になっていたり、近年これらのタスクではほぼデファクトスタンダードとして使われている技術である。

しかしながら、CRF は計算量が重い(出力するタグの数に依存)という欠点があり、これを回避する方法がいくつか知られているのだが、この論文の貢献は(しょぼいと言えばその通りだが)それらをまとめて2つのタスクで評価しましたよ、というもの。

(面倒くさくなってきたのでそのまま書く) 結局いちばん速いのは SGD (Stochactic Gradient Descent) という確率的にパラメータを最適化する手法であり、L1 正則化という正則化方法を使えばほとんどの素性が0になるのでモデルがコンパクトになりますよ、というお話。一つこの論文で強調しているものとしたら、bigram のテンプレートとして CRF++ も CRFsuite もタグの bigram しか使えないが、タグの bigram に加えて現在の入力も加えた3つ組を素性に入れると(素性数の爆発の見返りに)かなり精度が上がる、という話。メモリ64GBのマシンで数十億の素性を使えるそうなのだが、本当に意味あるのか? と思いつつ、確かに精度の向上を見ると意味ありそう、と説得されてしまう。

(2010-07-13 岡崎さんからコメントいただいたので、転記。他にコメントしようとしてできない人いますか?)

おもしろい論文を紹介して頂いてありがとうございます．日記にコメントを投稿
しようとしたのですが，画像認証がどうしてもうまくいきません．「画像の文字
列と入力された文字列が違います。」と表示されます．

10回以上トライしても失敗し続けているので，多分自分の目がおかしいというこ
とはないのだと信じておりますが，コメントを難なく書けている方もいらっしゃ
るので，こちらが何かドジをしている可能性も捨てきれません・・・．

ちなみに，コメントしようと思った内容は，多分CRF++では３つ組み素性が，Bテ
ンプレート（続けてxのマクロを書く必要有り）で使えるはずというものです．

なるほど。B テンプレートの右辺にさらに unigram のマクロ書いてもいいんですね……勉強になりました！

NLP.app 勉強会は実践的な勉強会にすることを狙っているので、論文に沿って CRF++ と CRFsuite という2つの CRF の実装のコードリーディングをしたり。どこが L1/L2 正則化か、L-BFGS や SGD はどう使われているか、どこで素性の展開をしているか、とか。CRF++ はすごくよく作られていて参考になる。MeCab は CRF++ の最新版より少し古いコードベースかな? 自分は読まれて恥ずかしいコードしか公開していないのだが、今年はちょっと論文ではなくコードを書く能力を上げようというキャンペーンをしているので、がんばりたい。

ちなみに上記 ACL 論文のソースコードも Wapiti - A simple and fast linear-chain CRF toolkit として公開されている。こうやって論文の companion コードが公開されるのは、あとから追試したい(再実装したい人含む)人にはとても助かる。みんなこうすればいいのにねえ。

それでふと思い出したが、id:naoya さんのエンジニアの不安と壁を読んで勇気づけられる。いろいろ壁や道があるものだろうけど、あとから学ぶことで体系化されるようなこともあるのだな、と。

「きれいなコードを書くにはどうしたらいいんだろう」。プログラマになって誰もが一度は経験する壁なのかな、と思います。社会人一年目くらいに「そもそも綺麗なコードってどんなコードなんだ」というところに始まり、四苦八苦したのでした。覚えたてのオブジェクト指向で「おれおれオブジェクト指向」を遺憾なく発揮し、周囲に迷惑をかけた、なんて黒歴史もきっちりと刻んできました。
自分がまあまあ綺麗にコードを書けるようになったな、と思えるようになったのは、結構時間が経ってからでした。そうですね、はてなに入ってしばらく経った頃だから、社会人プログラマ経験的には4年くらいが過ぎた頃だったと思います。何が設計のセオリーか、どういうコードが見本なのかというのは、断片的にあちこちから得た知識/コードからなんとなくは分かっていたのですが。それらの点と点が繋がって線になった、と感じたのは、結城浩さんのデザインパターンの本を久しぶりに読んだときでした。
あの本を読んで、同じような感想を持った人がどれくらいいらっしゃるかは正直なところわからないのですが、自分は繰り返し繰り返し読むうちに、パターンの根底に通じるプログラミング設計の概念がおぼろげながら分かるようになったと感じました。ひとことで言うなら「インタフェースでプログラミングする」ということなんですが、その概念が中心軸になって、それまでに持っていた自分の知識が徐々に体系化されていったのを良く覚えています。

最近このココロが分かってきた。katsuhiko-h くんから「解析器は Java で書いてほしい」と注文がついた(笑)ので、

増補改訂版Java言語で学ぶデザインパターン入門

増補改訂版Java言語で学ぶデザインパターン入門

でも読みながら書きますかねー(なにも指定がなければ C++ で書くつもりだったのだが)