Dual Decomposition for Parsing with Non-Projective Head Automata. Koo, T., Rush, A. M., Collins, M., Jaakkola, T., & Sontag, D. In Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1288-1298, 2010. Paper abstract bibtex 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.
@inproceedings{KooEtAl_emnlp10,
author = {Terry Koo and Alexander M. Rush and Michael Collins and Tommi Jaakkola and David Sontag},
title = {Dual Decomposition for Parsing with Non-Projective Head Automata},
booktitle = {Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing (EMNLP)},
pages = {1288-1298},
year = {2010},
keywords = {Machine learning, Natural language processing, Approximate inference in graphical models},
url_Paper = {http://people.csail.mit.edu/dsontag/papers/KooEtAl_emnlp10.pdf},
abstract = {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.}
}
Downloads: 0
{"_id":"GZMxy5S4W7BKbwAez","bibbaseid":"koo-rush-collins-jaakkola-sontag-dualdecompositionforparsingwithnonprojectiveheadautomata-2010","author_short":["Koo, T.","Rush, A. M.","Collins, M.","Jaakkola, T.","Sontag, D."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["Terry"],"propositions":[],"lastnames":["Koo"],"suffixes":[]},{"firstnames":["Alexander","M."],"propositions":[],"lastnames":["Rush"],"suffixes":[]},{"firstnames":["Michael"],"propositions":[],"lastnames":["Collins"],"suffixes":[]},{"firstnames":["Tommi"],"propositions":[],"lastnames":["Jaakkola"],"suffixes":[]},{"firstnames":["David"],"propositions":[],"lastnames":["Sontag"],"suffixes":[]}],"title":"Dual Decomposition for Parsing with Non-Projective Head Automata","booktitle":"Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing (EMNLP)","pages":"1288-1298","year":"2010","keywords":"Machine learning, Natural language processing, Approximate inference in graphical models","url_paper":"http://people.csail.mit.edu/dsontag/papers/KooEtAl_emnlp10.pdf","abstract":"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.","bibtex":"@inproceedings{KooEtAl_emnlp10,\n author = {Terry Koo and Alexander M. Rush and Michael Collins and Tommi Jaakkola and David Sontag},\n title = {Dual Decomposition for Parsing with Non-Projective Head Automata},\n booktitle = {Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing (EMNLP)},\n pages = {1288-1298},\n year = {2010},\n keywords = {Machine learning, Natural language processing, Approximate inference in graphical models},\n url_Paper = {http://people.csail.mit.edu/dsontag/papers/KooEtAl_emnlp10.pdf},\n abstract = {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.}\n}\n\n","author_short":["Koo, T.","Rush, A. M.","Collins, M.","Jaakkola, T.","Sontag, D."],"key":"KooEtAl_emnlp10","id":"KooEtAl_emnlp10","bibbaseid":"koo-rush-collins-jaakkola-sontag-dualdecompositionforparsingwithnonprojectiveheadautomata-2010","role":"author","urls":{" paper":"http://people.csail.mit.edu/dsontag/papers/KooEtAl_emnlp10.pdf"},"keyword":["Machine learning","Natural language processing","Approximate inference in graphical models"],"metadata":{"authorlinks":{}}},"bibtype":"inproceedings","biburl":"http://people.csail.mit.edu/dsontag/papers/bibtex/david_sontag_papers_all.bib","dataSources":["g3ofqhxNQWsRWkCrp"],"keywords":["machine learning","natural language processing","approximate inference in graphical models"],"search_terms":["dual","decomposition","parsing","non","projective","head","automata","koo","rush","collins","jaakkola","sontag"],"title":"Dual Decomposition for Parsing with Non-Projective Head Automata","year":2010}