×

Sharing hash codes for multiple purposes. (English) Zbl 1430.62274

Summary: Locality sensitive hashing (LSH) is a powerful tool in data science, which enables sublinear-time approximate nearest neighbor search. A variety of hashing schemes have been proposed for different dissimilarity measures. However, hash codes significantly depend on the dissimilarity, which prohibits users from adjusting the dissimilarity at query time. In this paper, we propose multiple purpose LSH (mp-LSH) which shares the hash codes for different dissimilarities. mp-LSH supports L2, cosine, and inner product dissimilarities, and their corresponding weighted sums, where the weights can be adjusted at query time. It also allows us to modify the importance of pre-defined groups of features. Thus, mp-LSH enables us, for example, to retrieve similar items to a query with the user preference taken into account, to find a similar material to a query with some properties (stability, utility, etc.) optimized, and to turn on or off a part of multi-modal information (brightness, color, audio, text, etc.) in image/video retrieval. We theoretically and empirically analyze the performance of three variants of mp-LSH, and demonstrate their usefulness on real-world data sets.

MSC:

62R07 Statistical aspects of big data and data science
62P30 Applications of statistics in engineering and industry; control charts
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bach, S., Binder, A., Montavon, G., Klauschen, F., Müller, K. R., & Samek, W. (2015). On pixel-wise explanations for non-linear classifier decisions by layer-wise relevance propagation. PLoS One, 10(7), e0130140. · doi:10.1371/journal.pone.0130140
[2] Bachrach, Y., Finkelstein, Y., Gilad-Bachrach, R., Katzir, L., Koenigstein, N., Nice, N., & Paquet, U. (2014). Speeding up the Xbox recommender system using a euclidean transformation for inner-product spaces. In: Proceedings of the 8th ACM conference on recommender systems (RecSys) (pp. 257-264).
[3] Baehrens, D., Schroeter, T., Harmeling, S., Kawanabe, M., Hansen, K., & Müller, K. R. (2010). How to explain individual classification decisions. Journal of Machine Learning Research, 11, 1803-1831. · Zbl 1242.62049
[4] Bengio, Y. (2009). Learning deep architectures for AI. Foundations and Trends in Machine Learning, 2(1), 1-127. · Zbl 1192.68503 · doi:10.1561/2200000006
[5] Bengio, Y., LeCun, Y., & Hinton, G. (2015). Deep learning. Nature, 521, 436. · doi:10.1038/nature14539
[6] Beygelzimer, A., Kakade, S., & Langford, J. (2006). Cover trees for nearest neighbor. In: Proceedings of International Conference on Machine Leanring (pp. 97-104).
[7] Bishop, C. M. (2006). Pattern Recognition and Machine Learning. New York: Springer. · Zbl 1107.68072
[8] Broder, A. Z., Glassman, S. C., Manasse, M. S., & Zweig, G. (1997). Syntactic clustering of the web. Computer Networks, 29, 1157-1166.
[9] Bustos, B., Kreft, S., & Skopal, T. (2012). Adapting metric indexes for searching in multi-metric spaces. Multimedia Tools and Applications, 58(3), 467-496. · doi:10.1007/s11042-011-0731-3
[10] Charikar, M. S. (2002). Similarity estimation techniques from rounding algorithms. In: Proceedings of the Annual ACM Symposium on Theory of Computing (STOC) (pp. 380-388). · Zbl 1192.68226
[11] Cremonesi, P., Koren, Y., & Turrin, R. (2010). Performance of recommender algorithms on top-n recommendation tasks. In: Proceedings of the Fourth ACM Conference on Recommender Systems (RecSys) (pp. 39-46).
[12] Datar, M., Immorlica, N., Indyk, P., & Mirrokn, V. S. (2004). Locality-sensitive hashing scheme based on p-stable distributions. In: Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG) (pp. 253-262). · Zbl 1373.68193
[13] Funk, S. (2006). Try this at home. http://sifter.org/simon/journal/20061211.html.
[14] Goemans, M. X., & Williamson, D. P. (1995). Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of ACM, 42(6), 1115-1145. · Zbl 0885.68088 · doi:10.1145/227683.227684
[15] Gorisse, D., Cord, M., & Precioso, F. (2012). Locality-sensitiv hashing for chi2 distance. IEEE Transactions on Pattern Analysis and Machine Intelligence, 34(2), 402-409. · doi:10.1109/TPAMI.2011.193
[16] Hastie, T., Tibshirani, R., & Friedman, J. (2001). The Elements of Statistical Learning. Berlin: Springer. · Zbl 0973.62007 · doi:10.1007/978-0-387-21606-5
[17] He, J., Chang, S. F., Radhakrishnan, R., & Bauer, C. (2011). Compact hashing with joint optimization of search accuracy and time. In: Proceedings of Computer Vision and Pattern Recognition (CVPR) (pp. 753-760).
[18] Heinonen, J. (2001). Lectures on analysis on metric spaces. Universitext. · Zbl 0985.46008
[19] Hinton, G. (2007). Learning multiple layers of representation. Trends in Cognitive Sciences, 11, 428-434. · doi:10.1016/j.tics.2007.09.004
[20] Indyk, P., & Motwani, R. (1998). Approximate nearest neighbors: Towards removing the curse of dimensionality. In: Proceedings of the Annual ACM Symposium on Theory of Computing (STOC) (pp. 604-613). · Zbl 1029.68541
[21] Jain, P., Vijayanarasimhan, S., & Grauman, K. (2010). Hashing hyperplane queries to near points with applications to large-scale active learning. In: Advances in Neural Information Processing Systems (NIPS) (Vol. 23).
[22] Jégou, H., Tavenard, R., Douze, M., & Amsaleg, L. (2011). Searching in one billion vectors: re-rank with source coding. In: Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) (pp. 861-864).
[23] Krizhevsky, A., Sutskever, I., & Hinton, G. (2012). Imagenet classification with deep convolutional neural networks. In: Advances in Neural Information Processing Systems (NIPS) (Vol. 25).
[24] Lin, K., Yang, H. F., Hsiao, J. H., & Chen, C. S. (2015). Deep learning of binary hash codes for fast image retrieval. In: Proceedings of Computer Vision and Pattern Recognition Workshops.
[25] Liu, G., Xu, H., & Yan, S. (2012). Exact subspace segmentation and outlier detection by low-rank representation. In: Proceedings of Artificial Intelligence and Statistics Conference (AISTATS).
[26] Lowe, D. G. (2004). Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision, 60(2), 91-110. · doi:10.1023/B:VISI.0000029664.99615.94
[27] Matsushita, Yusuke; Wada, Toshikazu, Principal Component Hashing: An Accelerated Approximate Nearest Neighbor Search, 374-385 (2009), Berlin, Heidelberg · doi:10.1007/978-3-540-92957-4_33
[28] Montavon, G., Lapuschkin, S., Binder, A., Samek, W., & Müller, K. R. (2017). Explaining nonlinear classification decisions with deep taylor decomposition. Pattern Recognition, 65, 211-222. · doi:10.1016/j.patcog.2016.11.008
[29] Montavon, G., Orr, G., & Müller, K. R. (2012). Neural Networks: Tricks of the Trade. New York: Springer. · doi:10.1007/978-3-642-35289-8
[30] Montavon, G., Samek, W., & Müller, K. R. (2018). Methods for interpreting and understanding deep neural networks. Digital Signal Processing, 73, 1-15. · doi:10.1016/j.dsp.2017.10.011
[31] Moran, S., Lavrenko, V. (2015). Regularized cross-modal hashing. In: Proc. of SIGIR.
[32] Neyshabur, B., Srebro, N. (2015) On symmetric and asymmetric lshs for inner product search. In: ICML, vol. 32.
[33] Ribeiro, M.T., Singh, S., Guestrin, C. (2016). Why should I trust you? In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1135-1144.
[34] Russakovsky, O., Deng, J., Su, H., Krause, J., Satheesh, S., Ma, S., et al. (2015). ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV), 115(3), 211-252. https://doi.org/10.1007/s11263-015-0816-y. · doi:10.1007/s11263-015-0816-y
[35] Schütt, K., Arbabzadah, F., Chmiela, S., Müller, K. R., & Tkatchenko, A. (2017). Quantum-chemical insights from deep tensor neural networks. Nature Communications, 8, 13890. · doi:10.1038/ncomms13890
[36] Shrivastava, A., Li, P. (2014). Asymmetric LSH (ALSH) for sublinear time maximum inner product search (MIPS). In: NIPS, vol. 27.
[37] Shrivastava, A., Li, P. (2015). Improved asymmetric locality sensitive hashing (ALSH) for maximum inner product search (MIPS). Proc. of UAI.
[38] Simonyan, K., Vedaldi, A., Zisserman, A. (2014). Deep inside convolutional networks: Visualising image classification models and saliency maps. In: ICLR Workshop 2014.
[39] Simonyan, K., Zisserman, A. (2014). Very deep convolutional networks for large-scale image recognition. CoRR abs/1409.1556
[40] Song, J., Yang, Y., Huang, Z., Schen, H. T., & Luo, J. (2013). Effective multiple feature hashing for large-scale near-duplicate video retrieval. IEEE Transaction on Multimedia, 15(8), 1997-2008. · doi:10.1109/TMM.2013.2271746
[41] Strecha, C., Bronstein, A. M., Bronstein, M. M., & Fua, P. (2012). LDA hash: Improved matching with smaller descriptors. IEEE Transactions on Pattern Analysis and Machine Intelligence, 34(1), 66-78. · doi:10.1109/TPAMI.2011.103
[42] Tagami, Y. (2017). AnnexML: Approximate nearest neighbor search for extreme multi-label classification. In: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 455-464
[43] Torralba, A., Fergus, R., & Freeman, W. (2008). 80 million tiny images: a large data set for nonparametric object and scene recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 30(11), 1958-1970. · doi:10.1109/TPAMI.2008.128
[44] Wang, J., Schen, H.T., Song, J., Ji, J. (2014). Hashing for similarity search: a survey. arXiv:1408.2927v1 [cs.DS].
[45] Xu, S., Wang, S., Zhang, Y. (2013). Summarizing complex events: a cross-modal solution of storylines extraction and reconstruction. In: Proc. of EMNLP, pp. 1281-1291.
[46] Zeiler, Matthew D.; Fergus, Rob, Visualizing and Understanding Convolutional Networks, 818-833 (2014), Cham
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.