TY - GEN

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

AU - Anandkumar, Anima

AU - Ge, Rong

AU - Hsu, Daniel

AU - Kakade, Sham M.

AU - Telgarsky, Matus

N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2015.

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84945907484&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84945907484&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-24486-0_2

DO - 10.1007/978-3-319-24486-0_2

M3 - Conference contribution

AN - SCOPUS:84945907484

SN - 9783319244853

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 19

EP - 38

BT - Algorithmic Learning Theory - 26th International Conference, ALT 2015

A2 - Gentile, Claudio

A2 - Zilles, Sandra

A2 - Chaudhuri, Kamalika

PB - Springer Verlag

T2 - 26th International Conference on Algorithmic Learning Theory, ALT 2015

Y2 - 4 October 2015 through 6 October 2015

ER -