Which graphical models are difficult to learn?

Abstract

We consider the problem of learning the structure of Ising models (pairwise binary Markov random fields) from i.i.d. samples. While several methods have been proposed to accomplish this task, their relative merits and limitations remain somewhat obscure. By analyzing a number of concrete examples, we show that low-complexity algorithms systematically fail when the Markov random field develops long-range correlations. More precisely, this phenomenon appears to be related to the Ising model phase transition (although it does not coincide with it).

References in corpus (4)

• Ising models on locally tree-like graphs
• High-Dimensional Graphical Model Selection Using ${\ell }_1$-Regularized Logistic Regression
• Information-theoretic limits on sparsity recovery in the high-dimensional and noisy setting
• Information-theoretic limits of selecting binary graphical models in high dimensions

Cited by in corpus (6)

• Structure learning of antiferromagnetic Ising models
• Greedy Learning of Markov Network Structure
• An Oracle Approach for Interaction Neighborhood Estimation in Random Fields
• Consistent model selection for estimating functional interactions among stochastic neurons with variable-length memory
• Scalable Coupling of Deep Learning with Logical Reasoning
• Ising Model Selection Using ${\ell }_1$-Regularized Linear Regression: A Statistical Mechanics Analysis