Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published October 2009 | Published
Book Section - Chapter Open

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

Abstract

The problem of learning tree-structured 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 least-squares 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 Markov chain for any fixed set of correlation coefficients on the edges of the tree. 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.

Additional Information

© 2009 IEEE. This work is supported in part by a AFOSR through Grant FA9550-08-1-1080, in part by a MURI funded through ARO Grant W911NF-06-1-0076 and in part under a MURI through AFOSR Grant FA9550-06-1-0324. Vincent Tan is also funded by A*STAR, Singapore.

Attached Files

Published - 05394929.pdf

Files

05394929.pdf
Files (270.8 kB)
Name Size Download all
md5:9e50dcaee4c3239142d0cf3cf3813d05
270.8 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
October 17, 2023