cvpr14:mu

Yadong Mu, Gang Hua, Wei Fan, Shih-Fu Chang. Hash-SVM: Scalable Kernel Machines for Large-Scale Visual Classification. In International Conference on Computer Vison and Pattern Recognition (CVPR), June 2014.

Download [help]

Download paper: Adobe portable document (pdf)

Copyright notice:This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract

This paper presents a novel algorithm which uses compact hash bits to greatly improve the efficiency of non-linear kernel SVM in very large scale visual classification problems. Our key idea is to represent each sample with compact hash bits, over which an inner product is defined to serve as the surrogate of the original nonlinear kernels. Then the problem of solving the nonlinear SVM can be transformed into solving a linear SVM over the hash bits. The proposed Hash-SVM enjoys dramatic storage cost reduction owing to the compact binary representation, as well as a (sub-)linear training complexity via linear SVM. As a critical component of Hash-SVM, we propose a novel hashing scheme for arbitrary non-linear kernels via random subspace projection in reproducing kernel Hilbert space. Our comprehensive analysis reveals a well behaved theoretic bound of the deviation between the proposed hashing-based kernel approximation and the original kernel function. We also derive requirements on the hash bits for achieving a satisfactory accuracy level. Several experiments on large-scale visual classification benchmarks are conducted, including one with over 1 million images. The results show that Hash-SVM greatly reduces the computational complexity (more than ten times faster in many cases) while keeping comparable accuracies

Contact

Yadong Mu
Shih-Fu Chang

BibTex Reference

@InProceedings{cvpr14:mu,
   Author = {Mu, Yadong and Hua, Gang and Fan, Wei and Chang, Shih-Fu},
   Title = {Hash-SVM: Scalable Kernel Machines for Large-Scale Visual Classification},
   BookTitle = {International Conference on Computer Vison and Pattern Recognition (CVPR)},
   Month = {June},
   Year = {2014}
}

EndNote Reference [help]

Get EndNote Reference (.ref)

For problems or questions regarding this web site contact The Web Master.