On Dual Decomposition and Linear Programming Relaxations for Natural Language Processing


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.

Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing (EMNLP)
David Sontag
David Sontag
Associate Professor of EECS

My research focuses on advancing machine learning and artificial intelligence, and using these to transform health care.