Binary embeddings with structured hashed projections

Anna Choromanska, Krzysztof Choromanski, Mariusz Bojarski, Tony Jebara, Sanjiv Kumar, Yann LeCun
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:344-353, 2016.

Abstract

We consider the hashing mechanism for constructing binary embeddings, that involves pseudo-random projections followed by nonlinear (sign function) mappings. The pseudo-random projection is described by a matrix, where not all entries are independent random variables but instead a fixed “budget of randomness” is distributed across the matrix. Such matrices can be edfficiently stored in sub-quadratic or even linear space, provide reduction in randomness usage (i.e. number of required random values), and very often lead to computational speed ups. We prove several theoretical results showing that projections via various structured matrices followed by nonlinear mappings accurately preserve the angular distance between input high-dimensional vectors. To the best of our knowledge, these results are the first that give theoretical ground for the use of general structured matrices in the nonlinear setting. We empirically verify our theoretical findings and show the dependence of learning via structured hashed projections on the performance of neural network as well as nearest neighbor classifier.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-choromanska16, title = {Binary embeddings with structured hashed projections}, author = {Choromanska, Anna and Choromanski, Krzysztof and Bojarski, Mariusz and Jebara, Tony and Kumar, Sanjiv and LeCun, Yann}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {344--353}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/choromanska16.pdf}, url = {https://proceedings.mlr.press/v48/choromanska16.html}, abstract = {We consider the hashing mechanism for constructing binary embeddings, that involves pseudo-random projections followed by nonlinear (sign function) mappings. The pseudo-random projection is described by a matrix, where not all entries are independent random variables but instead a fixed “budget of randomness” is distributed across the matrix. Such matrices can be edfficiently stored in sub-quadratic or even linear space, provide reduction in randomness usage (i.e. number of required random values), and very often lead to computational speed ups. We prove several theoretical results showing that projections via various structured matrices followed by nonlinear mappings accurately preserve the angular distance between input high-dimensional vectors. To the best of our knowledge, these results are the first that give theoretical ground for the use of general structured matrices in the nonlinear setting. We empirically verify our theoretical findings and show the dependence of learning via structured hashed projections on the performance of neural network as well as nearest neighbor classifier.} }
Endnote
%0 Conference Paper %T Binary embeddings with structured hashed projections %A Anna Choromanska %A Krzysztof Choromanski %A Mariusz Bojarski %A Tony Jebara %A Sanjiv Kumar %A Yann LeCun %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-choromanska16 %I PMLR %P 344--353 %U https://proceedings.mlr.press/v48/choromanska16.html %V 48 %X We consider the hashing mechanism for constructing binary embeddings, that involves pseudo-random projections followed by nonlinear (sign function) mappings. The pseudo-random projection is described by a matrix, where not all entries are independent random variables but instead a fixed “budget of randomness” is distributed across the matrix. Such matrices can be edfficiently stored in sub-quadratic or even linear space, provide reduction in randomness usage (i.e. number of required random values), and very often lead to computational speed ups. We prove several theoretical results showing that projections via various structured matrices followed by nonlinear mappings accurately preserve the angular distance between input high-dimensional vectors. To the best of our knowledge, these results are the first that give theoretical ground for the use of general structured matrices in the nonlinear setting. We empirically verify our theoretical findings and show the dependence of learning via structured hashed projections on the performance of neural network as well as nearest neighbor classifier.
RIS
TY - CPAPER TI - Binary embeddings with structured hashed projections AU - Anna Choromanska AU - Krzysztof Choromanski AU - Mariusz Bojarski AU - Tony Jebara AU - Sanjiv Kumar AU - Yann LeCun BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-choromanska16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 344 EP - 353 L1 - http://proceedings.mlr.press/v48/choromanska16.pdf UR - https://proceedings.mlr.press/v48/choromanska16.html AB - We consider the hashing mechanism for constructing binary embeddings, that involves pseudo-random projections followed by nonlinear (sign function) mappings. The pseudo-random projection is described by a matrix, where not all entries are independent random variables but instead a fixed “budget of randomness” is distributed across the matrix. Such matrices can be edfficiently stored in sub-quadratic or even linear space, provide reduction in randomness usage (i.e. number of required random values), and very often lead to computational speed ups. We prove several theoretical results showing that projections via various structured matrices followed by nonlinear mappings accurately preserve the angular distance between input high-dimensional vectors. To the best of our knowledge, these results are the first that give theoretical ground for the use of general structured matrices in the nonlinear setting. We empirically verify our theoretical findings and show the dependence of learning via structured hashed projections on the performance of neural network as well as nearest neighbor classifier. ER -
APA
Choromanska, A., Choromanski, K., Bojarski, M., Jebara, T., Kumar, S. & LeCun, Y.. (2016). Binary embeddings with structured hashed projections. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:344-353 Available from https://proceedings.mlr.press/v48/choromanska16.html.

Related Material