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 July 2009 | Published
Book Section - Chapter Open

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

Abstract

The problem of maximum-likelihood learning of the structure of an unknown discrete distribution from samples is considered when the distribution is Markov on a tree. Large-deviation analysis of the error in estimation of the set of edges of the tree is performed. Necessary and sufficient conditions are provided to ensure that this error probability decays exponentially. These conditions are based on the mutual information between each pair of variables being distinct from that of other pairs. The rate of error decay, or error exponent, is derived using the large-deviation principle. The error exponent is approximated using Euclidean information theory and is given by a ratio, to be interpreted as the signal-to-noise ratio (SNR) for learning. Numerical experiments show the SNR approximation is accurate.

Additional Information

© 2009 IEEE. The first author is supported by A*STAR, Singapore, 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. The second author is supported by the IBM Ph.D Fellowship for the year 2008-09 and is currently a visiting student at MIT, Cambridge, MA 02139. This work is also supported in part through collaborative participation in Communications and Networks Consortium sponsored by the U. S. Army Research Laboratory under the Collaborative Technology Alliance Program, Cooperative Agreement DAAD19-01-2-0011 and by the Army Research Office under Grant ARO-W911NF-06-1-0346.

Attached Files

Published - 05206012.pdf

Files

05206012.pdf
Files (1.0 MB)
Name Size Download all
md5:93ee7178d909eb5e96034b4bb296738e
1.0 MB Preview Download

Additional details

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