2008-07-09-sontag08a.md

abstract	title	year	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	note	address	container-title	volume	genre	issued	pdf	extras
Linear Programming (LP) relaxations have become powerful tools for finding the most probable (MAP) configuration in graphical models. These relaxations can be solved efficiently using message-passing algorithms such as belief propagation and, when the relaxation is tight, provably find the MAP configuration. The standard LP relaxation is not tight enough in many real-world problems, however, and this has lead to the use of higher order cluster-based LP relaxations. The computational cost increases exponentially with the size of the clusters and limits the number and type of clusters we can use. We propose to solve the cluster selection problem monotonically in the dual LP, iteratively selecting clusters with guaranteed improvement, and quickly re-solving with the added clusters by reusing the existing solution. Our dual message-passing algorithm finds the MAP configuration in protein side-chain placement, protein design, and stereo problems, in cases where the standard LP relaxation fails.	Tightening LP relaxations for MAP using message passing	2008	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	sontag08a	0	Tightening LP relaxations for MAP using message passing	503	510	503-510	503	false	Sontag, David and Meltzer, Talya and Globerson, Amir and Jaakkola, Tommi and Weiss, Yair	given family David Sontag given family Talya Meltzer given family Amir Globerson given family Tommi Jaakkola given family Yair Weiss	2008-07-09	Reissued by PMLR on 09 October 2024.		Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence	R6	inproceedings	date-parts 2008 7 9	https://raw.githubusercontent.com/mlresearch/r6/main/assets/sontag08a/sontag08a.pdf