@inproceedings{RusSonColJaa_emnlp10,
 author = {Alexander M. Rush and David Sontag and Michael Collins and Tommi Jaakkola},
 title = {On Dual Decomposition and Linear Programming Relaxations for Natural Language Processing},
 booktitle = {Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing (EMNLP)},
 pages = {1-11},
 year = {2010},
 keywords = {Machine learning, Natural language processing, Approximate inference in graphical models},
 url_Paper = {http://people.csail.mit.edu/dsontag/papers/RusSonColJaa_emnlp10.pdf},
 abstract = {This paper introduces dual decomposition as a framework for deriving inference algorithms for NLP problems. The approach relies on standard dynamic-programming algorithms as oracle solvers for sub-problems, together with a simple method for forcing agreement between the different oracles. The approach provably solves a linear programming (LP) relaxation of the global inference problem. It leads to algorithms that are simple, in that they use existing decoding algorithms; efficient, in that they avoid exact algorithms for the full model; and often exact, in that empirically they often recover the correct solution in spite of using an LP relaxation. We give experimental results on two problems: 1) the combination of two lexicalized parsing models; and 2) the combination of a lexicalized parsing model and a trigram part-of-speech tagger.}
}

{"_id":"dvMqgK4fiYoeQdmrA","bibbaseid":"rush-sontag-collins-jaakkola-ondualdecompositionandlinearprogrammingrelaxationsfornaturallanguageprocessing-2010","author_short":["Rush, A. M.","Sontag, D.","Collins, M.","Jaakkola, T."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["Alexander","M."],"propositions":[],"lastnames":["Rush"],"suffixes":[]},{"firstnames":["David"],"propositions":[],"lastnames":["Sontag"],"suffixes":[]},{"firstnames":["Michael"],"propositions":[],"lastnames":["Collins"],"suffixes":[]},{"firstnames":["Tommi"],"propositions":[],"lastnames":["Jaakkola"],"suffixes":[]}],"title":"On Dual Decomposition and Linear Programming Relaxations for Natural Language Processing","booktitle":"Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing (EMNLP)","pages":"1-11","year":"2010","keywords":"Machine learning, Natural language processing, Approximate inference in graphical models","url_paper":"http://people.csail.mit.edu/dsontag/papers/RusSonColJaa_emnlp10.pdf","abstract":"This paper introduces dual decomposition as a framework for deriving inference algorithms for NLP problems. The approach relies on standard dynamic-programming algorithms as oracle solvers for sub-problems, together with a simple method for forcing agreement between the different oracles. The approach provably solves a linear programming (LP) relaxation of the global inference problem. It leads to algorithms that are simple, in that they use existing decoding algorithms; efficient, in that they avoid exact algorithms for the full model; and often exact, in that empirically they often recover the correct solution in spite of using an LP relaxation. We give experimental results on two problems: 1) the combination of two lexicalized parsing models; and 2) the combination of a lexicalized parsing model and a trigram part-of-speech tagger.","bibtex":"@inproceedings{RusSonColJaa_emnlp10,\n author = {Alexander M. Rush and David Sontag and Michael Collins and Tommi Jaakkola},\n title = {On Dual Decomposition and Linear Programming Relaxations for Natural Language Processing},\n booktitle = {Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing (EMNLP)},\n pages = {1-11},\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/RusSonColJaa_emnlp10.pdf},\n abstract = {This paper introduces dual decomposition as a framework for deriving inference algorithms for NLP problems. The approach relies on standard dynamic-programming algorithms as oracle solvers for sub-problems, together with a simple method for forcing agreement between the different oracles. The approach provably solves a linear programming (LP) relaxation of the global inference problem. It leads to algorithms that are simple, in that they use existing decoding algorithms; efficient, in that they avoid exact algorithms for the full model; and often exact, in that empirically they often recover the correct solution in spite of using an LP relaxation. We give experimental results on two problems: 1) the combination of two lexicalized parsing models; and 2) the combination of a lexicalized parsing model and a trigram part-of-speech tagger.}\n}\n\n","author_short":["Rush, A. M.","Sontag, D.","Collins, M.","Jaakkola, T."],"key":"RusSonColJaa_emnlp10","id":"RusSonColJaa_emnlp10","bibbaseid":"rush-sontag-collins-jaakkola-ondualdecompositionandlinearprogrammingrelaxationsfornaturallanguageprocessing-2010","role":"author","urls":{" paper":"http://people.csail.mit.edu/dsontag/papers/RusSonColJaa_emnlp10.pdf"},"keyword":["Machine learning","Natural language processing","Approximate inference in graphical models"],"metadata":{"authorlinks":{}},"downloads":0,"html":""},"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","linear","programming","relaxations","natural","language","processing","rush","sontag","collins","jaakkola"],"title":"On Dual Decomposition and Linear Programming Relaxations for Natural Language Processing","year":2010}