Paper  abstract   bibtex   

@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.}
}