New closed-form bounds on the partition function |
| |
Authors: | Dvijotham Krishnamurthy Soumen Chakrabarti Subhasis Chaudhuri |
| |
Affiliation: | (1) IIT Bombay, Mumbai, India |
| |
Abstract: | 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 et al. 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 et al. gives tighter upper bounds. It optimizes an upper bound expressed in terms
of convex combinations of spanning trees of the graph. Recently, Globerson et al. 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 are too slow 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 closed-form
solution obviates the 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 LBP 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-BP 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 wide margins although it does worse on
sparsely connected graphs like chains. |
| |
Keywords: | Partition function Graphical model Associative potential Approximate inference Belief propagation Variational methods |
本文献已被 SpringerLink 等数据库收录! |
|