A Hybrid Method for Distance Metric Learning

Yi-Hao Kao, Benjamin Van Roy, Daniel L. Rubin, Jiajing Xu, Jessica S. Faruque, Sandy NapelarXiv 2012 · arXiv

Introduction

In information retrieval systems—ranging from medical image databases to music recommendation engines—the "distance metric" is the fundamental component that determines how similarity is calculated between objects. Traditionally, researchers have approached distance metric learning (DML) using one of two primary data sources: pairwise similarity ratings (e.g., "Object A is more similar to B than to C") or categorical class labels (e.g., "Object A is a 'Cyst'").

This research, conducted by Stanford University, proposes that these two data types should not be used in isolation. Instead, the authors introduce a hybrid method that integrates both labels and ratings to construct a more robust distance measure, particularly effective when raw features fail to capture the full semantic meaning of an object.

The Challenge: Features vs. Perceived Similarity

The central problem in DML is the "semantic gap": the raw features extracted from an object (such as pixel intensities or texture descriptors) often do not align perfectly with human-perceived similarity.

Existing methodologies typically fall into two categories:

  1. Similarity-based methods: These utilize user ratings to regress a distance function.
  2. Class-based methods: These operate on the assumption that objects within the same class should be clustered together, while objects in different classes should be separated.

The authors argue that class labels often serve as proxies for "missing features" that are not present in the raw data but are critical for determining similarity. For instance, two liver lesions might appear visually distinct in a CT scan but are both clinically classified as "metastases." A system relying solely on raw features might fail to recognize their relationship, whereas a system relying solely on labels might ignore important visual nuances.

The Hybrid Method (HYB)

The proposed Hybrid Method (HYB) is built upon a generative model that treats class labels as indicators of unobserved latent features. The algorithm proceeds in two distinct stages:

  1. Soft Classification: The system employs Kernel Density Estimation to learn a "soft classifier" from the labeled data. This assigns a probability distribution over all possible classes to every object, transforming a discrete label into a continuous "soft class label" vector.
  2. Convex Optimization: The method then solves a convex optimization problem to determine two components: a vector of weights for observed features (standard weighted Euclidean distance) and a matrix that encodes the distances between different classes.

The resulting distance metric combines feature-based distance with "class distance," allowing the model to learn that objects may be "close" if their class probabilities are similar, even if their raw features differ.

Experimental Evaluation

The researchers validated their approach using both synthetic and real-world datasets. The synthetic evaluation involved 100 generated datasets to observe how the model scales with increasing amounts of rating data.

The real-world evaluation utilized a dataset of 30 CT scans of liver lesions. Each image was characterized by 60 extracted features (e.g., texture, border sharpness) and categorized into one of three classes: cyst, metastasis, or hemangioma. Ground truth similarity ratings were provided by expert radiologists.

Examples of liver lesions: cyst, metastasis, and hemangioma.

Results

Performance was evaluated using Normalized Discounted Cumulative Gain (NDCG₁₀), where a score of 1.0 represents a perfect match to human expert ratings.

In synthetic tests, the HYB method consistently outperformed traditional approaches like Ordinal Regression (OR), Convex Optimization (CO), and Neighborhood Component Analysis (NCA). As shown in the figure below, the performance advantage of the hybrid approach becomes more pronounced as the size of the rating dataset increases.

Performance comparison on synthetic data across different rating dataset sizes.

The real-world results on the medical image dataset were even more significant. The HYB method achieved an NDCG of approximately 0.75, outperforming the class-only NCA method (~0.67) and the rating-only CO method (~0.57). This represents a margin of over 8% compared to the next best method, demonstrating the power of fusing labels and ratings.

Conclusion

The hybrid method successfully bridges the gap between different types of supervision in distance metric learning. By treating labels as proxies for latent information, it provides a more accurate reflection of expert-perceived similarity. While the current study is limited by a relatively small real-world sample size, the results suggest significant potential for improving retrieval accuracy in complex domains like medical imaging. Future work may explore the application of this method to datasets with a larger number of classes and the integration of more advanced generative-discriminative models.

Summary updated

BibTeX
@misc{kao2012hybrid,
  author = {Yi-Hao Kao and Benjamin Van Roy and Daniel L. Rubin and Jiajing Xu and Jessica S. Faruque and Sandy Napel},
  title = {{A Hybrid Method for Distance Metric Learning}},
  year = {2012},
  eprint = {1206.7112},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1206.7112},
}
Figure