Importance sampling over sets: a new probabilistic inference scheme
Stefan Hadjis, Stefano Ermon · 2015
Computing expectations in high-dimensional spaces is a key challenge in probabilistic infer-ence and machine learning. Monte Carlo sam-pling, and importance sampling in particular, is one of the leading approaches. We propose a generalized importance sampling scheme based on randomly selecting (exponentially large) sub-sets of states rather than individual ones. By col-lecting a small number of extreme states in the sampled sets, we obtain estimates of statistics of interest, such as the partition function of an undirected graphical model. We incorporate this idea into a novel maximum likelihood learning algorithm based on cutting planes. We demon-strate empirically that our scheme provides accu-rate answers and scales to problems with up to a million variables. 1