読者です 読者をやめる 読者になる 読者になる

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

自然言語処理

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

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)

Dependency Parsing (Synthesis Lectures on Human Language Technologies)