Tractable minor-free generalization of planar zero-field Ising models

Valerii Likhosherstov, Yury Maximov, Michael Chertkov

Research output: Contribution to journalArticlepeer-review

Abstract

We present a new family of zero-field Ising models over N binary variables/spins obtained by consecutive 'gluing' of planar and O(1)-sized components and subsets of at most three vertices into a tree. The polynomial time algorithm of the dynamic programming type for solving exact inference (computing partition function) and exact sampling (generating i.i.d. samples) consists of sequential application of an efficient (for planar) or brute-force (for O(1)-sized) inference and sampling to the components as a black box. To illustrate the utility of the new family of tractable graphical models, we first build a polynomial algorithm for inference and sampling of zero-field Ising models over K 33-minor-free topologies and over K 5-minor-free topologies - both of which are extensions of the planar zero-field Ising models - which are neither genus- nor treewidth-bounded. Second, we empirically demonstrate an improvement in the approximation quality of the NP-hard problem of inference over the square-grid Ising model in a node-dependent nonzero 'magnetic' field.

Original languageEnglish
Article number124007
JournalJournal of Statistical Mechanics: Theory and Experiment
Volume2020
Issue number12
DOIs
Publication statusPublished - 21 Dec 2020
Externally publishedYes

Keywords

  • analysis of algorithms
  • inference of graphical models
  • statistical inference

Fingerprint

Dive into the research topics of 'Tractable minor-free generalization of planar zero-field Ising models'. Together they form a unique fingerprint.

Cite this