Sparse Compositional Metric Learning (SCML) allows scalable learning of global, multi-task and multiple local Mahalanobis metrics for multi-class data under a unified framework based on sparse combinations of rank-one basis metrics. For this initial merge, only the global setting will be implemented.

The algorithm learns on triplets, so it is necessary to add the base class for the addition of this kind of algorithm. For the sake of clarity, this will be added in a separate concurrent PR.

This implementation follows closely the matlab implementation of Y. Shi, A. Bellet and F. Sha. Sparse Compositional Metric Learning. AAAI Conference on Artificial Intelligence (AAAI), 2014. SCML paper

Theory - Global setting

The Mahalanobis Matrix is constructed as a sum of rank-1 PSD matrices:

The basis are intended to be locally discriminative. In the original paper and in this implementation they are constructed with LDA of several local regions. There are other options to construct this basis that will be added later.

The constrains are a set of triplets C that are inforced through the minimization problem:

Advantages

• No need to project to SPD cone as M is constructed as a nonegative sum of SPD matrices.
• Only n_basis parameters must be learned and stored, without taking into account the basis.
• Uses stochastic composite optimization and in consequence, big datasets can be handled by this algorithm. An efficient implementation of regularized dual averaging is used for the optimization procedure.
• Faster to Train.
• Good Performance on standard datasets (see paper for detailed information) especially on multi-task and local settings. A Benchmark against the other algorithms of the package will be added to this PR later.
• First algorithm to learn on triplets to be implemented in this package.

Tests on Vehicles dataset
The results for the vehicles dataset found in the matlab implementation github are used to validate the consistency and the correctness of the current implementation.
On each of the tests, the algorithm was run 100 times, the mean and std of the resulted accuracy in test and train, as well as the time, are shown below each test link.
For the batch versions, the numbers of iterations are reduced to have the same amount of gradient computations for each method.

Test Vanilla

Time. Mean:  5.7989197754859925 std:  0.05547399180223441
Train - Accuracy. Mean:  79.3214990138067 std:  0.7612083562308343
Test - Accuracy. Mean:  77.71176470588235 std:  2.056124280977084

Test Batch

Time. Mean:  6.090397052764892 std:  0.048224950065408285
Train - Accuracy. Mean:  81.41222879684418 std:  0.9372967012148159
Test - Accuracy. Mean:  78.0 std:  1.6946894459868151

Test Adagrad

Time. Mean:  6.090397052764892 std:  0.048224950065408285
Train - Accuracy. Mean:  81.41222879684418 std:  0.9372967012148159
Test - Accuracy. Mean:  78.0 std:  1.6946894459868151

Test Batch+Adagrad

Time. Mean:  1.7653330016136168 std:  0.015989019692575546
Train - Accuracy. Mean:  81.31558185404339 std:  0.9613659886786882
Test - Accuracy. Mean:  78.03529411764706 std:  1.641208095836975

We can see that the result are almost the same and even with little variance improvements over the test accuracy. Also the use of mini-batches yields almost a 4-fold improvement on the time used.

Furthermore, the adagrad version has a faster convergence than the "vanilla" version as it can be observed of the results obtained with 1/20 the number of iterations, as observed on the achieved train acuracy. But this comes with an apparent tradeoff as the test accuracy of the vanilla version is a little bit better, this suggest that maybe it is a good idea to allow both options.
Test Vanilla - 1/20 iterations

Time. Mean:  1.2541892004013062 std:  0.02197305793469499
Train - Accuracy. Mean:  79.0 std:  0.8888682213828464
Test - Accuracy. Mean:  77.37647058823529 std:  1.5683284028668087

Test Adagrad - 1/20 iterations

Time. Mean:  1.3263736057281494 std:  0.020214300581072035
Train - Accuracy. Mean:  80.65483234714003 std:  1.1301895624652614
Test - Accuracy. Mean:  77.0764705882353 std:  2.0688077237684213

TODO:

• Code Comentaries and docstrings
• Documentation
• Basic Tests
• Specific Tests
• Benchmark