Stochastic Systems Group  

Learning Gaussian Tree Models: Analysis of Error Exponents and Extremal Structures
Vincent Tan
SSG, MIT
The problem of learning treestructured Gaussian graphical models from 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 leastsquares problem in the very noisy learning regime. In this regime, it is shown that universally, the extremal tree structures which maximize and minimize the error exponent are the star and the path (Markov chain) graphs for any fixed set of correlation coefficients on the edges of the tree. In other words, the star and the path graphs represent the hardest and the easiest structures to learn in the class of treestructured Gaussian graphical models. This result has an intuitive explanation in terms of correlation decay: pairs of nodes which are far apart, in terms of graph distance, are unlikely to be mistaken as edges by the maximumlikelihood estimator in the asymptotic regime.
Problems with this site should be emailed to jonesb@mit.edu