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

DOI10.1109/TSP.2010.2042478MaRDI QIDQ4570256zbMATH OpenOpenAlexFDO

Authors Vincent Y. F. Tan, Animashree Anandkumar, Alan S. Willsky

Publication date 9 July 2018

Published in IEEE Transactions on Signal Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0909.5216

Mathematics Subject Classification ID

Graphical methods in statistics (62A09) Random fields; image analysis (62M40) General topics in artificial intelligence (68T01) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

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.

Cited in

(5)

• Chernoff information between Gaussian trees
• Inequalities on partial correlations in Gaussian graphical models containing star shapes
• Predictive learning on hidden tree-structured Ising models
• scientific article; zbMATH DE number 6253918 (Why is no real title available?)
• High-dimensional structure estimation in Ising models: local separation criterion

This page was built for publication: Learning Gaussian Tree Models: Analysis of Error Exponents and Extremal Structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4570256)