On Spectral Learning of Mixtures of Distributions

We consider the problem of learning mixtures of distributions via spectral methods and derive a characterization of when such methods are useful. Specifically, given a mixture-sample, let \(\bar\mu_{i}, {\bar C_{i}}, \bar w_{i}\) denote the empirical mean, covariance matrix, and mixing weight of the samples from the i-th component. We prove that a very simple algorithm, namely spectral projection followed by single-linkage clustering, properly classifies every point in the sample provided that each pair of means \(\bar\mu_{i},\bar\mu_{j}\) is well separated, in the sense that \(\|\bar\mu_{i} - \bar\mu_{j}\|^{2}\) is at least \(\|{\bar C_{i}\|_{2}(1/\bar w_{i}+1/\bar w_{j})}\) plus a term that depends on the concentration properties of the distributions in the mixture. This second term is very small for many distributions, including Gaussians, Log-concave, and many others. As a result, we get the best known bounds for learning mixtures of arbitrary Gaussians in terms of the required mean separation. At the same time, we prove that there are many Gaussian mixtures {(μ _i ,C _i ,w _i )} such that each pair of means is separated by ||C _i ||₂(1/w _i  + 1/w _j ), yet upon spectral projection the mixture collapses completely, i.e., all means and covariance matrices in the projected mixture are identical.

Authors and Affiliations

1. Microsoft Research, One Microsoft Way, Redmond, WA, 98052, USA

   Dimitris Achlioptas

2. Microsoft Research, 1065 La Avenida, Mountain View, CA, 94043, USA

   Frank McSherry

Editors and Affiliations

1. University of Leoben, A-8700, Leoben, Austria

   Peter Auer

2. Department of Electrical Engineering, Technion, P.O. Box, 3200, Haifa, Israel

   Ron Meir

Reprints and permissions

© 2005 Springer-Verlag Berlin Heidelberg

Policies and ethics