Tensors, Learning, and 'Kolmogorov Extension' for Finite-alphabet Random Vectors

Abstract

Estimating the joint probability mass function (PMF) of a set of random variables lies at the heart of statistical learning and signal processing. Without structural assumptions, such as modeling the variables as a Markov chain, tree, or other graphical model, joint PMF estimation is often considered mission impossible - the number of unknowns grows exponentially with the number of variables. But who gives us the structural model? Is there a generic, `non-parametric' way to control joint PMF complexity without relying on a priori structural assumptions regarding the underlying probability model? Is it possible to discover the operational structure without biasing the analysis up front? What if we only observe random subsets of the variables, can we still reliably estimate the joint PMF of all? This paper shows, perhaps surprisingly, that if the joint PMF of any three variables can be estimated, then the joint PMF of all the variables can be provably recovered under relatively mild conditions. The result is reminiscent of Kolmogorov's extension theorem - consistent specification of lower-dimensional distributions induces a unique probability measure for the entire process. The difference is that for processes of limited complexity (rank of the high-dimensional PMF) it is possible to obtain complete characterization from only three-dimensional distributions. In fact not all three-dimensional PMFs are needed; and under more stringent conditions even two-dimensional will do. Exploiting multilinear algebra, this paper proves that such higher-dimensional PMF completion can be guaranteed - several pertinent identifiability results are derived. It also provides a practical and efficient algorithm to carry out the recovery task. Judiciously designed simulations and real-data experiments on movie recommendation and data classification are presented to showcase the effectiveness of the approach.

References in corpus (8)

• Tensor Decomposition for Signal Processing and Machine Learning
• All-at-once Optimization for Coupled Matrix and Tensor Factorizations
• Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application
• A Flexible and Efficient Algorithmic Framework for Constrained Matrix and Tensor Factorization
• Generic uniqueness conditions for the canonical polyadic decomposition and INDSCAL
• Joint Tensor Factorization and Outlying Slab Suppression with Applications
• A Tensor Approach to Learning Mixed Membership Community Models
• Learning Hidden Markov Models from Pairwise Co-occurrences with Application to Topic Modeling

Cited by in corpus (8)

• Recovering Joint Probability of Discrete Random Variables from Pairwise Marginals
• Stochastic Mirror Descent for Low-Rank Tensor Decomposition Under Non-Euclidean Losses
• Low-rank Characteristic Tensor Density Estimation Part I: Foundations
• Information-theoretic Feature Selection via Tensor Decomposition and Submodularity
• Low-rank Characteristic Tensor Density Estimation Part II: Compression and Latent Density Estimation
• Block-Randomized Stochastic Proximal Gradient for Low-Rank Tensor Factorization
• Minimizing low-rank models of high-order tensors: Hardness, span, tight relaxation, and applications
• Recovery of Joint Probability Distribution from one-way marginals: Low rank Tensors and Random Projections