PaperlayerView exact revision on arXiv

Source-linked AI summary

Tensor decompositions for learning latent variable models

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

arXiv:1210.7559v4cs.LGmath.NAstat.ML

TL;DR

Learning latent variable models is difficult because hidden states are unobserved and moment matching can require intractable polynomial systems. The paper exploits structured low-order moments, reducing estimation to orthogonal tensor decomposition and analyzing a robust tensor power method.

  • Problem

    Hidden states are unobserved, while matching latent-variable parameters to observed moments may require solving computationally intractable multivariate polynomial systems.

  • Method

    The paper uses uniquely decomposable orthogonal third-order tensors from structured low-order moments and analyzes a robust tensor power method for extracting their components.

  • Results

    The perturbation analysis provides an analogue of Wedin’s theorem, bounding recovered decomposition error in terms of tensor perturbation, while iterative deflation recovers all components with high probability.

  • Takeaways & Limitations

    Structured tensor decompositions support computationally tractable parameter estimation, and implicit moment computations with dimensionality reduction can avoid scaling more than linearly in dimension and sample size.

  • Takeaways & Limitations

    The perturbation analysis is algorithm-dependent because the perturbed tensor need not have an orthogonal decomposition, and model misspecification can affect convergence.

Abstract

from arXiv · show

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.

1. Introduction

The paper develops moment-based tensor decomposition methods for efficiently estimating parameters in latent variable models. It unifies the tensor structure underlying several models and analyzes a robust tensor power method, while addressing computational scalability and connections to prior approaches.

  • Motivation: Latent-state unobservability makes moment matching potentially require solving computationally intractable multivariate polynomial systems.Low-order moment structure in many latent variable models makes the inverse problem efficiently solvable.
  • Core framework: Gaussian mixture models, hidden Markov models, and latent Dirichlet allocation share low-order moment structure that permits tensor-based parameter estimation.The relevant tensor decomposition generalizes the singular value decomposition for matrices.
  • Core framework: The unified framework expresses observable moments as sums of rank-one terms and reduces estimation to extracting a symmetric orthogonal tensor decomposition.The decomposition can be obtained using fixed-point and variational methods.
  • Robust recovery: The robust tensor power method receives convergence and perturbation analyses, including an analogue of Wedin’s theorem that bounds decomposition error by tensor perturbation size.Random restarts and deflation yield an approximate decomposition even when the perturbed tensor lacks an orthogonal decomposition.
  • Scalability: Basic tensor-method operations can run in time linear in observation dimension and training-data size, including vocabulary size and nonzero term-document entries in topic modeling.This computational efficiency combined with robustness supports parameter estimation for latent variable models.
  • Relation to prior work: The approach builds on tensor-decomposition connections to independent component analysis, algebraic statistics, and earlier latent-variable-model methods, while targeting computational and finite-sample issues.Related approaches include simultaneous diagonalization, tensor flattening, and subspace-identification methods.
  • Tensor structure: The symmetric orthogonal decomposition represents a tensor as a linear combination of rank-one terms whose vectors form an orthonormal basis and correspond to tensor eigenvectors.This structure enables efficient and stable recovery using tensor generalizations of the matrix power method.
  • Relation to prior work: Subspace-identification methods can establish learnability for some latent models but do not necessarily provide parameter estimates such as HMM emission or transition matrices.This distinguishes learnability guarantees from direct parameter recovery.

2. Preliminaries

The preliminaries define tensors as multilinear objects represented by multidimensional arrays and explain their rank, symmetric rank, tensor products, multilinear actions, and symmetry. They emphasize that tensor rank and decomposition behave more delicately than their matrix counterparts.

  • Tensor notation: A p-th order tensor is identified with a p-way array of real coordinates and can be viewed as a multilinear map acting on matrices.The transformed tensor’s entries are obtained by contracting the original coordinates with the input matrices.
  • Tensor notation: The tensor power v⊗p denotes p copies of a vector tensor-multiplied together.The notation applies to vectors in R^n and is used for symmetric tensor constructions.
  • Tensor notation: The notation includes the identity matrix for contractions involving a matrix and vector, along with the canonical basis vectors e_1,...,e_n.These conventions support the multilinear tensor operations used later.
  • Symmetry: Symmetric tensors have array representations invariant under every permutation of their indices, generalizing symmetric matrices when p = 2.Symmetry is defined coordinatewise across all index permutations.
  • Rank and decomposition: Tensor rank is the smallest number of rank-one tensor terms needed to represent a tensor, while symmetric rank restricts the terms to repeated copies of one vector.For p = 2, tensor rank reduces to ordinary matrix rank and symmetric rank agrees with matrix rank.
  • Rank and decomposition: A decomposition into rank-one terms is called a canonical polyadic decomposition.The matrix singular value decomposition provides the p = 2 analogue.
  • Rank and decomposition: Tensor rank is more delicate than matrix rank: finite symmetric rank is not immediate, and removing a best rank-one approximation can increase the residual tensor’s rank.These issues motivate the paper’s focus on specially structured tensor decompositions.

3. Tensor Structure in Latent Variable Models

The paper shows that low-order observable moments of several latent variable models can be manipulated into structured tensors whose decompositions reveal model parameters. Examples include topic models, Gaussian mixtures, ICA, product distributions, and HMMs.

  • Exchangeable Single Topic Models: Exchangeable topic models represent words as conditionally independent one-hot vectors, so cross moments encode joint word probabilities and conditional means equal topic vectors.The second- and third-order moments therefore expose topic-dependent structure usable for estimation.
  • Exchangeable Single Topic Models: Theorem 3.1’s moment structure implies that topic vectors can be estimated through a symmetric tensor decomposition, using all word pairs and triples available in each document.Exchangeability permits aggregation beyond only the first two or three words.
  • Spherical Gaussian Mixtures: For spherical Gaussian mixtures, observations take the form x = µ_h + z, with latent component h and independent spherical Gaussian noise; covariance eigenvalues identify variance information.The common-covariance case relates closely to k-means, while the general case permits component-specific spherical variances.
  • Independent Component Analysis: ICA models observations as x := Ah + z, and fourth-cumulant tensors capture source non-Gaussianity through the mixing directions.The mixing matrix is not identifiable when the latent vector is multivariate Gaussian because the relevant excess kurtoses vanish.
  • Mixtures of Product Distributions: Randomly partitioning product-distribution dimensions creates three conditionally independent views whose conditional-mean matrices have full column rank under the stated incoherence construction.The partition yields view matrices with full column rank, enabling the multi-view tensor structure required by the estimation theorem.
  • Hidden Markov Models: For HMMs, three observations are conditionally independent given an intermediate hidden state, with conditional means determined by the observation matrix, transition matrix, and state distributions.The conditional-mean matrices have full column rank when the observation matrix and transition matrix satisfy the listed conditions.

4. Orthogonal Tensor Decompositions

The paper develops orthogonal tensor decompositions as a higher-order analogue of symmetric matrix eigendecomposition and uses their fixed-point and variational characterizations for parameter recovery. Under orthogonal structure, robust eigenvectors identify the decomposition components and map back to latent parameters.

  • Reduction to Tensor Decomposition: The estimation problem is reduced to extracting an orthogonal decomposition of a symmetric tensor derived from observable moments.This reduction connects latent-variable parameter estimation to a structured tensor problem.
  • Comparison with the Matrix Case: Repeated matrix eigenvalues create non-unique eigendecompositions, whereas tensor power iterations identify robust attracting directions even though tensors can have additional eigenvectors.The tensor and matrix cases therefore differ in how degeneracy affects the recovered directions.
  • Tensor Characterizations: Unlike general tensors, orthogonally decomposable third-order tensors admit unique component recovery through robust eigenvectors under the paper’s non-degeneracy structure.The robust eigenvectors are precisely the decomposition vectors, and almost every initialization converges to one of them under the tensor power map.
  • Fixed-Point Characterization: For an orthogonally decomposable tensor, each decomposition vector v_i forms an eigenvector/eigenvalue pair under the multilinear tensor map.Orthogonality directly gives T(I, v_i, v_i) = λ_i v_i.
  • Variational Characterization: The generalized Rayleigh quotient has isolated local maximizers exactly at the decomposition vectors, while stationary points correspond to tensor eigenvectors.This supplies a variational route for identifying the desired components and rejecting other stationary points.
  • Reduction to Tensor Decomposition: In the latent-model reduction, the robust eigenvectors of the transformed third-order moment tensor are normalized component means, and their eigenvalues equal 1/√w_i.Applying the pseudoinverse of W^⊤ to an eigenvector/eigenvalue pair recovers a component mean µ_i.

5. Tensor Power Method

The tensor power method extracts orthogonal tensor components, with quadratic convergence in the exact case and a robust, restart-based variant for perturbed tensors. Its perturbation analysis bounds recovery error, while deflation and efficient iterations support estimating all components at scale.

  • Robust tensor power method: When empirical moments perturb the tensor, an exact orthogonal decomposition may not exist, so the method uses a robust approximate-decomposition variant.The perturbation arises when estimated moments replace population moments.
  • Exact tensor power method: Repeated tensor power iterations converge quadratically to one component when the initialization has a uniquely dominant component correlation.The initial vector determines the convergent eigenvector, and deflation enables subsequent component extraction.
  • Robust tensor power method: After estimating an eigenvector/eigenvalue pair, the algorithm deflates the tensor and repeats the procedure to recover all components.The returned deflated tensor is ˜T − ˆλ ˆθ⊗3.
  • Perturbation analysis: Theorem 5.1 provides an algorithm-dependent perturbation bound analogous to Wedin’s theorem for matrix singular vectors.The guarantee applies when the perturbation is sufficiently small and bounds the recovered decomposition using the perturbation size and tensor component magnitudes.
  • Robust tensor power method: The robust method uses multiple random restarts and power iterations to find an initialization whose contraction toward an eigenvector dominates the perturbation.The required number of trials is L = poly(k) log(1/η), and for large k the bound is close to linear in k.
  • Computational considerations: The basic iterative operations can be executed in time linear in the observation dimension and training-data size, including vocabulary size and nonzero document-matrix entries in topic modeling.Domain-informed initialization points, such as single-topic documents, can improve starting points in topic-modeling applications.

6. Discussion

The discussion addresses practical computation of moment tensors, especially for sparse observations and large vocabularies, and reviews complexity and statistical implications of tensor-based estimation.

  • Efficient moment computation: Third-order moments can use all ordered word triples in a document, while exchangeability permits implicit averaging instead of explicit enumeration.The paper notes that all words should be used in practice for efficient moment estimation.
  • Efficient moment computation: Sparse word-count representations allow efficient multiplication by empirical moment matrices and tensors, with time linear in the corpus's nonzero term-document entries.The document contribution can be represented through its sparse count vector rather than enumerating all word triples explicitly.
  • Scaling to large vocabularies: Large third-order tensors require Ω(d^3) storage in general, motivating sparsity and randomized linear dimensionality reduction.The vocabulary dimension d can make explicit storage prohibitive.
  • Scaling to large vocabularies: Approximate whitening and tensor contractions can be performed implicitly, with the core power-method computation requiring O(dk + N) operations.Here N denotes the number of nonzero entries in the term-document matrix.
  • Computational complexity: Dense tensor power extraction costs O(k^(5+δ)(log(k)+log log(1/ε))) under the stated restart and iteration assumptions, whereas flattening enables an O(k^4) SVD approach.The matrix approach is unreliable with repeated eigenvalues and can be unstable when eigenvalue gaps are small.
  • Complexity and statistical bounds: The tensor power method's Θ(k^(1+δ)) runtime gap from random restarts may be reduced through improved initialization and exploitation of special structure.The perturbation analysis also improves sample-complexity dependence on rank because tensor-estimation error is not explicitly amplified by k.

Orthogonal Tensor Decompositions

This section provides complete proofs for two preceding theorems.

  • The authors give detailed proofs of Theorems 4.1 and 4.2 for completeness.

A.1 Proof of Theorem 4.1

The proof establishes that tensor power iteration converges generically to a component and that the robust eigenvectors are exactly the decomposition vectors.

  • For almost every initialization, repeated tensor power iteration converges to one of the decomposition vectors.The exceptional set of initial vectors has measure zero.
  • The robust eigenvectors of an orthogonally decomposable tensor are exactly v1, v2, ..., vk.Each decomposition vector has a neighborhood whose points converge to it, while any other robust eigenvector would contradict the measure-zero exception result.

A.2 Proof of Theorem 4.2

The proof characterizes isolated local maximizers of the tensor optimization problem as precisely the decomposition vectors.

  • Stationary points of the constrained optimization problem satisfy the tensor eigenvector equation.The Lagrangian formulation yields T(I,u,u)=λu for an eigenvector/eigenvalue pair.
  • Negative-eigenvalue stationary points cannot be local maximizers because scaling toward zero increases the cubic objective.
  • Positive-eigenvalue local maximizers must lie on the unit sphere, since scaling an interior point outward increases the objective.
  • A stationary point is an isolated local maximizer if and only if it equals one of the decomposition vectors vi.The proof excludes stationary points supported on multiple components or having zero objective value.
  • The corrected constraint is essential because using ||u||=1 alone permits isolated local maximizers with nonpositive tensor value that are not decomposition vectors.

Appendix B. Analysis of Robust Power Method

The analysis establishes robust tensor power-method behavior through random initialization, phased convergence, perturbation control, and deflation-error bounds. These components yield approximate eigenvector recovery under structured tensor perturbations.

  • Convergence: The perturbed power iterations proceed through an initial linear-convergence phase followed by quadratic convergence until perturbation error dominates.The analysis tracks projection growth and perturbation-dependent error across these phases.
  • Deflation: The proof controls deflation errors by showing that errors from already recovered eigenvectors contribute only lower-order terms.This makes the tensor setting subtler than matrix eigendecomposition while preserving recursive recovery.
  • Recovery: The single-eigenvector recovery result applies after a bounded number of iterations when the tensor satisfies structured perturbation conditions.The theorem identifies an iteration threshold N and a final vector satisfying the stated recovery guarantee.
  • Phased analysis: The analysis divides the iterations into three phases: before moderate alignment, intermediate quadratic growth, and final perturbation-limited convergence.The first phase has linear growth, while later phases use stronger alignment conditions and refined perturbation bounds.

B.4 Proof of the Main Theorem

The main theorem analyzes repeated robust power-method calls with deflation on a perturbed orthogonally decomposable tensor. With high probability, the procedure recovers all components up to permutation while controlling the residual error.

  • Theorem setup: The theorem assumes a symmetric tensor with an orthogonal decomposition, positive component weights, and perturbation operator norm ǫ.The component-weight and perturbation conditions determine the recovery regime.
  • Initialization and induction: At least one of poly(k) log(1/η) random starts is sufficiently separated for each successive component with high probability.The proof combines conditional initialization guarantees across the k deflation stages.
  • Deflation procedure: The algorithm is called k times, using the deflated tensor from each call as the input to the next.An induction maintains recovery and residual-error properties throughout the sequence.
  • Recovery guarantee: With probability at least 1−η, the estimated eigenvector/eigenvalue pairs correspond to the true components under a permutation.The final induction step establishes the simultaneous recovery statement.
  • Error control: The final residual tensor error is bounded by 55ǫ in the stated recovery event.This bound follows after the last induction step and controls the difference between the original tensor and the recovered decomposition.

Appendix C. Variant of Robust Power Method that uses a Stopping Condition

Algorithm 2 replaces a fixed number of random restarts with a stopping condition that certifies convergence toward an eigenvector. Its analysis links termination, eigenvector proximity, and robust recovery under perturbation.

  • Algorithm: Algorithm 2 repeatedly draws random unit vectors and performs power updates until a stopping condition is satisfied.After termination, it performs N additional updates, estimates the eigenvalue, and returns a deflated tensor.
  • Output and deflation: The returned estimate is paired with eigenvalue ˜T(ˆθ,ˆθ,ˆθ), and deflation subtracts ˆλ ˆθ⊗3 from the input tensor.These operations define the output passed to subsequent decomposition stages.
  • Stopping condition: The stopping condition guarantees that the current vector is close to an eigenvector of the perturbed tensor.A separate lemma establishes this implication for any vector satisfying the condition.
  • Termination: When initialized from a good starting point, the stopping condition is reached after the power iterations.The analysis uses this fact to connect successful initialization with termination.
  • Recovery analysis: The proof uses a matrix formed by contracting the tensor with the current vector and applies singular-value perturbation reasoning to relate its leading direction to a tensor eigenvector.The argument shows that most of the relevant energy lies in the top singular component before transferring the conclusion back to the tensor iterate.

C.2 Sketch of Analysis of Algorithm 2

The stopping-condition variant retains the robust recovery guarantee while replacing a fixed restart count with termination-based control. Under suitable conditions, it terminates after polynomially many random restarts with high probability.

  • Guarantee: Upon termination, Algorithm 2 returns an accurate decomposition under the appropriate perturbation and iteration conditions.This is the first part of the variant’s guarantee.
  • Termination: The algorithm terminates after poly(k) random restarts with high probability.The stopping condition is shown to be reached using initialization and convergence lemmas.
  • Conditions: The conditions on ǫ and N match those of the main theorem up to potentially different universal constants.The Frobenius-norm requirement is subsumed by the operator-norm condition through ∥E∥F ≤k∥E∥≤kǫ.
  • Proof strategy: The induction combines stopping-condition accuracy with high-probability termination and then invokes the single-vector recovery lemma.The proof structure remains essentially the same as for the fixed-restart algorithm.
  • Perturbation scaling: Using κ=4k instead of κ=O(1) still yields the same guarantee when the perturbation condition is scaled as ǫ≤C1λmin/k.The altered parameter affects the intermediate analysis but is absorbed by the stronger perturbation requirement.

Appendix D. Simultaneous Diagonalization for Tensor Decomposition

Simultaneous diagonalization recasts tensor decomposition as finding a shared basis that diagonalizes related matrices. A single random projection can identify the components, but multiple projections weaken uniqueness requirements and may improve robustness, while robust numerical alternatives remain an open direction.

  • Simultaneous diagonalization: Simultaneous diagonalization seeks X such that X⊤M2X and X⊤M3(I, I, η)X are diagonal for every η.When the component vectors µi are linearly independent, X⊤ = V† is unique up to column permutation and rescaling.
  • Exact moments: With exact moments and d = k, a simple construction reduces the decomposition problem to an eigenvalue problem.The supplied passage introduces this construction but does not include its defining equation.
  • Uniqueness condition: Distinct diagonal entries of D(η) make the eigenvectors of M(η) equal to V up to permutation and scaling, almost surely for a random continuous η.This criterion depends on choosing η so the diagonal entries are distinct.
  • Finite-sample robustness: Earlier diagonalization methods had polynomial complexity but large dependence on rank k because finite-sample recovery requires well-separated diagonal entries.The separation requirement drives the unfavorable rank dependence described for prior approaches.
  • Multiple projections: Using several η vectors weakens uniqueness: each pair of columns need only differ in at least one row across the collection.This weaker requirement may support improved perturbation analysis and an orthogonal simultaneous diagonalization.
  • Alternative algorithms: Robust simultaneous-diagonalization and Schur-like methods exist, but whether they match tensor power methods’ learnability and computational advantages remains open.The Schur-like alternative simultaneously triangularizes the matrices with a unitary matrix U.
Loading 1210.7559v4…