Approximate inference by intersecting semidefinite bound and local polytope

摘要: Inference in probabilistic graphical models can be represented as a constrained optimization problem of free-energy functional. Substantial research has been focused on the approximation constraint set, also known marginal polytope. This paper presents novel inference algorithm that tightens and solves by intersecting popular local polytope semidefinite outer bound Using dual decomposition, our method separates into two subproblems: program (SDP), which is solved low-rank SDP algorithm, based problem, convex belief propagation. Our very reasonable computational complexity its actual running time typically within small factor ( 10) Tested both synthetic data real-world protein sidechain packing benchmark, significantly outperforms tree-reweighted propagation probability MAP inference. competitive with state-of-the-art MRF inference, solving all tasks recently presented MPLP [19], beating lattices strong edge potentials.