LEARNING MIXTURES OF SEPARATED NONSPHERICAL GAUSSIANS

By Sanjeev Arora, R. Kannan. 2005

102 citations recorded by the source corpus.

Mixtures of Gaussian (or normal) distributions arise in a variety of application areas. Many heuristics have been proposed for the task of finding the component Gaussians given samples from the mixture, such as the EM algorithm, a local-search heuristic from Dempster, Laird and Rubin [J. Roy. Statist. Soc. Ser. B 39 (1977) 1-38]. These do not provably run in polynomial time. We present the first algorithm that provably learns the component Gaussians in time that is polynomial in the dimension. The Gaussians may have arbitrary shape, but they must satisfy a ``separation condition'' which places a lower bound on the distance between the centers of any two component Gaussians. The mathematical results at the heart of our proof are ``distance concentration'' results--proved using isoperimetric inequalities--which establish bounds on the probability distribution of the distance between a pair of points generated according to the mixture. We also formalize the more general problem of max-likelihood fit of a Gaussian mixture to unstructured data.

Subfields: Artificial Intelligence, Statistics and Probability, Statistical Learning Theory, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

In Statistical Learning Theory

In Signal Processing

Citations in the corpus

Beyond CCA: Moment Matching for Multi-View Models (2016, neutral): “…of models is possible within the moment matching framework: ICA (e.g., Cardoso & Comon, 1996; Comon & Jutten, 2010), mixtures of Gaus-sians (e.g., Arora & Kannan, 2005; Hsu & Kakade, 2013), latent Dirichlet allocation and topic models (Arora et al., 2012; 2013; Anandkumar et al., 2012;…”
Causal Effect Inference with Deep Latent-Variable Models (2017, neutral): “Although in many cases learning latent-variable models are computationally intractable [50, 7], the machine learning community has made significant progress in the past few years developing computationally efficient algorithms for latent-variable modeling.”
Tensor decompositions for learning latent variable models (2012, background): “r science and machine learning have addressed computational and sample complexity issues related to estimating certain latent variable models such as Gaussian mixture models and HMMs (Dasgupta, 1999; Arora and Kannan, 2005; Dasgupta and Schulman, 2007; Vempala and Wang, 2004; Kannan et al., 2008;Ach”
Scalable Training of Mixture Models via Coresets (2011, unknown): “We decompose the negative log-likelihood L(D | θ) of a data set D as L(D | θ) = − n∑ j=1 ln k∑ i=1 wi√ |2πΣi| exp ( −1 2 (xj − µi)TΣ−1i (xj − µi) ) = −n lnZ(θ) + φ(D | θ) where Z(θ) = ∑ i wi√ |2πΣi| is a normalizer, and the function φ is defined as φ(D | θ) = − n∑ j=1 ln k∑ i=1 wi Z(θ) √ |2πΣi|…”
A Spectral Algorithm for Latent Dirichlet Allocation (2012, result): “For clustering, the first learnability result [19] was under a rather strong separation condition; subsequent results relaxed [1,10,16,17,20,33,45] or removed these conditions [11,28,32,38]; roughly speaking, learning under a weaker separation condition is more challenging, both computationally and ”
Mixture models, robustness, and sum of squares proofs (2017, background): “A highlight of this work is a series of algorithmic results when the components of the mixture model are Gaussian [3, 19, 20, 67].”
Practical Coreset Constructions for Machine Learning (2017, background): “Based on the idea studied in Arora and Kannan [2005], the negative log-likelihood can be decomposed as where function φ is deﬁned as and Z ( θ ) = P i w i / p | 2 π Σ i | is a normalizer which can be computed exactly , independently of the set X .”
Training Mixture Models at Scale via Coresets (2017, methodology): “The problem of fitting a mixture model with near-optimal log-likelihood for arbitrary data is studied by Arora and Kannan (2005).”
Training Gaussian Mixture Models at Scale via Coresets (2017, methodology): “To this end, we apply the following decomposition suggested by Arora and Kannan (2005): where is a normalizer, and the function cost is deﬁned as p Hereby, Z ( θ ) is a normalizing term which can be computed exactly and independently of the set X .”
Multi-view clustering via canonical correlation analysis (2009, methodology): “Apply single linkage clustering (Dunn & Everitt, 2004) (for mixtures of log-concave distributions), or the algorithm in Section 3.5 of (Arora & Kannan, 2005) (for mixtures of Gaussians) on the projected examples in View 1.”
An Analysis of the t-SNE Algorithm for Data Visualization (2018, methodology): “…are satisﬁed by well-studied probabilistic generative models for clusterable data such as mixture of Gaussians and more generally, mixture of log-concave distributions, and have been used in previous work (Dasgupta, 1999; Arora and Kannan, 2005) studying “distance-based” clustering algorithms.”