Classification using intersection kernel support vector machines is efficient

Abstract

Straightforward classification using kernelized SVMs re- quires evaluating the kernel for a test vector and each of the support vectors. For a class of kernels we show that one can do this much more efficiently. In particular we showthat one canbuild histogramintersection kernel SVMs (IKSVMs)with runtimecomplexityofthe classifierlogarith- mic in the number of support vectors as opposed tolinear for the standardapproach. We further show that by precom- puting auxiliary tables we can construct an approximate classifier with constant runtime and space requirements, independent of the number of support vectors, with negli- gible loss in classification accuracy on various tasks. This approximation also applies to 1 − �2 and other kernels of similar form. We also introduce novel features based on a multi-level histogramsof oriented edgeenergy andpresent experiments on various detection datasets. On the INRIA pedestrian dataset an approximate IKSVM classifier based on these features has the current best performance, with a miss rate 13% lower at 10 6 False Positive Per Window than the linear SVM detector of Dalal & Triggs. On the Daimler Chrysler pedestrian dataset IKSVM gives comparable ac- curacy to the best results (based on quadratic SVM), while being 15× faster. In these experiments our approximate IKSVM is up to2000× faster than a standard implementa- tion and requires200× less memory. Finally we show that a 50× speedup is possible using approximate IKSVM based on spatial pyramid features on the Caltech 101 dataset with negligible loss of accuracy.