arXiv Analytics

Sign in

arXiv:0910.5761 [stat.ML]AbstractReferencesReviewsResources

Which graphical models are difficult to learn?

Jose Bento, Andrea Montanari

Published 2009-10-30Version 1

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

Related articles: Most relevant | Search more
arXiv:2210.15471 [stat.ML] (Published 2022-10-27)
Adaptive Estimation of $\text{MTP}_2$ Graphical Models
arXiv:2009.00038 [stat.ML] (Published 2020-08-31)
Uncertainty quantification for Markov Random Fields
arXiv:1107.4067 [stat.ML] (Published 2011-07-20, updated 2012-03-18)
Finding Non-overlapping Clusters for Generalized Inference Over Graphical Models