Source-linked AI summary
Parametric Local Metric Learning for Nearest Neighbor Classification
Jun Wang, Adam Woznica, Alexandros Kalousis
TL;DR
Local metric learning can represent neighborhood-specific discrimination, but learning unrelated local metrics carries an overfitting risk. PLML approximates a smooth metric-matrix function with anchor-point basis metrics and manifold regularization. In large-scale classification experiments, it significantly outperforms state-of-the-art metric-learning methods and multiclass SVM with automatic kernel selection.
Problem
Local metric learning offers neighborhood-specific distances, but independently learned local metrics risk overfitting.
Source: §1 · p. 1Method
PLML represents local metrics as weighted combinations of anchor-point basis metrics and regularizes the weights to vary smoothly over the data manifold.
Source: §1 · p. 2, §3 · p. 3, §3.1 · p. 4Results
Takeaways & Limitations
The reported experiments show PLML combining local metric learning with predictive performance and scalability on problems with tens of thousands of instances.
Source: §1 · p. 2The approximation assumes the local-metric function is Lipschitz smooth.
Source: §3 · p. 3
Abstract
from arXiv · showhide
We study the problem of learning local metrics for nearest neighbor classification. Most previous works on local metric learning learn a number of local unrelated metrics. While this "independence" approach delivers an increased flexibility its downside is the considerable risk of overfitting. We present a new parametric local metric learning method in which we learn a smooth metric matrix function over the data manifold. Using an approximation error bound of the metric matrix function we learn local metrics as linear combinations of basis metrics defined on anchor points over different regions of the instance space. We constrain the metric matrix function by imposing on the linear combinations manifold regularization which makes the learned metric matrix function vary smoothly along the geodesics of the data manifold. Our metric learning method has excellent performance both in terms of predictive power and scalability. We experimented with several large-scale classification problems, tens of thousands of instances, and compared it with several state of the art metric learning methods, both global and local, as well as to SVM with automatic kernel selection, all of which it outperforms in a significant manner.
1 Introduction
Nearest-neighbor classification depends strongly on the distance measure, and a single global metric may not capture neighborhood-specific feature discrimination. PLML represents local metrics through a smooth metric-matrix function over the data manifold, aiming to retain local flexibility while avoiding overfitting.
1 Introduction
- A global metric may fail when feature discrimination varies across neighborhoods, motivating local metrics that fit different regions of the data.The nearest-neighbor classifier’s finite-sample performance depends strongly on the distance measure.Source: §1 · p. 1
- Earlier local methods learn independent metrics, which can overfit; limiting metrics by region still leaves them independent and potentially overly specific.Other approaches cited address overfitting through target-position fitting or generative modeling, but introduce learning-order and target-definition dependence or strong distributional assumptions.Source: §1 · p. 2
- PLML models a smooth metric-matrix function using linear combinations of anchor-point basis metrics and manifold regularization.Its two-stage algorithm learns instance weights and then anchor metrics, using FISTA for efficiency.Source: §1 · p. 2
- Experiments on large-scale classification problems report that PLML outperforms state-of-the-art metric-learning methods and multiclass SVM with automatic kernel selection.The experiments include tens of thousands of instances.Source: §1 · p. 2
2 Preliminaries
The preliminaries establish Mahalanobis distance and triplet constraints as the metric-learning setup, then motivate instance-specific local metrics when discrimination varies across neighborhoods. The local-distance formulation is computationally practical but may be asymmetric.
2 Preliminaries
- A Mahalanobis metric is a PSD matrix used to define squared distances between input instances.Metric-learning methods optimize the matrix under PSD and pairwise-distance constraints.Source: §2 · p. 2
- A triplet constraint requires one instance pair to be closer than another in the space projected by the learned metric.The constraint c(xi, xj, xk) requires xi and xj to be closer than xi and xk.Source: §2 · p. 2
- Because discriminative features can vary by neighborhood, the method learns one local metric per instance rather than a single global metric.Geodesic distances on a Riemannian manifold would use local metrics but are computationally difficult, motivating a simpler distance definition.Source: §2 · p. 2
- The local distance may be asymmetric because the metrics associated with the two instances can differ, so it is not a proper metric.The paper follows standard practice in continuing to call this approach local metric learning.Source: §2 · p. 3
3 Parametric Local Metric Learning
PLML approximates a smooth local-metric function with anchor-associated basis metrics and instance-specific weights. It regularizes neighboring weights for smoothness, then learns the basis metrics with large-margin triplet constraints.
3 Parametric Local Metric Learning
- The local metric function is approximated under a Lipschitz-smoothness assumption, with an error bound motivating a weighted combination of anchor-point metric bases.The anchor-based parameterization provides a global way to regularize the function’s flexibility; the described anchor points may be cluster means from k-means.Source: §3 · p. 3
- Each instance’s metric is a weighted combination of basis metrics, and nonnegative weights summing to one preserve PSD metrics when the anchor metrics are PSD.The normalization constraint removes the scaling problem between local metrics; each weight specifies an instance’s contribution from a basis metric.Source: §3 · p. 3
3.1 Smooth Local Linear Weighting
- Smooth Local Linear Weighting minimizes the approximation error bound while regularizing neighboring instances to have similar weight vectors.The objective’s graph-Laplacian term encourages similar instances to share similar coefficients, while another term makes weights reflect local properties.Source: §3.1 · p. 4
- The weight problem is convex with row-wise simplex constraints and is solved by projected-gradient updates accelerated with FISTA.The paper reports O(nm log(m)) complexity for simplex projection and O(nmd + n^2m) for the main per-iteration computations.Source: §3.1 · p. 4
- For test instances, the experiments assign the weights of the nearest training instance rather than optimizing new weights.The paper also describes optimizing weights conditional on the training weights as an alternative.Source: §3.1 · p. 4
3.2 Large Margin Basis Metric Learning
- Large-margin basis learning requires different-class neighbors to be farther than same-class neighbors and minimizes margin errors alongside within-class distances.Unlike LMNN-MM, PLML compares both distances using the same instance’s local metric; the objective also regularizes basis-metric Frobenius norms and is optimized through a dual formulation.Source: §3.2 · p. 5
4 Experiments
The experiments compare PLML with global and local metric-learning baselines and automatically kernel-selected SVMs on six datasets. PLML achieves the strongest overall benchmark ranking, while results and metric visualizations examine its performance and behavior relative to less-regularized local methods.
4 Experiments
- Evaluation covers six datasets with 5K–70K instances, comparing PLML with metric-learning baselines and multi-class SVM using inner-fold kernel selection.USPS, Isolet, and MNIST were PCA-reduced to components explaining 95% of variance; features were standardized and instances L2-normalized. Accuracy used default splits or 10-fold cross-validation, with McNemar testing at p = 0.05.Source: §4 · pp. 6–7
4.1 Results
- PLML ranks first overall with 37 points, ahead of SVM with automatic kernel selection at 32.5 and SML at 28.5, and is significantly better than CBLML and LMNN-MM on all six datasets.It is significantly better than LMNN, SML, and BoostMetric on three, four, and five datasets respectively, never significantly worse than those methods, and significantly better than SVM on two datasets without being significantly worse.Source: §4.1 · p. 7, Table 1 · p. 7
- CBLML and LMNN-MM tend to overfit, whereas PLML’s manifold regularization is reported to avoid that problem despite learning local metrics.The comparison with global-metric SML and LMNN supports the authors’ overfitting interpretation; they attribute LMNN-MM’s poorer performance than in to a different validation setting.Source: §4.1 · pp. 7–8
- On four handwritten MNIST digits, PLML reaches 82.76% accuracy, versus 82.59% for CBLML, 82.56% for LMNN-MM, and 82.51% for GLML.The learned-metric visualization is described as showing a better fit for PLML than LMNN-MM and smoother variation in PLML’s local metrics.Source: Figure 1 · p. 7, §4.1 · p. 8
- As basis metrics increase from 5 to 40, PLML often improves and then saturates without overfitting, while CBLML worsens at larger counts.The authors interpret this contrast as further evidence of CBLML overfitting and of the utility of manifold regularization.Source: §4.1 · p. 8, Figure 2 · p. 8
5 Conclusions
PLML regularizes local metrics to vary smoothly over the data manifold by representing them as weighted combinations of anchor-point metrics. The authors report that it scales to tens of thousands of instances, avoids overfitting seen in other local methods, and outperforms state-of-the-art metric learning methods.
5 Conclusions
- PLML significantly outperforms state-of-the-art metric learning methods and performs significantly better or equivalently to SVM with automatic kernel selection.The conclusion reports these comparisons across the paper’s experiments.Source: §5 · p. 8
- PLML scales to learning problems with tens of thousands of instances and avoids the overfitting that affects other local metric learning methods.Source: §5 · p. 8
- PLML uses an approximation error bound to represent local metrics as weighted linear combinations of anchor-point metrics, regularizing them to vary smoothly over the data manifold.Source: §5 · p. 8
- Local metric learning offers a more flexible distance function, but can involve many parameters and risk overfitting.Source: §5 · p. 8