NCA - performance issues

[ab-anssi]

The current NCA implementation creates a numpy matrix (tmp) of shape (n, n, d, d). It is problem even with medium size datasets(memory requirement n².d²). On my computer I have 64Go of memory, and I cannot run NCA on a dataset of 1021 instances in dimension 122.

A simple solution to deal with this memory problem is to compute tmp_i at each iteration:
tmp_i = np.einsum('...i,...j->...ij', dX[i], dX[i]) # shape (n, d, d)
This way, the memory requirement in only (n . d²), and it works on the dataset of dimension (1021, 122). However, it requires more than 12 hours to compute !!

This solution increases the execution time as tmp_i is recomputed at each iteration :

Shape of the input data | Previous execution time | New execution time
(44, 122) | 45s | 52s
(198, 122) | 20min | 25min
(1021, 122) | Memory Error | >12h

Even for small datasets the execution time is very long. Do you have any idea on how improve the performance of NCA ?

• Can we use an optimization library such as scipy.optimize (used for the implementation of MLKR for instance) ? Do you think it would significantly reduce the execution time ?
• Another solution which seems more complex is to re-implementing the optimization in cython.

[halachkin]

Hello @ab-anssi ,

it's magical, I read the paper yesterday, and today also found the same problem., and then I see your issue.
However it seems, that for datasets with around 10K instances and 30 features (which is my case), NCA is a wrong choice. Is this understanding correct, that for relatively large datasets we can train only LMNN?

[ab-anssi]

The paper "A Survey on Metric Learning for Feature Vectors and Structured Data" compares different metric learning algorithms according to the scalability w.r.t the number of instances and w.r.t the number of features. Indeed, LMNN scales better with the number of instances than NCA. However, this metric learning algorithm does not support dimension reduction. For my application I focus now on RCA as it is more scalable than NCA and it supports dimension reduction too.

I agree that NCA is not the best solution for large datasets. Do you think it makes sense to improve NCA implementation ? Or this method is too unscalable and it would be a waste of time to work on optimizing its implementation ?

[borgr]

If it is chosen not to be changed, perhaps a documentation may be useful, as if it is know there is no reason for others not to know about it before trying to fix their own bugs...
(and yes, I had ran out of memory as I have many features, even using 5% of my data won't have enough data for it).
This might be off topic for this issue, but many of the algorithms throw things without any documentation why would they do it, (NCA memory, RCA apparently cant handle boolean, and LSML has something with linalg problems, perhaps with the prior, that it just throws out without explanation of what is wrong with the input.) The user should not guess (or debug the project) to know why his data doesn't fit the algorithm.

RCA

  File "/cs/labs/oabend/borgr/py3/lib/python3.5/site-packages/metric_learn/rca.py", line 67, in fit
    data -= data.mean(axis=0)
TypeError: Cannot cast ufunc subtract output from dtype('float64') to dtype('bool') with casting rule 'same_kind'
'same_kind'

NCA

Traceback (most recent call last):
  File "binarise_representation.py", line 576, in <module>
    main()
  File "binarise_representation.py", line 572, in main
    calculate_distances_main(inv_db, feature_db, base_db)
  File "binarise_representation.py", line 513, in calculate_distances_main
    nca = create_learned_distance_matrix(inv_db, ml.NCA(), train_percentage, to_comparable_array, clust_dir + save_nca, models_dir + save_nca)
  File "binarise_representation.py", line 478, in create_learned_distance_matrix
    model = learn_metric(db, normalize, learning_algorithm, train_percentage, save_model)
  File "binarise_representation.py", line 425, in learn_metric
    model = learning_algorithm.fit(np.array(x), np.array(y))
  File "/cs/labs/oabend/borgr/py3/lib/python3.5/site-packages/metric_learn/nca.py", line 36, in fit
    tmp = np.einsum('...i,...j->...ij', dX, dX)  # shape (n, n, d, d)
  File "/cs/usr/borgr/.local/lib/python3.5/site-packages/numpy/core/einsumfunc.py", line 948, in einsum
    return c_einsum(*operands, **kwargs)
MemoryError

LSML:

 File "/cs/labs/oabend/borgr/py3/lib/python3.5/site-packages/metric_learn/base_metric.py", line 46, in transform
    L = self.transformer()
  File "/cs/labs/oabend/borgr/py3/lib/python3.5/site-packages/metric_learn/base_metric.py", line 29, in transformer
    return inv(cholesky(self.metric()))
  File "/cs/usr/borgr/.local/lib/python3.5/site-packages/numpy/linalg/linalg.py", line 612, in cholesky
    r = gufunc(a, signature=signature, extobj=extobj)
  File "/cs/usr/borgr/.local/lib/python3.5/site-packages/numpy/linalg/linalg.py", line 93, in _raise_linalgerror_nonposdef
    raise LinAlgError("Matrix is not positive definite")
numpy.linalg.linalg.LinAlgError: Matrix is not positive definite

[perimosocordiae]

@borgr I agree that the docs and error messages can be improved in many locations. I'm open to suggestions and pull requests. In your specific cases:

• RCA: This is due to a recent numpy change in behavior, but in general I would recommend to convert boolean data to a numeric dtype before any sort of math operation.
• NCA: That's what this bug is about, and needs to be fixed.
• LSML: This code has changed very recently. Try again on the master branch?