Introduction
Winner Take All (WTA) hashing has emerged as a powerful technique for Locality Sensitive Hashing (LSH), particularly effective at capturing relative rankings in high-dimensional data. However, a significant limitation arises when applying WTA to sparse datasets, such as those common in natural language processing or computer vision using Bag-of-Words (BoW) representations. In these scenarios, random subsets of features often contain only zeros, resulting in "empty bins." Vanilla WTA treats these empty bins as matches, leading to spurious collisions that degrade the discriminative power of the resulting hashes.
The Densified WTA (DWTA) Approach
To address the empty bin problem, this paper introduces Densified WTA (DWTA). Instead of allowing empty bins to produce uninformative collisions, DWTA employs a deterministic "borrowing" strategy to fill these gaps with discriminative information.
The process involves four key steps:
- Standard WTA Hashing: Initial hashes are generated by identifying the index of the maximum value in random feature subsets.
- Detection of Empty Bins: Subsets where all sampled features are zero are identified.
- Information Borrowing: For each empty bin, a 2-universal hash function is used to find a non-empty "neighboring" bin.
- Reassignment with Offset: The value from the non-empty neighbor is reassigned to the empty bin, modified by a unique offset ($C$) to maintain the uniqueness of the feature representation.
This densification ensures that every bit in the final hash fingerprint contributes to the representation of the data's structure, preserving the locality-sensitive properties essential for efficient retrieval.
Experimental Evaluation
The efficacy of DWTA was evaluated using three standard computer vision benchmarks: VOC2010, LabelMe-12-50k, and MSRc. Images were converted into Bag-of-Words representations with varying dictionary sizes (1,000 to 10,000) to simulate different levels of sparsity, reaching up to 92% zeros in some cases.
Results and Performance
DWTA consistently outperformed vanilla WTA in image retrieval tasks across all tested datasets. The performance gap becomes increasingly pronounced as the sparsity of the data increases, demonstrating that DWTA effectively mitigates the noise introduced by empty bins.
Beyond retrieval accuracy, DWTA showed significant gains in classification tasks using linear SVMs. For example, on the VOC2010 dataset with 10,000 BoW features, DWTA maintained high accuracy while vanilla WTA's performance plateaued. Furthermore, the computational efficiency of DWTA is noteworthy; it is approximately 200 times faster than Sparse Random Projection (SRP). On the VOC2010 dataset, DWTA computation took 0.032ms compared to 8.578ms for SRP, offering a high-accuracy solution with minimal overhead.
Conclusion
Densified WTA hashing provides a robust solution for the challenges posed by high-dimensional sparse data. By transforming uninformative empty bins into discriminative features through a clever borrowing mechanism, DWTA significantly improves retrieval precision and classification accuracy while maintaining the high speed characteristic of WTA hashing. Future research may explore the application of this technique to other sparse domains, such as recommendation systems or graph analytics.
Summary updated