統語解析入門続編

前回のメモと今回の資料。

Chart Parsing

• どこまで進んだという解析結果と次に何がくるか

• top down chart法
  • (bottom upと比べて)新しい文法規則を展開するタイミングが違うだけ
  • 単語の隙間にb[i, j]とかがあるのに注意
  • 最初のきっかけが必要(例: b[0, 0]にs -> np vpなどを追加する)

• cabocha
  • 文節まとめあげ、NER、係り受け解析をまとめてやっている

Direct bottom up

先読みをする。どう頑張ってもつながりえないやつは展開しない。closureを作ってつながりえないとかを判断できる。

依存構造解析

• 矢印が論文とかによってまちまちなのでどっちなのかを最初に把握しておく
• projective: iとjの内側には係らない(間のkはw_k -> * w_i, w_k -> * w_j)
  • 現実にはnon-projectiveな言語もある
    • 日本語の書き言葉にはほとんど出てこないが、オランダ語はnon-projectiveなのが10%以上あるらしい

Shift-Reduce Baseの方法

• stackの中身はすでにかかっているものが入っている
• 後ろのほうは終わっていないので、Right-Arcの部分は消せない
  • 消す作業はReduceがやる
  • 最初の論文ではbacktrackはなし(Nivre's Algorithm => 論文)
    • 途中でミスとボロボロ

• なんでrightとかreduceとかの操作のどれをやるか決定できるのか => example baseでやっているらしい(のちにSVMになったとか)

• 日本語文節係り受け解析
  • 左から右のみ(shiftとleftだけでできる) => SVMでかかるかかからないかの二値分類

• 係り受けに基づく統語解析
  • 言語に依存しない(文法規則が必要ない)
    • non-projectiveかどうかとかの知識はいる
• O(n)でできる。高々2n
  • CKYやchartではO(n^3)かかる

Dependency Parsing (Synthesis Lectures on Human Language Technologies)