On Dual Decomposition and Linear Programming Relaxations for Natural Language Processing. Rush, A. M.; Sontag, D.; Collins, M.; and Jaakkola, T. In Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1-11, 2010.
Paper abstract bibtex 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.
@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.}
}