Linear Programming Relaxations and Belief Propagation - An Empirical Study

By Chen Yanover, Talya Meltzer, Yair Weiss. 2006

219 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Determinantal Point Processes for Machine Learning (2012, background): “What makes DPPs particularly unique is the marriage of these computational advantages with the ability to express global, negative interactions between modeling variables; this repulsive domain is notoriously intractable using traditional approaches like graphical models [17, 70, 82, 109, 146, 156, ”
Discriminative Models for Multi-Class Object Layout (2009, methodology): “The TRW algorithm is a variant of Belief Propagation that solves the resulting LP and has been shown to be significantly faster for this problem structure than off-the-shelf LP solvers (Yanover and Meltzer 2006).”
Hinge-Loss Markov Random Fields and Probabilistic Soft Logic (2015, background): “Although in practice they perform better than their worst-case bounds (Wright, 2005), they do not scale well to large structured prediction problems (Yanover et al., 2006).”
MRF Energy Minimization and Beyond via Dual Decomposition (2011, unknown): “The importance of relaxation LP MRF to MRF optimization and/ or its connection to message-passing methods has also been explored in some other interesting works (e.g., we point the interested reader to [52], [28], [43], [56] for more details).”
Fixing Max-Product: Convergent Message Passing Algorithms for MAP LP-Relaxations (2007, methodology): “Although LP relaxations can be solved using standard LP solvers, this may be computationally intensive for large problems [11].”
Introduction to dual composition for inference (2011, background): “frequently found using dual decomposition, in spite of the corresponding optimization problems being NP-complete (Koo et al., 2010; Sontag et al., 2008; Yanover et al., 2006).”
Tightening LP Relaxations for MAP using Message Passing (2008, methodology): “While the problem is quite different from side-chain prediction, it can be solved using the same graph structure, as shown in [18].”
Fault Identification Via Nonparametric Belief Propagation (2009, background): “problem structure can be more efficient than generic linear programming packages [38].”
Fields of Experts (2009, background): “Yanover et al. (2006) have recently obtained global solutions to low-level vision problems even with non-convex pairwise MRFs.”
AD3: alternating directions dual decomposition for MAP inference in graphical models (2015, background): “7, specialized algorithms have been designed to exploit the graph structure, achieving superior performance on several benchmarks (Yanover et al., 2006).”
A Linear Programming Approach to Max-Sum Problem: A Review (2007, methodology): “We have not done experimental comparison of the max-sum diffusion and the augmenting DAG algorithms with other approximative algorithms for the max-sum problem [75], [79], [80].”
Learning to place new objects in a scene (2012, methodology): “Several prior works have successfully applied ILP to solve inference in Conditional Random Fields or Markov networks, e.g., Roth and Yih, 2005; Taskar et al., 2004; Yanover et al., 2006; Globerson and Jaakkola, 2007.”
Graphical Models, Exponential Families, and Variational Inference (2008, methodology): “Various forms of these reweighted maxproduct algorithms have been applied in problems such as segmentation and disparity problems in computer vision [165, 134, 136, 246, 222, 260], error-control coding [73], side-chain prediction [261, 246], sensor fusion [43, 46].”
New Outer Bounds on the Marginal Polytope (2007, background): “[14] showed that minimization of the Rosetta energy function corresponds to finding the MAP assignment of a non-binary pairwise MRF.”
Advanced Structured Prediction (2014, methodology): “We compare the performance of the algorithms on protein side-chain prediction problems from the dataset of Yanover et al. (2006). These problems involve finding the 3D configuration of rotamers given the backbone structure of a protein.”