SDML raises SDP error on iris

[wdevazelhes]

Description

Trying to update the metric_plotting.ipynb notebook, it didn't work for SDML, so here is a minimal example to reproduce.

Steps/Code to Reproduce

import numpy as np
from sklearn.datasets import load_iris
from metric_learn import SDML_Supervised
dataset = load_iris()
X, y = dataset.data, dataset.target
sdml = SDML_Supervised(num_constraints=200)
sdml.fit(X, y, random_state = np.random.RandomState(1234))

Expected Results

No error is thrown

Actual Results

/home/will/anaconda3/envs/standard/lib/python3.7/site-packages/sklearn/utils/validation.py:761: DataConversionWarning: A column-vector y was passed when a 1d array was expected. Please change the shape of y to (n
_samples, ), for example using ravel().
  y = column_or_1d(y, warn=True)
/home/will/anaconda3/envs/standard/lib/python3.7/site-packages/sklearn/utils/deprecation.py:77: DeprecationWarning: Function pinvh is deprecated; sklearn.utils.extmath.pinvh was deprecated in version 0.19 and wil
l be removed in 0.21. Use scipy.linalg.pinvh instead.
  warnings.warn(msg, category=DeprecationWarning)
/home/will/anaconda3/envs/standard/lib/python3.7/site-packages/sklearn/utils/deprecation.py:77: DeprecationWarning: Function pinvh is deprecated; sklearn.utils.extmath.pinvh was deprecated in version 0.19 and wil
l be removed in 0.21. Use scipy.linalg.pinvh instead.
  warnings.warn(msg, category=DeprecationWarning)
/home/will/anaconda3/envs/standard/lib/python3.7/site-packages/sklearn/utils/deprecation.py:77: DeprecationWarning: Function graph_lasso is deprecated; The 'graph_lasso' was renamed to 'graphical_lasso' in versio
n 0.20 and will be removed in 0.22.
  warnings.warn(msg, category=DeprecationWarning)
---------------------------------------------------------------------------
FloatingPointError                        Traceback (most recent call last)
<ipython-input-2-caf37592524f> in <module>
      3 X, y = load_iris(return_X_y=True)
      4 sdml = SDML_Supervised(num_constraints=200)
----> 5 sdml.fit(X, y, random_state = np.random.RandomState(1234))

~/Code/metric-learn/metric_learn/sdml.py in fit(self, X, y, random_state)
    181                                         random_state=random_state)
    182     pairs, y = wrap_pairs(X, pos_neg)
--> 183     return _BaseSDML._fit(self, pairs, y)

~/Code/metric-learn/metric_learn/sdml.py in _fit(self, pairs, y)
     68     # hack: ensure positive semidefinite
     69     emp_cov = emp_cov.T.dot(emp_cov)
---> 70     _, self.M_ = graph_lasso(emp_cov, self.sparsity_param, verbose=self.verbose)
     71 
     72     self.transformer_ = transformer_from_metric(self.M_)

~/anaconda3/envs/standard/lib/python3.7/site-packages/sklearn/utils/deprecation.py in wrapped(*args, **kwargs)
     76         def wrapped(*args, **kwargs):
     77             warnings.warn(msg, category=DeprecationWarning)
---> 78             return fun(*args, **kwargs)
     79 
     80         wrapped.__doc__ = self._update_doc(wrapped.__doc__)

~/anaconda3/envs/standard/lib/python3.7/site-packages/sklearn/covariance/graph_lasso_.py in graph_lasso(emp_cov, alpha, cov_init, mode, tol, enet_tol, max_iter, verbose, return_costs, eps, return_n_iter)
    815     return graphical_lasso(emp_cov, alpha, cov_init, mode, tol,
    816                            enet_tol, max_iter, verbose, return_costs,
--> 817                            eps, return_n_iter)
    818 
    819 

~/anaconda3/envs/standard/lib/python3.7/site-packages/sklearn/covariance/graph_lasso_.py in graphical_lasso(emp_cov, alpha, cov_init, mode, tol, enet_tol, max_iter, verbose, return_costs, eps, return_n_iter)
    267         e.args = (e.args[0]
    268                   + '. The system is too ill-conditioned for this solver',)
--> 269         raise e
    270 
    271     if return_costs:

~/anaconda3/envs/standard/lib/python3.7/site-packages/sklearn/covariance/graph_lasso_.py in graphical_lasso(emp_cov, alpha, cov_init, mode, tol, enet_tol, max_iter, verbose, return_costs, eps, return_n_iter)
    258                 break
    259             if not np.isfinite(cost) and i > 0:
--> 260                 raise FloatingPointError('Non SPD result: the system is '
    261                                          'too ill-conditioned for this solver')
    262         else:

FloatingPointError: Non SPD result: the system is too ill-conditioned for this solver. The system is too ill-conditioned for this solver

Versions

Linux-4.4.0-141-generic-x86_64-with-debian-stretch-sid
Python 3.7.1 (default, Dec 14 2018, 19:28:38)
[GCC 7.3.0]
NumPy 1.15.4
SciPy 1.2.0
Scikit-Learn 0.20.2
Metric-Learn 0.4.0

Note that it works for these versions, though printing this warning:

/home/will/anaconda3/envs/old_scipy_sk/lib/python2.7/site-packages/sklearn/covariance/graph_lasso_.py:252: ConvergenceWarning: graph_lasso: did not converge after 100 iteration: dual gap: 2.377e-04
  ConvergenceWarning)

Linux-4.4.0-141-generic-x86_64-with-debian-stretch-sid
('Python', '2.7.15 |Anaconda, Inc.| (default, Dec 14 2018, 19:04:19) \n[GCC 7.3.0]')
('NumPy', '1.11.3')
('SciPy', '0.17.1')
('Scikit-Learn', '0.17.1')
metric-learn: commit: ddfac99

[wdevazelhes]

Also note that it works if the random seed is 12345 instead of 1234...

[wdevazelhes]

@perimosocordiae in this #1 (comment), you say that the SDML test was flaky because of the prepare_constraints method. Did you notice some instabilities of SDML ?

@bellet do you know some instabilities of SDML ?

I'll try to find in metric-learn/scikit-learn/scipy/numpy's code what has changed since the two versions in the code executed by the example, then I'll try to understand the code and see values at run time to understand why there would be instabilities

[wdevazelhes]

After comparing the old environment and the new environment, I first saw that the variable loss_matrix differs between the two. I guess this is because of the preprocessing that is done just before. The change comes from PR #92. I'll look at it more throroughly to see if the PR was wrong or understand why it could make the result differ. I guess I should have been more careful on the tolerance of assert_almost_equal in the gist...

[[ -248.48    80.43  -657.42  -281.26]
 [   80.43   -37.43   221.47    88.26]
 [ -657.42   221.47 -1748.9   -740.06]
 [ -281.26    88.26  -740.06  -318.21]]

[[ -248.48    83.43  -658.02  -281.14]
 [   83.43   -38.73   226.95    90.37]
 [ -658.02   226.95 -1751.04  -740.23]
 [ -281.14    90.37  -740.23  -318.  ]]

[perimosocordiae]

I don't remember getting too deep into why certain sets of constraints caused instability, unfortunately.

[wdevazelhes]

@perimosocordiae no problem, it was just in case

I doubled checked the two formulas from the , and the results should be correct. But since the expressions are different, some uncertainties can be introduced.
I did a gist trying to decompose the two expressions by putting in light similar terms so that it is easier to see where these uncertainties come from: https://gist.github.com/wdevazelhes/6ce454a73ef9ed1edc2951244c447b15, with comments on what to do to investigate where the uncertainties are introduced.
I could do the investigation but I think that trying to obtain the exact same results with the new formula (from pairs) as with the old formula (with laplacian) is doomed, except trying to reconstruct the laplacian from the pairs, which does not seem very efficient.
Therefore I'd rather focus more on trying to solve the instabilities of SDML, what do you think ?

[bellet]

Now that #162 has been merged I think we can close this (it is a normal error due to the fact that with the default parameters, the input matrix is not PSD, hence the solver can fail).

[wdevazelhes]

Also, with skggm, the example converges