Dual Decomposition with Many Overlapping Components

Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 238–249, Edinburgh, Scotland, UK, July 27–31, 2011. c⃝2011 Association for Computational Linguistics Dual Decomposition with Many Overlapping Components Andr´e F. T. Martins∗† Noah A. Smith∗ Pedro M. Q. Aguiar‡ M´ario A. T. Figueiredo† ∗School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, USA ‡Instituto de Sistemas e Rob´otica, Instituto Superior T´ecnico, Lisboa, Portugal †Instituto de Telecomunicac¸˜oes, Instituto Superior T´ecnico, Lisboa, Portugal {afm,nasmith}@cs.cmu.edu, aguiar@isr.ist.utl.pt, mtf@lx.it.pt Abstract Dual decomposition has been recently pro- posed as a way of combining complemen- tary models, with a boost in predictive power. However, in cases where lightweight decom- positions are not readily available (e.g., due to the presence of rich features or logical con- straints), the original subgradient algorithm is inefficient. We sidestep that difficulty by adopting an augmented Lagrangian method that accelerates model consensus by regular- izing towards the averaged votes. We show how first-order logical constraints can be han- dled efficiently, even though the correspond- ing subproblems are no longer combinatorial, and report experiments in dependency pars- ing, with state-of-the-art results. 1 Introduction The last years have witnessed increasingly accurate models for syntax, semantics, and machine transla- tion (Chiang, 2007; Finkel et al., 2008; Petrov and Klein, 2008; Smith and Eisner, 2008; Martins et al., 2009a; Johansson and Nugues, 2008; Koo et al., 2010). The predictive power of such models stems from their ability to break locality assumptions. The resulting combinatorial explosion typically demands some form of approximate decoding, such as sam- pling, heuristic search, or variational inference. In this paper, we focus on parsers built from lin- ear programming relaxations, the so-called “turbo parsers” (Martins et al., 2009a; Martins et al., 2010). Rush et al. (2010) applied dual decomposition as a way of combining models which alone permit efficient decoding, but whose combination is in- tractable. This results in a relaxation of the origi- nal problem that is elegantly solved with the sub- gradient algorithm. While this technique has proven quite effective in parsing (Koo et al., 2010; Auli and Lopez, 2011) as well as machine translation (Rush and Collins, 2011), we show here that its success is strongly tied to the ability of finding a “good” decomposition, i.e., one involving few over- lapping components (or slaves). With many compo- nents, the subgradient algorithm exhibits extremely slow convergence (cf. Fig. 2). Unfortunately, a lightweight decomposition is not always at hand, ei- ther because the problem does not factor in a natural way, or because one would like to incorporate fea- tures that cannot be easily absorbed in few tractable components. Examples include features generated by statements in first-order logic, features that vio- late Markov assumptions, or history features such as the ones employed in transition-based parsers. To tackle the kind of problems above, we adopt DD-ADMM (Alg. 1), a recently proposed algorithm that accelerates dual decomposition (Martins et al., 2011). DD-ADMM retains the modularity of the subgradient-based method, but it speeds up consen- sus by regularizing each slave subproblem …

Content truncated to 500 words