Inference and Sampling of $K_33$-free Ising Models

Valerii Likhosherstov, Yury Maximov, Misha Chertkov
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:3963-3972, 2019.

Abstract

We call an Ising model tractable when it is possible to compute its partition function value (statistical inference) in polynomial time. The tractability also implies an ability to sample configurations of this model in polynomial time. The notion of tractability extends the basic case of planar zero-field Ising models. Our starting point is to describe algorithms for the basic case, computing partition function and sampling efficiently. Then, we extend our tractable inference and sampling algorithms to models whose triconnected components are either planar or graphs of $O(1)$ size. In particular, it results in a polynomial-time inference and sampling algorithms for $K_{33}$ (minor)-free topologies of zero-field Ising models—a generalization of planar graphs with a potentially unbounded genus.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-likhosherstov19a, title = {Inference and Sampling of $K_{33}$-free Ising Models}, author = {Likhosherstov, Valerii and Maximov, Yury and Chertkov, Misha}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {3963--3972}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/likhosherstov19a/likhosherstov19a.pdf}, url = {https://proceedings.mlr.press/v97/likhosherstov19a.html}, abstract = {We call an Ising model tractable when it is possible to compute its partition function value (statistical inference) in polynomial time. The tractability also implies an ability to sample configurations of this model in polynomial time. The notion of tractability extends the basic case of planar zero-field Ising models. Our starting point is to describe algorithms for the basic case, computing partition function and sampling efficiently. Then, we extend our tractable inference and sampling algorithms to models whose triconnected components are either planar or graphs of $O(1)$ size. In particular, it results in a polynomial-time inference and sampling algorithms for $K_{33}$ (minor)-free topologies of zero-field Ising models—a generalization of planar graphs with a potentially unbounded genus.} }
Endnote
%0 Conference Paper %T Inference and Sampling of $K_33$-free Ising Models %A Valerii Likhosherstov %A Yury Maximov %A Misha Chertkov %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-likhosherstov19a %I PMLR %P 3963--3972 %U https://proceedings.mlr.press/v97/likhosherstov19a.html %V 97 %X We call an Ising model tractable when it is possible to compute its partition function value (statistical inference) in polynomial time. The tractability also implies an ability to sample configurations of this model in polynomial time. The notion of tractability extends the basic case of planar zero-field Ising models. Our starting point is to describe algorithms for the basic case, computing partition function and sampling efficiently. Then, we extend our tractable inference and sampling algorithms to models whose triconnected components are either planar or graphs of $O(1)$ size. In particular, it results in a polynomial-time inference and sampling algorithms for $K_{33}$ (minor)-free topologies of zero-field Ising models—a generalization of planar graphs with a potentially unbounded genus.
APA
Likhosherstov, V., Maximov, Y. & Chertkov, M.. (2019). Inference and Sampling of $K_33$-free Ising Models. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:3963-3972 Available from https://proceedings.mlr.press/v97/likhosherstov19a.html.

Related Material