Abstraction Sampling in Graphical Models

Filjor Broka, Rina Dechter, Alexander Ihler, Kalev Kask
Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, PMLR R16:631-640, 2018.

Abstract

We present a new sampling scheme for approx- imating hard to compute queries over graphical models, such as computing the partition func- tion. The scheme builds upon exact algorithms that traverse a weighted directed state-space graph representing a global function over a graphical model (e.g., probability distribution). With the aid of an abstraction function and ran- domization, the state space can be compacted (or trimmed) to facilitate tractable computa- tion, yielding a Monte Carlo Estimate that is unbiased. We present the general scheme and analyze its properties analytically and empiri- cally, investigating two specific ideas for pick- ing abstractions - targeting reduction of vari- ance or search space size.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR16-broka18a, title = {Abstraction Sampling in Graphical Models}, author = {Broka, Filjor and Dechter, Rina and Ihler, Alexander and Kask, Kalev}, booktitle = {Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence}, pages = {631--640}, year = {2018}, editor = {Globerson, Amir and Silva, Ricardo}, volume = {R16}, series = {Proceedings of Machine Learning Research}, month = {06--10 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r16/main/assets/broka18a/broka18a.pdf}, url = {https://proceedings.mlr.press/r16/broka18a.html}, abstract = {We present a new sampling scheme for approx- imating hard to compute queries over graphical models, such as computing the partition func- tion. The scheme builds upon exact algorithms that traverse a weighted directed state-space graph representing a global function over a graphical model (e.g., probability distribution). With the aid of an abstraction function and ran- domization, the state space can be compacted (or trimmed) to facilitate tractable computa- tion, yielding a Monte Carlo Estimate that is unbiased. We present the general scheme and analyze its properties analytically and empiri- cally, investigating two specific ideas for pick- ing abstractions - targeting reduction of vari- ance or search space size.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Abstraction Sampling in Graphical Models %A Filjor Broka %A Rina Dechter %A Alexander Ihler %A Kalev Kask %B Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2018 %E Amir Globerson %E Ricardo Silva %F pmlr-vR16-broka18a %I PMLR %P 631--640 %U https://proceedings.mlr.press/r16/broka18a.html %V R16 %X We present a new sampling scheme for approx- imating hard to compute queries over graphical models, such as computing the partition func- tion. The scheme builds upon exact algorithms that traverse a weighted directed state-space graph representing a global function over a graphical model (e.g., probability distribution). With the aid of an abstraction function and ran- domization, the state space can be compacted (or trimmed) to facilitate tractable computa- tion, yielding a Monte Carlo Estimate that is unbiased. We present the general scheme and analyze its properties analytically and empiri- cally, investigating two specific ideas for pick- ing abstractions - targeting reduction of vari- ance or search space size. %Z Reissued by PMLR on 04 October 2026.
APA
Broka, F., Dechter, R., Ihler, A. & Kask, K.. (2018). Abstraction Sampling in Graphical Models. Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R16:631-640 Available from https://proceedings.mlr.press/r16/broka18a.html. Reissued by PMLR on 04 October 2026.

Related Material