Source-linked AI summary
Learning with Average Precision: Training Image Retrieval with a Listwise Loss
Jerome Revaud, Jon Almazan, Rafael Sampaio de Rezende, Cesar Roberto de Souza
TL;DR
Existing retrieval losses optimize upper bounds instead of mAP and depend on engineering heuristics such as pre-training and hard-negative mining. This paper directly optimizes mAP with a listwise, histogram-binning loss and a scalable training scheme, achieving state-of-the-art results on multiple benchmarks. The reported benefits include reduced reliance on such heuristics and improved coding effort, training budget, and performance.
Problem
Existing ranking losses are not guaranteed to optimize mAP and often require complicated heuristics, including special pre-training and hard-negative mining.
Method
The paper uses a listwise loss with differentiable histogram binning to optimize mAP over large image batches, supported by a multistaged optimization scheme.
Results
The method achieves state-of-the-art results on multiple retrieval benchmarks.
Takeaways & Limitations
The findings support optimizing the target retrieval metric directly and reduce reliance on expensive sample mining and careful pre-training.
Takeaways & Limitations
Some comparison metrics are not exactly comparable because competing results use different training sets or whitening and pooling mechanisms.
Abstract
from arXiv · showhide
Image retrieval can be formulated as a ranking problem where the goal is to order database images by decreasing similarity to the query. Recent deep models for image retrieval have outperformed traditional methods by leveraging ranking-tailored loss functions, but important theoretical and practical problems remain. First, rather than directly optimizing the global ranking, they minimize an upper-bound on the essential loss, which does not necessarily result in an optimal mean average precision (mAP). Second, these methods require significant engineering efforts to work well, e.g. special pre-training and hard-negative mining. In this paper we propose instead to directly optimize the global mAP by leveraging recent advances in listwise loss formulations. Using a histogram binning approximation, the AP can be differentiated and thus employed to end-to-end learning. Compared to existing losses, the proposed method considers thousands of images simultaneously at each iteration and eliminates the need for ad hoc tricks. It also establishes a new state of the art on many standard retrieval benchmarks. Models and evaluation scripts have been made available at https://europe.naverlabs.com/Deep-Image-Retrieval/
1. Introduction
Image retrieval is treated as a ranking problem, but prevailing local ranking losses do not directly optimize mAP and often require complicated heuristics. The paper proposes a listwise loss that directly optimizes mAP over large image sets and reports state-of-the-art performance.
- Image retrieval ranks database images by similarity to a query, with applications including item identification and personal-photo organization.
- Existing ranking losses optimize upper bounds rather than mAP itself, providing no guarantee of optimal retrieval performance.They also rely on pre-training, combined losses, and hard-negative mining, which add hyperparameters and implementation complexity.
- The proposed listwise loss directly optimizes mAP by jointly ranking thousands of images instead of updating from only a few examples.It uses differentiable histogram binning to replace the non-differentiable sorting operation in AP.
- The approach introduces an optimization scheme for training with extremely large batches, arbitrary image resolutions, and network depths.This addresses the memory difficulties created by high-resolution images and deep retrieval networks.
- The authors report improved performance, coding effort, and training-budget benefits, including state-of-the-art results across multiple benchmarks.
2. Related work
Prior image-retrieval systems evolved from handcrafted local descriptors to CNN-based global representations trained with local ranking losses. The paper positions listwise AP optimization as a direct alternative that addresses both metric alignment and the practical costs of mining and large-scale training.
- Early retrieval methods used local patch descriptors aggregated into image-level signatures, while CNNs later became a strong alternative.Networks were subsequently trained specifically for retrieval using ranking objectives rather than classification alone.
- Pairwise and tuplewise losses sample limited image sets, repeatedly mining difficult examples before computing gradients.These local losses require heuristics such as classification pre-training, multiple losses, and hard-negative mining.
- Listwise losses optimize the ranking of a variable, potentially large, number of examples jointly through differentiable histogram approximations to mAP.
- The paper proposes a stable, straightforward AP-loss formulation for image retrieval, extending beyond prior patch-matching and hashing applications.The target setting includes high-resolution images, clutter, viewpoint changes, and deeper networks.
- Direct mAP optimization creates memory challenges because image-retrieval training combines high-resolution inputs with substantially larger networks.The paper motivates multistage backpropagation methods to make this training feasible.
3. Method
The method directly optimizes a differentiable approximation of average precision using listwise soft histogram binning, while a multistaged procedure makes large-batch, high-resolution training feasible without approximating the loss.
- Definitions: For each query, image similarities are ranked against database images and evaluated using binary relevance labels.Embeddings are L2-normalized, so cosine similarity is computed through their inner product before sorting database images in decreasing order.
- Learning with average precision: The training objective directly targets mAP by replacing nondifferentiable ranking assignments with differentiable soft histogram binning.The soft assignment approaches hard bin indicators as the number of bins increases and enables gradients with respect to similarity scores.
- Learning with average precision: The quantized AP computes precision and incremental recall at histogram bins rather than at every rank, then combines them into a smooth AP approximation.Bins partition the similarity interval, while triangular kernels softly assign similarity values to neighboring bins.
- Training procedure: The batch loss averages quantized AP over all images treated as queries, with L(D, Y ) = 1 − mAPQ(D, Y ).Each query compares its descriptor with all other batch descriptors, and relevance is determined by matching class labels.
- Training for high-resolution images: A three-stage backpropagation scheme computes all descriptors and the compact loss gradient first, then recomputes descriptors image by image to continue backpropagation.This avoids storing intermediary tensors for the full batch and supports arbitrary network depth, image resolution, and batch size without approximating the loss.
4. Experimental results
Experiments show that the proposed mAPQ loss benefits from large batches and class balancing, remains stable across quantization choices, outperforms tie-aware and triplet alternatives, and achieves strong benchmark performance with less engineering.
- Datasets: The experiments use Landmarks-clean for training and evaluate on the revised Oxford and Paris retrieval benchmarks under Easy, Medium, and Hard protocols.Landmarks-clean contains 42,410 images across 586 landmarks; ROxford and RParis contain 4,993 and 6,322 database images, respectively.
- Implementation details and parameter study: B = 4096 is used subsequently because larger batches improve results, while performance saturates beyond 4096 and training slows substantially.The batch-size study identifies large batches as beneficial but finds diminishing returns beyond the selected batch size.
- Implementation details and parameter study: Class weighting improves mAP by around +2% by counterbalancing dataset classes that are overrepresented within batches.Sampling classes rather than images has little effect, whereas weighting classes equally within each batch improves performance.
- Ceteris paribus analysis: mAPQ consistently outperforms the simplified tie-aware mAPT formulation by a small but significant margin, so mAPQ is used thereafter.The authors attribute this difference possibly to approximations in practical tie-aware AP implementations.
- Implementation details and parameter study: M = 20 quantization bins is used because varying M has little impact on performance.The quantization-bin study covers the medium RParis and ROxford benchmarks.
- Ceteris paribus analysis: Increasing triplet-loss batches does not improve performance, indicating mAPQ’s advantage is not solely due to processing more images per update.The comparison uses triplet loss with hard-negative mining and contrasts TL-1024’s 3,072 images per update with mAPQ’s batch size of 4,096.
- Comparison with the state of the art: The model outperforms the state of the art by 1% to 5% on most datasets and protocols, including more than four points on hard ROxford and RParis.It uses single-scale testing and ImageNet initialization without special pre-training; training from scratch takes a few hours on one P40 GPU.
- Comparison with the state of the art: With query expansion, the model outperforms other query-expansion methods in 6 of 8 protocols and remains competitive with a local-descriptor method.It also outperforms that method on ROxford and RParis without added distractors despite using global descriptors without geometric verification.
5. Conclusion
The paper applies a listwise ranking loss that directly optimizes a differentiable relaxation of mAP for image retrieval, avoiding costly sample mining and specialized pre-training while achieving state-of-the-art results across multiple benchmarks.
- The proposed mAPQ loss directly optimizes a differentiable relaxation of mean average precision for image retrieval.It applies a listwise ranking loss to the retrieval task.
- mAPQ avoids expensive image-sample mining and careful pre-training required by standard retrieval losses.
- A multistaged optimization scheme enables training on high-resolution images with arbitrary batch sizes.
- The approach achieves state-of-the-art results on multiple image-retrieval benchmarks.
- The method supports learning from ranked lists of arbitrary size, encouraging exploration beyond instance-level image retrieval.