[mlpack] Fwd: Degenerate cases and other GMM problems

[Ryan Curtin]

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