Learning a tree-structured ising model in order to make predictions
We study the problem of learning a tree Ising model from samples such that subsequent predictions made using the model are accurate. The prediction task considered in this paper is that of predicting the values of a subset of variables given values of some other subset of variables. Virtually all pr...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute of Mathematical Statistics
2021
|
| Online Access: | https://hdl.handle.net/1721.1/129620 |
| _version_ | 1826207726693253120 |
|---|---|
| author | Bresler, Guy Karzand, Mina |
| 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 Karzand, Mina |
| author_sort | Bresler, Guy |
| collection | MIT |
| description | We study the problem of learning a tree Ising model from samples such that subsequent predictions made using the model are accurate. The prediction task considered in this paper is that of predicting the values of a subset of variables given values of some other subset of variables. Virtually all previous work on graphical model learning has focused on recovering the true underlying graph. We define a distance (“small set TV” or ssTV) between distributions P and Q by taking the maximum, over all subsets S of a given size, of the total variation between the marginals of P and Q on S; this distance captures the accuracy of the prediction task of interest. We derive nonasymptotic bounds on the number of samples needed to get a distribution (from the same class) with small ssTV relative to the one generating the samples. One of the main messages of this paper is that far fewer samples are needed than for recovering the underlying tree, which means that accurate predictions are possible using the wrong tree. |
| first_indexed | 2024-09-23T13:54:01Z |
| format | Article |
| id | mit-1721.1/129620 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T13:54:01Z |
| publishDate | 2021 |
| publisher | Institute of Mathematical Statistics |
| record_format | dspace |
| spelling | mit-1721.1/1296202022-09-28T16:57:15Z Learning a tree-structured ising model in order to make predictions Bresler, Guy Karzand, Mina Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems We study the problem of learning a tree Ising model from samples such that subsequent predictions made using the model are accurate. The prediction task considered in this paper is that of predicting the values of a subset of variables given values of some other subset of variables. Virtually all previous work on graphical model learning has focused on recovering the true underlying graph. We define a distance (“small set TV” or ssTV) between distributions P and Q by taking the maximum, over all subsets S of a given size, of the total variation between the marginals of P and Q on S; this distance captures the accuracy of the prediction task of interest. We derive nonasymptotic bounds on the number of samples needed to get a distribution (from the same class) with small ssTV relative to the one generating the samples. One of the main messages of this paper is that far fewer samples are needed than for recovering the underlying tree, which means that accurate predictions are possible using the wrong tree. United States. Office of Naval Research (Grant N00014-17-1-2147) United States. Defense Advanced Research Projects Agency (Grant W911NF-16-1-0551) National Science Foundation (U.S.). Computing and Communication Foundation (Grant CCF-1565516) 2021-02-02T13:01:12Z 2021-02-02T13:01:12Z 2020-04 2020-12-03T17:34:34Z Article http://purl.org/eprint/type/JournalArticle 0090-5364 https://hdl.handle.net/1721.1/129620 Bresler, Guy and Mina Karzand. “Learning a tree-structured ising model in order to make predictions.” Annals of Statistics, 48, 2 (April 2020): 713-737 © 2020 The Author(s) en 10.1214/19-AOS1808 Annals of Statistics Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Mathematical Statistics arXiv |
| spellingShingle | Bresler, Guy Karzand, Mina Learning a tree-structured ising model in order to make predictions |
| title | Learning a tree-structured ising model in order to make predictions |
| title_full | Learning a tree-structured ising model in order to make predictions |
| title_fullStr | Learning a tree-structured ising model in order to make predictions |
| title_full_unstemmed | Learning a tree-structured ising model in order to make predictions |
| title_short | Learning a tree-structured ising model in order to make predictions |
| title_sort | learning a tree structured ising model in order to make predictions |
| url | https://hdl.handle.net/1721.1/129620 |
| work_keys_str_mv | AT breslerguy learningatreestructuredisingmodelinordertomakepredictions AT karzandmina learningatreestructuredisingmodelinordertomakepredictions |