A Lower Bound on the Partition Function of Attractive Graphical Models in the Continuous Case

Nicholas Ruozzi
Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, PMLR 54:1048-1056, 2017.

Abstract

Computing the partition function of an arbitrary graphical model is generally intractable. As a result, approximate inference techniques such as loopy belief propagation and expectation propagation are used to compute an approximation to the true partition function. However, due to general issues of intractability in the continuous case, our understanding of these approximations is relatively limited. In particular, a number of theoretical results known for these approximations in the discrete case are missing in the continuous case. In this work, we use graph covers to extend several such results from the discrete case to the continuous case. Specifically, we provide a graph cover based upper bound for continuous graphical models, and we use this characterization (along with a continuous analog of a discrete correlation-type inequality) to show that the Bethe partition function also provides a lower bound on the true partition function of attractive graphical models in the continuous case.

Cite this Paper

BibTeX
@InProceedings{pmlr-v54-ruozzi17a, title = {{A Lower Bound on the Partition Function of Attractive Graphical Models in the Continuous Case}}, author = {Ruozzi, Nicholas}, booktitle = {Proceedings of the 20th International Conference on Artificial Intelligence and Statistics}, pages = {1048--1056}, year = {2017}, editor = {Singh, Aarti and Zhu, Jerry}, volume = {54}, series = {Proceedings of Machine Learning Research}, month = {20--22 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v54/ruozzi17a/ruozzi17a.pdf}, url = {https://proceedings.mlr.press/v54/ruozzi17a.html}, abstract = {Computing the partition function of an arbitrary graphical model is generally intractable. As a result, approximate inference techniques such as loopy belief propagation and expectation propagation are used to compute an approximation to the true partition function. However, due to general issues of intractability in the continuous case, our understanding of these approximations is relatively limited. In particular, a number of theoretical results known for these approximations in the discrete case are missing in the continuous case. In this work, we use graph covers to extend several such results from the discrete case to the continuous case. Specifically, we provide a graph cover based upper bound for continuous graphical models, and we use this characterization (along with a continuous analog of a discrete correlation-type inequality) to show that the Bethe partition function also provides a lower bound on the true partition function of attractive graphical models in the continuous case.} }
Endnote
%0 Conference Paper %T A Lower Bound on the Partition Function of Attractive Graphical Models in the Continuous Case %A Nicholas Ruozzi %B Proceedings of the 20th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2017 %E Aarti Singh %E Jerry Zhu %F pmlr-v54-ruozzi17a %I PMLR %P 1048--1056 %U https://proceedings.mlr.press/v54/ruozzi17a.html %V 54 %X Computing the partition function of an arbitrary graphical model is generally intractable. As a result, approximate inference techniques such as loopy belief propagation and expectation propagation are used to compute an approximation to the true partition function. However, due to general issues of intractability in the continuous case, our understanding of these approximations is relatively limited. In particular, a number of theoretical results known for these approximations in the discrete case are missing in the continuous case. In this work, we use graph covers to extend several such results from the discrete case to the continuous case. Specifically, we provide a graph cover based upper bound for continuous graphical models, and we use this characterization (along with a continuous analog of a discrete correlation-type inequality) to show that the Bethe partition function also provides a lower bound on the true partition function of attractive graphical models in the continuous case.
APA
Ruozzi, N.. (2017). A Lower Bound on the Partition Function of Attractive Graphical Models in the Continuous Case. Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 54:1048-1056 Available from https://proceedings.mlr.press/v54/ruozzi17a.html.

Related Material