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.
This behavior leads to two major issues:
- 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.
- 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.
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