Geometry Aware Mappings for High Dimensional Sparse Factors

Avradeep Bhowmik, Nathan Liu, Erheng Zhong, Badri Bhaskar, Suju Rajan
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, PMLR 51:455-463, 2016.

Abstract

While matrix factorisation models are ubiquitous in large scale recommendation and search, real time application of such models requires inner product computations over an intractably large set of item factors. In this manuscript we present a novel framework that exploits structural properties of sparse vectors, using the inverted index representation, to significantly reduce the run time computational cost of factorisation models. We develop techniques that use geometry aware permutation maps on a tessellated unit sphere to obtain high dimensional sparse embeddings for latent factors with sparsity patterns related to angular closeness of the original latent factors. We also design several efficient and deterministic realisations within this framework and demonstrate with experiments that our techniques lead to faster run time operation with minimal loss of accuracy.

Cite this Paper

BibTeX
@InProceedings{pmlr-v51-bhowmik16, title = {Geometry Aware Mappings for High Dimensional Sparse Factors}, author = {Bhowmik, Avradeep and Liu, Nathan and Zhong, Erheng and Bhaskar, Badri and Rajan, Suju}, booktitle = {Proceedings of the 19th International Conference on Artificial Intelligence and Statistics}, pages = {455--463}, year = {2016}, editor = {Gretton, Arthur and Robert, Christian C.}, volume = {51}, series = {Proceedings of Machine Learning Research}, address = {Cadiz, Spain}, month = {09--11 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v51/bhowmik16.pdf}, url = {https://proceedings.mlr.press/v51/bhowmik16.html}, abstract = {While matrix factorisation models are ubiquitous in large scale recommendation and search, real time application of such models requires inner product computations over an intractably large set of item factors. In this manuscript we present a novel framework that exploits structural properties of sparse vectors, using the inverted index representation, to significantly reduce the run time computational cost of factorisation models. We develop techniques that use geometry aware permutation maps on a tessellated unit sphere to obtain high dimensional sparse embeddings for latent factors with sparsity patterns related to angular closeness of the original latent factors. We also design several efficient and deterministic realisations within this framework and demonstrate with experiments that our techniques lead to faster run time operation with minimal loss of accuracy.} }
Endnote
%0 Conference Paper %T Geometry Aware Mappings for High Dimensional Sparse Factors %A Avradeep Bhowmik %A Nathan Liu %A Erheng Zhong %A Badri Bhaskar %A Suju Rajan %B Proceedings of the 19th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2016 %E Arthur Gretton %E Christian C. Robert %F pmlr-v51-bhowmik16 %I PMLR %P 455--463 %U https://proceedings.mlr.press/v51/bhowmik16.html %V 51 %X While matrix factorisation models are ubiquitous in large scale recommendation and search, real time application of such models requires inner product computations over an intractably large set of item factors. In this manuscript we present a novel framework that exploits structural properties of sparse vectors, using the inverted index representation, to significantly reduce the run time computational cost of factorisation models. We develop techniques that use geometry aware permutation maps on a tessellated unit sphere to obtain high dimensional sparse embeddings for latent factors with sparsity patterns related to angular closeness of the original latent factors. We also design several efficient and deterministic realisations within this framework and demonstrate with experiments that our techniques lead to faster run time operation with minimal loss of accuracy.
RIS
TY - CPAPER TI - Geometry Aware Mappings for High Dimensional Sparse Factors AU - Avradeep Bhowmik AU - Nathan Liu AU - Erheng Zhong AU - Badri Bhaskar AU - Suju Rajan BT - Proceedings of the 19th International Conference on Artificial Intelligence and Statistics DA - 2016/05/02 ED - Arthur Gretton ED - Christian C. Robert ID - pmlr-v51-bhowmik16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 51 SP - 455 EP - 463 L1 - http://proceedings.mlr.press/v51/bhowmik16.pdf UR - https://proceedings.mlr.press/v51/bhowmik16.html AB - While matrix factorisation models are ubiquitous in large scale recommendation and search, real time application of such models requires inner product computations over an intractably large set of item factors. In this manuscript we present a novel framework that exploits structural properties of sparse vectors, using the inverted index representation, to significantly reduce the run time computational cost of factorisation models. We develop techniques that use geometry aware permutation maps on a tessellated unit sphere to obtain high dimensional sparse embeddings for latent factors with sparsity patterns related to angular closeness of the original latent factors. We also design several efficient and deterministic realisations within this framework and demonstrate with experiments that our techniques lead to faster run time operation with minimal loss of accuracy. ER -
APA
Bhowmik, A., Liu, N., Zhong, E., Bhaskar, B. & Rajan, S.. (2016). Geometry Aware Mappings for High Dimensional Sparse Factors. Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 51:455-463 Available from https://proceedings.mlr.press/v51/bhowmik16.html.

Related Material