Efficient additive kernels via explicit feature maps.

Area of Science:

• Computer Vision
• Machine Learning
• Kernel Methods

Background:

• Large-scale nonlinear Support Vector Machines (SVMs) are computationally expensive.
• Approximation by linear SVMs using feature maps offers significant speed advantages.
• Commonly used kernels in computer vision, like intersection, Hellinger's, and χ2, are often nonlinear.

Purpose of the Study:

• To develop explicit feature maps for additive kernels to enable their use in large-scale SVM problems.
• To provide approximate finite-dimensional feature maps for efficient computation.
• To analyze and quantify the approximation error.

Main Methods:

• Deriving explicit feature maps for additive homogeneous kernels.
• Employing spectral analysis to create approximate finite-dimensional feature maps.
• Quantifying approximation error and its dependence on approximation order.

Main Results:

• Explicit feature maps were derived for additive homogeneous kernels, including closed-form expressions for common kernels.
• Approximate feature maps were generated, showing error independent of data dimension and exponentially fast decay with approximation order for kernels like χ2.
• Approximations demonstrated indistinguishable performance from full kernels, significantly reducing SVM train/test times.

Conclusions:

• The proposed explicit feature maps enable efficient large-scale application of nonlinear SVMs with additive kernels.
• The approximations offer a favorable trade-off between computational efficiency and predictive accuracy.
• The method provides a data-independent approximation, outperforming or matching other data-dependent and independent methods on benchmark datasets.