Tensor decompositions for learning latent variable models (A survey for ALT)

Anima Anandkumar, Rong Ge, Daniel Hsu, Sham M. Kakade, Matus Telgarsky

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This note is a short version of that in [1]. It is intended as a survey for the 2015 Algorithmic Learning Theory (ALT) conference. This work considers a computationally and statistically efficient parameter estimation method for a wide class of latent variable models— including Gaussian mixture models, hidden Markov models, and latent Dirichlet allocation—which exploits a certain tensor structure in their low-order observable moments (typically, of second- and third-order). Specifically, parameter estimation is reduced to the problem of extracting a certain (orthogonal) decomposition of a symmetric tensor derived from the moments; this decomposition can be viewed as a natural generalization of the singular value decomposition for matrices. Although tensor decompositions are generally intractable to compute, the decomposition of these specially structured tensors can be efficiently obtained by a variety of approaches, including power iterations and maximization approaches (similar to the case of matrices). A detailed analysis of a robust tensor power method is provided, establishing an analogue of Wedin’s perturbation theorem for the singular vectors of matrices. This implies a robust and computationally tractable estimation approach for several popular latent variable models.

Original languageEnglish (US)
Title of host publicationAlgorithmic Learning Theory - 26th International Conference, ALT 2015
EditorsClaudio Gentile, Sandra Zilles, Kamalika Chaudhuri
PublisherSpringer-Verlag
Pages19-38
Number of pages20
ISBN (Print)9783319244853
DOIs
StatePublished - Jan 1 2015
Externally publishedYes
Event26th International Conference on Algorithmic Learning Theory, ALT 2015 - Banff, Canada
Duration: Oct 4 2015Oct 6 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9355
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other26th International Conference on Algorithmic Learning Theory, ALT 2015
CountryCanada
CityBanff
Period10/4/1510/6/15

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Tensor decompositions for learning latent variable models (A survey for ALT)'. Together they form a unique fingerprint.

  • Cite this

    Anandkumar, A., Ge, R., Hsu, D., Kakade, S. M., & Telgarsky, M. (2015). Tensor decompositions for learning latent variable models (A survey for ALT). In C. Gentile, S. Zilles, & K. Chaudhuri (Eds.), Algorithmic Learning Theory - 26th International Conference, ALT 2015 (pp. 19-38). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9355). Springer-Verlag. https://doi.org/10.1007/978-3-319-24486-0_2