Bucket Renormalization for Approximate Inference

Sungsoo Ahn, Michael Chertkov, Adrian Weller, Jinwoo Shin
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:109-118, 2018.

Abstract

Probabilistic graphical models are a key tool in machine learning applications. Computing the partition function, i.e., normalizing constant, is a fundamental task of statistical inference but is generally computationally intractable, leading to extensive study of approximation methods. Iterative variational methods are a popular and successful family of approaches. However, even state of the art variational methods can return poor results or fail to converge on difficult instances. In this paper, we instead consider computing the partition function via sequential summation over variables. We develop robust approximate algorithms by combining ideas from mini-bucket elimination with tensor network and renormalization group methods from statistical physics. The resulting “convergence-free” methods show good empirical performance on both synthetic and real-world benchmark models, even for difficult instances.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-ahn18a, title = {Bucket Renormalization for Approximate Inference}, author = {Ahn, Sungsoo and Chertkov, Michael and Weller, Adrian and Shin, Jinwoo}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {109--118}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/ahn18a/ahn18a.pdf}, url = {https://proceedings.mlr.press/v80/ahn18a.html}, abstract = {Probabilistic graphical models are a key tool in machine learning applications. Computing the partition function, i.e., normalizing constant, is a fundamental task of statistical inference but is generally computationally intractable, leading to extensive study of approximation methods. Iterative variational methods are a popular and successful family of approaches. However, even state of the art variational methods can return poor results or fail to converge on difficult instances. In this paper, we instead consider computing the partition function via sequential summation over variables. We develop robust approximate algorithms by combining ideas from mini-bucket elimination with tensor network and renormalization group methods from statistical physics. The resulting “convergence-free” methods show good empirical performance on both synthetic and real-world benchmark models, even for difficult instances.} }
Endnote
%0 Conference Paper %T Bucket Renormalization for Approximate Inference %A Sungsoo Ahn %A Michael Chertkov %A Adrian Weller %A Jinwoo Shin %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-ahn18a %I PMLR %P 109--118 %U https://proceedings.mlr.press/v80/ahn18a.html %V 80 %X Probabilistic graphical models are a key tool in machine learning applications. Computing the partition function, i.e., normalizing constant, is a fundamental task of statistical inference but is generally computationally intractable, leading to extensive study of approximation methods. Iterative variational methods are a popular and successful family of approaches. However, even state of the art variational methods can return poor results or fail to converge on difficult instances. In this paper, we instead consider computing the partition function via sequential summation over variables. We develop robust approximate algorithms by combining ideas from mini-bucket elimination with tensor network and renormalization group methods from statistical physics. The resulting “convergence-free” methods show good empirical performance on both synthetic and real-world benchmark models, even for difficult instances.
APA
Ahn, S., Chertkov, M., Weller, A. & Shin, J.. (2018). Bucket Renormalization for Approximate Inference. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:109-118 Available from https://proceedings.mlr.press/v80/ahn18a.html.

Related Material