Spectral Methods for Learning Multivariate Latent Tree Structure

Abstract

This work considers the problem of learning the structure of multivariate linear tree models, which include a variety of directed tree graphical models with continuous, discrete, and mixed latent variables such as linear-Gaussian models, hidden Markov models, Gaussian mixture 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 each other and to the observed variables). We propose the Spectral Recursive Grouping algorithm, an efficient and simple bottom-up procedure for recovering the tree structure from independent samples of the observed variables. Our finite sample size bounds for exact recovery of the tree structure reveal 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 from second-order statistics.

References in corpus (4)

• High-dimensional Ising model selection using ${\ell }_1$-regularized logistic regression
• A Spectral Algorithm for Learning Hidden Markov Models
• Learning Mixtures of Gaussians using the k-means Algorithm
• Dimension-free tail inequalities for sums of random matrices

Cited by in corpus (10)

• A Survey on Latent Tree Models and Applications
• Discovering Structure in High-Dimensional Data Through Correlation Explanation
• Learning loopy graphical models with latent variables: Efficient methods and guarantees
• Identifiability of Hierarchical Latent Attribute Models
• Learning High-Dimensional Mixtures of Graphical Models
• Anchored Discrete Factor Analysis
• Discovery of Latent Factors in High-dimensional Data Using Tensor Methods
• Spectral Methods for Nonparametric Models
• The correlation space of Gaussian latent tree models and model selection without fitting
• Robustifying Algorithms of Learning Latent Trees with Vector Variables