Error on covariance initialization when there are linearly dependent dimensions

[grudloff]

Description

While fitting on MMC_Supervised with init="covariance" on the MNIST dataset, a warning is raised and an error is thrown. I tracked down the problem to the initialization which is done with the inverse of the covariance matrix, which isn't invertible in this case because there are some LD dimensions.

This can be easily fixed by replacing by the (Moore-Penrose) pseudo-inverse as it is done for the random initialization. I am not sure this would be necessarily the desired behavior, but in any case, this issue should be addressed at least whit a more user-friendly error stating that there are some linearly dependent dimensions and that the input should be reduced to eliminate this redundancy.

Haven't checked but this issue should arise on any algorithm using the covariance initialization that doesn't require an SDP matrix.

Steps/Code to Reproduce

from metric_learn import MMC_Supervised
from sklearn import datasets

# Load digits dataset
digits = datasets.load_digits()
X = digits.data
y = digits.target

mmc=MMC_Supervised(init='covariance')
mmc.fit(X,y)

Expected Results

No error or a more user-friendly error.

Actual Results

The following warnings are thrown during runtime.

/home/gabrielrudloff/anaconda3/lib/python3.7/site-packages/metric_learn/_util.py:718: RuntimeWarning: divide by zero encountered in true_divide
  M = np.dot(u / s, u.T)
/home/gabrielrudloff/anaconda3/lib/python3.7/site-packages/metric_learn/_util.py:718: RuntimeWarning: invalid value encountered in true_divide
  M = np.dot(u / s, u.T)

And this is the error thrown, which states that the matrix is not symetric. The computed matrix is full of nan/inf.

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-1-272efe10621c> in <module>
      9 
     10 mmc=MMC_Supervised(init='covariance')
---> 11 mmc.fit(X,y)

~/anaconda3/lib/python3.7/site-packages/metric_learn/mmc.py in fit(self, X, y, random_state)
    609                                         random_state=self.random_state)
    610     pairs, y = wrap_pairs(X, pos_neg)
--> 611     return _BaseMMC._fit(self, pairs, y)

~/anaconda3/lib/python3.7/site-packages/metric_learn/mmc.py in _fit(self, pairs, y)
     63       return self._fit_diag(pairs, y)
     64     else:
---> 65       return self._fit_full(pairs, y)
     66 
     67   def _fit_full(self, pairs, y):

~/anaconda3/lib/python3.7/site-packages/metric_learn/mmc.py in _fit_full(self, pairs, y)
    186     self.n_iter_ = cycle
    187 
--> 188     self.components_ = components_from_metric(self.A_)
    189     return self
    190 

~/anaconda3/lib/python3.7/site-packages/metric_learn/_util.py in components_from_metric(metric, tol)
    398   """
    399   if not np.allclose(metric, metric.T):
--> 400     raise ValueError("The input metric should be symmetric.")
    401   # If M is diagonal, we will just return the elementwise square root:
    402   if np.array_equal(metric, np.diag(np.diag(metric))):

ValueError: The input metric should be symmetric.

Versions

Linux-5.3.0-26-generic-x86_64-with-debian-buster-sid
Python 3.7.4 (default, Aug 13 2019, 20:35:49)
[GCC 7.3.0]
NumPy 1.17.2
SciPy 1.3.1
Scikit-Learn 0.21.3
Metric-Learn 0.5.0

[perimosocordiae]

Thanks for the detailed report! I agree that we should handle this more gracefully, and I'm surprised we don't catch it earlier in the initialization code. It seems like we need to insert a NaN check after computing the covariance matrix.

[grudloff]

I thought of fixing this by using the pseudo-inverse but I am not sure what are the theoretical implications in this context of using the pseudo-inverse when the inverse doesn't exist.

[bellet]

Using the pseudo-inverse would be fine as long as the algorithm does not require the matrix to be strictly PD. The pseudo inverse of a PSD matrix is only guaranteed to be PSD, and will be non-singular when the original matrix is non-singular

[wdevazelhes]

Good catch @grudloff !

Thanks for the detailed report! I agree that we should handle this more gracefully, and I'm surprised we don't catch it earlier in the initialization code. It seems like we need to insert a NaN check after computing the covariance matrix.

Yes, I agree, the check was done in RCA (see

metric-learn/metric_learn/rca.py

Lines 99 to 104 in 1b40c3b

	warnings.warn('The inner covariance matrix is not invertible, '
	'so the transformation matrix may contain Nan values. '
	'You should remove any linearly dependent features and/or '
	'reduce the dimensionality of your input, '
	'for instance using `sklearn.decomposition.PCA` as a '
	'preprocessing step.')

), but indeed not in the general _initialize_metric_mahalanobis

[wdevazelhes]

Also, we had a similar problem on LSML (see #202 (comment)), but I think we decided in that case that we wanted to enforce strict PD for LSML, which is why in #195 we thought to test the case where strict_pd=True and the cov matrix is singular (see

metric-learn/test/test_mahalanobis_mixin.py

Line 572 in 1e42acb

def test_singular_covariance_init_or_prior(estimator, build_dataset):

), but we forgot to test the case where strict_pd=False and the cov matrix is singular.