構文解析と情報科学

そろそろ論文紹介記事を書いてみます．
NLP2010のプログラムにもあるとおり，しばらく係り受け構文解析周りをやっていました（います）．私の出身研究室では構文解析をやっている人がたくさんいたのですが，最近その面白さがなんとなくわかってきました．いや，一応私も2年間日本語係り受け解析の演習担当やってたよ！　構文解析のおもしろさというのは，言語学，機械学習，プログラミング，情報科学が非常にバランスよくミックスされた問題で，いろんな定式化の仕方や，いろんな技術が，いろいろな組み合わせで，かつわりとキレイな形で程々の難しさに仕上がっているあたりにあると思います．今日は，特に情報科学的教養が大事でしたという話を3つ．

Non-Projective Dependency Parsing using Spanning Tree Algorithms
Ryan McDonald, Fernando Pereira, Kiril Ribarov and Jan Hajic, HLT-EMNLP 2005.

Ryan McDonaldのMSTパーザーの論文．これまで，projective（非交差）のdependency parsingが主流だったところに，突如現れたグラフ理論を使った構文解析．「突如」だったかどうかは，当時の実情を知りませんが．構文解析というのは出力候補が入力長に対して指数爆発する問題であるため，全部列挙して比較することができません．そこで部分問題を順次解いて局所的な最適解をとるか，強い独立性を仮定した緩いモデルの上で大域最適解をとるかという選択があります．今まで後者の手法として動的計画法を使った，CKY風の解法（Eisnerとか）が主流でした．ところが，単語を頂点，係り関係を枝とする木を構築する問題だと思うと，これってmaximum spanning treeの構築だよね，ということに気づいたわけです．しかも，この問題はCKYのO(n^3)ではなくてO(n^2)でとけるというから，性能的にも優れます．
これを最初に聞いたとき，すげー，頭いい！と思いました．構文解析といえば動的計画法という固定観念がやはり私の中にもあったようですね．

Probabilistic Models of Nonprojective Dependency Trees
David A. Smith and Noah A. Smith, EMNLP2007.

オリジナルのMSTパーザーは学習はMIRAで行っている．つまり，ちゃんと勾配を求めずに学習します．CRF同様，この種の線形対数モデルは勾配を計算するときに分配関数が効率的に計算できる必要があります．CKYでは，この計算はinside-outsideで求めることができます．これは，HMMのforward-backwardをCRFのforward-backwardに拡張するのと同じ．
さて，肝心のMSTではこの計算が無理なんだろうと思っていました．しかし，実はこれは行列木定理（Matrix tree theorem）を使うと計算できるよ，ということに「気づいた」のがこの論文．行列木定理というのは全域木の総数を計算する手法を示した定理です．これを重み付きに拡張すると，分配関数の計算そのものになります．ここまで聞くと，行列木定理を使うのは至極当たり前な話なのですが，そもそも私これ読むまで行列木定理なんてしりませんでした．実情はしらないんですが，当時もみんな気づかなかったんじゃないでしょうか？　Ryan McDonaldがMSTパーザーを発表してから，実に2年間も誰も「気づかなかった」．そう思うと，すごくどきっとしませんか．

Concise Integer Linear Programming Formulations for Dependency Parsing
Andr´e F. T. Martins, Noah A. Smith and Eric P. Xing. ACL 2009.

かわって，今度は整数線形計画法（ILP）でdependency parsingした論文．ILPというのは，解が整数，制約式と目的関数が線形な最適化問題．各単語の係り先を変数におきます．上述したMSTパーザーでいうところのMaximum spanning treeのスコアは枝の重みの総和なので，これが目的関数．これは当然線形式でかける（書けそう）．あとは，ちゃんと木になっていることをうまいこと線形式で書き表せればよくて，これがちゃんと出来るよということが書かれています．大事なのは，この線形式の総数が文長に対して多項式サイズで済むことを示しています（今まであったILPの手法は指数サイズになった）．ILPはNP困難ですが，多項式時間で近似解を求める方法が知られているので，全体で多項式時間だぜ！というはなし．けっこうめちゃくちゃですが，筋は通ってます．うん．


いずれの方法も，既存の手法を，別の情報科学的テクニックで切り抜けた論文というくくりでした．応用分野であるNLPは，他分野のテクニックが押し寄せてくることがよくあります．こういうときに勝つのは，やっぱりいろいろな基礎体力を持っている人なんだなぁ，と思った次第．