Source-linked AI summary
Learning Deep Embeddings with Histogram Loss
Evgeniya Ustinova, Victor Lempitsky
TL;DR
Deep embedding learning lacks a reliably effective, low-tuning loss despite widespread use across applications. The paper proposes Histogram loss, which compares positive and negative similarity distributions through differentiable one-dimensional histograms and reverse-order probability. It achieves competitive results across several datasets, outperforming other losses on two person re-identification datasets.
Problem
Learning deep embeddings remains difficult to optimize reliably, with existing approaches using diverse losses and optimization tricks.
Method
Histogram loss estimates positive and negative similarity distributions with one-dimensional histograms, then minimizes the probability of their incorrect ordering using piecewise-differentiable operations.
Results
The Histogram loss gives the best results on CUHK03 and Market-1501, comes close to the best loss on CUB-200-2011 and Online Products, and uniformly outperforms the triplet-based LSSS loss in the experiments.
Takeaways & Limitations
The loss provides an out-of-the-box approach that requires virtually no associated parameter tuning while incorporating information across many mini-batch quadruplets.
Takeaways & Limitations
Performance remains sensitive to the learning rate, and comparison results for another loss depend on its tuned parameter C.
Abstract
from arXiv · showhide
We suggest a loss for learning deep embeddings. The new loss does not introduce parameters that need to be tuned and results in very good embeddings across a range of datasets and problems. The loss is computed by estimating two distribution of similarities for positive (matching) and negative (non-matching) sample pairs, and then computing the probability of a positive pair to have a lower similarity score than a negative pair based on the estimated similarity distributions. We show that such operations can be performed in a simple and piecewise-differentiable manner using 1D histograms with soft assignment operations. This makes the proposed loss suitable for learning deep embeddings using stochastic optimization. In the experiments, the new loss performs favourably compared to recently proposed alternatives.
1 Introduction
Learning deep embeddings remains difficult to optimize reliably, motivating a loss that compares positive and negative similarity distributions while requiring little parameter tuning. The proposed histogram loss is differentiable enough for backpropagation and performs close to state of the art across varied datasets.
- Motivation: Deep embedding learning remains challenging because tuple-based objectives often require specialized losses and optimization strategies.Recent methods use pairs, triplets, or quadruplets alongside pretraining, auxiliary classification losses, or semi-hard triplet mining.
- Histogram loss: The proposed loss estimates one-dimensional similarity distributions separately for matching and non-matching pairs.It processes a batch by constructing positive and negative similarity distributions before comparing them.
- Histogram loss: The loss measures the probability that a randomly sampled positive pair has lower similarity than a randomly sampled negative pair.This probability is obtained from the negative distribution and the cumulative distribution function of the positive distribution.
- Optimization: The two histogram stages use piecewise-differentiable operations, allowing optimization with standard backpropagation.The histograms use linearly interpolated value-to-bin assignments.
- Evaluation: The number of histogram bins is the only associated tunable parameter, and experiments report favourable performance across four image datasets.The bin count can be set from batch size independently of the data, while results show low sensitivity to it.
2 Related work
Prior deep-embedding methods use classification, pairwise, triplet, and quadruplet objectives. These approaches differ in whether they optimize absolute similarities or relative ordering, and several introduce tuning or sampling complications.
- Overview: Recent embedding systems commonly use deep architectures, especially ConvNets, together with stochastic optimization.The related methods reviewed below use these architectures and optimization procedures.
- Classification losses: Classification losses use intermediate network representations trained for classification, often with post-hoc normalization or classification pretraining.Some methods additionally combine classification and embedding losses during fine-tuning.
- Pairwise losses: Pairwise losses score sampled training pairs independently and may use margins, double margins, log-sum-exp, or cross-entropy objectives.Their main difficulty is that margin parameters can be hard to tune.
- Triplet losses: Triplet losses emphasize relative ordering between positive and negative distances or similarities rather than their absolute values.An embedding can satisfy many applications when positive-pair similarities exceed negative-pair similarities.
- Quadruplet losses: Quadruplet losses compare positive and negative pairs that do not share a common point, extending the relative-comparison perspective of triplet losses.They provide less flexibility than triplet losses in the cited discussion.
3 Histogram loss
The histogram loss estimates positive- and negative-pair similarity distributions from normalized embeddings, then minimizes their overlap through a differentiable reverse-order probability. Its histogram formulation avoids exhaustive quadruplet comparisons while retaining optional margin extensions.
- Loss setup: The loss operates on L2-normalized embeddings and separates matching from non-matching pairs using their pairwise similarities.Positive and negative labels define the two sample sets used to estimate p+ and p−.
- Distribution estimation: Uniformly spaced one-dimensional histograms estimate the positive and negative similarity distributions, assigning each pair linearly to adjacent bins.The similarity range is bounded to [−1; +1], and the weights implement linear interpolation between neighboring histogram nodes.
- Reverse probability: The loss estimates the probability that a random negative pair has higher similarity than a random positive pair, using the positive distribution’s cumulative density function.This probability is the overlap or reverse-order quantity minimized by the method.
- Optimization: The histogram loss is differentiable with respect to pairwise similarities, allowing backpropagation through embedded points and the deep network.The stated derivatives support standard gradient-based optimization.
- Relation to quadruplet loss: Separating distribution estimation from reverse-probability computation reduces batch complexity from quartic for exhaustive pair-of-pairs sampling to quadratic.This provides a computational contrast with a purely non-parametric quadruplet-style estimate.
- Margin extension: A margin can be incorporated through a modified loss, but the experiments omit it because preliminary results show no benefit.The modification effectively enforces margin µ∆.
4 Experiments
The experiments compare Histogram loss with pairwise and triplet-based alternatives across four image datasets using Recall@K. Histogram loss performs best on both person re-identification datasets, while coming close to the best method on bird recognition and product search.
- Experimental setup: The evaluation compares pairwise and triplet losses on CUB-200-2011, Online Products, CUHK03, and Market-1501 using Recall@K.Recall@K measures the probability that the correct match appears among the first K gallery candidates sorted by similarity.
- Results: Histogram loss outperforms Binomial Deviance, LSSS, and Triplet losses on CUHK03 and Market-1501.On CUHK03, Histogram loss gives a 2.64% boost over Binomial Deviance with C = 10; on Market-1501, it outperforms Binomial Deviance for both tested C values.
- Practical considerations: The Histogram loss has no loss-specific parameters requiring tuning, although learning with it is sensitive to the learning rate.Its histogram-bin count can be set according to batch size independently of the data itself.
5 Conclusion
The Histogram loss offers a minimally tuned approach to learning deep embeddings and performs competitively across several datasets, including person re-identification.
- The Histogram loss has virtually no parameters that need to be tuned.Its only associated tunable parameter is the histogram bin count, which can be set according to batch size independently of the data.
- The loss incorporates information across a large number of quadruplets formed from mini-batch training samples.It implicitly takes into account all such quadruplets rather than relying on selected individual configurations.
- The Histogram loss produced competitive results across multiple datasets and outperformed other losses for person re-identification on CUHK03 and Market-1501.