Classification using intersection kernel support vector machines is efficient
Classification using intersection kernel support vector machines is efficient
复制标题
DOI：
10.1109/cvpr.2008.4587630
复制
发表时间：
2008-06
期刊：
影响因子：
--
通讯作者：
Subhransu Maji;A. Berg;Jitendra Malik
中科院分区：
文献类型：
--
作者：
Subhransu Maji;A. Berg;Jitendra Malik
使用核化SVM的简单分类需要评估测试向量和每个支持向量的核。对于一类内核，我们表明，可以更有效地做到这一点。特别是，我们可以建立直方图交叉核支持向量机（IKSVMs）与运行时复杂度的分类对数的支持向量的数量，而不是线性的标准方法。我们进一步表明，通过预计算辅助表，我们可以构建一个近似的分类器，具有恒定的运行时间和空间要求，独立于支持向量的数量，在各种任务的分类精度可以忽略不计的损失。这种近似也适用于1 -chi 2和其他类似形式的内核。我们还介绍了新的功能的基础上，面向边缘能量的多级直方图，并在各种检测数据集上进行实验。在INRIA行人数据集上，基于这些特征的近似IKSVM分类器具有当前最好的性能，在每窗口10-6假阳性时，错过率比Dalal & Triggs的线性SVM检测器低13%。在戴姆勒克莱斯勒行人数据集上，IKSVM的准确度与最佳结果相当（基于二次SVM），同时速度快15倍。在这些实验中，我们的近似IKSVM比标准实现快2000倍，需要的内存少200倍。最后，我们表明，一个50倍的加速是可能的使用近似IKSVM的基础上的空间金字塔功能的加州理工学院101数据集的准确性可以忽略不计的损失。
Straightforward classification using kernelized SVMs requires 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 show that one can build histogram intersection kernel SVMs (IKSVMs) with runtime complexity of the classifier logarithmic in the number of support vectors as opposed to linear for the standard approach. We further show that by precomputing auxiliary tables we can construct an approximate classifier with constant runtime and space requirements, independent of the number of support vectors, with negligible loss in classification accuracy on various tasks. This approximation also applies to 1 - chi2 and other kernels of similar form. We also introduce novel features based on a multi-level histograms of oriented edge energy and present 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 accuracy to the best results (based on quadratic SVM), while being 15times faster. In these experiments our approximate IKSVM is up to 2000times faster than a standard implementation and requires 200times less memory. Finally we show that a 50times speedup is possible using approximate IKSVM based on spatial pyramid features on the Caltech 101 dataset with negligible loss of accuracy.