On Dual Decomposition and Linear Programming Relaxations for Natural Language Processing

Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 1–11, MIT, Massachusetts, USA, 9-11 October 2010. c⃝2010 Association for Computational Linguistics On Dual Decomposition and Linear Programming Relaxations for Natural Language Processing Alexander M. Rush David Sontag Michael Collins Tommi Jaakkola MIT CSAIL, Cambridge, MA 02139, USA {srush,dsontag,mcollins,tommi}@csail.mit.edu 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 be- tween the different oracles. The approach provably solves a linear programming (LP) re- laxation 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 experimen- tal results on two problems: 1) the combina- tion of two lexicalized parsing models; and 2) the combination of a lexicalized parsing model and a trigram part-of-speech tagger. 1 Introduction Dynamic programming algorithms have been re- markably useful for inference in many NLP prob- lems. Unfortunately, as models become more com- plex, for example through the addition of new fea- tures or components, dynamic programming algo- rithms can quickly explode in terms of computa- tional or implementational complexity.1 As a re- sult, efficiency of inference is a critical bottleneck for many problems in statistical NLP. This paper introduces dual decomposition (Dantzig and Wolfe, 1960; Komodakis et al., 2007) as a framework for deriving inference algorithms in NLP. Dual decomposition leverages the observation that complex inference problems can often be decomposed into efficiently solvable sub-problems. The approach leads to inference algorithms with the following properties: 1The same is true for NLP inference algorithms based on other exact combinatorial methods, for example methods based on minimum-weight spanning trees (McDonald et al., 2005), or graph cuts (Pang and Lee, 2004). • The resulting algorithms are simple and efficient, building on standard dynamic-programming algo- rithms as oracle solvers for sub-problems,2 to- gether with a method for forcing agreement be- tween the oracles. • The algorithms provably solve a linear program- ming (LP) relaxation of the original inference problem. • Empirically, the LP relaxation often leads to an exact solution to the original problem. The approach is very general, and should be appli- cable to a wide range of problems in NLP. The con- nection to linear programming ensures that the algo- rithms provide a certificate of optimality when they recover the exact solution, and also opens up the possibility of methods that incrementally tighten the LP relaxation until it is exact (Sherali and Adams, 1994; Sontag et al., 2008). The structure of this paper is as follows. We first give two examples as an illustration of the ap- proach: 1) integrated parsing and trigram part-of- speech (POS) tagging; and 2) combined phrase- structure and dependency parsing. In both settings, …

Content truncated to 500 words