Quantization based Fast Inner Product Search

Ruiqi Guo, Sanjiv Kumar, Krzysztof Choromanski, David Simcha
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, PMLR 51:482-490, 2016.

Abstract

We propose a quantization based approach for fast approximate Maximum Inner Product Search (MIPS). Each database vector is quantized in multiple subspaces via a set of codebooks, learned directly by minimizing the inner product quantization error. Then, the inner product of a query to a database vector is approximated as the sum of inner products with the subspace quantizers. Different from recently proposed LSH approaches to MIPS, the database vectors and queries do not need to be augmented in a higher dimensional feature space. We also provide a theoretical analysis of the proposed approach, consisting of the concentration results under mild assumptions. Furthermore, if a small set of held-out queries is given at the training time, we propose a modified codebook learning procedure which further improves the accuracy. Experimental results on a variety of datasets including those arising from deep neural networks show that the proposed approach significantly outperforms the existing state-of-the-art.

Cite this Paper

BibTeX
@InProceedings{pmlr-v51-guo16a, title = {Quantization based Fast Inner Product Search}, author = {Guo, Ruiqi and Kumar, Sanjiv and Choromanski, Krzysztof and Simcha, David}, booktitle = {Proceedings of the 19th International Conference on Artificial Intelligence and Statistics}, pages = {482--490}, 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/guo16a.pdf}, url = {https://proceedings.mlr.press/v51/guo16a.html}, abstract = {We propose a quantization based approach for fast approximate Maximum Inner Product Search (MIPS). Each database vector is quantized in multiple subspaces via a set of codebooks, learned directly by minimizing the inner product quantization error. Then, the inner product of a query to a database vector is approximated as the sum of inner products with the subspace quantizers. Different from recently proposed LSH approaches to MIPS, the database vectors and queries do not need to be augmented in a higher dimensional feature space. We also provide a theoretical analysis of the proposed approach, consisting of the concentration results under mild assumptions. Furthermore, if a small set of held-out queries is given at the training time, we propose a modified codebook learning procedure which further improves the accuracy. Experimental results on a variety of datasets including those arising from deep neural networks show that the proposed approach significantly outperforms the existing state-of-the-art.} }
Endnote
%0 Conference Paper %T Quantization based Fast Inner Product Search %A Ruiqi Guo %A Sanjiv Kumar %A Krzysztof Choromanski %A David Simcha %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-guo16a %I PMLR %P 482--490 %U https://proceedings.mlr.press/v51/guo16a.html %V 51 %X We propose a quantization based approach for fast approximate Maximum Inner Product Search (MIPS). Each database vector is quantized in multiple subspaces via a set of codebooks, learned directly by minimizing the inner product quantization error. Then, the inner product of a query to a database vector is approximated as the sum of inner products with the subspace quantizers. Different from recently proposed LSH approaches to MIPS, the database vectors and queries do not need to be augmented in a higher dimensional feature space. We also provide a theoretical analysis of the proposed approach, consisting of the concentration results under mild assumptions. Furthermore, if a small set of held-out queries is given at the training time, we propose a modified codebook learning procedure which further improves the accuracy. Experimental results on a variety of datasets including those arising from deep neural networks show that the proposed approach significantly outperforms the existing state-of-the-art.
RIS
TY - CPAPER TI - Quantization based Fast Inner Product Search AU - Ruiqi Guo AU - Sanjiv Kumar AU - Krzysztof Choromanski AU - David Simcha 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-guo16a PB - PMLR DP - Proceedings of Machine Learning Research VL - 51 SP - 482 EP - 490 L1 - http://proceedings.mlr.press/v51/guo16a.pdf UR - https://proceedings.mlr.press/v51/guo16a.html AB - We propose a quantization based approach for fast approximate Maximum Inner Product Search (MIPS). Each database vector is quantized in multiple subspaces via a set of codebooks, learned directly by minimizing the inner product quantization error. Then, the inner product of a query to a database vector is approximated as the sum of inner products with the subspace quantizers. Different from recently proposed LSH approaches to MIPS, the database vectors and queries do not need to be augmented in a higher dimensional feature space. We also provide a theoretical analysis of the proposed approach, consisting of the concentration results under mild assumptions. Furthermore, if a small set of held-out queries is given at the training time, we propose a modified codebook learning procedure which further improves the accuracy. Experimental results on a variety of datasets including those arising from deep neural networks show that the proposed approach significantly outperforms the existing state-of-the-art. ER -
APA
Guo, R., Kumar, S., Choromanski, K. & Simcha, D.. (2016). Quantization based Fast Inner Product Search. Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 51:482-490 Available from https://proceedings.mlr.press/v51/guo16a.html.

Related Material