Mean Local Group Average Precision (mLGAP): A New Performance Metric for Hashing-based Retrieval

Pak Lun Kevin Ding, Yikang Li, Baoxin LiarXiv 2018 · arXiv

Abstract

In large-scale image retrieval, hashing-based systems are evaluated primarily using Mean Average Precision (mAP). However, mAP focuses solely on class-level accuracy, inadvertently encouraging models to collapse all images of the same class into a single hash code. This "collision" phenomenon destroys fine-grained visual similarity and turns retrieval systems into simple classifiers. This paper introduces Mean Local Group Average Precision (mLGAP), a novel metric that reconciles retrieval accuracy with the uniform utilization of the hash space. By penalizing code collisions, mLGAP ensures that models preserve intra-class variance, leading to more semantically rich and visually consistent retrieval results.

The Flaw in Standard mAP

In large-scale image retrieval, hashing compresses high-dimensional images into compact binary codes to enable rapid search via Hamming distances. The dominant evaluation metric, Mean Average Precision (mAP), measures whether retrieved items belong to the correct class.

However, the authors identify a critical flaw: supervised hashing models can "game" mAP by mapping all images of a specific class to the exact same binary code. While this maximizes class-level precision, it results in a high collision rate and poor utilization of the available hash space.

Figure 1: Histograms of hash code distributions across various hashing methods. Many state-of-the-art models, such as DSH, exhibit highly non-uniform distributions with massive spikes, indicating that most images are being mapped to a very small subset of available codes.

This behavior leads to two major issues:

  1. Loss of Ranking: If all "cat" images share the same code, a query for a specific type of cat returns all cats in a random order, losing fine-grained similarity.
  2. Evaluation Instability: Massive collisions result in identical Hamming distances, making mAP scores highly sensitive to arbitrary sorting orders.

Methodology: Introducing mLGAP

To solve this, the authors propose mLGAP, a metric that reconciles retrieval accuracy with hash code dispersion.

The mLGAP Metric

mLGAP modifies standard precision by introducing a penalty function, $\phi$. For a given query and a specific Hamming radius, the metric calculates the precision and multiplies it by $\phi$. This penalty function measures how uniformly the retrieved hash codes are distributed (dispersion) within that Hamming ball.

Figure 6: (a) Illustration of hash code collisions where multiple images share identical or near-identical binary strings. (b) A histogram showing the resulting non-uniform distribution. mLGAP uses this information to penalize models that fail to utilize the hash space effectively.

If all retrieved items are crammed into one or two hash codes, $\phi$ approaches 0. If they are uniformly spread out, $\phi$ approaches 1. This ensures that the system is rewarded for maintaining "room" in the hash space to preserve subtle visual or semantic distinctions between images of the same class.

Dispersion-Aware Objective Function

To demonstrate the value of dispersed hash codes, the authors modified the objective function of the Deep Supervised Hashing (DSH) model. Instead of using an L2 norm that forces same-class images to have identical codes, they used an L1 norm and introduced "buffer zones" (margin parameters). This encourages same-class images to be close in Hamming space, but not identical, preserving intra-class variance.

Experimental Results

The researchers evaluated their approach on the CIFAR-10 and CIFAR-100 datasets. CIFAR-100 was particularly useful for testing hierarchical buffer zones, ensuring that variance within a specific class is smaller than variance within its superclass.

Quantitative Shift

When training a 12-bit DSH model with the new dispersion-aware objective, the standard mAP score plummeted from 0.6012 to 0.3008. However, the proposed mLGAP score increased from 0.2633 to 0.2796. This discrepancy highlights the core finding: mAP penalizes models that maintain intra-class diversity, whereas mLGAP correctly rewards them for preserving semantic structure.

Qualitative Improvements

Visual inspections of retrieval results confirmed that the dispersion-optimized model successfully grouped visually similar images (e.g., specific angles or features of an object) at low Hamming distances. Unlike the baseline, which returned a random assortment of class members, the mLGAP-optimized system maintained fine-grained visual consistency.

Limitations and Conclusion

While mLGAP addresses the collision problem, the modified objective function used for testing relies on several heuristically set margin parameters to define the buffer zones. A strictly principled method for optimizing these hyperparameters remains an area for future work.

In conclusion, the pursuit of high mAP scores has led the hashing community toward models that act as simple classifiers rather than similarity search engines. mLGAP provides a necessary correction, forcing models to balance accuracy with hash space efficiency. Future research in hashing-based retrieval should adopt dispersion-aware metrics to ensure that binary codes remain semantically meaningful and practically useful for large-scale similarity search.

Summary updated

Abstract

The research on hashing techniques for visual data is gaining increased attention in recent years due to the need for compact representations supporting efficient search/retrieval in large-scale databases such as online images. Among many possibilities, Mean Average Precision(mAP) has emerged as the dominant performance metric for hashing-based retrieval. One glaring shortcoming of mAP is its inability in balancing retrieval accuracy and utilization of hash codes: pushing a system to attain higher mAP will inevitably lead to poorer utilization of the hash codes. Poor utilization of the hash codes hinders good retrieval because of increased collision of samples in the hash space. This means that a model giving a higher mAP values does not necessarily do a better job in retrieval. In this paper, we introduce a new metric named Mean Local Group Average Precision (mLGAP) for better evaluation of the performance of hashing-based retrieval. The new metric provides a retrieval performance measure that also reconciles the utilization of hash codes, leading to a more practically meaningful performance metric than conventional ones like mAP. To this end, we start by mathematical analysis of the deficiencies of mAP for hashing-based retrieval. We then propose mLGAP and show why it is more appropriate for hashing-based retrieval. Experiments on image retrieval are used to demonstrate the effectiveness of the proposed metric.
BibTeX
@misc{ding2018mean,
  author = {Pak Lun Kevin Ding and Yikang Li and Baoxin Li},
  title = {{Mean Local Group Average Precision (mLGAP): A New Performance Metric for Hashing-based Retrieval}},
  year = {2018},
  eprint = {1811.09763},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1811.09763},
}
Figure