Hash-SVM: Scalable Kernel Machines for Large-Scale Visual Classification

This paper presents a novel algorithm which uses com-pact hash bits to greatly improve the efficiency of non-linear kernel SVM in very large scale visual classification prob-lems. 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 arbi-trary non-linear kernels via random subspace projection in reproducing kernel Hilbert space. Our comprehensive anal-ysis reveals a well behaved theoretic bound of the deviation between the proposed hashing-based kernel approximation and the original kernel function. We also derive require-ments on the hash bits for achieving a satisfactory accuracy level. Several experiments on large-scale visual classifica-tion 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. 1