Inference and sampling of K33-free ising models

Valerii Likhosherstov, Yury Maximov, Michael Chertkov

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    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 K33 (minor)-free topologies of zero-field Ising models - a generalization of planar graphs with a potentially unbounded genus.

    Original languageEnglish
    Title of host publication36th International Conference on Machine Learning, ICML 2019
    PublisherInternational Machine Learning Society (IMLS)
    Pages6996-7005
    Number of pages10
    ISBN (Electronic)9781510886988
    Publication statusPublished - 2019
    Event36th International Conference on Machine Learning, ICML 2019 - Long Beach, United States
    Duration: 9 Jun 201915 Jun 2019

    Publication series

    Name36th International Conference on Machine Learning, ICML 2019
    Volume2019-June

    Conference

    Conference36th International Conference on Machine Learning, ICML 2019
    Country/TerritoryUnited States
    CityLong Beach
    Period9/06/1915/06/19

    Fingerprint

    Dive into the research topics of 'Inference and sampling of K33-free ising models'. Together they form a unique fingerprint.

    Cite this