Learning Gaussian Tree Models: Analysis of Error Exponents and Extremal Structures
The problem of learning tree-structured Gaussian graphical models from independent and identically distributed (i.i.d.) samples is considered. The influence of the tree structure and the parameters of the Gaussian distribution on the learning rate as the number of samples increases is discussed. Spe...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2011
|
| Online Access: | http://hdl.handle.net/1721.1/62145 https://orcid.org/0000-0003-0149-5888 |
| _version_ | 1811085383919730688 |
|---|---|
| author | Tan, Vincent Yan Fu Anandkumar, Animashree Willsky, Alan S. |
| 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 Tan, Vincent Yan Fu Anandkumar, Animashree Willsky, Alan S. |
| author_sort | Tan, Vincent Yan Fu |
| collection | MIT |
| description | The problem of learning tree-structured Gaussian graphical models from independent and identically distributed (i.i.d.) samples is considered. The influence of the tree structure and the parameters of the Gaussian distribution on the learning rate as the number of samples increases is discussed. Specifically, the error exponent corresponding to the event that the estimated tree structure differs from the actual unknown tree structure of the distribution is analyzed. Finding the error exponent reduces to a least-squares problem in the very noisy learning regime. In this regime, it is shown that the extremal tree structure that minimizes the error exponent is the star for any fixed set of correlation coefficients on the edges of the tree. If the magnitudes of all the correlation coefficients are less than 0.63, it is also shown that the tree structure that maximizes the error exponent is the Markov chain. In other words, the star and the chain graphs represent the hardest and the easiest structures to learn in the class of tree-structured Gaussian graphical models. This result can also be intuitively explained by correlation decay: pairs of nodes which are far apart, in terms of graph distance, are unlikely to be mistaken as edges by the maximum-likelihood estimator in the asymptotic regime. |
| first_indexed | 2024-09-23T13:08:44Z |
| format | Article |
| id | mit-1721.1/62145 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:08:44Z |
| publishDate | 2011 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/621452022-10-01T13:16:48Z Learning Gaussian Tree Models: Analysis of Error Exponents and Extremal Structures Tan, Vincent Yan Fu Anandkumar, Animashree Willsky, Alan S. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Willsky, Alan S. Tan, Vincent Yan Fu Anandkumar, Animashree Willsky, Alan S. The problem of learning tree-structured Gaussian graphical models from independent and identically distributed (i.i.d.) samples is considered. The influence of the tree structure and the parameters of the Gaussian distribution on the learning rate as the number of samples increases is discussed. Specifically, the error exponent corresponding to the event that the estimated tree structure differs from the actual unknown tree structure of the distribution is analyzed. Finding the error exponent reduces to a least-squares problem in the very noisy learning regime. In this regime, it is shown that the extremal tree structure that minimizes the error exponent is the star for any fixed set of correlation coefficients on the edges of the tree. If the magnitudes of all the correlation coefficients are less than 0.63, it is also shown that the tree structure that maximizes the error exponent is the Markov chain. In other words, the star and the chain graphs represent the hardest and the easiest structures to learn in the class of tree-structured Gaussian graphical models. This result can also be intuitively explained by correlation decay: pairs of nodes which are far apart, in terms of graph distance, are unlikely to be mistaken as edges by the maximum-likelihood estimator in the asymptotic regime. United States. Air Force Office of Scientific Research (Grant FA9550-08-1-1080) United States. Army Research Office (MURI Grant No. W911NF-06-1-0076) Multidisciplinary University Research Initiative (MURI) (AFOSR Grant FA9550-06-1-0324) Singapore. Agency for Science, Technology and Research 2011-04-06T13:48:59Z 2011-04-06T13:48:59Z 2010-04 2008-09 Article http://purl.org/eprint/type/JournalArticle 1053-587X INSPEC Accession Number: 11228720 http://hdl.handle.net/1721.1/62145 Tan, V.Y.F., A. Anandkumar, and A.S. Willsky. “Learning Gaussian Tree Models: Analysis of Error Exponents and Extremal Structures.” Signal Processing, IEEE Transactions on 58.5 (2010): 2701-2714. © Copyright 20110 IEEE https://orcid.org/0000-0003-0149-5888 en_US http://dx.doi.org/10.1109/tsp.2010.2042478 IEEE Transactions on Signal Processing Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Institute of Electrical and Electronics Engineers IEEE |
| spellingShingle | Tan, Vincent Yan Fu Anandkumar, Animashree Willsky, Alan S. Learning Gaussian Tree Models: Analysis of Error Exponents and Extremal Structures |
| title | Learning Gaussian Tree Models: Analysis of Error Exponents and Extremal Structures |
| title_full | Learning Gaussian Tree Models: Analysis of Error Exponents and Extremal Structures |
| title_fullStr | Learning Gaussian Tree Models: Analysis of Error Exponents and Extremal Structures |
| title_full_unstemmed | Learning Gaussian Tree Models: Analysis of Error Exponents and Extremal Structures |
| title_short | Learning Gaussian Tree Models: Analysis of Error Exponents and Extremal Structures |
| title_sort | learning gaussian tree models analysis of error exponents and extremal structures |
| url | http://hdl.handle.net/1721.1/62145 https://orcid.org/0000-0003-0149-5888 |
| work_keys_str_mv | AT tanvincentyanfu learninggaussiantreemodelsanalysisoferrorexponentsandextremalstructures AT anandkumaranimashree learninggaussiantreemodelsanalysisoferrorexponentsandextremalstructures AT willskyalans learninggaussiantreemodelsanalysisoferrorexponentsandextremalstructures |