Eisnerアルゴリズムのチュートリアル

III期初のD-Lec。岩立さんによるEisnerアルゴリズムのチュートリアル。今日の午前に松本先生の依存構造解析とかの授業があった後なので、すごくよいタイミング。Eisnerアルゴリズムは依存構造解析を行なうためのアルゴリズムの1つで

言語に依存しない
Projectiveな係り受けを仮定
Graph-basedなアルゴリズムでDPを用いて効率よく全探索するので、Shift-Reduceなどと比べると解析精度重視

なものである。EisnerアルゴリズムにはFirst-order、Second-orderなど色々あるが、N-th orderだと同時にN個の係り受け関係を見て、それ以外の係り受け関係は独立である、という風な考え方。個々の係り受け関係にスコアを付けて、その総和が最大になるように係り受けの組み合わせを見ていく。係り受けの組み合わせを全部見るが、CKYアルゴリズムのようなDPを採用しているため効率的(O(N^3))に計算できる。

重みベクトルの学習にはstructured perceptron系のアルゴリズムがよく使われるそうで、実際にはMIRAなどが使われる。この重みを使ってCKYと同様にbottom upに解析をやっていく。部分構造としてincomplete structureとcomplete structureが使われ、complete structureは低い側のspanを連結することはできない。

First-orderだと素性の表現として貧素なところがあるので、2つ以上の係り受け関係を使って素性ベクトルを考えようというのがHigher-orderのEisnerアルゴリズム。ここ5年くらいで色々登場しているようで、今年のACLとかではThird-orderのものをO(N^4)でできるアルゴリズムが提案されている。

Eisnerアルゴリズムの概要はThird-orderを提案したKooさんの博士論文が詳しいので、そちらを参考にするとよさそう。