TY - GEN
T1 - On dual decomposition and linear programming relaxations for natural language processing
AU - Rush, Alexander M.
AU - Sontag, David
AU - Collins, Michael
AU - Jaakkola, Tommi
PY - 2010
Y1 - 2010
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=80053227279&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=80053227279&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:80053227279
SN - 1932432868
SN - 9781932432862
T3 - EMNLP 2010 - Conference on Empirical Methods in Natural Language Processing, Proceedings of the Conference
SP - 1
EP - 11
BT - EMNLP 2010 - Conference on Empirical Methods in Natural Language Processing, Proceedings of the Conference
T2 - Conference on Empirical Methods in Natural Language Processing, EMNLP 2010
Y2 - 9 October 2010 through 11 October 2010
ER -