New Closed-Form Bounds on the Partition Function

Abstract

Estimating the partition function is a key computation in graphical models that is required for important tasks like parameter estimation, model selection and structure learning. However, this computation is intractable in general. Thus, developing efficient and accurate approximations is of considerable interest. Variational methods express the computation of the partition function as an optimization problem (solving which intractable in general) and then relax the optimization problem in various ways to obtain approximations to the partition function. Two popular algorithms belonging to this framework are loopy belief propagation (LBP) and tree-reweighted belief propagation (TRW-BP). Both these algorithms are so-called message passing algorithms that work by updating local beliefs about probabilities at graph nodes by passing messages between the nodes in the graph until convergence is achieved. TRW-BP is guaranteed to give an upper bound on the partition function. However, neither algorithm is guaranteed to converge in general. Although convergent alternatives to TRW-BP have been proposed, they have no guarantees on the number of iterations required for convergence. Thus, these algorithms could be prohibitively expensive for applications requiring repeated inference on large graphs (like training large CRFs). In order to overcome this problem, Sutton et al. propose the piecewise approximation (PW) to the partition function. PW tends to be loose, but can be computed very fast, because it has a closed-form expression. Sutton et al. apply it successfully to common NLP tasks. In this paper, for a special class of potentials (that contain associative potentials), we prove that both LBP and TRW-BP converge in a single iteration. Using this fact, we obtain closed-form expressions for the TRW and LBP approximations to the partition function. In recent work, Wainwright et al. prove that LBP gives a lower bound on the partition function for binary attractive MRFs. We thus also get closed-form lower bounds for attractive associative MRFs. This enables us to obtain bounds on the error between the true partition function and these approximations for attractive associative MRFs. We also construct examples which show that TRW and LBP can give arbitrarily bad approximations to the marginal probabilities. Using the closed-form bounds for these special cases, we also develop novel closed-form upper bounds for arbitrary MRFs and closed-form lower bounds for associative binary MRFs. We also present experimental results showing that the new upper bounds are almost always tighter than the piecewise bound. The experiments also show that the novel lover bounds beat popular existing bounds like the mean-field bound on densely connected graphs.