Hashing as Tie-Aware Learning to Rank
This work addresses retrieval accuracy issues in hashing for applications like image search, though it is incremental as it builds on existing learning-to-rank and hashing methods.
The paper tackled the problem of tied rankings in hashing for nearest neighbor retrieval by proposing tie-aware versions of ranking metrics like AP and NDCG, and optimizing them with continuous relaxations and deep neural networks, achieving new state-of-the-art results in image retrieval benchmarks.
Hashing, or learning binary embeddings of data, is frequently used in nearest neighbor retrieval. In this paper, we develop learning to rank formulations for hashing, aimed at directly optimizing ranking-based evaluation metrics such as Average Precision (AP) and Normalized Discounted Cumulative Gain (NDCG). We first observe that the integer-valued Hamming distance often leads to tied rankings, and propose to use tie-aware versions of AP and NDCG to evaluate hashing for retrieval. Then, to optimize tie-aware ranking metrics, we derive their continuous relaxations, and perform gradient-based optimization with deep neural networks. Our results establish the new state-of-the-art for image retrieval by Hamming ranking in common benchmarks.