A Caltech Library Service

Learning High-Dimensional Markov Forest Distributions: Analysis of Error Rates

Tan, Vincent Y. F. and Anandkumar, Animashree and Willsky, Alan S. (2011) Learning High-Dimensional Markov Forest Distributions: Analysis of Error Rates. Journal of Machine Learning Research, 12 . pp. 1617-1653. ISSN 1533-7928.

[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 learning forest-structured discrete graphical models from i.i.d. samples is considered. An algorithm based on pruning of the Chow-Liu tree through adaptive thresholding is proposed. It is shown that this algorithm is both structurally consistent and risk consistent and the error probability of structure learning decays faster than any polynomial in the number of samples under fixed model size. For the high-dimensional scenario where the size of the model d and the number of edges k scale with the number of samples n, sufficient conditions on (n,d,k) are given for the algorithm to satisfy structural and risk consistencies. In addition, the extremal structures for learning are identified; we prove that the independent (resp., tree) model is the hardest (resp., easiest) to learn using the proposed algorithm in terms of error rates for structure learning.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Additional Information:© 2011 Vincent Tan, Animashree Anandkumar and Alan Willsky. This work was supported by a AFOSR funded through Grant FA9559-08-1-1080, a MURI funded through ARO Grant W911NF-06-1-0076 and a MURI funded through AFOSR Grant FA9550-06-1-0324. V. Tan is also funded by A*STAR, Singapore. The authors would like to thank Sanjoy Mitter, Lav Varshney, Matt Johnson and James Saunderson for discussions. The authors would also like to thank Rui Wu (UIUC) for pointing out an error in the proof of Theorem 3.
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)FA9559-08-1-1080
Army Research Office (ARO)W911NF-06-1-0076
Air Force Office of Scientific Research (AFOSR)FA9550-06-1-0324
Agency for Science, Technology and Research (A*STAR)UNSPECIFIED
Subject Keywords:graphical models, forest distributions, structural consistency, risk consistency, method of types
Record Number:CaltechAUTHORS:20170927-144736867
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:81885
Deposited By: Tony Diaz
Deposited On:27 Sep 2017 21:58
Last Modified:03 Oct 2019 18:48

Repository Staff Only: item control page