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 -
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