Densified Winner Take All (WTA) Hashing for Sparse Datasets

Beidi Chen, Anshumali Shrivastava
Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, PMLR R16:905-915, 2018.

Abstract

WTA (Winner Take All) hashing has been suc- cessfully applied in many large-scale vision applications. This hashing scheme was tai- lored to take advantage of the comparative rea- soning (or order based information), which showed significant accuracy improvements. In this paper, we identify a subtle issue with WTA, which grows with the sparsity of the datasets. This issue limits the discriminative power of WTA. We then propose a solution to this problem based on the idea of Densification which makes use of 2-universal hash functions in a novel way. Our experiments show that Densified WTA Hashing outperforms Vanilla WTA Hashing both in image retrieval and clas- sification tasks consistently and significantly.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR16-chen18b, title = {Densified Winner Take All ({WTA}) Hashing for Sparse Datasets}, author = {Chen, Beidi and Shrivastava, Anshumali}, booktitle = {Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence}, pages = {905--915}, year = {2018}, editor = {Globerson, Amir and Silva, Ricardo}, volume = {R16}, series = {Proceedings of Machine Learning Research}, month = {06--10 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r16/main/assets/chen18b/chen18b.pdf}, url = {https://proceedings.mlr.press/r16/chen18b.html}, abstract = {WTA (Winner Take All) hashing has been suc- cessfully applied in many large-scale vision applications. This hashing scheme was tai- lored to take advantage of the comparative rea- soning (or order based information), which showed significant accuracy improvements. In this paper, we identify a subtle issue with WTA, which grows with the sparsity of the datasets. This issue limits the discriminative power of WTA. We then propose a solution to this problem based on the idea of Densification which makes use of 2-universal hash functions in a novel way. Our experiments show that Densified WTA Hashing outperforms Vanilla WTA Hashing both in image retrieval and clas- sification tasks consistently and significantly.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Densified Winner Take All (WTA) Hashing for Sparse Datasets %A Beidi Chen %A Anshumali Shrivastava %B Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2018 %E Amir Globerson %E Ricardo Silva %F pmlr-vR16-chen18b %I PMLR %P 905--915 %U https://proceedings.mlr.press/r16/chen18b.html %V R16 %X WTA (Winner Take All) hashing has been suc- cessfully applied in many large-scale vision applications. This hashing scheme was tai- lored to take advantage of the comparative rea- soning (or order based information), which showed significant accuracy improvements. In this paper, we identify a subtle issue with WTA, which grows with the sparsity of the datasets. This issue limits the discriminative power of WTA. We then propose a solution to this problem based on the idea of Densification which makes use of 2-universal hash functions in a novel way. Our experiments show that Densified WTA Hashing outperforms Vanilla WTA Hashing both in image retrieval and clas- sification tasks consistently and significantly. %Z Reissued by PMLR on 04 October 2026.
APA
Chen, B. & Shrivastava, A.. (2018). Densified Winner Take All (WTA) Hashing for Sparse Datasets. Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R16:905-915 Available from https://proceedings.mlr.press/r16/chen18b.html. Reissued by PMLR on 04 October 2026.

Related Material