TY - JOUR

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

AU - Likhosherstov, Valerii

AU - Maximov, Yury

AU - Chertkov, Michael

N1 - Publisher Copyright:
© 2020 IOP Publishing Ltd and SISSA Medialab srl.
Copyright:
Copyright 2021 Elsevier B.V., All rights reserved.

PY - 2020/12/21

Y1 - 2020/12/21

N2 - 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.

AB - 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.

KW - analysis of algorithms

KW - inference of graphical models

KW - statistical inference

UR - http://www.scopus.com/inward/record.url?scp=85099045825&partnerID=8YFLogxK

U2 - 10.1088/1742-5468/abcaf1

DO - 10.1088/1742-5468/abcaf1

M3 - Article

AN - SCOPUS:85099045825

VL - 2020

JO - Journal of Statistical Mechanics: Theory and Experiment

JF - Journal of Statistical Mechanics: Theory and Experiment

SN - 1742-5468

IS - 12

M1 - 124007

ER -