constraints on the covariance matrix in GMM/EMFit #283

Closed
rcurtin opened this Issue Dec 29, 2014 · 4 comments

Projects

None yet

1 participant

@rcurtin
Member
rcurtin commented Dec 29, 2014

Reported by hanslovsky on 7 May 43506170 01:55 UTC
Having a way to force constraints on the covariance matrix in GMM/EMFit would be great.
Useful constraints would be:
-covariance matrix is diagonal
-ratios of eigenvalues are r1, r2, r3, ...

This would allow for injecting prior knowledge about the shape of the distribution.

@rcurtin rcurtin self-assigned this Dec 29, 2014
@rcurtin rcurtin added this to the mlpack 1.0.7 milestone Dec 29, 2014
@rcurtin rcurtin closed this Dec 29, 2014
@rcurtin
Member
rcurtin commented Dec 30, 2014

Commented by rcurtin on 7 Oct 43506251 13:25 UTC
Hello there,

I think the right way to do this will be to add an extra template parameter to EMFit<>. This template parameter should be a class that holds one method (something like UpdateCovariance() or maybe I will think of a better name later), and right now the functionality that forces matrices to be positive definite can be put into a separate class and that can be used as the default. There could also be a NoCovarianceModification class (which does nothing) and then a DiagonalCovarianceRestriction and EigenvalueRatioRestriction class to perform each of the functions you suggested.

I'm a bit busy right now so this probably won't get done today, but this is definitely something that will be worked into the next release (1.0.7).

@rcurtin
Member
rcurtin commented Dec 30, 2014

Commented by hanslovsky on 13 Mar 43506273 19:27 UTC
Replying to rcurtin:

Hello there,

I think the right way to do this will be to add an extra template parameter to EMFit<>. This template parameter should be a class that holds one method (something like UpdateCovariance() or maybe I will think of a better name later), and right now the functionality that forces matrices to be positive definite can be put into a separate class and that can be used as the default. There could also be a NoCovarianceModification class (which does nothing) and then a DiagonalCovarianceRestriction and EigenvalueRatioRestriction class to perform each of the functions you suggested.

I'm a bit busy right now so this probably won't get done today, but this is definitely something that will be worked into the next release (1.0.7).

Hi,

I'll be very happy to see those features in 1.0.7 and your approach seems very reasonable to me. Thank you for your effort!

@rcurtin
Member
rcurtin commented Dec 30, 2014

Commented by rcurtin on 5 Sep 43758207 12:21 UTC
Ok, I have implemented all of these features. EMFit<> now accepts a template parameter that can apply constraints to the covariance matrix after estimation. So, after each covariance re-estimation step, the ApplyConstraint() function of the CovarianceConstraintPolicy class is called. There are a number of choices for this policy class that are found in src/mlpack/methods/gmm/:

  • NoConstraint (no_constraint.hpp): doesn't modify anything
  • PositiveDefiniteConstraint (positive_definite_constraint.hpp): makes sure det(cov) >= 1e-50 so that the matrix is invertible
  • DiagonalConstraint (diagonal_constraint.hpp): forces non-diagonal elements of the covariance matrix to zero
  • EigenvalueRatioConstraint (eigenvalue_ratio_constraint.hpp): forces eigenvalues to adhere to a predefined list of ratios

So, in practice, here is an example of how you would use EigenvalueRatioConstraint:

arma::vec ratios; // Fill this somehow...
EigenvalueRatioConstraint erc(ratios);

// Now create the EMFit object.
// The key is that we're passing the instantiated constraint object as the fourth parameter.
EMFit<KMeans<>, EigenvalueRatioConstraint> em(300, 1e-10, KMeans(), erc);

// Now create the GMM object with the instantiated EMFit object.
GMM<EMFit<KMeans<>, EigenvalueRatioConstraint> gmm(gaussians, dimensionality, em);

// Now you can run the training, etc...

I actually think using DiagonalConstraint yields the same results as if you re-derive the EM algorithm for the case of diagonal covariance, but it isn't as fast because it's calculating the complete covariance matrix and then setting most of those elements to zero.

The only option given in the 'gmm' command-line executable is still the option to not check for a positive-definite covariance matrix (i.e. use NoConstraint instead of PositiveDefiniteConstraint), because adding too many more options makes it rather complex.

Anyway, I'm about to release 1.0.7, so you can either wait for that or just download trunk from svn now. Your feedback is appreciated, if you find the features useful. :)

@rcurtin
Member
rcurtin commented Dec 30, 2014

Commented by hanslovsky on 19 Feb 44119092 17:49 UTC
Hi,

this answer is coming with a lag of time. The constraints are indeed very useful and much appreciated. Thank you for implementing those. Also, the choice of PositiveDefiniteConstraint as default appears reasonable to me.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment