Metric Learning With HORDE: High-Order Regularizer for Deep Embeddings

Pierre Jacob, David Picard, Aymeric Histace, Edouard KleinICCV 2019 · OpenReview

Deep Metric Learning (DML) aims to map images into an embedding space where semantic similarity corresponds to geometric proximity. While standard approaches have achieved significant success, they often rely on Global Average Pooling (GAP) to aggregate deep features. This paper identifies a fundamental "scattering problem" in this aggregation and proposes HORDE (High-Order Regularizer for Deep Embeddings) to address it.

The Scattering Problem in Deep Metric Learning

Most modern DML architectures use GAP to collapse a grid of deep features (e.g., $7 \times 7 \times 512$) into a single representative vector. While the average of these features may be discriminative, the individual features themselves are often widely dispersed across the feature space. This lack of localization makes the resulting embeddings fragile. For instance, if an object is partially occluded, the network only samples a subset of these scattered features. The mean of this subset can shift drastically from the global mean, leading to retrieval failures.

The HORDE Framework

HORDE introduces a distribution-aware regularization that moves beyond first-order statistics (the mean). By aligning high-order moments—such as variance, skewness, and kurtosis—of feature distributions, HORDE ensures that deep features are not just "correct on average" but are tightly packed and well-behaved as a whole distribution.

The HORDE architecture integrates a cascaded structure to learn informative high-order components alongside standard DML losses.

The architecture, shown above, utilizes a cascaded structure with $1 \times 1$ convolutions and Hadamard products to efficiently compute these high-order moments. To overcome the "curse of dimensionality" associated with high-order statistics, the authors employ the Random Maclaurin (RM) algorithm for efficient approximation. This allows the model to learn which high-order components are most informative for the task.

Robustness to Feature Scattering

The primary benefit of HORDE is the creation of more robust embeddings. The authors demonstrate this by simulating heavy occlusion—sampling only 1/6th of the available deep features during inference.

t-SNE visualizations of embedding spaces. (a) Standard features. (b) Standard features under 1/6th sampling (scattering problem). (c) HORDE features under 1/6th sampling (robustness).

As seen in the visualization, a standard model's embedding space (b) becomes disorganized when features are subsampled. In contrast, a model trained with HORDE (c) maintains a perfectly organized space because its features were "tightly packed" during the training process. Mathematically, HORDE acts as a lower bound for the Wasserstein distance and an upper bound for Maximum Mean Discrepancy (MMD), providing a solid theoretical foundation for this observed stability.

Experimental Results

HORDE was evaluated on four major image retrieval benchmarks: CUB-200-2011, Cars-196, Stanford Online Products (SOP), and In-Shop Clothes Retrieval. It consistently improved performance when added to various baseline losses (Triplet, Contrastive, Binomial Deviance).

  • State-of-the-Art Performance: On CUB-200-2011, HORDE achieved a Recall@1 of 63.9%.
  • Large-Scale Scalability: On the SOP dataset, adding HORDE to a Binomial Deviance baseline resulted in a significant jump in Recall@1 from 67.4% to 72.6%.
  • Efficiency: The cascaded architecture adds minimal overhead during training and can be optionally discarded at inference time if maximum speed is required, while still retaining the benefits of the regularized feature space.

Conclusion

HORDE addresses a critical but often overlooked aspect of deep metric learning: the distribution of local features. By enforcing high-order moment alignment, it produces embeddings that are significantly more robust to variations like occlusion and background noise. Its ability to consistently boost performance across diverse datasets makes it a powerful tool for modern visual search and retrieval tasks.

Summary updated

Abstract

Learning an effective similarity measure between image representations is key to the success of recent advances in visual search tasks (e.g. verification or zero-shot learning). Although the metric learning part is well addressed, this metric is usually computed over the average of the extracted deep features. This representation is then trained to be discriminative. However, these deep features tend to be scattered across the feature space. Consequently, the representations are not robust to outliers, object occlusions, background variations, etc. In this paper, we tackle this scattering problem with a distribution-aware regularization named HORDE. This regularizer enforces visually-close images to have deep features with the same distribution which are well localized in the feature space. We provide a theoretical analysis supporting this regularization effect. We also show the effectiveness of our approach by obtaining state-of-the-art results on 4 well-known datasets (Cub-200-2011, Cars-196, Stanford Online Products and Inshop Clothes Retrieval).
BibTeX
@inproceedings{jacob2019metric,
  author = {Pierre Jacob and David Picard and Aymeric Histace and Edouard Klein},
  title = {{Metric Learning With HORDE: High-Order Regularizer for Deep Embeddings}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2019},
  url = {https://openreview.net/forum?id=wJQZk61oeYp},
}
Figure