[mlpack] Fwd: Degenerate cases and other GMM problems

[John Demme]

Hi Ryan,

Thanks a ton for looking into this. I owe you a beer or 6! Especially
thanks for looking into it quickly -- I'm using mlpack to try and do
additional analysis for a camera ready version of a paper due Wednesday.

As you might imagine I'm using mlpack API in a much larger, slower system.
I'm running a bunch of GMMs now with a larger data set. I'll get back to
you on whether or not this patch fixes all my issues. Might not know for a
day or so. (As an aside, the full data set will likely become public in the
near future if anyone here has any interest in using it.)

~John


On Fri, Apr 12, 2013 at 1:43 PM, Ryan Curtin <gth671b at mail.gatech.edu>wrote:

> On Wed, Apr 10, 2013 at 04:10:12PM -0400, John Demme wrote:
> > Hi Ryan,
> >
> > I'll try out your latest in a little bit. It sounds like there's an issue
> > with my data, so I will likely do some conditioning. However, I've found
> > another case that gets the "matrix appears to be singular" issue:
> >
> > $ ./gmm -i gmm_obs0.csv -g 50 -t 10
> > [DEBUG] Compiled with debugging symbols.
> > <>
> >
> > error: inv(): matrix appears to be singular
> >
> > terminate called after throwing an instance of 'std::runtime_error'
> >   what():
> > Aborted (core dumped)
>
> Hello John,
>
> I have dug into the depths of covariance matrix estimation and returned
> with what I think is an answer and a fix which should explain all of the
> issues you've been having (...I think).
>
> Matrices aren't positive definite and can't be inverted* when the
> determinant is less than or equal to 0; this is the same as saying that
> matrices must be positive definite.  That explains the inv() errors.
>
> But, there is one more odd thing, which is that LAPACK actually *will*
> invert matrices with extremely small but negative determinants
> (something like -1e-150).  This usually results in two very weird things
> happened to the multivariate Gaussian probability density function:
>
>  1. The sqrt(det(cov)) term becomes NaN because you can't take the
>     square root of a negative number.
>
>  2. The "distance", or the exponent term, actually ends up being
>     positive, which should never happen.
>
> So, if LAPACK decides that it's going to take the inverse of a
> non-positive definite matrix (which I assume only happens because of
> machine precision issues), we don't get the inv() error and instead we
> end up introducing a NaN into the system, and NaNs propagate everywhere,
> and suddenly our model is busted.
>
> The solution I've devised here is that each time we update the
> covariance matrix, we check to see that the determinant is greater than
> 1e-30 (which is an arbitrarily-chosen tolerance) and if it isn't, we add
> continually larger perturbations to the diagonal until the determinant
> is above that tolerance.
>
> Checking the determinant is a time-consuming task and the method I came
> up with is definitely not very efficient.  There exist more efficient
> methods to project a non-positive definite matrix into the cone of
> positive definite matrices.  I need to do a little research on that
> (unless you want to... ;)) but when that's done I'll submit that method
> as a patch to Armadillo and update the GMM code.
>
> You can disable the check for positive definiteness (which speeds up the
> method significantly) by passing the -P flag to the gmm program.  The
> fixes are committed with r14894.
>
> I've cc'ed the mailing list in case anyone else is watching...
>
> * I think you can use a few tricks to invert negative definite matrices,
>   but that's definitely not what's going on here.
>
> --
> Ryan Curtin       | "Are you or are you not the Black Angel of Death?"
> ryan at igglybob.com |   - Steve
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cc.gatech.edu/pipermail/mlpack/attachments/20130412/d965ee6a/attachment-0003.html>