Random Feature Maps for Dot Product Kernels

Abstract

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.

To appear in the proceedings of the 15th International Conference on Artificial Intelligence and Statistics (AISTATS 2012). This version corrects a minor error with Lemma 10. Acknowledgements : Devanshu Bhimwal

Cited by in corpus (25)

• Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity
• Randomized Nonlinear Component Analysis
• Scalable Kernel Methods via Doubly Stochastic Gradients
• Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels
• Expected Similarity Estimation for Large-Scale Batch and Streaming Anomaly Detection
• How to Scale Up Kernel Methods to Be As Good As Deep Neural Nets
• Vehicle Attribute Recognition by Appearance: Computer Vision Methods for Vehicle Type, Make and Model Classification
• Harmonizing Transferability and Discriminability for Adapting Object Detectors
• Approximate Kernel PCA Using Random Features: Computational vs. Statistical Trade-off
• Reservoir Computing meets Recurrent Kernels and Structured Transforms
• Random Features for Compositional Kernels
• Deep Quantization: Encoding Convolutional Activations with Deep Generative Model
• On Sampling Random Features From Empirical Leverage Scores: Implementation and Theoretical Guarantees
• Low-rank Bilinear Pooling for Fine-Grained Classification
• Factorized Bilinear Models for Image Recognition
• Relative Error Embeddings for the Gaussian Kernel Distance
• Sublinear Partition Estimation
• Fast Landmark Subspace Clustering
• A Compact Kernel Approximation for 3D Action Recognition
• RCoNet: Deformable Mutual Information Maximization and High-order Uncertainty-aware Learning for Robust COVID-19 Detection
• Exploiting sparsity to build efficient kernel based collaborative filtering for top-N item recommendation
• Complex-to-Real Sketches for Tensor Products with Applications to the Polynomial Kernel
• Index Set Fourier Series Features for Approximating Multi-dimensional Periodic Kernels
• Random Feature Maps via a Layered Random Projection (LaRP) Framework for Object Classification
• Towards Unbiased Random Features with Lower Variance For Stationary Indefinite Kernels