Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Message Passing for Soft Constraint Dual Decomposition
David Belanger, Alexandre Passos, Sebastian Riedel, Andrew McCallum
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.
Keywords:
Pages: 62-71
PS Link:
PDF Link: /papers/14/p62-belanger.pdf
BibTex:
@INPROCEEDINGS{Belanger14,
AUTHOR = "David Belanger and Alexandre Passos and Sebastian Riedel and Andrew McCallum",
TITLE = "Message Passing for Soft Constraint Dual Decomposition",
BOOKTITLE = "Proceedings of the Thirtieth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-14)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2014",
PAGES = "62--71"
}


hosted by DSL   •   site info   •   help