Thursday, December 9, 2010

Paper notes - Dual Decomposition for Parsing with Non-Projective Head Automata

Koo, Rush, Collins, Jaakkola, Sontag. EMNLP 2010.

Problem: Non-projective head automata (I dont know this) parsing - building a parse tree for a sentence, using annotated data (sentences and their parse trees).

Contribution: A dual decomposition formulation of the problem. Leads to efficient algorithms based on minimum spanning tree (MST) algorithms and dynamic programming.

TODO : Got stuck in understanding the basics of the optimization and algorithms involved. Will get back to this later.

Some of the things to look up -
  • Head automata; parsing
  • Dual decomposition, Lagrangian relaxation - in combinatorial optimization
  • LP/ILP solvers
  • MST based optimization
  • NP-hard/complete - practice judging hardness of problems

No comments:

Post a Comment