Learning Arbitrary Statistical Mixtures of Discrete Distributions

DOI10.1145/2746539.2746584MaRDI QIDQ2941569zbMATH OpenOpenAlexFDO

Authors Jian Li, Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy

Publication date 21 August 2015

Published in Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.02526, https://authors.library.caltech.edu/58890/

zbMATH Keywords

approximation theoryconvex geometryKantorovich-Rubinstein dualitymixture learningrandomized algorithmsspectral methodstransportation distance

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Randomized algorithms (68W20)

Abstract: We study the problem of learning from unlabeled samples very general statistical mixture models on large finite sets. Specifically, the model to be learned, $vartheta$, is a probability distribution over probability distributions $p$, where each such $p$ is a probability distribution over $[n]=1,2,dots,n$. When we sample from $vartheta$, we do not observe $p$ directly, but only indirectly and in very noisy fashion, by sampling from $[n]$ repeatedly, independently $K$ times from the distribution $p$. The problem is to infer $vartheta$ to high accuracy in transportation (earthmover) distance. We give the first efficient algorithms for learning this mixture model without making any restricting assumptions on the structure of the distribution $vartheta$. We bound the quality of the solution as a function of the size of the samples $K$ and the number of samples used. Our model and results have applications to a variety of unsupervised learning scenarios, including learning topic models and collaborative filtering.

Recommendations

• Learning mixtures of arbitrary distributions over large discrete domains
• Learning mixtures of structured distributions over discrete domains
• Learning mixtures of arbitrary Gaussians
• Learning Mixtures of Product Distributions over Discrete Domains
• scientific article; zbMATH DE number 1931863
• scientific article; zbMATH DE number 1934581
• On learning statistical mixtures maximizing the complete likelihood
• Learning Theory
• scientific article; zbMATH DE number 4215160

Cites work

• Approximate distance oracles
• Approximate distance oracles with constant query time
• Automata, Languages and Programming
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Fast C-K-R partitions of sparse graphs
• Near-Linear Time Construction of Sparse Neighborhood Covers
• On approximate distance labels and routing schemes with affine stretch
• On sparse spanners of weighted graphs
• Ramsey partitions and proximity data structures
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• Shortest-path queries in static networks

Cited in

(12)

• Learning mixtures of separated nonspherical Gaussians
• Mixed membership Gaussians
• Learning mixtures of arbitrary distributions over large discrete domains
• On learning mixture models for permutations
• Generalization from observed to unobserved features by clustering
• The search problem in mixture models
• Decontamination of mutual contamination models
• On learning statistical mixtures maximizing the complete likelihood
• Learning entangled single-sample Gaussians
• Assigning topics to documents by successive projections
• Learning a mixture of two subspaces over finite fields
• Algorithms for learning a mixture of linear classifiers

Describes a project that uses

Uses Software

• Graphs

This page was built for publication: Learning Arbitrary Statistical Mixtures of Discrete Distributions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2941569)