<p>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.</p>

<p>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:</p>

<blockquote>
  <p>Ankur Moitra and Greg Valiant, <a href="http://arxiv.org/abs/1004.4223">"Settling the Polynomial Learnability of Mixtures of Gaussians"</a>, FOCS 2010.</p>
</blockquote>

<p>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.  </p>

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

<blockquote>
  <p>Daniel Hsu and Sham Kakade, <a href="http://arxiv.org/abs/1206.5766">"Learning mixtures of spherical Gaussians: moment methods and spectral decompositions"</a>, ITCS 2013.</p>
</blockquote>

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

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

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

<p>So, oh well.</p>

CC BY-SA 3.0
2013-01-11T07:29:45.403Z
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
CC BY-SA 3.0
2013-01-11T08:08:36.557Z
@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 http://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
CC BY-SA 3.0
2013-01-11T04:07:02.220Z
2013-01-11T04:07:02.220Z
matus
<p>Since <em>univariate</em> Gaussians are a special case of <em>multivariate</em> Gaussians, 
in terms of formal guarantees (e.g. provable bounds on run time, confidence, etc.), all papers on learning mixtures of <em>multivariate</em> Guassians also give results on <em>univariate</em> Gaussians.  (And often the papers start with the simpler case of learning <em>univariate</em> Gaussians, then reduce the general case of learning <em>multivariate</em> Gaussians to the special case by some tricks, e.g. projections).</p>

<p>Two recent papers on learning mixtures of Gaussians, based on the method of moments:</p>

<ol>
<li><p><em>Disentangling Gaussians</em> by Adam Tauman Kalai, Ankur Moitra, and Gregory Valiant. (<a href="http://dx.doi.org/10.1145/2076450.2076474" rel="nofollow">CACM 2012</a> and <a href="http://people.csail.mit.edu/moitra/docs/disentangling.pdf" rel="nofollow">manuscript</a>).</p></li>
<li><p><em>Polynomial Learning of Distribution Families</em> by Mikhail Belkin, Kaushik Sinha. (<a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2010.16" rel="nofollow">FOCS 2010</a> and <a href="http://arxiv.org/abs/1004.4864" rel="nofollow">arXiv</a>).  See also Table 1 for further references.</p></li>
</ol>

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

CC BY-SA 3.0
2013-01-08T06:37:21.197Z
Right, but none of these is polynomial in the number of components. I'll update the question.
Aryeh
CC BY-SA 3.0
2013-01-06T23:30:46.117Z
2013-01-06T23:46:46.630Z
2013-01-06T23:46:46.630Z
siuman
<p>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?</p>

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

<machine-learning><lg.learning>
Learning Mixture of Univariate Gaussians
Aryeh
# Learning Mixture of Univariate Gaussians

(Asked by: username_0 on 2013-01-06)

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

**Tags:** machine-learning, lg.learning


---

## 2 answers

### Answer by username_1 on 2013-01-11. Score: 7 | Accepted answer

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"](http://arxiv.org/abs/1004.4223), 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"](http://arxiv.org/abs/1206.5766), 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.

> **Comments:**
> **username_0**: 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?  
> **username_1**: @username_0: There's a table in Belkin&Sinha's second paper (referenced by username_2) which summarizes the separation assumptions needed in prior work: see Table 1 on page 2 of http://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.  

---

### Answer by username_2 on 2013-01-06. Score: 1

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](http://dx.doi.org/10.1145/2076450.2076474) and [manuscript](http://people.csail.mit.edu/moitra/docs/disentangling.pdf)).
2. *Polynomial Learning of Distribution Families* by Mikhail Belkin, Kaushik Sinha. ([FOCS 2010](http://doi.ieeecomputersociety.org/10.1109/FOCS.2010.16) and [arXiv](http://arxiv.org/abs/1004.4864)). 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).

> **Comments:**
> **username_0**: Right, but none of these is polynomial in the number of components. I'll update the question.  

---

