The DOI matches its Crossref record; 44 of the 44 references it cites were found in a registry or an index.
Efficient Additive Kernels via Explicit Feature Maps
Abstract
Large scale nonlinear support vector machines (SVMs) can be approximated by linear ones using a suitable feature map. The linear SVMs are in general much faster to learn and evaluate (test) than the original nonlinear SVMs. This work introduces explicit feature maps for the additive class of kernels, such as the intersection, Hellinger's, and χ2 kernels, commonly used in computer vision, and enables their use in large scale problems. In particular, we: 1) provide explicit feature maps for all additive homogeneous kernels along with closed form expression for all common kernels; 2) derive corresponding approximate finite-dimensional feature maps based on a spectral analysis; and 3) quantify the error of the approximation, showing that the error is independent of the data dimension and decays exponentially fast with the approximation order for selected kernels such as χ2. We demonstrate that the approximations have indistinguishable performance from the full kernels yet greatly reduce the train/test times of SVMs. We also compare with two other approximation methods: Nystrom's approximation of Perronnin et al., which is data dependent, and the explicit map of Maji and Berg for the intersection kernel, which, as in the case of our approximations, is data independent. The approximations are evaluated on a number of standard data sets, including Caltech-101, Daimler-Chrysler pedestrians, and INRIA pedestrians.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Histograms of Oriented Gradients for Human Detection
Dalal, N., & Triggs, B. (2005) · 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) · doi:10.1109/cvpr.2005.177 · Cited by 33,584
Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond
Schölkopf, B., & Smola, A. J. (2001) · The MIT Press eBooks · doi:10.7551/mitpress/4175.001.0001 · Cited by 11,703
Object Detection with Discriminatively Trained Part-Based Models
Felzenszwalb, P. F., Girshick, R. B., McAllester, D., & Ramanan, D. (2010) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2009.167 · Cited by 9,853
Beyond Bags of Features: Spatial Pyramid Matching for Recognizing Natural Scene Categories
Lazebnik, S., Schmid, C., & Ponce, J. (2006) · 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition - Volume 2 (CVPR'06) · doi:10.1109/cvpr.2006.68 · Cited by 7,916
Video Google: a text retrieval approach to object matching in videos
Sivic, & Zisserman (2003) · Proceedings Ninth IEEE International Conference on Computer Vision · doi:10.1109/iccv.2003.1238663 · Cited by 6,367
Visual categorization with bags of keypoints
Csurka, G. (2004) · Cited by 4,379
Random Features for Large-Scale Kernel Machines
Rahimi, A., & Recht, B. (2007) · Cited by 2,783
Vlfeat: an open and portable library of computer vision algorithms
Vedaldi, A., & Fulkerson, B. (2010) · Proceedings of the 18th ACM international conference on Multimedia · doi:10.1145/1873951.1874249 · Cited by 2,664
Self-citationLearning to detect natural image boundaries using local brightness, color, and texture cues
Martin, D. R., Fowlkes, C. C., & Malik, J. (2004) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2004.1273918 · Cited by 2,420
Zhang, J., Marszałek, M., Lazebnik, S., & Schmid, C. (2007) · International Journal of Computer Vision · doi:10.1007/s11263-006-9794-4 · Cited by 1,923
Training linear SVMs in linear time
Joachims, T. (2006) · Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1150402.1150429 · Cited by 1,920
An HOG-LBP human detector with partial occlusion handling
Wang, X., Han, T. X., & Yan, S. (2009) · 2009 IEEE 12th International Conference on Computer Vision · doi:10.1109/iccv.2009.5459207 · Cited by 1,727
The pyramid match kernel: discriminative classification with sets of image features
Grauman, K., & Darrell, T. (2005) · Tenth IEEE International Conference on Computer Vision (ICCV'05) Volume 1 · doi:10.1109/iccv.2005.239 · Cited by 1,481
Sparse Gaussian Processes using Pseudo-inputs
Snelson, E., & Ghahramani, Z. (2005) · Cited by 1,415
The Tradeoffs of Large-Scale Learning
Bottou, L., & Bousquet, O. (2011) · Optimization for Machine Learning · doi:10.7551/mitpress/8996.003.0015 · Cited by 1,128
Pegasos: Primal Estimated sub-GrAdient SOlver for SVM
Shalev-Shwartz, S., Singer, Y., & Srebro, N. (2007) · Proceedings of the 24th international conference on Machine learning · doi:10.1145/1273496.1273598 · Cited by 973
Cutting-plane training of structural SVMs
Joachims, T., Finley, T., & Yu, C.-N. J. (2009) · Machine Learning · doi:10.1007/s10994-009-5108-8 · Cited by 958
Classification using intersection kernel support vector machines is efficient
Maji, S., Berg, A. C., & Malik, J. (2008) · 2008 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2008.4587630 · Cited by 940
Multiple kernels for object detection
Vedaldi, A., Gulshan, V., Varma, M., & Zisserman, A. (2009) · 2009 IEEE 12th International Conference on Computer Vision · doi:10.1109/iccv.2009.5459183 · Cited by 757
Self-citationLocality-sensitive binary codes from shift-invariant kernels
Raginsky, M., & Lazebnik, S. (2009) · Cited by 600
Efficient svm training using low-rank kernel representations
Fine, S., & Scheinberg, K. (2002) · doi:10.5555/944790.944812 · Cited by 579
Sparse Greedy Matrix Approximation for Machine Learning
Smola, A. J., & Schökopf, B. (2000) · doi:10.5555/645529.657980 · Cited by 574
Kernel independent component analysis
Bach, F. R., & Jordan, M. I. (2004) · 2003 IEEE International Conference on Acoustics, Speech, and Signal Processing, 2003. Proceedings. (ICASSP '03). · doi:10.1109/icassp.2003.1202783 · Cited by 568
An Experimental Study on Pedestrian Classification
Munder, S., & Gavrila, D. M. (2006) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2006.217 · Cited by 555
(2007) · The MIT Press eBooks · doi:10.7551/mitpress/7496.001.0001 · Cited by 536
The Kernel Trick for Distances
Schölkopf, B. (2000) · Cited by 505
VLFeat: An open and portable library of computer vision algorithms
Vedaldi, A., & Fulkerson, B. (2010) · Cited by 485
Self-citationA Bayesian Approach to Unsupervised One-Shot Learning of Object Categories
Fei-Fei, L., Fergus, R., & Perona, P. (2003) · Cited by 423
A Bayesian approach to unsupervised one-shot learning of object categories
Fe-Fei, L., Fergus, & Perona (2003) · Proceedings Ninth IEEE International Conference on Computer Vision · doi:10.1109/iccv.2003.1238476 · Cited by 403
Empirical evaluation of dissimilarity measures for color and texture
Puzicha, J., Buhmann, J. M., Rubner, Y., & Tomasi, C. (1999) · Proceedings of the Seventh IEEE International Conference on Computer Vision · doi:10.1109/iccv.1999.790412 · Cited by 361
Support Vector Machine Solvers
Bottou, L., & Lin, C.-J. (2007) · Large-Scale Kernel Machines · doi:10.7551/mitpress/7496.003.0003 · Cited by 336
LIBLINEAR: A Library for Large Linear Classification
FanRong-En, ChangKai-Wei, HsiehCho-Jui, WangXiang-Rui, & LinChih-Jen (2008) · Journal of Machine Learning Research · doi:10.5555/1390681.1442794 · Cited by 328
Learning to Localize Objects with Structured Output Regression
Blaschko, M. B., & Lampert, C. H. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-88682-2_2 · Cited by 324
Histogram intersection kernel for image classification
Barla, A., Odone, F., & Verri, A. (2004) · Proceedings 2003 International Conference on Image Processing (Cat. No.03CH37429) · doi:10.1109/icip.2003.1247294 · Cited by 281
Predictive low-rank decomposition for kernel methods
Bach, F. R., & Jordan, M. I. (2005) · Proceedings of the 22nd international conference on Machine learning - ICML '05 · doi:10.1145/1102351.1102356 · Cited by 238
Coordinate Descent Method for Large-scale L2-loss Linear Support Vector Machines
Chang, K., Hsieh, C., & Lin, C. (2008) · Cited by 219
Efficient Match Kernel between Sets of Features for Visual Recognition
Bo, L., & Sminchisescu, C. (2009) · Cited by 212
Max-margin additive classifiers for detection
Maji, S., & Berg, A. C. (2009) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2009.5459203 · Cited by 160
Large-scale image categorization with explicit data embedding
Perronnin, F., Sánchez, J., & Liu, Y. (2010) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2010.5539914 · Cited by 159
The Effect of the Input Density Distribution on Kernel-based Classifiers
Williams, C. K. I., & Seeger, M. (2000) · Cited by 140
Hilbertian Metrics and Positive Definite Kernels on Probability Measures
Hein, M., & Bousquet, O. (2005) · Cited by 135
Efficient Learning using Forward-Backward Splitting
Singer, Y., & Duchi, J. C. (2009) · neural information processing systems · Cited by 87
Generalized RBF feature maps for Efficient Detection
Vempati, S., Vedaldi, A., Zisserman, A., & Jawahar, C. V. (2010) · British Machine Vision Conference (BMVC) · doi:10.5244/c.24.2 · Cited by 80
Self-citationImplicit color segmentation features for pedestrian and object detection
Ott, P., & Everingham, M. (2009) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2009.5459238 · Cited by 75
Cited by
High-Speed Tracking with Kernelized Correlation Filters
Henriques, J. F., Caseiro, R., Martins, P., & Batista, J. (2015) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2014.2345390 · Cited by 5,753
Return of the Devil in the Details: Delving Deep into Convolutional Nets
Chatfield, K., Simonyan, K., Vedaldi, A., & Zisserman, A. (2014) · Proceedings of the British Machine Vision Conference 2014 · doi:10.5244/c.28.6 · Cited by 3,335
Self-citationImage Classification with the Fisher Vector: Theory and Practice
Sánchez, J., Perronnin, F., Mensink, T., & Verbeek, J. (2013) · International Journal of Computer Vision · doi:10.1007/s11263-013-0636-x · Cited by 1,498
BING: Binarized Normed Gradients for Objectness Estimation at 300fps
Cheng, M.-M., Zhang, Z., Lin, W.-Y., & Torr, P. (2014) · 2014 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2014.414 · Cited by 1,050
The Little Engine That Could: Regularization by Denoising (RED)
Romano, Y., Elad, M., & Milanfar, P. (2017) · SIAM Journal on Imaging Sciences · doi:10.1137/16m1102884 · Cited by 934
Metadata
- Authors
- Vedaldi, A., & Zisserman, A.
- Venue
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Published
- 2012-03
- Volume
- 34
- Issue
- 3
- Pages
- 480-492
- ISSN
- 0162-8828 (ISSN-L)
- 2160-9292
- OpenAlex
- W2109235804
- Cited by
- 688
- References
- 44
- FWCI
- 57.06
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.
