Evolutionary Adaptive Metric Learning: A Multi-Objective Framework for Learning Local Distance Functions in Nearest Neighbor Classification
Organizations: Department of Mathematics and Computer Science, Faculty of Science, University of Maroua, P.O. Box 814, Maroua, Cameroon · Laboratoire de Recherche en Informatique (LaRI), University of Maroua, Maroua, Cameroon
Abstract
Nearest neighbour classifiers inherit the geometry of their distance function. Fixed distances and globally learned metrics apply the same geometry throughout the input space, although relevant feature directions may vary across regions. We propose EAML (Evolutionary Adaptive Metric Learning), a framework that learns instance-dependent positive-definite metrics through a low-dimensional parameterization. Each local metric combines an input-dependent diagonal scaling, generated by softmax interpolation between anchor points, with a global low-rank correlation component. A real-coded elitist genetic algorithm optimizes the parameters using a scalar objective combining leave-one-out prediction error, robustness, metric smoothness, and regularization. We establish positive definiteness, metric equivalence, existence of an optimal solution, and Lipschitz continuity of the metric field. We further investigate prediction stability, generalization bounds, and evolutionary convergence under explicit assumptions. Experiments on synthetic data with region-dependent feature relevance show that EAML can recover local metric variations and outperform global metrics. Evaluation on thirteen public datasets using nested 5-fold cross-validation reveals a more nuanced picture: EAML improves performance on selected datasets but does not significantly outperform global metric baselines overall. Additional experiments show that global diagonal metrics can be preferable under nuisance features and test-time noise. These findings identify the conditions under which evolutionary local metric learning is beneficial and highlight its practical limitations.
Figures & tables
| Dataset | Imb. ratio | |||
|---|---|---|---|---|
| Fashion-MNIST | 3000 | 783 40 | 10 | 1.0 |
| Digits | 1797 | 61 | 10 | 1.1 |
| Iris | 150 | 4 | 3 | 1.0 |
| Wine | 178 | 13 | 3 | 1.5 |
| Breast cancer | 569 | 30 | 2 | 1.7 |
| Sonar | 208 | 60 | 2 | 1.1 |
| Euclidean | NCA | LMNN | GA-global | EAML | left / | right / | ||
|---|---|---|---|---|---|---|---|---|
| 0 | 90.95 | 89.91 | 90.90 | 91.40 | 93.22 | 0.002 | 13.95/5.95 | 5.20/14.99 |
| 4 | 64.91 | 86.51 | 66.14 | 91.46 | 88.23 | 0.002 | 11.49/12.42 | 10.14/13.32 |
| 8 | 58.47 | 75.34 | 58.94 | 90.43 | 83.12 | 0.002 | 10.17/10.88 | 9.70/11.04 |
| Dataset | Euclidean | Manhattan | Mahalanobis | NCA | LMNN | ITML | GA-global | EAML |
|---|---|---|---|---|---|---|---|---|
| Fashion-MNIST | 80.2 1.3 | 80.3 1.3 | 80.2 1.3 | 76.6 1.7 | 80.8 1.0 | 80.5 1.1 | 79.8 1.1 | 79.9 1.4 |
| Digits | 97.6 0.5 | 98.0 0.6 | 95.6 1.2 | 97.8 0.6 | 98.0 0.7 | 98.0 0.8 | 97.7 0.9 | 97.5 0.7 |
| Iris | 96.3 3.5 | 94.5 4.1 | 90.3 4.5 | 95.9 3.9 | 96.3 3.5 | 96.9 2.5 | 94.5 3.6 | 94.5 4.4 |
| Wine | 96.3 2.5 | 97.2 2.3 | 93.5 3.4 | 96.6 2.9 | 96.4 3.3 | 98.3 2.3 | 95.7 2.8 | 97.4 2.9 |
| Breast cancer | 96.6 1.5 | 96.7 1.8 | 84.0 2.7 | 95.3 1.4 | 96.7 1.5 | 95.5 1.7 | 95.1 1.6 | 96.3 1.6 |
| Sonar | 84.9 5.1 | 85.2 5.2 | 76.5 5.6 | 86.7 3.9 | 87.3 4.7 | 78.3 4.8 | 85.0 6.4 | 84.6 6.2 |
| Baseline | W/T/L | sig. better/worse | ||
|---|---|---|---|---|
| Euclidean | 4/0/9 | 0.414 | 1.000 | 2/0 |
| Manhattan | 3/1/9 | 0.062 | 0.438 | 0/0 |
| Mahalanobis | 7/0/6 | 0.110 | 0.659 | 4/0 |
| NCA | 8/0/5 | 0.146 | 0.732 | 2/0 |
| LMNN | 4/0/9 | 0.376 | 1.000 | 2/0 |
| ITML | 4/0/9 | 0.635 | 1.000 | 1/1 |
| Euclidean | Manhattan | Mahalanobis | NCA | LMNN | ITML | GA-global | EAML | |
|---|---|---|---|---|---|---|---|---|
| Mean acc., | 87.37 | 87.76 | 84.65 | 85.88 | 87.72 | 86.80 | 87.98 | 87.72 |
| Mean rank, | 4.65 | 3.65 | 5.69 | 5.00 | 3.54 | 3.46 | 4.77 | 5.23 |
| Mean acc., | 86.08 | 86.54 | 77.71 | 83.46 | 86.22 | 84.24 | 85.80 | 86.02 |
| Mean rank, | 3.77 | 2.69 | 6.54 | 5.96 | 2.92 | 5.04 | 4.54 | 4.54 |
| Mean acc., | 83.57 | 83.49 | 70.31 | 79.39 | 83.62 | 78.44 | 81.57 | 81.93 |
| Mean rank, | 2.19 | 2.69 | 6.77 | 6.00 | 2.42 | 6.27 | 4.88 | 4.77 |
| Euclidean | Manhattan | Mahalanobis | NCA | LMNN | ITML | GA-global | EAML | |
| Macro-F1 (mean) | 84.04 | 84.25 | 80.86 | 82.41 | 84.40 | 82.86 | 84.91 | 84.28 |
| Macro-F1 (rank) | 4.69 | 3.92 | 6.00 | 5.00 | 3.54 | 3.46 | 4.46 | 4.92 |
| Fit time, median over datasets (s) | 0.00 | 0.00 | 0.00 | 0.09 | 0.51 | 0.25 | 3.62 | 3.93 |
| Fit time, Fashion-MNIST (s) | 0.2 | 0.1 | 0.1 | 22.7 | 9.1 | 29.7 | 162.2 | 171.1 |
| Median selected | 6 | 5 | 4 | 1 | 6 | 6 | 1 | 1 |
| Variant | Acc. | Rank | Acc. | Time | |||
|---|---|---|---|---|---|---|---|
| EAML | 87.95 | 2.88 | 81.70 | 0.577 | 0.114 | 0.293 | 3.8 |
| EAML (no robustness) | 87.25 | 4.14 | 81.16 | 0.477 | 0.113 | 0.332 | 3.3 |
| EAML (no smoothness) | 88.33 | 2.50 | 81.48 | 0.543 | 0.117 | 0.289 | 2.9 |
| EAML (no low-rank, q=0) | 87.97 | 3.95 | 80.34 | 0.565 | 0.119 | 0.299 | 3.2 |
| EAML (random search) | 87.31 | 3.23 | 80.69 | 0.684 | 0.138 | 0.331 | 1.9 |
| EAML (NCA term only) | 87.55 | 3.95 | 81.53 | 0.442 | 0.113 | 0.331 | 3.1 |
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
| Setting | Value | Setting | Value |
|---|---|---|---|
| anchors , rank | , | population, generations | , (patience 15) |
| bounds , | , | tournament size | |
| SBX probability, index | , | ||
| , , | mutation probability per gene | ||
| margin target | mutation step | ||
| query rows | elites |
Metric Learning
Metric learning trains distances or embedding geometries so task-relevant examples are close and irrelevant ones far apart for retrieval, clustering, and recognition.
See all 92 papers