Constraints Based Convex Belief Propagation
Inference in Markov random fields subject to consistency structure is a fundamental problem that arises in many real-life applications. In order to enforce consistency, classical approaches utilize consistency potentials or encode constraints over feasible instances. Unfortunately this comes at the price of a serious computational bottleneck. In this paper we suggest to tackle consistency by incorporating constraints on beliefs. This permits derivation of a closed-form message-passing algorithm which we refer to as the Constraints Based Convex Belief Propagation (CBCBP). Experiments show that CBCBP outperforms the standard approach while being at least an order of magnitude faster.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Convex Combination Belief Propagation Algorithms
We present new message passing algorithms for performing inference with graphical models. Our methods are designed for the most difficult inference problems where loopy belief propagation and other heuristics fail to con…
Belief Propagation Min-Sum Algorithm for Generalized Min-Cost Network Flow
Belief Propagation algorithms are instruments used broadly to solve graphical model optimization and statistical inference problems. In the general case of a loopy Graphical Model, Belief Propagation is a heuristic which…
Model OptimizationPairwise Matching Through Max-Weight Bipartite Belief Propagation
Feature matching is a key problem in computer vision and pattern recognition. One way to encode the essential interdependence between potential feature matches is to cast the problem as inference in a graphical model, th…
An Improved Three-Weight Message-Passing Algorithm
We describe how the powerful "Divide and Concur" algorithm for constraint satisfaction can be derived as a special case of a message-passing version of the Alternating Direction Method of Multipliers (ADMM) algorithm for…
Bounds on marginal probability distributions
We propose a novel bound on single-variable marginal probability distributions in factor graphs with discrete variables. The bound is obtained by propagating bounds (convex sets of probability distributions) over a subtr…
Medical Diagnosis