係り受け解析器を設計する

cabochaの係り受けは、短い文だとまあまあいいものの、ちょっと長い文になるとけっこう間違う。この理由は、おそらく次の２つがあるだろう：

・構文と辞書（品詞）情報のみに頼っており、意味を見ていない

・決定的動作で、全域探索をしていない

このうち前者の意味を見る方はぱっと見大変で、すぐにはできそうな気が全然しない。が、後者の全域探索の方は、少なくとも作るだけならばそう難しくはなさそうな気がする。というわけで、

「構文と辞書（品詞）情報のみを使い、全域探索を行う係り受け解析器」

を作ってみることにする。

まず作る前に前例を調べてみる。cabochaはまあ大体わかった（つもりだ）が、KNPの方も見てみる。…わからん。cabochaよりかなり作りが複雑。ソースのコメントはむしろcabochaより親切に入っているのだが、いかんせん元の設計がどんなものかまったく情報がないのでちょっとお手上げ状態。cabochaのときは「段階的チャンキング」の論文があったのだが。まあ dpnd_analysis.c とか kakari_uke.rule とかをざっと見ると、多少「ああ、こんなことやってそうだな」というのが断片的にわかるところもあるので、まあそのくらいにしておく。他にEDAというのもあるようだが、あまり他のソースばっかり読んで時間とられるわけにもいかないのでこれはパス。単語ベースってことだし、文節ベースでいいだろ。

論文も探す。dependency parser とかでググる。shift-reduce, Eisner, MST, ILP, 等々いろいろあるようだ。全域探索が目的なので、shift-reduceは除外。他のを見てると、どうも探索の計算量がO(**)だ、とかいうあたりがいろいろ皆さん気にしてるようだ。…うーん、でもどうなんだろう。人間が読んで理解できるような文章なら、そんな計算量が必要なはずないと思うのだが（でないと人間にわからないはず）。まあまずはあまり計算量気にせずとにかく作ってみて、計算量かかって遅いようならまた考えよう、といういいかげんな気分で設計を始める。

論文を見てるとすべての文節の組み合わせをトライしてるようだが、少なくとも日本語書き言葉ならさすがにそこまでしなくてもいいんじゃないかと思う。連体詞なら必ず名詞にかかると思ってよいし、格補語なら必ず述語にかかるだろう。そういう「絶対こうなる」的ルールと、「大体こうなることが多いんだけど、例外もある」ようなルールとは分けられるだろう。前者をハードルール、後者をソフトルール、と仮に呼ぼう。ハードルールが適用できるなら、係り先が「（自分より右の）全ての文節」よりもかなり小さいサブセットに限定される。これプラスいくつか枝刈りの技術を組み合わせれば、探索空間は十分小さく抑えられるのではないかな、というのがまあ楽観的かもしれないが当方の予想。

探索のやり方もいろいろ工夫が考えられるが、まずは単純な木探索で、文末側から機械的に（ハードルールで選んだ）可能な係り先をしらみつぶしに辿っていく、という方式で行ってみる。文頭まで行ったら（つまり、木の末端では）係り受けの評価（スコア計算）を行う。ここでソフトルールが出てきて、「は」は文末にかかりやすいとか、同じ格の補語は２つ以上あれば減点とか、点数づけをしていく。

入出力もいるのだが、これはcabochaを流用することにしよう。cabochaが 1.形態素解析 2.文節分割 3.素性選択 4.係り受け となっていることは前に書いたが、この 2.文節分割 まではcabochaをそのまま使う。（正確に言うと、3.素性選択 の中のfindHead()の結果も使う。まあたいした処理ではないが。）cabochaのデータ構造から文節や形態素の情報をひっぱってきて解析する、とするのがいちばん楽そうだ。出力も、やろうと思えばcabochaのデータ構造に書き込んでcabochaの出力ルーチンを使うこともできるが、とりあえずはcabochaの結果と比較してどこが違うかを見たいので、テキストで文節ごとの係り先をcabochaと独自ルーチンの方と両方出す、くらいで当面はいいことにする。

以上のようなプログラムならそんなに難しくないだろう、ということで、作ってみる。というか実はもう作っていてだいぶ動いている。せっかくなので公開してみようか、と思うが、ちょっと現状ソースが汚いのでもうちょっと整えてからにしようか。