PaperlayerView exact revision on arXiv

Source-linked AI summary

Introduction to Tensor Decompositions and their Applications in Machine Learning

Stephan Rabanser, Oleksandr Shchur, Stephan Günnemann

arXiv:1711.10781v1stat.MLcs.LG

TL;DR

The paper addresses how tensor decompositions can provide identifiable structure beyond matrix factorizations and surveys their theory and machine-learning uses. It presents CP and Tucker decompositions, applications to latent-variable models, and current research boundaries.

  • Problem

    Matrix factorization approaches are often non-unique, while maximum likelihood estimation for some latent-variable models can be NP-hard and iterative alternatives may converge slowly without consistency guarantees.

  • Method

    The paper provides a broad overview of tensor concepts and decompositions, emphasizing CP and Tucker methods and tensor-based method-of-moments estimation for mixture models.

  • Results

    Tensor decompositions provide stronger identifiability conditions than matrix decompositions, and the presented method efficiently learns simple GMMs and topic models from low-order moments.

  • Takeaways & Limitations

    Tensor decompositions offer a framework for uncovering hidden low-dimensional structure and addressing machine-learning problems including mixture-model and topic-model estimation.

  • Takeaways & Limitations

    Research remains open on applying tensor methods to additional machine-learning problems and computing decompositions under weaker assumptions.

Abstract

from arXiv · show

Tensors are multidimensional arrays of numerical values and therefore generalize matrices to multiple dimensions. While tensors first emerged in the psychometrics community in the $20^{\text{th}}$ century, they have since then spread to numerous other disciplines, including machine learning. Tensors and their decompositions are especially beneficial in unsupervised learning settings, but are gaining popularity in other sub-disciplines like temporal and multi-relational data analysis, too. The scope of this paper is to give a broad overview of tensors, their decompositions, and how they are used in machine learning. As part of this, we are going to introduce basic tensor concepts, discuss why tensors can be considered more rigid than matrices with respect to the uniqueness of their decomposition, explain the most important factorization algorithms and their properties, provide concrete examples of tensor decomposition applications in machine learning, conduct a case study on tensor-based estimation of mixture models, talk about the current state of research, and provide references to available software libraries.

1 INTRODUCTION

The paper introduces tensors as higher-dimensional generalizations of matrices and surveys their decompositions, machine-learning applications, software, and open research questions.

  • Tensors generalize matrices to higher dimensions and can be treated as multidimensional fields.
  • Since expanding beyond psychometrics and computer science, tensors have reached statistics, data science, and machine learning.
  • The paper motivates tensors through Spearman’s hypothesis and evaluates low-rank matrix decompositions alongside their associated issues.
  • It introduces tensor concepts, analyzes why low-rank tensor decompositions are more rigid than matrix decompositions, and presents CP and Tucker methods.
  • Tensor decompositions are applied to efficiently learn simple Gaussian mixture and topic models from low-order moments.

2 MATRIX DECOMPOSITION: A MOTIVATING EXAMPLE

The section uses matrix rank decomposition to motivate tensor methods: matrix factorizations can be non-unique, whereas higher-dimensional structure can support stronger identifiability.

  • Matrix decompositions support efficient algorithms, linear-system solutions, and extraction of latent information from matrices.
  • A rank-r matrix is expressed as M = AB^T, where A and B^T encode r latent factors.
  • Different factor matrices can produce the same matrix, so matrix factorization is generally non-unique without additional constraints.
  • Spearman’s hypothesis: Spearman’s hypothesis models intelligence using eductive and reproductive latent factors inferred from student test scores.
  • The rotation problem: The rotation problem constructs alternative factors by inserting an invertible rotation matrix and its inverse between the original factors.
  • The rotation problem: Tensor decompositions are usually unique under milder conditions than matrix decompositions, which require stringent constraints such as orthogonality for uniqueness.

3 INTRODUCTION TO TENSORS

This section introduces tensors as multidimensional arrays, develops core operations and notation, and explains why tensor decompositions can be more rigid and identifiable than matrix decompositions.

  • Tensor basics: Tensors generalize matrices to higher dimensions; third-order tensors can be viewed as three-dimensional data cubes.Their order is the number of dimensions, with scalars, vectors, and matrices corresponding to orders zero, one, and two.
  • Tensor basics: Fibers fix all but one index, while slices fix all but two indices and provide lateral, horizontal, and frontal views of a third-order tensor.These subarrays organize tensor elements by mode and support visualizing higher-dimensional structure.
  • Tensor operations: Outer products combine vectors into rank-one tensors, whereas inner products combine two vectors into a scalar.The N-way outer product forms tensor entries by multiplying corresponding vector elements.
  • Tensor decompositions: Rank is the minimum number of rank-one tensors whose sum produces a tensor, with factor matrices storing component vectors and λ absorbing component weights.A rank-R tensor is represented as a sum of weighted outer products across its modes.
  • Tensor operations: Matricization reorders a tensor into a matrix, while n-mode products transform mode-n fibers through matrix or vector multiplication.For matrix multiplication, the unfolded representation is Y_(n) = M X_(n).
  • Tensor uniqueness and rigidness: Tensor slices share factor structure: the same rank-one matrices must explain every slice, producing stronger interrelations and weaker uniqueness requirements than for matrices.This shared structure supports identifying latent factors, whereas matrix decompositions are generally non-unique without stringent constraints.

4 TENSOR DECOMPOSITION ALGORITHMS

The paper presents CPD and Tucker as central tensor decompositions, then surveys CPD algorithms, uniqueness conditions, and rank-related complications. CPD targets latent parameter estimation, while Tucker supports subspace estimation, compression, and dimensionality reduction.

  • 4.1 Canonical Polyadic Decomposition (CPD): CPD expresses a tensor as a sum of rank-one tensors and unifies CANDECOMP and PARAFAC under one decomposition framework.
  • 4.1.1 Jennrich’s Algorithm: Jennrich’s algorithm recovers CPD factor matrices when all three factor matrices are linearly independent, subject to permutation and scaling indeterminacies.
  • 4.1.1 Jennrich’s Algorithm: Jennrich’s algorithm may become numerically unstable because it uses random slices and requires sufficiently large eigengaps.
  • 4.1.2 Alternating Least Squares (ALS) Algorithm: ALS repeatedly optimizes one factor matrix while fixing the others, but convergence can be slow, initialization-sensitive, and non-global.
  • 4.1.3 Tensor Power Method: The tensor power method applies to tensors with identical, orthogonal factor vectors and iteratively extracts dominant components with deflation.
  • 4.1.4 Uniqueness and 4.1.5 Tensor Rank Peculiarities: Tensor decompositions can be unique under relaxed conditions, but tensor rank is difficult to determine because rank computation is NP-hard and best low-rank approximations may fail to exist.

5 TENSOR APPLICATIONS IN MACHINE LEARNING

Tensor decompositions extend machine-learning representations to temporal, multirelational, and latent-variable data. The paper connects these structures to pattern discovery, relation inference, and moment-based inference for mixture and topic models.

  • 5.1 Temporal Data: Tensorizing matrix relationships adds temporal structure and supports pattern discovery, evolution prediction, anomaly detection, and temporal community detection.
  • 5.1 Temporal Data: Temporal interpretation constrains arbitrary permutations across tensor dimensions because time introduces an additional relationship between data points.
  • 5.2 Multi-relational Data: Multirelational tensors represent subject-relation-object interactions and enable analysis of interdependencies across multiple relational levels.
  • 5.2 Multi-relational Data: In knowledge graphs, tensor decomposition methods infer new relations with state-of-the-art quality and computational efficiency, supporting question answering and entity resolution.
  • 5.3 Latent Variable Modeling: Latent-variable inference uses empirical low-order moments whose tensor structure enables efficient algorithms for models including hidden Markov models, independent component analysis, and topic models.

6 CASE STUDY: ESTIMATION OF MIXTURE MODELS

The case study applies tensor decompositions to parameter estimation in Gaussian mixture and simplified topic models. Its procedure constructs moments, whitens the third-order moment, decomposes it with the tensor power method, and transforms the factors back.

  • 6 Case Study: The case study examines tensor-based parameter estimation for Gaussian mixture and topic models as concrete latent-variable learning problems.
  • 6 Case Study: Unsupervised learning requires identifiable parameters and efficient latent-variable estimation, while MLE can be NP-hard and EM can converge slowly to local optima.
  • 6 Case Study: The estimation pipeline calculates moments, whitens the third-order moment, decomposes it with the tensor power method, and un-whitens the recovered factors.
  • 6.1 Gaussian Mixture Models: The Gaussian mixture model assumes data come from k Gaussian components with unknown parameters and constrains all components to share one spherical covariance variance σ^2.
  • 6.2 Topic Models: The simplified topic model assigns each document one topic, then generates at least three words independently from that topic’s discrete vocabulary distribution.

6.4 Method of Moments (MoM)

The method of moments learns spherical GMMs and topic models from low-order moments, reducing both models to a shared moment form whose latent factors require additional assumptions to recover.

  • The method of moments infers model information from higher-order moments, which are computed as averages of the data.
  • In GMMs, latent factors are cluster mean vectors, whereas in topic models they are word probability-vectors conditioned on topics.
  • GMM first and second moments correspond to the mixture mean and covariance matrix, respectively.
  • After simplifying known mean and variance terms, the second and third moments become bilinear and trilinear equations in the mean vectors.
  • Recovering latent factors from the shared moment form requires simplifying assumptions, beginning with an orthogonality assumption that is later relaxed.

6.5 Orthogonalization Through Whitening

Whitening transforms the second moment to orthogonalize the third moment, enabling tensor power decomposition and subsequent recovery of latent factors in the original space.

  • The whitening matrix W satisfies W^T M2W = I and orthogonalizes the third moment through a multilinear transformation.Whitening transforms variables so their covariance becomes the identity matrix.
  • Un-whitening recovers the original latent factors from the whitened factors, provided the latent factors are linearly independent.
  • Whitening reduces M3 from d×d×d to V∈R^k×k×k, imposing k≤d and limiting applicability when GMM components exceed data dimensionality.
  • The whitened tensor V is decomposed with the tensor power method to uncover latent structure.
  • The complete procedure computes moments, extracts GMM variance when applicable, whitens the data, applies tensor power iterations, and back-transforms the estimates.
  • The algorithm repeatedly extracts dominant eigenvalue-eigenvector pairs, deflates the tensor, and continues until k pairs are recovered.

6.7 Algorithm Summary

The paper summarizes tensor-based latent-variable estimation as an algorithmic pipeline and provides Matlab and Python implementations for the case study.

  • Algorithm 4 outlines tensorized mixture-model learning from data through moment computation, whitening, tensor decomposition, and back-transformation.
  • Matlab and Python scripts are provided for estimating GMMs, alongside Matlab code for exchangeable hidden-variable models.

7 AVAILABLE SOFTWARE LIBRARIES

The paper highlights tensor libraries as optimized tools for storing, treating, and decomposing multidimensional arrays, and directs readers to an overview table.

  • Tensor libraries provide optimized storage and processing for tensors, along with efficient implementations of decomposition algorithms.
  • Table 1 presents an overview of popular tensor libraries.

8 CURRENT RESEARCH

Current research focuses on extending tensor decompositions to more machine-learning problems and weakening the assumptions required for effective use. Existing applications can be efficient, but conditions such as k ≤ d remain strong limitations.

  • Researchers are investigating whether tensor decompositions can benefit additional machine-learning problems, including neural networks.
  • A second research direction is computing tensor decompositions under weaker assumptions for machine-learning applications.
  • Although tensor decompositions often have weak uniqueness conditions, their effective use in machine learning can require much stronger requirements.
  • The GMM estimation example requires k ≤ d, illustrating a strong dimensionality limitation for current tensor-based methods.

9 CONCLUSIONS

The paper concludes that tensor decompositions offer greater rigidity than matrix decompositions and connect multilinear structure to machine-learning applications. It highlights CP and Tucker methods, their computation and uniqueness conditions, and tensor-based estimation of mixture models and topic models.

  • Low-rank tensors are generally more rigid than low-rank matrices because their slices are interrelated across dimensions.
  • The paper introduces CP and Tucker decompositions, explains their computation through methods such as ALS, and examines conditions for uniqueness.
  • Tensor decompositions are applied across machine-learning sub-disciplines, including a detailed example of estimating Gaussian mixture models and simple topic models.
  • The paper uses the method of moments and the tensor power method to extract parameters needed for mixture-model and topic-model estimation.
Loading 1711.10781v1…