SPARK-4156 [MLLIB] EM algorithm for GMMs

Implementation of Expectation-Maximization for Gaussian Mixture Models.

This is my maiden contribution to Apache Spark, so I apologize now if I have done anything incorrectly; having said that, this work is my own, and I offer it to the project under the project's open source license.


I had considered using pseudo inverse here for that reason (I ultimately decided this was unlikely to actually cause a problem in practice); what do you think of using pinv instead?

> On Dec 17, 2014, at 7:23 PM, jkbradley <notifications@github.com> wrote:
> 
> In mllib/src/main/scala/org/apache/spark/mllib/clustering/GaussianMixtureModelEM.scala:
> 
> > +          (1.0 / k, 
> > +            vectorMean(samples.slice(i * nSamples, (i + 1) * nSamples)), 
> > +            initCovariance(samples.slice(i * nSamples, (i + 1) * nSamples)))
> > +        }.toArray
> > +      }
> > +    }
> > +    
> > +    var llh = Double.MinValue // current log-likelihood 
> > +    var llhp = 0.0            // previous log-likelihood
> > +    
> > +    var iter = 0
> > +    do {
> > +      // pivot gaussians into weight and distribution arrays 
> > +      val weights = (0 until k).map(i => gaussians(i)._1).toArray
> > +      val dists = (0 until k).map{ i => 
> > +        new MultivariateGaussian(gaussians(i)._2, gaussians(i)._3)
> This is brittle since it fails when the covariance matrix is not full rank. I'd say any of these is acceptable for now:
> 
> Temporary fix: Check for an exception and printing a warning about the data not being full rank.
> OK fix: Adding a little epsilon smoothing.
> Actual fix: Do a matrix decomposition (like Cholesky) instead of a direct inversion to handle non-full rank matrices.
> —
> Reply to this email directly or view it on GitHub.