cvpr cvpr2013 cvpr2013-223 cvpr2013-223-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Fumin Shen, Chunhua Shen, Qinfeng Shi, Anton van_den_Hengel, Zhenmin Tang
Abstract: Learning based hashing methods have attracted considerable attention due to their ability to greatly increase the scale at which existing algorithms may operate. Most of these methods are designed to generate binary codes that preserve the Euclidean distance in the original space. Manifold learning techniques, in contrast, are better able to model the intrinsic structure embedded in the original highdimensional data. The complexity of these models, and the problems with out-of-sample data, havepreviously rendered them unsuitable for application to large-scale embedding, however. In this work, we consider how to learn compact binary embeddings on their intrinsic manifolds. In order to address the above-mentioned difficulties, we describe an efficient, inductive solution to the out-of-sample data problem, and a process by which non-parametric manifold learning may be used as the basis of a hashing method. Our proposed approach thus allows the development of a range of new hashing techniques exploiting the flexibility of the wide variety of manifold learning approaches available. We particularly show that hashing on the basis of t-SNE [29] outperforms state-of-the-art hashing methods on large-scale benchmark datasets, and is very effective for image classification with very short code lengths.
[1] M. Belkin and P. Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In Proc. Adv. Neural Inf. Process. Syst., 2001 .
[2] Y. Bengio, O. Delalleau, N. Roux, J. Paiement, P. Vincent, and M. Ouimet. Learning eigenfunctions links spectral embedding and kernel PCA. Neural Comput., 16(10):2197–2219, 2004.
[3] M. M. Bronstein and P. Fua. LDAHash: Improved matching with smaller descriptors. IEEE Trans. Pattern Anal. Mach. Intell., 2012.
[4] M. Carreira-Perpin a´n. The elastic embedding algorithm for dimensionality reduction. In Proc. Int. Conf. Mach. Learn., 2010.
[5] M. Carreira-Perpin a´n and Z. Lu. The laplacian eigenmaps latent variable model. Proc. Int. Conf. Artif. Intell. Stat., 2007.
[6] M. Datar, N. Immorlica, P. Indyk, and V. Mirrokni. Locality-sensitive hashing scheme based on p-stable distributions. In Ann. Symp. Comput. Geometry, 2004.
[7] O. Delalleau, Y. Bengio, and N. Le Roux. Efficient non-parametric function induction in semi-supervised learning. In Proc. Int. Workshop Artif. Intelli. Stat., pages 96–103, 2005.
[8] A. Gionis, P. Indyk, and R. Motwani. Similarity search in high dimensions via hashing. In Proc. Int. Conf. Very Large Datadases, 1999.
[9] Y. Gong and S. Lazebnik. Iterative quantization: A procrustean approach to learning binary codes. In Proc. IEEE Conf. Comp. Vis. Patt. Recogn., 2011.
[10] X. He, W.-Y. Ma, and H.-J. Zhang. Learning an image manifold for retrieval. In Proc. ACM Multimedia, 2004.
[11] J. Heo, Y. Lee, J. He, S. Chang, and S. Yoon. Spherical hashing. In Proc. IEEE Conf. Comp. Vis. Patt. Recogn., 2012.
[12] R. Herbrich and R. C. Williamson. Algorithmic luckiness. J. Mach. Learn. Res., 3: 175–212, 2002.
[13] G. Hinton and S. Roweis. Stochastic neighbor embedding. In Proc. Adv. Neural Inf. Process. Syst., 2002.
[14] A. Joly and O. Buisson. Random maximum margin hashing. In Proc. IEEE Conf. Comp. Vis. Patt. Recogn., 2011.
[15] B. Kulis and T. Darrell. Learning to hash with binary reconstructive embeddings. In Proc. Adv. Neural Inf. Process. Syst., 2009.
[16] B. Kulis and K. Grauman. Kernelized locality-sensitive hashing for scalable image search. In Proc. IEEE Int. Conf. Comp. Vis., 2009.
[17] B. Kulis, P. Jain, and K. Grauman. Fast similarity search for learned metrics. IEEE Trans. Pattern Anal. Mach. Intell., pages 2143–2157, 2009.
[18] S. Lafon and A. Lee. Diffusion maps and coarse-graining: A unified framework for dimensionality reduction, graph partitioning, and data set parameterization. IEEE Trans. Pattern Anal. Mach. Intell., 28(9): 1393–1403, 2006.
[19] X. Li, G. Lin, C. Shen, A. van den Hengel, and A. Dick. Learning hash functions using column generation. In Proc. Int. Conf. Mach. Learn., 2013.
[20] W. Liu, J. Wang, R. Ji, Y. Jiang, and S. Chang. Supervised hashing with kernels. In Proc. IEEE Conf. Comp. Vis. Patt. Recogn., 2012.
[21] W. Liu, J. Wang, S. Kumar, and S.-F. Chang. Hashing with graphs. In Proc. Int. Conf. Mach. Learn., 2011.
[22] C. D. Manning, P. Raghavan, and H. Schtze. Introduction to Information Retrieval. Cambridge University Press, New York, NY, USA, 2008.
[23] A. Oliva and A. Torralba. Modeling the shape of the scene: A holistic representation of the spatial envelope. Int. J. Comp. Vis., 2001.
[24] M. Raginsky and S. Lazebnik. Locality-sensitive binary codes from shiftinvariant kernels. In Proc. Adv. Neural Inf. Process. Syst., 2009.
[25] S. Roweis and L. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, pages 2323–2326, 2000.
[26] A. Talwalkar, S. Kumar, and H. Rowley. Large-scale manifold learning. In Proc. IEEE Conf. Comp. Vis. Patt. Recogn., 2008.
[27] J. Tenenbaum, V. De Silva, and J. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, pages 23 19–2323, 2000.
[28] A. Torralba, R. Fergus, and W. Freeman. 80 million tiny images: A large data set for nonparametric object and scene recognition. IEEE Trans. Pattern Anal. Mach. Intell., pages 1958–1970, 2008.
[29] L. Van der Maaten and G. Hinton. Visualizing data using t-SNE. J. Mach. Learn. Res., 9:2579–2605, 2008.
[30] J. Venna, J. Peltonen, K. Nybo, H. Aidos, and S. Kaski. Information retrieval perspective to nonlinear dimensionality reduction for data visualization. J. Mach. Learn. Res., 11:451–490, 2010.
[31] J. Wang, S. Kumar, and S.-F. Chang. Semi-supervised hashing for large scale search. IEEE Trans. Pattern Anal. Mach. Intell., 34(12):2393 –2406, 2012.
[32] J. Wang, J. Yang, K. Yu, F. Lv, T. Huang, and Y. Gong. Locality-constrained linear coding for image classification. In Proc. IEEE Conf. Comp. Vis. Patt. Recogn., 2010.
[33] Y. Weiss, A. Torralba, and R. Fergus. Spectral hashing. In Proc. Adv. Neural Inf. Process. Syst., 2008.
[34] K. Yu, T. Zhang, and Y. Gong. Nonlinear learning using local coordinate coding. In Proc. Adv. Neural Inf. Process. Syst., 2009.
[35] D. Zhang, J. Wang, D. Cai, and J. Lu. Self-taught hashing for fast similarity search. In Proc. ACM SIGIR Conf., 2010. 111555666977