TY - GEN
T1 - Inference and sampling of K33-free ising models
AU - Likhosherstov, Valerii
AU - Maximov, Yury
AU - Chertkov, Michael
N1 - Funding Information:
This work was supported by the U.S. Department of Energy through the Los Alamos National Laboratory as part of LDRD and the DOE Grid Modernization Laboratory Consortium (GMLC). Los Alamos National Laboratory is operated by Triad National Security, LLC, for the National Nuclear Security Administration of U.S. Department of Energy (Contract No. 89233218CNA000001).
Publisher Copyright:
© 36th International Conference on Machine Learning, ICML 2019. All rights reserved.
PY - 2019
Y1 - 2019
N2 - 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 K33 (minor)-free topologies of zero-field Ising models - a generalization of planar graphs with a potentially unbounded genus.
AB - 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 K33 (minor)-free topologies of zero-field Ising models - a generalization of planar graphs with a potentially unbounded genus.
UR - http://www.scopus.com/inward/record.url?scp=85078330423&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85078330423&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85078330423
T3 - 36th International Conference on Machine Learning, ICML 2019
SP - 6996
EP - 7005
BT - 36th International Conference on Machine Learning, ICML 2019
PB - International Machine Learning Society (IMLS)
T2 - 36th International Conference on Machine Learning, ICML 2019
Y2 - 9 June 2019 through 15 June 2019
ER -