依存構文解析(MST parserとLIP)

前回の続きと今回の資料。係り受けの問題をちょっと違う見方で見てみる。

• Graph-based Method
• Integer Linear Programming Method
• Span-based Method
  • こっちは次回らしい(Eisnerアルゴリズム => この前岩立さんのチュートリアルがあった)

Graph-based Method

最大全域木(MST)をbaseにしたもの。MST parserとも呼ばれる。今までのparsingと全然違う考え方(EMNLP 2005)。

• spanning treeだとprojectiveに限定されない(交差を許す)
  • よしあしがある
    • 交差を許すと、交差が逆に悪さをする場合もあるので

• transition baseのものだと途中で間違うとボロボロになる
  • MST baseのものだと全体最適化なのでそういうのに強い

• edgeのコストの決め方は?
  • dependecy treeに対するスコア関数を枝を素性としたときに、その素性に重みを付けたものをスコアとする
  • 素性に対する重みの学習に対する問題となる
  • 制約付き最小化問題として定式化される
• パーセプトンと同じようなアルゴリズムを使って最適化(マージン最大化 => SVM、MIRA)
  • • 間違いがひどいほど大きなスコアの差になるように

• コストが計算できるようになれば、MSTの計算は効率的にできる
  • Chu-Liu-Edmonds algorithm => O(n^2)
    • CKYベースだとO(n^3)であった

• あまり細かい素性を入れられないのは問題点
  • 詳細な素性を入れるためにhigher order Eisnerアルゴリズムっぽい話に繋ってくる...!

Integer Linear Programming Method

• 最大全域木になるというのが制約の元で目的関数を最大にしよう
  • MST parsingとどう違う?

• 全域木になっているという制約(こっちは自然)
• サイクルがないという制約(こっちがややこしい)

• 0-1の制約を実数に緩めるというよくあるやり方も試されている
  • スペクトラルクラスタリングの時とかもそうだったなぁ

• Integer Linear Programming MethodとMST parsingは本質的にやっていることは同じ?
• 返す結果も同じなら何が違うのか?
  • こっちのほうが交差がないとかの条件が入れやすい(MST parsingと比較して)

Dependency Parsing (Synthesis Lectures on Human Language Technologies)