Explicit Embeddings for Nearest Neighbor Search with Mercer Kernels
Tóm tắt
Many approximate nearest neighbor search algorithms operate under memory constraints, by computing short signatures for database vectors while roughly keeping the neighborhoods for the distance of interest. Encoding procedures designed for the Euclidean distance have attracted much attention in the last decade. In the case where the distance of interest is based on a Mercer kernel, we propose a simple, yet effective two-step encoding scheme: first, compute an explicit embedding to map the initial space into a Euclidean space; second, apply an encoding step designed to work with the Euclidean distance. Comparing this simple baseline with existing methods relying on implicit encoding, we demonstrate better search recall for similar code sizes with the chi-square kernel in databases comprised of visual descriptors, outperforming concurrent state-of-the-art techniques by a large margin.
Tài liệu tham khảo
Boiman, O., Shechman, E., Irani, M.: In defense of nearest neighbor based image classification. In: Proceedings of the Computer Vision and Pattern Recognition (CVPR) (2008)
Braun, M.: Accurate error bounds for the eigenvalues of the kernel matrix. J. Mach. Learn. Res. 7, 2303–2328 (2006)
Charikar, M.: Similarity estimation techniques from rounding algorithms. In: Proceedings of the ACM Symposium on Theory of Computing, STOC (2002)
Datar, M., Immorlica, N., Indyk, P., Mirrokni, V.: Locality-sensitive hashing scheme based on p-stable distributions. In: Proceedings of the Symposium on Computational Geometry, pp. 253–262 (2004)
Deng, J., Dong, W., Socher, R., Li, L.J., Li, K., Fei-Fei, L.: ImageNet: a large-scale hierarchical image database. In: Proceedings of the Computer Vision and Pattern Recognition CVPR (2009)
Gong, Y., Lazebnik, S.: Iterative quantization: A procrustean approach to learning binary codes. In: Proceedings of the Computer Vision and Pattern Recognition CVPR (2011)
Gorisse, D., Cord, M., Precioso, F.: Locality-sensitive hashing for chi2 distance. IEEE Trans. Pattern Anal. Mach. Intell. 34(2), 402–409 (2012)
Grauman, K., Darrell, T.: The pyramid match kernel: Discriminative classification with sets of image features. In: Proceedings of the International Conference on Computer Vision ICCV (2005)
He, J., Liu, W., Chang, S.F.: Scalable similarity search with optimized kernel hashing. In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’10, pp. 1129–1138. ACM, New York (2010)
Jégou, H., Douze, M., Schmid, C.: Product quantization for nearest neighbor search. Trans. PAMI 33(1), 117–128 (2011)
Jégou, H., Douze, M., Schmid, C., Pérez, P.: Aggregating local descriptors into a compact image representation. In: Proceedings of the Computer Vision Pattern Recognition CVPR (2010)
Jégou, H., Tavenard, R., Douze, M., Amsaleg, L.: Searching in one billion vectors: re-rank with source coding. In: International Conference on Acoustics, Speech and Signal Processing ICASSP. Prague Czech Republic (2011)
Joly, A., Buisson, O.: Random maximum margin hashing. In: Proceedings of the Computer Vision and Pattern Recognition CVPR (2011)
Knig, H.: Eigenvalues of compact operators with applications to integral operators. Linear Algebra Appl. 84, 111–122 (1986)
Kulis, B., Grauman, K.: Kernelized locality-sensitive hashing for scalable image search. In: Proceedings of the International Conference on Computer Vision ICCV (2009)
Lowe, D.: Distinctive image features from scale-invariant keypoints. IJCV 60(2), 91–110 (2004)
Maji, S., Berg, A.: Max-margin additive models for detection. In: Proceedings of the International Conference on Computer Vision ICCV (2009)
Mikolajczyk, K., Tuytelaars, T., Schmid, C., Zisserman, A., Matas, J., Schaffalitzky, F., Kadir, T., Gool, L.V.: A comparison of affine region detectors. IJCV 65(1/2), 43–72 (2005)
Muja, M., Lowe, D.G.: Fast approximate nearest neighbors with automatic algorithm configuration. In: VISAPP International Conference on Computer Vision Theory and Applications (2009)
Perronnin, F., Sánchez, J., Liu, Y.: Large-scale image categorization with explicit data embedding. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition CVPR (2010)
Raginsky, M., Lazebnik, S.: Locality-sensitive binary codes from shift-invariant kernels. In: Proceedings of the Advances in Neural Information Processing Systems NIPS (2010)
Schölkopf, B., Smola, A.: Learning with Kernels: Support Vector Machines, Regularization, Optimization and Beyond. MIT Press, Cambridge, MA (2002)
Schölkopf, B., Smola, A., Müller, K.R.: Nonlinear component analysis as a kernel eigenvalue problem. Neural Comput., 10(5), 1299–1319 (1998)
Shawe-Taylor, J., Williams, C., Cristianini, N., Kandola, J.: On the eigenspectrum of the gram matrix and the generalization error of kernel pca. IEEE Trans. Inform. Theory 51(7), 2510–2522 (2005)
Sivic, J., Zisserman, A.: Video Google: A text retrieval approach to object matching in videos. In: Proceedings of the International Conference on Computer Vision ICCV (2003)
Torralba, A., Fergus, R., Weiss, Y.: Small codes and large databases for recognition. In: Proceedings of the Computer Vision and Pattern Recognition CVPR (2008)
Vedaldi, A., Zisserman, A.: Efficient additive kernels via explicit feature maps. In: Proceedings of the Computer Vision and Pattern Recognition CVPR (2010)
Vedaldi, A., Zisserman, A.: Efficient additive kernels via explicit feature maps. Trans. PAMI 34(3), 480–492 (2012)
Weiss, Y., Torralba, A., Fergus, R.: Spectral hashing. In: Proceedings of the Neural Information Processing Systems NIPS (2008)