Comparing apples to apples in the evaluation of binary coding methods

Mohammad Rastegari, Shobeir Fakhraei, Jonghyun Choi, David W. Jacobs, Larry S. DavisarXiv 2014 · arXiv

TL;DR

This paper highlights critical methodological flaws in evaluating binary coding methods for nearest neighbor search, showing that seemingly minor differences in data normalization can drastically alter performance comparisons. The authors propose standardized evaluation protocols and introduce a novel "Predictable Hashing" method that leverages data correlations, often outperforming existing state-of-the-art techniques.

What Problem Does This Paper Address?

Efficiently finding similar items in massive datasets is a cornerstone of many modern applications, from image retrieval to recommendation systems. Binary codes offer a compact and computationally efficient way to represent data for similarity search, as they allow for fast comparisons using Hamming distance. However, the field has struggled with a consistent and fair evaluation of different binary coding methods. Many existing papers compare methods without accounting for how the original data is preprocessed or what type of similarity (e.g., Euclidean distance vs. cosine similarity) each method is designed to preserve. This leads to conflicting results and an unclear understanding of which methods are truly superior. The authors aim to establish a fair comparison framework and propose a new method that addresses the limitations of current approaches.

Methods

The core contribution of this paper is a methodological framework for fair comparison. They identify two key issues:

  • Preserving Cosine Similarity: Methods aiming to preserve cosine similarity in the binary space should normalize the original features to lie on a unit hypersphere. This ensures that angular differences (cosine similarity) are directly comparable to Euclidean distances in this normalized space.
  • Preserving Euclidean Distance: Methods aiming to preserve Euclidean distance can benefit from mapping data to a higher dimension by including a bias term in the binary mapping functions. This allows the method to capture correlations within the data more effectively.

Based on these insights, the authors propose Predictable Hashing (PH), a variation of Iterative Quantization (ITQ). PH incorporates a bias term into ITQ's hyperplane formulation, inspired by the concept of "predictability" where a bit value in a binary code can be predicted from its neighbors. This bias term allows the method to model data correlations, which is crucial for preserving Euclidean distance. They also explore using random perturbations in the optimization process to escape local minima.

Datasets

The authors evaluate their methods on three standard computer vision datasets:

  • ImageNet20K: A subset of ImageNet with 1000 categories, from which 20 images per category were selected (total 20K images). Visual features like BoW, SPHOG, GIST, and LBP were concatenated and reduced to 1000 dimensions using PCA.
  • 1MGist: Contains 1 million internet images with GIST features (960 dimensions).
  • SUN14K: A dataset for scene recognition, with 14K images. Visual features (19K dimensions) were used, with dimensionality reduced to 1K.

Key Insights and Ideas

  • "Apples to Apples" Comparison is Crucial: The paper strongly emphasizes that comparing binary coding methods without proper data normalization and understanding their underlying similarity preservation goals leads to misleading conclusions.
  • Normalization Matters: Mapping data to the unit hypersphere is essential for fair comparison when evaluating cosine similarity preservation.
  • Bias Term for Euclidean Distance: Including a bias term in binary mapping functions significantly improves performance for methods aiming to preserve Euclidean distance, especially for longer binary codes.
  • Data Correlation is Key: Unlike previous assumptions that uncorrelated bits are always optimal, the authors show that modeling data correlations is vital for effective Euclidean distance preservation.
  • Predictability as a Guiding Principle: The concept of predictable binary codes, where bit values are consistent among neighbors, provides a principled way to incorporate data structure into binary coding.

Key Results

  • Under the proposed fair comparison framework, ITQ consistently outperforms other methods when preserving cosine similarity, contrary to some prior claims.
  • For preserving Euclidean distance, LSH with a bias term (LSHbias) shows superior performance, especially with longer binary codes, often outperforming state-of-the-art data-driven methods.
  • The proposed Predictable Hashing (PH) method, which augments ITQ with a bias term, achieves significantly better performance than standard ITQ and often outperforms LSHbias, particularly for larger code lengths (256 and 512 bits).
  • The authors demonstrate that the "hard constraint" of uncorrelated bits in methods like SPH and ITQ can actually degrade performance, whereas modeling correlations (as done by PH and LSHbias) is beneficial.

Limitations and Future Work

  • Computational Cost: While PH shows improved accuracy, the paper doesn't extensively detail its computational complexity compared to other methods, especially for very large datasets.
  • Parameter Tuning: The effectiveness of PH relies on parameters like the bias term and the perturbation factor t. While t=0.9 was used, optimal tuning for different datasets might be explored further.
  • Unsupervised Focus: The paper focuses on unsupervised methods. Extending the predictability concept to supervised settings for tasks like classification could be a future direction.
  • Generalizability: While tested on image datasets, the applicability and performance of the proposed methods on other data modalities (e.g., text, audio) could be investigated.

Summary updated

Abstract

We discuss methodological issues related to the evaluation of unsupervised binary code construction methods for nearest neighbor search. These issues have been widely ignored in literature. These coding methods attempt to preserve either Euclidean distance or angular (cosine) distance in the binary embedding space. We explain why when comparing a method whose goal is preserving cosine similarity to one designed for preserving Euclidean distance, the original features should be normalized by mapping them to the unit hypersphere before learning the binary mapping functions. To compare a method whose goal is to preserves Euclidean distance to one that preserves cosine similarity, the original feature data must be mapped to a higher dimension by including a bias term in binary mapping functions. These conditions ensure the fair comparison between different binary code methods for the task of nearest neighbor search. Our experiments show under these conditions the very simple methods (e.g. LSH and ITQ) often outperform recent state-of-the-art methods (e.g. MDSH and OK-means).
BibTeX
@misc{rastegari2014comparing,
  author = {Mohammad Rastegari and Shobeir Fakhraei and Jonghyun Choi and David W. Jacobs and Larry S. Davis},
  title = {{Comparing apples to apples in the evaluation of binary coding methods}},
  year = {2014},
  eprint = {1405.1005},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1405.1005},
}
Figure