Importance sampling over sets: a new probabilistic inference scheme

Stefan Hadjis, Stefano Ermon
Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, PMLR R13:447-456, 2015.

Abstract

Computing expectations in high-dimensional spaces is a key challenge in probabilistic inference and machine learning. Monte Carlo sampling, and importance sampling in particular, is one of the leading approaches. We propose a generalized importance sampling scheme based on randomly selecting (exponentially large) subsets of states rather than individual ones. By collecting 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 demonstrate empirically that our scheme provides accurate answers and scales to problems with up to a million variables.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR13-hadjis15a, title = {Importance sampling over sets: a new probabilistic inference scheme}, author = {Hadjis, Stefan and Ermon, Stefano}, booktitle = {Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence}, pages = {447--456}, year = {2015}, editor = {Meila, Marina and Heskes, Tom}, volume = {R13}, series = {Proceedings of Machine Learning Research}, month = {12--16 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r13/main/assets/hadjis15a/hadjis15a.pdf}, url = {https://proceedings.mlr.press/r13/hadjis15a.html}, abstract = {Computing expectations in high-dimensional spaces is a key challenge in probabilistic inference and machine learning. Monte Carlo sampling, and importance sampling in particular, is one of the leading approaches. We propose a generalized importance sampling scheme based on randomly selecting (exponentially large) subsets of states rather than individual ones. By collecting 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 demonstrate empirically that our scheme provides accurate answers and scales to problems with up to a million variables.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Importance sampling over sets: a new probabilistic inference scheme %A Stefan Hadjis %A Stefano Ermon %B Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2015 %E Marina Meila %E Tom Heskes %F pmlr-vR13-hadjis15a %I PMLR %P 447--456 %U https://proceedings.mlr.press/r13/hadjis15a.html %V R13 %X Computing expectations in high-dimensional spaces is a key challenge in probabilistic inference and machine learning. Monte Carlo sampling, and importance sampling in particular, is one of the leading approaches. We propose a generalized importance sampling scheme based on randomly selecting (exponentially large) subsets of states rather than individual ones. By collecting 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 demonstrate empirically that our scheme provides accurate answers and scales to problems with up to a million variables. %Z Reissued by PMLR on 04 October 2026.
APA
Hadjis, S. & Ermon, S.. (2015). Importance sampling over sets: a new probabilistic inference scheme. Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R13:447-456 Available from https://proceedings.mlr.press/r13/hadjis15a.html. Reissued by PMLR on 04 October 2026.

Related Material