Learning Graphical Models From the Glauber Dynamics

DOI10.1109/TIT.2017.2713828MaRDI QIDQ5375563zbMATH OpenOpenAlexWikidataFDO

Authors Guy Bresler, David Gamarnik, Devavrat Shah

Publication date 14 September 2018

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.7659

Mathematics Subject Classification ID

Markov processes: estimation; hidden Markov models (62M05) Applications of graph theory (05C90) Estimation in multivariate analysis (62H12) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Graphical methods in statistics (62A09) Applications of graph theory to circuits and networks (94C15)

Abstract: In this paper we consider the problem of learning undirected graphical models from data generated according to the Glauber dynamics. The Glauber dynamics is a Markov chain that sequentially updates individual nodes (variables) in a graphical model and it is frequently used to sample from the stationary distribution (to which it converges given sufficient time). Additionally, the Glauber dynamics is a natural dynamical model in a variety of settings. This work deviates from the standard formulation of graphical model learning in the literature, where one assumes access to i.i.d. samples from the distribution. Much of the research on graphical model learning has been directed towards finding algorithms with low computational cost. As the main result of this work, we establish that the problem of reconstructing binary pairwise graphical models is computationally tractable when we observe the Glauber dynamics. Specifically, we show that a binary pairwise graphical model on $p$ nodes with maximum degree $d$ can be learned in time $f(d)p^{2}logp$, for a function $f(d)$, using nearly the information-theoretic minimum number of samples.

Recommendations

• Learning Gaussian graphical models with latent confounders
• Bayesian structure learning in graphical models
• Gaussian graphical models
• Learning graphical models with hubs
• GRAPHICAL MODELS IN MACHINE LEARNING, NETWORKS AND UNCERTAINTY QUANTIFICATION
• scientific article; zbMATH DE number 1728719
• scientific article; zbMATH DE number 1568690
• Graphical models
• Graphical models

Cited in

(6)

• Estimating the interaction graph of stochastic neuronal dynamics by observing only pairs of neurons
• Exact recovery in the Ising blockmodel
• Structure recovery for partially observed discrete Markov random fields on graphs under not necessarily positive distributions
• Model selection for Markov random fields on graphs under a mixing condition
• scientific article; zbMATH DE number 1728719 (Why is no real title available?)
• Higher-order interaction learning of line failure cascading in power networks

This page was built for publication: Learning Graphical Models From the Glauber Dynamics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5375563)