Generative Local Metric Learning for Nearest Neighbor Classification

Yung-Kyun Noh, Byoung-Tak Zhang, Daniel D. Lee

Introduction

Nearest Neighbor (NN) classification is a staple of machine learning, but its performance hinges entirely on the distance metric used. In theory—with infinite data—the choice of distance metric does not actually change the error rate. However, in the real world of finite datasets, the metric is everything.

Most existing "metric learning" techniques are discriminative and global. They try to find a single transformation for the entire feature space that pushes different classes apart and pulls similar ones together. This paper argues that global approaches are suboptimal because they fail to account for how the "best" direction to look for neighbors changes depending on your location in the data space. Furthermore, they ignore the underlying probability distributions (generative models) that can provide a more stable foundation when data is sparse.

To address this, the authors introduce Generative Local Metric Learning (GLML), a method that uses generative models to derive optimal local distance metrics that minimize classification error caused by finite sampling noise.

Methods: Bridging Generative and Discriminative Models

The authors bridge the gap between generative and discriminative models by focusing on the bias introduced by finite sampling.

  • Bias Analysis: Using a second-order Taylor expansion, they model how the probability density behaves near a test point. They show that the expected error of a NN classifier deviates from the theoretical "infinite data" limit based on the curvature (the Hessian/Laplacian) of the class distributions.
  • Local Metric Optimization: Instead of one global matrix, they solve for a local metric $A$ at each point. The goal is to find a metric that adapts to the specific geometry of class boundaries to minimize the sampling bias.
  • Analytical Solution: They frame this as a Semi-Definite Programming (SDP) problem. Remarkably, they find an analytical solution for the optimal metric $A_{opt}$ based on the eigenvectors and eigenvalues of a matrix derived from the class-conditional Hessians. Because the local metric has an analytical spectral solution, it is often more computationally efficient than global methods that require iterative optimization over the entire dataset.
  • Regularization: Since calculating true "geodesic" distances on a curved manifold is computationally expensive, they use a practical surrogate: a local Mahalanobis distance regularized by an identity matrix.
Visualization of the learned local metric field and the resulting reduction in sampling bias compared to an identity metric.

Key Results

The researchers evaluated GLML against several state-of-the-art discriminative methods—including Large Margin Nearest Neighbor (LMNN) and Information-Theoretic Metric Learning (ITML)—across a variety of benchmarks. Datasets included synthetic data, UCI/IDA repositories (Ionosphere, Wine, German, Image, Waveform, Twonorm), USPS handwritten digits, and TI46 speech data.

Performance comparison of GLML against other metric learning methods across various synthetic and real-world datasets.
  • Dimensionality Resilience: In synthetic tests, as the number of dimensions increased, standard NN and global metric methods saw performance degrade. GLML, however, maintained high accuracy, effectively "ignoring" noisy dimensions.
  • Superior Accuracy: On benchmark datasets like Twonorm, Wine, and USPS, GLML consistently outperformed global methods.
  • Generative Stability: Interestingly, using simple generative models (like standard Gaussians) directly for classification via Bayes' rule often performed poorly. However, using those same models to inform the metric for a discriminative NN classifier yielded excellent, robust results.

Limitations and Future Work

While GLML presents a strong theoretical and empirical step forward, the authors note a few areas for future exploration:

  • The Geodesic Hurdle: The current implementation uses a "flat" local approximation. A more mathematically rigorous approach would involve calculating true geodesic distances on a Riemannian manifold, though this remains a significant computational challenge.
  • Model Dependency: The method's success depends on the quality of the generative model. While simple Gaussians worked well in these tests, more complex data might require Mixture Models or Hidden Markov Models.
  • Extension to k-NN: The theoretical derivation focuses on 1-Nearest Neighbor. Extending the bias analysis to $k$-neighbors is a suggested path for future research.
  • Unifying Frameworks: The authors suggest that their framework could eventually unify metric learning and dimensionality reduction into a single theoretical approach.

Summary updated

Abstract

We consider the problem of learning a local metric to enhance the performance of nearest neighbor classification. Conventional metric learning methods attempt to separate data distributions in a purely discriminative manner; here we show how to take advantage of information from parametric generative models. We focus on the bias in the information-theoretic error arising from finite sampling effects, and find an appropriate local metric that maximally reduces the bias based upon knowledge from generative models. As a byproduct, the asymptotic theoretical analysis in this work relates metric learning with dimensionality reduction, which was not understood from previous discriminative approaches. Empirical experiments show that this learned local metric enhances the discriminative nearest neighbor performance on various datasets using simple class conditional generative models.
BibTeX
@inproceedings{noh2010generative,
  author = {Yung-Kyun Noh and Byoung-Tak Zhang and Daniel D. Lee},
  title = {{Generative Local Metric Learning for Nearest Neighbor Classification}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2010},
  url = {https://openreview.net/forum?id=HyW43LWdWS},
}
Figure