Random Feature Maps for Dot Product Kernels

By Purushottam Kar, Harish Karnick. 2012

272 citations recorded by the source corpus.

Approximating non-linear kernels using feature maps has gained a lot of interest in recent years due to applications in reducing training and testing times of SVM classifiers and other kernel based learning algorithms. We extend this line of work and present low distortion embeddings for dot product kernels into linear Euclidean spaces. We base our results on a classical result in harmonic analysis characterizing all dot product kernels and use it to define randomized feature maps into explicit low dimensional Euclidean spaces in which the native dot product provides an approximation to the dot product kernel with high confidence.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Representation & Self-Supervised Learning, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Representation & Self-Supervised Learning

In Statistical Learning Theory

Citations in the corpus

Kernel Mean Embedding of Distributions: A Review and Beyonds (2016, methodology): “, Kar and Karnick (2012), Le et al. (2013), Pham and Pagh (2013) and references therein for extensions).”
Scalable Kernel Methods via Doubly Stochastic Gradients (2014, background): “Explicit random features have been designed for many other kernels, such as dot product kernel [28], additive/multiplicative class of homogeneous kernels [29], e.”
Orthogonal Random Features (2016, background): “2 Related Works Explicit nonlinear random feature maps have been constructed for many types of kernels, such as intersection kernels [15], generalized RBF kernels [22], skewed multiplicative histogram kernels [14], additive kernels [24], and polynomial kernels [11, 18].”
Memory Efficient Kernel Approximation (2014, background): “In addition to shift invariant kernels, Kar and Karnick (2012) construct the random feature map for polynomial kernels, and Hamid et al. (2014) propose the condensed random feature map to improve performance.”
Spherical Random Features for Polynomial Kernels (2015, methodology): “Kar and Karnick [14] catalyzed this line of research by introducing the Random Maclaurin (RM) technique, which approximates 〈x,y〉p by the product ∏p i=1〈wi,x〉 ∏p i=1〈wi,y〉, where wi is a vector consisting of Bernoulli random variables.”
Coded Computing for Federated Learning at the Edge (2020, methodology): “Training and inference with random features have been shown to work considerably well in practice (Rahimi & Recht, 2008a;b; Shahrampour et al., 2018; Kar & Karnick, 2012; Rick Chang et al., 2016).”
Compact Random Feature Maps (2013, methodology): “We begin by demonstrating that previous approaches for approximating polynomial kernels (Kar & Karnick, 2012) (Pham & Pagh, 2013) construct rank-deﬁcient spaces.”
Robust Domain Generalisation by Enforcing Distribution Invariance (2016, methodology): “Recently, randomisation has been applied to other kernel methods, such as dot-product kernels [Kar and Karnick, 2012], and one-class SVM [Erfani et al.”
Kernel Pooling for Convolutional Neural Networks (2017, methodology): “There are several recently proposed work on kernel approximation with random feature projections [33, 17, 31, 2].”
Fast and scalable polynomial kernels via explicit feature maps (2013, methodology): “Hoeffding’s inequality, we achieve a tighter absolute error bound than the previous approach [10] as follows:”
Randomized Nonlinear Component Analysis (2014, methodology): “For instance, their extensions to dot-product kernels (Kar & Karnick, 2012) and polynomial kernels (Hamid et al., 2014); the development of advanced sampling techniques using Quasi-Monte-Carlo methods (Yang et al., 2014) or their accelerated computation via fast Walsh-Hadamard transforms (Le et…”
Grassmann Pooling as Compact Homogeneous Bilinear Pooling for Fine-Grained Visual Classification (2018, methodology): “To address this problem, Gao et al. [23] proposed two approximate methods via Random Maclaurin [38] and Tensor Sketch [39] to obtain compact bilinear representations.”
How to Scale Up Kernel Methods to Be As Good As Deep Neural Nets (2014, background): “Since, there has been a growing interest in using random projections to approximate different kernels [25, 19, 31, 50].”
Harmonizing Transferability and Discriminability for Adapting Object Detectors (2020, methodology): “In order to tackle the dimension explosion issue, we propose to leverage the randomized methods [34, 24] as an unbiased estimator of the tensor product.”