Approximating Marginals Using Discrete Energy Minimization

We consider the problem of inference in a graphical model with binary variables. While in theory it is arguably preferable to com-pute marginal probabilities, in practice re-searchers often use MAP inference due to the availability of efficient discrete optimiza-tion algorithms. We bridge the gap between the two approaches by introducing the Dis-crete Marginals technique in which approxi-mate marginals are obtained by minimizing an objective function with unary and pair-wise terms over a discretized domain. This allows the use of techniques originally devel-oped for MAP-MRF inference and learning. We explore two ways to set up the objective function- by discretizing the Bethe free en-ergy and by learning it from training data. Experimental results show that for certain types of graphs a learned function can out-perform the Bethe approximation. We also establish a link between the Bethe free en-ergy and submodular functions. 1