A Caltech Library Service

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

Tan, Vincent Y. F. and Anandkumar, Animashree and Tong, Lang and Willsky, Alan S. (2011) A Large-Deviation Analysis of the Maximum-Likelihood Learning of Markov Tree Structures. IEEE Transactions on Information Theory, 57 (3). pp. 1714-1735. ISSN 0018-9448.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


The problem of maximum-likelihood (ML) estimation of discrete tree-structured distributions is considered. Chow and Liu established that ML-estimation reduces to the construction of a maximum-weight spanning tree using the empirical mutual information quantities as the edge weights. Using the theory of large-deviations, we analyze the exponent associated with the error probability of the event that the ML-estimate of the Markov tree structure differs from the true tree structure, given a set of independently drawn samples. By exploiting the fact that the output of ML-estimation is a tree, we establish that the error exponent is equal to the exponential rate of decay of a single dominant crossover event. We prove that in this dominant crossover event, a non-neighbor node pair replaces a true edge of the distribution that is along the path of edges in the true tree graph connecting the nodes in the non-neighbor pair. Using ideas from Euclidean information theory, we then analyze the scenario of ML-estimation in the very noisy learning regime and show that the error exponent can be approximated as a ratio, which is interpreted as the signal-to-noise ratio (SNR) for learning tree distributions. We show via numerical experiments that in this regime, our SNR approximation is accurate.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Additional Information:© 2011 IEEE. Manuscript received May 06, 2009; revised October 19, 2010; accepted November 18, 2010. Date of current version February 18, 2011. This work was supported in part by A*STAR, Singapore, by a MURI funded through ARO Grant W911NF-06-1-0076 and by AFOSR Grant FA9550-08-1-0180 and in part by the Army Research Office MURI Program under award W911NF-08-1-0238. The material in this paper was presented in part at the International Symposium on Information Theory (ISIT), Seoul, Korea, June 2009. V. Y. F. Tan performed this work while at MIT. The authors would like to thank the anonymous referees and Associate Editor A. Krzyzak who have helped to improve the exposition. One reviewer, in particular, helped highlight the connection of this work with robust hypothesis testing, leading to Section V-D. The authors would also like to thank Prof. L. Zheng, M. Agrawal, and A. Olshevsky for many stimulating discussions.
Funding AgencyGrant Number
Agency for Science, Technology and Research (A*STAR)UNSPECIFIED
Army Research Office (ARO)W911NF-06-1-0076
Air Force Office of Scientific Research (AFOSR)FA9550-08-1-0180
Army Research Office (ARO)W911NF-08-1-0238
Subject Keywords:Error exponent, Euclidean information theory, large-deviations principle, Markov structure, maximum-likelihood (ML) distribution estimation, tree-structured distributions
Issue or Number:3
Record Number:CaltechAUTHORS:20170922-092634649
Persistent URL:
Official Citation:V. Y. F. Tan, A. Anandkumar, L. Tong and A. S. Willsky, "A Large-Deviation Analysis of the Maximum-Likelihood Learning of Markov Tree Structures," in IEEE Transactions on Information Theory, vol. 57, no. 3, pp. 1714-1735, March 2011. doi: 10.1109/TIT.2011.2104513 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:81737
Deposited By: Tony Diaz
Deposited On:22 Sep 2017 16:33
Last Modified:03 Oct 2019 18:46

Repository Staff Only: item control page