NDLI: Learning Gaussian Tree Models: Analysis of Error Exponents and Extremal Structures

Content Provider	IEEE Xplore Digital Library
Author	Tan, V.Y.F. Anandkumar, A. Willsky, A.S.
Copyright Year	1991
Abstract	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.
Sponsorship	IEEE Signal Processing Society
Starting Page	2701
Ending Page	2714
Page Count	14
File Size	808935
File Format	PDF
ISSN	1053587X
Volume Number	58
Issue Number	5
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2010-05-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Error analysis Tree data structures Tree graphs Error probability Graphical models Maximum likelihood estimation Gaussian distribution Signal processing algorithms Noise reduction Information theory tree distributions Error exponents Euclidean information theory Gauss-Markov random fields Gaussian graphical models large deviations structure learning
Content Type	Text
Resource Type	Article
Subject	Signal Processing Electrical and Electronic Engineering

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

How do the structure and the parameters of Gaussian tree models affect structure learning?

A Large-Deviation Analysis of the Maximum-Likelihood Learning of Markov Tree Structures

A large-deviation analysis for the maximum likelihood learning of tree structures

Learning gaussian tree models: analysis of error exponents and extremal structures (2009).

Learning Gaussian Tree Models: Analysis of Error Exponents and Extremal Structures (2010)

Learning Gaussian tree models: Analysis of error exponents and extremal structures (2010)

Estimation in Gaussian Graphical Models Using Tractable Subgraphs: A Walk-Sum Analysis

Sample complexity of determining structures of graphical models

Learning Gaussian tree models: Analysis of error exponents and extremal structures. arXiv:0909.5216 (2009)

Learning Gaussian Tree Models: Analysis of Error Exponents and Extremal Structures

Similar Documents

How do the structure and the parameters of Gaussian tree models affect structure learning?

A Large-Deviation Analysis of the Maximum-Likelihood Learning of Markov Tree Structures

A large-deviation analysis for the maximum likelihood learning of tree structures

Learning gaussian tree models: analysis of error exponents and extremal structures (2009).

Learning Gaussian Tree Models: Analysis of Error Exponents and Extremal Structures (2010)

Learning Gaussian tree models: Analysis of error exponents and extremal structures (2010)

Estimation in Gaussian Graphical Models Using Tractable Subgraphs: A Walk-Sum Analysis

Sample complexity of determining structures of graphical models

Learning Gaussian tree models: Analysis of error exponents and extremal structures. arXiv:0909.5216 (2009)

Learning Gaussian Tree Models: Analysis of Error Exponents and Extremal Structures