Random Feature Maps for Dot Product Kernels

Purushottam Kar, Harish KarnickAISTATS 2012

Introduction

Kernel methods are fundamental to machine learning, enabling linear algorithms to solve complex non-linear problems through the "kernel trick." However, traditional kernel-based models like Support Vector Machines (SVMs) face a significant scalability challenge known as the Curse of Support. According to the Representer Theorem, the complexity of these models often scales with the number of support vectors, which grows alongside the training dataset. For massive datasets, prediction becomes prohibitively slow.

To mitigate this, researchers seek explicit feature maps $Z(x)$ such that the inner product $\langle Z(x), Z(y) \rangle$ approximates the kernel $K(x, y)$. While techniques like Random Fourier Features exist for translation-invariant kernels, this paper introduces a randomized method to approximate dot product kernels ($K(x, y) = f(\langle x, y \rangle)$), such as polynomial and exponential kernels. By mapping data into low-dimensional linear spaces, the authors achieve speedups of up to 200x in SVM training and testing while maintaining high classification accuracy.

Methodology: Random Maclaurin Feature Maps

The authors' approach is grounded in a classical result from harmonic analysis by Schoenberg (1942): a function $f$ defines a valid dot product kernel if and only if its Maclaurin expansion $f(x) = \sum a_n x^n$ has non-negative coefficients ($a_n \geq 0$). This positivity ensures the embedding remains in real Euclidean space.

The core contribution is Algorithm 1: Random Maclaurin Feature Maps. The process involves sampling a degree $N$ from a probability distribution, choosing $N$ random Rademacher vectors, and constructing a feature map as the product of these random projections scaled by the Maclaurin coefficient $a_N$. This is repeated $D$ times to create a $D$-dimensional embedding.

Approximation error for homogeneous, polynomial, and exponential kernels across varying dimensions (d) and feature counts (D).

A key refinement introduced is the H0/1 heuristic. Since the first two terms of a Maclaurin expansion (constant and linear) are computationally inexpensive to calculate exactly, the authors suggest adjoining the original features directly to the random features. This significantly reduces approximation error, especially when using a small number of random features.

Experimental Evaluation

The proposed method was evaluated on several standard UCI benchmark datasets, including Nursery, Spambase, Cod-RNA, Adult, IJCNN, and Covertype. The tests focused on three kernel types: Homogeneous Polynomial, Non-homogeneous Polynomial, and the Exponential Dot Product kernel.

Key Results and Speedups

The experimental results confirm that Random Maclaurin features are a highly efficient alternative to exact kernel methods:

  • Computational Efficiency: On the Cod-RNA dataset, training with random features was 229x faster than using LIBSVM with an exact polynomial kernel, while testing was 56x faster.
  • Classification Accuracy: Accuracy loss was generally negligible. For instance, on the Nursery dataset, the exact kernel achieved 99.9% accuracy, whereas the random feature map with $D=500$ reached 99.7%.
  • Impact of H0/1: The H0/1 heuristic proved vital for performance at low feature counts. As shown in the accuracy plots, it allows models to reach high accuracy much faster than "plain" random features, creating a distinct "elbow" in the performance curve.
Comparison of classification accuracy with and without the H0/1 heuristic as a function of the number of random features (D).

Conclusion and Future Directions

While the Random Maclaurin approach offers massive speedups, it has some limitations. Unlike translation-invariant kernels, dot product kernels are inherently unbounded, meaning approximation quality depends on the data's radius. Additionally, kernels with "heavy-tailed" Maclaurin coefficients may require a larger $D$ to manage estimator variance. Future work may explore inducing sparsity in the random feature space to further optimize memory usage and investigate the application of these maps in nested "compositional kernels" for more complex architectures.

Summary updated

BibTeX
@article{kar2012random,
  author = {Purushottam Kar and Harish Karnick},
  title = {{Random Feature Maps for Dot Product Kernels}},
  journal = {AISTATS},
  year = {2012},
}
Figure