Learning Graphical Models From the Glauber Dynamics
In this paper, we consider the problem of learning undirected graphical models from data generated according to the Glauber dynamics (also known as the Gibbs sampler). The Glauber dynamics is a Markov chain that sequentially updates individual nodes (variables) in a graphical model and it is frequen...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2019
|
| Online Access: | http://hdl.handle.net/1721.1/120526 https://orcid.org/0000-0003-1303-582X https://orcid.org/0000-0001-8898-8778 https://orcid.org/0000-0003-0737-3259 |
| _version_ | 1826207602540806144 |
|---|---|
| author | Bresler, Guy Gamarnik, David Shah, Devavrat |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Bresler, Guy Gamarnik, David Shah, Devavrat |
| author_sort | Bresler, Guy |
| collection | MIT |
| description | In this paper, we consider the problem of learning undirected graphical models from data generated according to the Glauber dynamics (also known as the Gibbs sampler). 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 paper deviates from the standard formulation of graphical model learning in the literature, where one assumes access to independent identically distributed samples from the distribution. Much of the research on graphical model learning has been directed toward finding algorithms with low computational cost. As the main result of this paper, 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[superscript 2]log p, for a function f(d) defined explicitly in this paper, using nearly the information-Theoretic minimum number of samples. |
| first_indexed | 2024-09-23T13:52:07Z |
| format | Article |
| id | mit-1721.1/120526 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T13:52:07Z |
| publishDate | 2019 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1205262022-09-28T16:45:27Z Learning Graphical Models From the Glauber Dynamics Bresler, Guy Gamarnik, David Shah, Devavrat Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Sloan School of Management Bresler, Guy Gamarnik, David Shah, Devavrat In this paper, we consider the problem of learning undirected graphical models from data generated according to the Glauber dynamics (also known as the Gibbs sampler). 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 paper deviates from the standard formulation of graphical model learning in the literature, where one assumes access to independent identically distributed samples from the distribution. Much of the research on graphical model learning has been directed toward finding algorithms with low computational cost. As the main result of this paper, 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[superscript 2]log p, for a function f(d) defined explicitly in this paper, using nearly the information-Theoretic minimum number of samples. National Science Foundation (U.S.) (Grant CNS-11619) National Science Foundation (U.S.) (Grant CMMI-13351) United States. Army Research Office. Multidisciplinary University Research Initiative (Award W911NF-11-1-00) 2019-02-21T19:01:07Z 2019-02-21T19:01:07Z 2017-06 2019-02-13T18:03:45Z Article http://purl.org/eprint/type/JournalArticle 0018-9448 1557-9654 http://hdl.handle.net/1721.1/120526 Bresler, Guy, David Gamarnik, and Devavrat Shah. “Learning Graphical Models From the Glauber Dynamics.” IEEE Transactions on Information Theory 64, no. 6 (June 2018): 4072–4080. © 1963-2012 IEEE https://orcid.org/0000-0003-1303-582X https://orcid.org/0000-0001-8898-8778 https://orcid.org/0000-0003-0737-3259 http://dx.doi.org/10.1109/TIT.2017.2713828 IEEE Transactions on Information Theory Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Bresler, Guy Gamarnik, David Shah, Devavrat Learning Graphical Models From the Glauber Dynamics |
| title | Learning Graphical Models From the Glauber Dynamics |
| title_full | Learning Graphical Models From the Glauber Dynamics |
| title_fullStr | Learning Graphical Models From the Glauber Dynamics |
| title_full_unstemmed | Learning Graphical Models From the Glauber Dynamics |
| title_short | Learning Graphical Models From the Glauber Dynamics |
| title_sort | learning graphical models from the glauber dynamics |
| url | http://hdl.handle.net/1721.1/120526 https://orcid.org/0000-0003-1303-582X https://orcid.org/0000-0001-8898-8778 https://orcid.org/0000-0003-0737-3259 |
| work_keys_str_mv | AT breslerguy learninggraphicalmodelsfromtheglauberdynamics AT gamarnikdavid learninggraphicalmodelsfromtheglauberdynamics AT shahdevavrat learninggraphicalmodelsfromtheglauberdynamics |