Download: PDF
“Spectral Methods for Learning Multivariate Latent Tree Structure”
by A. Anandkumar, K. Chaudhuri, D. Hsu, S.M. Kakade, L. Song and T. Zhang
Preprint
. July 2011.
This work considers the problem of learning the structure of a broad class of multivariate latent variable tree models, which include a variety of continuous and discrete models (including the widely used linear-Gaussian models, hidden Markov models, and Markov evolutionary trees). The setting is one where we only have samples from certain observed variables in the tree and our goal is to estimate the tree structure (i.e., the graph of how the underlying hidden variables are connected to the observed variables). We provide the Spectral Recursive Grouping algorithm, an ecient and simple bottom-up procedure for recovering the tree structure from independent samples of the observed variables. Our nite sample size bounds for exact recovery of the tree structure elucidate certain natural dependencies on underlying statistical and structural properties of the underlying joint distribution. Furthermore, our sample complexity guarantees have no explicit dependence on the dimensionality of the observed variables, making the algorithm applicable to many high-dimensional settings. At the heart of our algorithm is a spectral quartet test for determining the relative topology of a quartet of variables, which only utilizes certain second order statistics and is based on the determinants of certain cross-covariance matrices.
Download: PDF
BibTeX entry:
@article{AnandkumarEtal:spectral,
author={A. Anandkumar and K. Chaudhuri and D. Hsu and S.M. Kakade and L. Song and T. Zhang},
title={{Spectral Methods for Learning Multivariate Latent Tree Structure}},
journal={Preprint, ArXiv 1107.1283},
month={July},
year={2011}
}
IEEE Copyright Information: Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works, must be obtained from the copyright holder.
(This webpage was created with bibtex2web.)