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. https://resolver.caltech.edu/CaltechAUTHORS:20170927-144736867
![]() |
PDF
- Published Version
See Usage Policy. 323Kb |
![]() |
PDF
- Submitted Version
See Usage Policy. 492Kb |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20170927-144736867
Abstract
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: |
| ||||||||||
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. | ||||||||||
Funders: |
| ||||||||||
Subject Keywords: | graphical models, forest distributions, structural consistency, risk consistency, method of types | ||||||||||
Record Number: | CaltechAUTHORS:20170927-144736867 | ||||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20170927-144736867 | ||||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||
ID Code: | 81885 | ||||||||||
Collection: | CaltechAUTHORS | ||||||||||
Deposited By: | Tony Diaz | ||||||||||
Deposited On: | 27 Sep 2017 21:58 | ||||||||||
Last Modified: | 03 Oct 2019 18:48 |
Repository Staff Only: item control page