Learning Graphical Models From the Glauber Dynamics

DOI10.1109/TIT.2017.2713828zbMATH Open1395.62254arXiv1410.7659OpenAlexW2622935962WikidataQ105584788 ScholiaQ105584788MaRDI QIDQ5375563FDOQ5375563

Authors: Guy Bresler, David Gamarnik, Devavrat Shah 

Publication date: 14 September 2018

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

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.

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

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

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)

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
• Title not available (Why is that?)
• 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)