ECML PKDD 2008

New Closed-form Bounds on the Partition Function

Estimating the partition function is a key but difficult computation in graphical models. One approach is to estimate tractable upper and lower bounds. The piecewise upper bound of Sutton etal{} is computed by breaking the graphical model into pieces and approximating the partition function as a product of local normalizing factors for these pieces. The tree reweighted belief propagation algorithm (TRW-BP) by Wainwright etal{} gives tighter upper bounds. It optimizes an upper bound expressed in terms of convex combinations of spanning trees of the graph. Recently, Globerson etal{} gave a different, convergent iterative dual optimization algorithm TRW-GP for the TRW objective. However, in many practical applications, particularly those that train CRFs with many nodes, TRW-BP and TRW-GP take too long to be practical. Without changing the algorithm, we prove that TRW-BP converges in a single iteration for associative potentials, and give a closed form for the solution it finds. The solution decomposes along edges, obviating any need for complex optimization. We use this result to develop new closed-form upper bounds for MRFs with arbitrary pairwise potentials. Being closed-form, they are much faster to compute than TRW-based bounds. We also prove similar convergence results for loopy belief propagation (LBP) and use it to obtain closed-form solutions to the BP pseudomarginals and approximation to the partition function for associative potentials. We then use recent results proved by Wainwright et al{} for binary MRFs to obtain closed-form lower bounds on the partition function. We then develop novel lower bounds for arbitrary associative networks. We report on experiments with synthetic and real-world graphs. Our new upper bounds are considerably tighter than the piecewise bounds in practice. Moreover, we can compute our bounds on several graphs where TRW does not converge. Our novel lower bound, in spite of being closed-form and much faster to compute, outperforms more complicated popular algorithms for computing lower bounds like mean-field on densely connected graphs by large margins although it does worse on sparsely connected graphs like chains.