Learning Mixture of Univariate Gaussians

Question

There are many papers on learning mixtures of multivariate Gaussians, which exploit various separation/projection techniques. What about one-dimensional (univariate) Gaussians -- any formal guarantees for learning these?

UPDATE: I should clarify: I am particularly interested in polynomial-time algorithms, in the number of mixture components.

Answer 1

Sorry, but there is lots of evidence that not only is this problem a pain in the univariate case, but moreover that having few dimensions actually makes things worse.

For evidence of the difficulty, please see Proposition 15 in Section 6 ("Exponential dependence on $k$ is inevitable") and the related Figure 1 of the following paper, the follow-up to Ankur Moitra and Greg Valiant's original joint work with Adam Kalai:

Ankur Moitra and Greg Valiant, "Settling the Polynomial Learnability of Mixtures of Gaussians", FOCS 2010.

Proposition 15 states that there exist two mixtures of $k^2$ Gaussians on the line whose $L^1$ distance is exponentially small in $k$. Since the construction is careful and the distribution parameters are well-behaved (polynomially-sized), this dependence on $k$ is real, and thus any algorithm whose performance depends on statistical distance will run into trouble.

For evidence that few dimensions actually forms a bad regime, please see the following very recent work:

Daniel Hsu and Sham Kakade, "Learning mixtures of spherical Gaussians: moment methods and spectral decompositions", ITCS 2013.

This work presents a spectral method for recovering spherical mixtures of Gaussians. So far, so good: univariate Gaussians are spherical. However, this algorithm requires the $k$ individual means to span a rank-$k$ subspace (and the performance depends on the condition number of these points, meaning you can't just perturb your univariate instance in a $k$-dimensional space and then closely recover your original Gaussians). As such, you could view their circumvention of the Moitra-Valiant lower bound as coming from an increase in dimension (and of course by maintaining the speherical nature you find from 1-d).

The above two papers have lots of excellent discussion, techniques, nice references. This is not my field and I can only offer a very surface intuition for what is going on. In the univariate case, things are really crowded, so the contribution of different Gaussians is confused and it's hard to disentangle them. In the high-dimensional case, basically everything is far apart and low density; it's hard to get crowded, and easy to pick out points of high density (which now must reside near means).

I only have one other thing to point out, and that's the connection to $k$-means. $k$-means has a DP in the 1-d case; google tells me it's from the 40s, and while I haven't seen that reference, we can cook up a DP fairly easily: make your table have size $n\times k$, where $n$ is the number of points, and use "optimal $k$-means cost using $j\leq k$ means and the first $m\leq n$ data points" as your subproblem, noting that each mean owns a contiguous subset of the data. As I tried just now to adjust this to the Gaussians case, it was interesting to see how the differences between these two scenarios became acute. First, the hard vs. soft clustering aspect means we can't just knock out contiguous subsets and claim they are owned by some Gaussian (furthermore, for univariate Gaussians of differing variances, the regions where one or the other dominates aren't just two intervals..). Second, we have no relationship between the variances, the univariate assumption really doesn't help us there (it would seem we need more; and of course, $k$-means is like knowing a fixed (common) variance up front).

So, oh well.

Answer 2

Since univariate Gaussians are a special case of multivariate Gaussians, in terms of formal guarantees (e.g. provable bounds on run time, confidence, etc.), all papers on learning mixtures of multivariate Guassians also give results on univariate Gaussians. (And often the papers start with the simpler case of learning univariate Gaussians, then reduce the general case of learning multivariate Gaussians to the special case by some tricks, e.g. projections).

Two recent papers on learning mixtures of Gaussians, based on the method of moments:

1. Disentangling Gaussians by Adam Tauman Kalai, Ankur Moitra, and Gregory Valiant. (CACM 2012 and manuscript).

2. Polynomial Learning of Distribution Families by Mikhail Belkin, Kaushik Sinha. (FOCS 2010 and arXiv). See also Table 1 for further references.

They give algorithms for learning mixtures of Gaussians with time bounds polynomial in (the inverse of) precision $\epsilon$, confidence error $\delta$, and some "condition number" measuring the separation in parameters (for each fixed number of Gaussians in the mixture).