Abstract
Learning application-specific distance metrics from labeled data is critical for both statistical classification and information retrieval. Most of the earlier work in this area has focused on finding metrics that simultaneously optimize compactness and separability in a global sense. Specifically, such distance metrics attempt to keep all of the data points in each class close together while ensuring that data points from different classes are separated. However, particularly when classes exhibit multimodal data distributions, these goals conflict and thus cannot be simultaneously satisfied. This paper proposes a Local Distance Metric (LDM) that aims to optimize local compactness and local separability. We present an efficient algorithm that employs eigenvector analysis and bound optimization to learn the LDM from training data in a probabilistic framework. We demonstrate that LDM achieves significant improvements in both classification and retrieval accuracy compared to global distance learning and kernel-based KNN.
Introduction: The Global Conflict
In machine learning, the "distance" between two data points is the fundamental measure used to classify them or retrieve similar items. Traditional supervised distance metric learning algorithms typically seek a global metric. The objective is to minimize the distance between all pairs of points within the same class (global compactness) while maximizing the distance between points of different classes (global separability).
However, real-world data often exhibits "multimodal" distributions, where a single class consists of several distinct clusters. In such cases, a global metric can be counterproductive. For example, if a cluster of Class B is positioned between two clusters of Class A, a global algorithm attempting to pull the Class A clusters together will inevitably pull the Class B cluster into the mix, destroying separability. This "global conflict" often results in a metric that performs worse than simple Euclidean distance.
The Local Distance Metric (LDM) Approach
To address this, the authors propose the Local Distance Metric (LDM). Instead of enforcing global constraints, LDM prioritizes local geometry. It employs a probabilistic framework based on leave-one-out K-Nearest Neighbor (KNN) evaluation, focusing on keeping neighbors of the same class close and neighbors of different classes far apart.
Technical Innovations
- Locality Weighting: LDM introduces a weighting factor ($\phi_{i,j}$) that prioritizes pairs that are already relatively close. This allows the model to ignore distant same-class pairs that do not reflect local structure, avoiding the distortions caused by global metrics.
- Eigenvector Approximation: To avoid the computational cost and overfitting risks of optimizing a full $m \times m$ matrix, LDM models the metric as a linear combination of the top $K$ eigenvectors of the data's correlation matrix. This significantly reduces the parameter space from thousands of variables to just a few.
- Bound Optimization: The objective function (log-likelihood) is non-concave. The authors utilize an iterative approach similar to Expectation-Maximization (EM), approximating the objective with a concave lower bound and solving it via Newton’s method to ensure convergence.
- Semi-Supervised Integration: LDM can leverage unlabeled data to improve the estimation of principal eigenvectors, providing a more accurate representation of the underlying data manifold.
Solving the "Chicken-and-Egg" Dilemma
A primary challenge in local metric learning is that defining a "local" neighborhood requires an existing metric, yet learning the metric requires knowing the neighborhood. LDM addresses this by initializing with a Euclidean metric and iteratively refining both the neighborhood constraints and the distance metric itself.
Experimental Evaluation
The LDM algorithm was tested on two real-world datasets: the COREL image dataset and the Newsgroup text dataset.
Image Classification and Retrieval
On the COREL dataset (500 images, 5 categories), LDM achieved a classification accuracy of 81.0%, which rose to 82.0% when incorporating 1,500 unlabeled images. This outperformed global metric learning (77.8%) and standard Euclidean KNN (79.8%). In retrieval tasks, LDM consistently maintained higher precision across various ranks compared to baseline methods.
Text Categorization
For the Newsgroup dataset (500 documents, 5 categories), LDM reached 95.2% accuracy. This significantly surpassed the Euclidean baseline (91.8%) and approached the performance of Support Vector Machines (96.8%), which are traditionally the gold standard for text classification.
Conclusion
LDM effectively resolves the conflict between global compactness and separability by focusing on local data relationships. By combining a probabilistic framework with efficient eigenvector-based optimization, it provides a robust solution for multimodal data distributions. The results demonstrate that LDM not only improves classification accuracy but also excels in information retrieval, particularly when enhanced by semi-supervised learning.
Summary updated