Beyond Similar and Dissimilar Relations : A Kernel Regression Formulation for Metric Learning

Pengfei Zhu, Ren Qi, Qinghua Hu, Qilong Wang, Changqing Zhang, Liu Yang

Introduction

In machine learning, the concept of "distance" is fundamental. Whether performing face recognition or scene categorization, a robust method for measuring similarity between data points is essential. Traditionally, Metric Learning has been treated as a binary classification problem: pairs of samples are either similar (belonging to the same category) and should be pulled together, or dissimilar and should be pushed apart.

However, real-world data is rarely so binary. Consider two images: one contains a "tree, park, and girl," while another contains a "tree, flower, and park." Are they similar or dissimilar? The answer is "somewhat." Traditional frameworks struggle with this nuance. In their IJCAI-18 paper, researchers from Tianjin University propose Relation Alignment Metric Learning (RAML), a framework that moves beyond binary labels to treat similarity as a continuous spectrum.

Rethinking Metric Learning Constraints

Most established metric learning algorithms, such as Large Margin Nearest Neighbor (LMNN) or Information-Theoretic Metric Learning (ITML), rely on discrete "doublet" or "triplet" constraints. While effective for simple classification tasks, this approach falters in more complex scenarios:

  1. Multi-label Learning: Images often have multiple tags. Two samples might share a subset of labels, making a binary "same/different" classification reductive.
  2. Label Distribution Learning: Instead of a single hard label, a sample may be represented by a probability distribution (e.g., a face that is 70% happy and 30% surprised).
  3. Continuous Values: In tasks where targets are real numbers, binary logic is mathematically impossible to apply directly.
Comparison of metric learning scenarios: (a) Single-label, (b) Multi-label, and (c) Label distribution learning.

The RAML Framework: Metric Learning as Regression

The core innovation of RAML is Relation Alignment. The authors argue that the distance between two samples in the feature space should be strictly consistent with their "difference degree" in the label (decision) space. By adopting this view, they reformulate metric learning as a continuous kernel regression problem.

Technical Implementation

Instead of complex, specialized optimization loops, RAML leverages standard regression tools:

  • The Objective: The model minimizes the discrepancy between the learned feature distance $f(x_i, x_j)$ and the ground-truth label difference $g(y_i, y_j)$.
  • The Kernel Trick: The researchers introduced a 2-degree polynomial kernel specifically designed for sample pairs. This allows the use of powerful solvers like Support Vector Regression (SVR) and Kernel Ridge Regression (KRR) to learn the underlying Mahalanobis distance matrix.
  • Ensuring Validity: To be a valid distance metric, the learned matrix must be Positive Semi-Definite (PSD). RAML employs Singular Value Decomposition (SVD) as a post-processing step to project the regression output back into a valid PSD space.

Experimental Validation

The authors tested RAML across three distinct learning domains to demonstrate its versatility and robustness:

  • Single-label Classification: On the MNIST dataset, RAML-KRR achieved 90.87% accuracy, significantly outperforming ITML (86.95%) and LMNN (87.21%).
  • Multi-label Classification: RAML consistently beat the standard MLKNN baseline across metrics like Hamming Loss and Ranking Loss on the Emotion and Corel800 datasets.
  • Label Distribution Learning: On the Nature Scene dataset, RAML improved the "Intersection Similarity" from 0.55 to 0.57, proving it learns a more discriminative metric for complex distributions.

Key Insights and Future Directions

RAML's primary contribution is the realization that with the correct kernel, distance learning becomes a value prediction problem. This allows metric learning to benefit from decades of regression research. Furthermore, the authors provide a theoretical proof that the generalization error bound of RAML is independent of feature dimensionality, making it highly suitable for high-dimensional data like images or text.

While powerful, the framework leaves room for future optimization. Currently, the PSD constraint is enforced after regression; integrating this constraint directly into the optimization loop could further enhance performance. Additionally, identifying the mathematically optimal relation function $g(y_i, y_j)$ for specific tasks remains an open area for exploration.

Summary updated

Abstract

Most existing metric learning methods focus on learning a similarity or distance measure relying on similar and dissimilar relations between sample pairs. However, pairs of samples cannot be simply identified as similar or dissimilar in many real-world applications, e.g., multi-label learning, label distribution learning or tasks with continuous decision values. To this end, in this paper we propose a novel relation alignment metric learning (RAML) formulation to handle the metric learning problem in those scenarios. Since the relation of two samples can be measured by the difference degree of the decision values, motivated by the consistency of the sample relations in the feature space and decision space, our proposed RAML utilizes the sample relations in the decision space to guide the metric learning in the feature space. Specifically, our RAML method formulates metric learning as a kernel regression problem, which can be efficiently optimized by the standard regression solvers. We carry out several experiments on the single-label classification, multi-label classification, and label distribution learning tasks, to demonstrate that our method achieves favorable performance against the state-of-the-art methods.
BibTeX
@inproceedings{zhu2018beyond,
  author = {Pengfei Zhu and Ren Qi and Qinghua Hu and Qilong Wang and Changqing Zhang and Liu Yang},
  title = {{Beyond Similar and Dissimilar Relations : A Kernel Regression Formulation for Metric Learning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/450},
}
Figure