Timezone: »

 
Poster
Dynamic Importance Sampling for Anytime Bounds of the Partition Function
Qi Lou · Rina Dechter · Alexander Ihler

Mon Dec 04 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #181
in Posters Mon »

Computing the partition function is a key inference task in many graphical models. In this paper, we propose a dynamic importance sampling scheme that provides anytime finite-sample bounds for the partition function. Our algorithm balances the advantages of the three major inference strategies, heuristic search, variational bounds, and Monte Carlo methods, blending sampling with search to refine a variationally defined proposal. Our algorithm combines and generalizes recent work on anytime search and probabilistic bounds of the partition function. By using an intelligently chosen weighted average over the samples, we construct an unbiased estimator of the partition function with strong finite-sample confidence intervals that inherit both the rapid early improvement rate of sampling with the long-term benefits of an improved proposal from search. This gives significantly improved anytime behavior, and more flexible trade-offs between memory, time, and solution quality. We demonstrate the effectiveness of our approach empirically on real-world problem instances taken from recent UAI competitions.

Keywords: Graphical Models
[ Paper] 

Author Information

Qi Lou (UCI)
Rina Dechter (UCI)
Alexander Ihler (UC Irvine)

More from the Same Authors