Paper: Dual Decomposition with Many Overlapping Components

ACL ID D11-1022
Title Dual Decomposition with Many Overlapping Components
Venue Conference on Empirical Methods in Natural Language Processing
Session Main Conference
Year 2011

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.