TY - GEN
T1 - Dual decomposition for parsing with non-projective head automata
AU - Koo, Terry
AU - Rush, Alexander M.
AU - Collins, Michael
AU - Jaakkola, Tommi
AU - Sontag, David
PY - 2010
Y1 - 2010
N2 - This paper introduces algorithms for non-projective parsing based on dual decomposition. We focus on parsing algorithms for non-projective head automata, a generalization of head-automata models to non-projective structures. The dual decomposition algorithms are simple and efficient, relying on standard dynamic programming and minimum spanning tree algorithms. They provably solve an LP relaxation of the non-projective parsing problem. Empirically the LP relaxation is very often tight: for many languages, exact solutions are achieved on over 98% of test sentences. The accuracy of our models is higher than previous work on a broad range of datasets.
AB - This paper introduces algorithms for non-projective parsing based on dual decomposition. We focus on parsing algorithms for non-projective head automata, a generalization of head-automata models to non-projective structures. The dual decomposition algorithms are simple and efficient, relying on standard dynamic programming and minimum spanning tree algorithms. They provably solve an LP relaxation of the non-projective parsing problem. Empirically the LP relaxation is very often tight: for many languages, exact solutions are achieved on over 98% of test sentences. The accuracy of our models is higher than previous work on a broad range of datasets.
UR - http://www.scopus.com/inward/record.url?scp=80053229665&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=80053229665&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:80053229665
SN - 1932432868
SN - 9781932432862
T3 - EMNLP 2010 - Conference on Empirical Methods in Natural Language Processing, Proceedings of the Conference
SP - 1288
EP - 1298
BT - EMNLP 2010 - Conference on Empirical Methods in Natural Language Processing, Proceedings of the Conference
T2 - Conference on Empirical Methods in Natural Language Processing, EMNLP 2010
Y2 - 9 October 2010 through 11 October 2010
ER -