Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 6 down vote accepted

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.

share|improve this answer
    
Thanks for the detailed and informative answer, matus! –  Aryeh Jan 11 '13 at 7:27
    
However, let me follow this up with another question. What about adding some assumption on the separation -- not in the statistical distance, but in actual parameter space? –  Aryeh Jan 11 '13 at 7:29
1  
@Aryeh: There's a table in Belkin&Sinha's second paper (referenced by siuman) which summarizes the separation assumptions needed in prior work: see Table 1 on page 2 of arxiv.org/abs/1004.4864 ("Polynomial learning of distribution families", also FOCS 2010). The best ones seem to say you need the means to be separated by (standard deviation) * k for the algorithm to work (i.e., performance doesn't simply degrade when separation is smaller). I think that table is up to date; some nice, recent, overview discussion is in the intro to the Hsu&Kakade paper I mentioned in my answer. –  matus Jan 11 '13 at 8:08
    
Thanks again, matus! –  Aryeh Jan 11 '13 at 8:12

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).

share|improve this answer
    
Right, but none of these is polynomial in the number of components. I'll update the question. –  Aryeh Jan 8 '13 at 6:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.