Efficiently Learning Ising Models on Arbitrary Graphs
We consider the problem of reconstructing the graph underlying an Ising model from i.i.d. samples. Over the last fifteen years this problem has been of significant interest in the statistics, machine learning, and statistical physics communities, and much of the effort has been directed towards find...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery (ACM)
2017
|
| Online Access: | http://hdl.handle.net/1721.1/110787 https://orcid.org/0000-0003-1303-582X |
| _version_ | 1826210833975214080 |
|---|---|
| author | Bresler, Guy |
| 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 |
| author_sort | Bresler, Guy |
| collection | MIT |
| description | We consider the problem of reconstructing the graph underlying an Ising model from i.i.d. samples. Over the last fifteen years this problem has been of significant interest in the statistics, machine learning, and statistical physics communities, and much of the effort has been directed towards finding algorithms with low computational cost for various restricted classes of models. Nevertheless, for learning Ising models on general graphs with p nodes of degree at most d, it is not known whether or not it is possible to improve upon the p[superscript d] computation needed to exhaustively search over all possible neighborhoods for each node. In this paper we show that a simple greedy procedure allows to learn the structure of an Ising model on an arbitrary bounded-degree graph in time on the order of p[superscript 2]. We make no assumptions on the parameters except what is necessary for identifiability of the model, and in particular the results hold at low-temperatures as well as for highly non-uniform models. The proof rests on a new structural property of Ising models: we show that for any node there exists at least one neighbor with which it has a high mutual information. This structural property may be of independent interest. |
| first_indexed | 2024-09-23T14:56:10Z |
| format | Article |
| id | mit-1721.1/110787 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:56:10Z |
| publishDate | 2017 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1107872022-09-29T11:32:17Z Efficiently Learning Ising Models on Arbitrary Graphs Bresler, Guy Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Bresler, Guy We consider the problem of reconstructing the graph underlying an Ising model from i.i.d. samples. Over the last fifteen years this problem has been of significant interest in the statistics, machine learning, and statistical physics communities, and much of the effort has been directed towards finding algorithms with low computational cost for various restricted classes of models. Nevertheless, for learning Ising models on general graphs with p nodes of degree at most d, it is not known whether or not it is possible to improve upon the p[superscript d] computation needed to exhaustively search over all possible neighborhoods for each node. In this paper we show that a simple greedy procedure allows to learn the structure of an Ising model on an arbitrary bounded-degree graph in time on the order of p[superscript 2]. We make no assumptions on the parameters except what is necessary for identifiability of the model, and in particular the results hold at low-temperatures as well as for highly non-uniform models. The proof rests on a new structural property of Ising models: we show that for any node there exists at least one neighbor with which it has a high mutual information. This structural property may be of independent interest. 2017-07-20T15:21:12Z 2017-07-20T15:21:12Z 2015-06 Article http://purl.org/eprint/type/JournalArticle 978-1-4503-3536-2 http://hdl.handle.net/1721.1/110787 Bresler, Guy. “Efficiently Learning Ising Models on Arbitrary Graphs.” ACM Press, Forty-Seventh Annual ACM on Symposium on Theory of Computing - STOC '15, Portand, Oregon, USA, 14-17 Junes, 2015. Association for Computing Machinery (ACM), 2015, pp. 771–782. https://orcid.org/0000-0003-1303-582X en_US http://dx.doi.org/10.1145/2746539.2746631 Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing - STOC '15 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) arXiv |
| spellingShingle | Bresler, Guy Efficiently Learning Ising Models on Arbitrary Graphs |
| title | Efficiently Learning Ising Models on Arbitrary Graphs |
| title_full | Efficiently Learning Ising Models on Arbitrary Graphs |
| title_fullStr | Efficiently Learning Ising Models on Arbitrary Graphs |
| title_full_unstemmed | Efficiently Learning Ising Models on Arbitrary Graphs |
| title_short | Efficiently Learning Ising Models on Arbitrary Graphs |
| title_sort | efficiently learning ising models on arbitrary graphs |
| url | http://hdl.handle.net/1721.1/110787 https://orcid.org/0000-0003-1303-582X |
| work_keys_str_mv | AT breslerguy efficientlylearningisingmodelsonarbitrarygraphs |