Message Passing for Soft Constraint Dual Decomposition

Abstract

Dual decomposition provides the opportunity to build complex, yet tractable, structured predic-tion models using linear constraints to link to-gether submodels that have available MAP infer-ence routines. However, since some constraints might not hold on every single example, such models can often be improved by relaxing the requirement that these constraints always hold, and instead replacing them with soft constraints that merely impose a penalty if violated. A dual objective for the resulting MAP inference prob-lem differs from the hard constraint problem’s associated dual decomposition objective only in that the dual variables are subject to box con-straints. This paper introduces a novel primal-dual block coordinate descent algorithm for min-imizing this general family of box-constrained objectives. Through experiments on two nat-ural language corpus-wide inference tasks, we demonstrate the advantages of our approach over the current alternative, based on copying vari-ables, adding auxiliary submodels and using tra-ditional dual decomposition. Our algorithm per-forms inference in the same model as was previ-ously published for these tasks, and thus is capa-ble of achieving the same accuracy, but provides a 2-10x speedup over the current state of the art. 1