Learning Similarity Metrics from Relative Comparisons

70 concepts53 papers1 proposal

When we ask humans to evaluate how similar two things are, we rarely think in absolute numbers. If you are asked to rate the visual similarity of two images on a scale from 1 to 10, or to provide an exact geometric distance between two abstract concepts, your response will likely be highly inconsistent. However, if you are shown three items and asked a relative question—"Is item A more similar to item B than to item C?"—your judgment becomes remarkably stable and robust.

This fundamental insight shifts the paradigm of similarity learning. Instead of training models using absolute class labels or rigid pairwise distances, relative similarity learning optimizes embedding spaces using ordinal comparisons, typically structured as triplets: an anchor $A$, a positive instance $B$, and a negative instance $C$.

The Limits of Absolute and Pairwise Labels

Traditional supervised metric learning relies heavily on absolute labels (e.g., classification categories) or binary pairwise constraints ("similar" versus "dissimilar"). While effective for coarse category-level separation, these frameworks struggle in complex, fine-grained, or highly subjective domains.

As noted by Glenn Fung et al. in Feature Selection and Kernel Design via Linear Programming, absolute labels are difficult for humans to provide consistently, whereas relative comparisons naturally capture complex data relationships without requiring explicit class definitions.

Furthermore, binary pairwise labels collapse the rich, continuous spectrum of similarity into a flat binary choice. They tell a model whether two items belong together, but not how much closer one item is compared to another. As a result, pairwise constraints fail to explicitly model the relative distances between multiple samples simultaneously, a limitation highlighted by Haomiao Liu et al. in Deep Supervised Hashing for Fast Image Retrieval.

The Geometry of the Triplet Margin

To capture the nuanced hierarchy of real-world data, relative similarity learning structures supervision around a triplet constraint:

$$D(x, x^+) + \alpha < D(x, x^-)$$

Where $x$ is the anchor, $x^+$ is a known similar (positive) example, $x^-$ is a dissimilar (negative) example, $D(\cdot, \cdot)$ is the distance metric, and $\alpha$ is a enforcement margin.

   Unoptimized Space                  Optimized Space (with Margin α)

        x^-                                      x^-
       /                                          |
      /                                           |
     x ------ x^+                                 |  > α
                                                  |
                                         x ------ x^+

Geometrically, this objective does not force the anchor and the positive instance to map to the exact same coordinate. Instead, it creates a dynamic, localized ranking. It continuously pulls the positive instance closer to the anchor while pushing the negative instance outside of a defined safety radius.

In Learning a Distance Metric from Relative Comparisons, Matthew Schultz et al. demonstrated that framing metric learning as a convex optimization problem based on these relative triplets allows models to capture qualitative user feedback and implicit preferences far more robustly than quantitative distance measurements. This geometric flexibility is what allows Jiang Wang et al. in Learning Fine-Grained Image Similarity with Deep Ranking to build embedding spaces sensitive to subtle, fine-grained visual differences that standard classification models completely ignore.

Scaling the Optimization

Early implementations of relative similarity learning faced severe scalability bottlenecks. Enforcing triplet constraints across an entire dataset typically required Semidefinite Programming (SDP), which becomes computationally prohibitive as the number of constraints grows cubically with the dataset size.

To circumvent this, researchers sought more efficient mathematical reformulations:

  1. Linear Programming Relaxation: Glenn Fung et al. leveraged the Diagonal Dominance Theorem in Feature Selection and Kernel Design via Linear Programming to transform the slow SDP optimization into a fast Linear Programming task that simultaneously performs feature selection.
  2. Eigenvector Decomposition: Chunhua Shen et al. introduced a scalable large-margin Mahalanobis distance framework in Scalable large-margin Mahalanobis distance metric learning that replaces expensive solvers with a specialized gradient descent requiring only a single principal eigenvector computation at each step.
  3. End-to-End Deep Learning: Modern architectures bypass traditional optimization solvers entirely by integrating the triplet loss directly into deep neural networks. As shown by Hanjiang Lai et al. in Simultaneous feature learning and hash coding with deep neural networks, optimizing features and similarity rankings simultaneously in a unified framework yields a much richer supervisory signal than decoupled pipelines.

Preserving Hierarchies in Discrete and Subjective Spaces

The power of relative similarity learning becomes especially apparent when mapping high-dimensional data into compact, discrete spaces (such as binary hash codes) or when modeling highly subjective human concepts.

Preserving Semantic Structure in Hashing

When compressing images into binary codes for ultra-fast retrieval, binary pairwise labels often fail because they force a rigid, flat categorization. In contrast, Xiaofang Wang et al. showed in Deep Supervised Hashing with Triplet Labels that optimizing a triplet-based likelihood function ensures that relative semantic hierarchies are preserved even within low-dimensional Hamming spaces. This allows cross-modal systems, such as the one proposed by Zhaojia Chen et al. in Triplet-Based Deep Hashing Network for Cross-Modal Retrieval, to bridge the semantic gap between entirely different modalities (like text and video) by focusing purely on relative ranking alignment.

Capturing Human Intuition

Because triplets mirror human cognitive processes, they serve as an ideal bridge for training models on subjective or abstract criteria. For instance, the authors of Image Aesthetic Assessment: An Experimental Survey highlight that pre-training models on relative aesthetic rankings between image pairs establishes a far more robust feature space for visual quality than attempting to predict absolute aesthetic scores directly.

Similarly, in the domain of algorithmic ethics, Hanchen Wang et al. demonstrated in An Empirical Study on Learning Fairness Metrics for COMPAS Data with Human Supervision that relative triplets can successfully capture highly inconsistent human intuitions about individual fairness—the principle that similar people should be treated similarly—outperforming rigid mathematical baselines.

Beyond the Triplet: Listwise and Partial Orderings

While triplets are powerful, evaluating data in isolated groups of three can occasionally miss global context or create redundant constraints. Modern extensions of this research direction generalize the triplet concept to even denser ranking structures.

Instead of breaking a search result list into independent triplets, Jun Wang 0006 et al. introduced listwise supervision in Learning Hash Codes with Listwise Supervision. By representing an entire sequence of ordered search results simultaneously, the model receives a dense, globally consistent hierarchical signal that preserves the ground-truth similarity structure much more accurately than isolated classifications.

Triplet Supervision:   [Anchor] ---> (Positive) vs (Negative)
Listwise Supervision:  [Query]  ---> [Rank 1] -> [Rank 2] -> [Rank 3] -> [Rank 4]

In the unsupervised domain, Miguel Ángel Bautista pushed this boundary further in Deep Unsupervised Similarity Learning Using Partially Ordered Sets by utilizing Partially Ordered Sets (posets). This framework allows a single unlabeled sample to be related to multiple data clusters simultaneously. By moving from local triplets to multi-sample partial orderings, the model achieves global consistency and captures fine-grained relationships without requiring any manual human labeling.

Ultimately, relative similarity learning works because it aligns the mathematical optimization objective with the ordinal nature of both human perception and downstream retrieval tasks. By focusing on the ordering of neighbors rather than their absolute coordinates, it builds representation spaces that are inherently more flexible, scalable, and faithful to the underlying structure of complex data.

Key Foundational Work

Feature Selection and Kernel Design via Linear Programming (2007) — contributed 3 concept elements to this direction.
Learning a Distance Metric from Relative Comparisons (2003) — contributed 1 concept elements to this direction.
Semi-definite Manifold Alignment (2007) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_relative_similarity_learning_02245c28,
  title = {relative similarity learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/relative-similarity-learning/rdr_02245c28a8f44f1aabb5e8d3dbdd4c69},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_relative_similarity_learning_02245c28_v1,
  title = {relative similarity learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/relative-similarity-learning/rdr_02245c28a8f44f1aabb5e8d3dbdd4c69/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake