構文解析とは、文を構成する全ての単語の位置関係（掛り受け等）を決める手法である。
まず、「古びた京都の宿に彼だけが泊まったらしい」という文を考える。この中で、「古びた」は「宿」に係ることは、日本語に慣れている人にはすぐ分かるだろう。しかし、構文解析の段階では、「古びた」は「京都」に係ることも間違いではない。両者とも正しいものとして出力される。
構文解析の段階では、優先的解釈、例えば「古びた」が施設、具体物を修飾する表現としてはよく用いられるが、「古びた京都」のように地名を修飾する表現は一般的でないという考え方に基づく。このような判断を行うためには、実際の言語使用における語の振る舞いを学習する必要がある。この問題は注釈付与コーパスを用いて、教師有機械学習で扱うことができる。
最大全域木
入力の単語列を、x = x1x2....xnとし、語をノードで、依存関係を主辞から修飾語
への有向辺で表現する。どういうことかというと、
全ての語の間に依存関係の有向辺(i, j)を作り、スコアを与える。なお、文全体の主辞を指し示すためのROOTを文頭に置いている。
このようなグラフ表現に基づいて、構文解析の問題をこのグラフから最大全域木（MST）を発見するという問題として捉える訳だ。
全域木をyで表すと、
y = arg max Σ s(i, j)
となるyを求めることと同義である。下記がそこに含まれる辺のスコア和が最大になる全域木となる。
Chu-Liu-Edmonds法
上記のスコア和を最大化する場合に、ループができてはならないという規則がある。これは当然ながら係り受けの順序が不明になるためであるが、どのように回避すればよいのだろうか。例えば、各ノードへのスコア最大の入力辺を選ぶと、下記のようになる。
この場合、Johnとsawではループが出来ているため、Johnとsawを縮約ノードとしてまとめる。
まず、縮約ノードへの入力辺を考える。まず、sawに着目すると、Rootからsawへは-5、そしてsawからJohnへは30、合計で25というスコアになる。一方で、Johnに着目すると、Rootから-6、Johnからsawへ20なので合計は14となり、sawを起点ノードとするべきであると考えられる。
次に、縮約ノードからの出力辺だが、縮約ノード以外に存在するノードのうち、Rootは入力辺がないため、Maryだけに着目する。すると、Johnからの3と、sawからの30で、後者を採用する。
この操作を繰り返し、縮約ノードがなくなるまで全域木を求めれば最大全域木が求まるということになる。
スコアの学習方法
xiからxjへの有向辺のスコア、すなわちxiが主辞、xjが修飾語となる依存関係のスコアを下記式で算出する。
s(i, j) = Σ λm × fm (i,j)
ここでfm (i,j)はxi、xjの依存関係を特徴づける素性を取り出す素性関数である。素性としては、xi、xjの語そのものと品詞、xiとxjの距離と依存関係の方向、さらにxi、xjの周辺の語と品詞などを考慮する。
λmは各素性関数に対応する重みベクトルで、注釈付与コーパスを用いて、ある重みで求まる依存木と正しい依存木との差分に基づく反復計算によって求められる。
参考：自然言語処理（黒崎禎夫）