Random Feature Maps for Dot Product Kernels

Purushottam Kar; Harish Karnick

Source-linked AI summary

Random Feature Maps for Dot Product Kernels

Purushottam Kar, Harish Karnick

arXiv:1201.6530v3Jan 31, 2012cs.LGcs.CGmath.FAstat.ML

TL;DR

Kernel methods need efficient explicit representations because support-based prediction costs can grow with training-set size. This paper uses Schoenberg’s characterization of positive definite dot product kernels to construct randomized low-dimensional Euclidean feature maps, and extends them to compositional kernels. The approach applies under boundedness, Lipschitz, and compact-domain conditions, while higher-order estimation introduces additional randomness and application overhead.

Problem
Support-based kernel prediction can become costly as training sets and support sizes grow, motivating systematic explicit feature maps for nonlinear kernels.
Method
The paper characterizes positive definite dot product kernels through non-negative Maclaurin expansions and uses randomized feature maps to approximate them in explicit Euclidean spaces, including compositional kernels.
Results
The constructed maps approximate dot product kernels with very high probability and extend to compositional kernels under the stated boundedness and Lipschitz conditions.
Takeaways & Limitations
The framework provides explicit low-dimensional representations for dot product kernels and extends feature-map construction beyond the directly targeted kernel to compositional forms.
Takeaways & Limitations
The heuristic H0/1 adds feature-application overhead because its higher-order estimates require more randomness, while non-Maclaurin kernels can become indefinite beyond a dimensionality threshold.

Abstract

from arXiv · show

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.

1 Introduction

Kernel methods avoid explicit nonlinear feature spaces through the kernel trick, but support-based evaluation can become costly as datasets grow. Existing sparsity and support-reduction approaches provide empirical benefits without systematically addressing this issue across kernel algorithms.

Motivation: The kernel trick lets linear algorithms operate through pairwise inner products in implicit, often infinite-dimensional, nonlinear feature spaces.This avoids explicitly representing the nonlinear feature space.
Motivation: Representer Theorems ensure that learned objects such as SVM hyperplanes, kernel k-means centers, and kernel PCA components lie in the span of training-point features.For SVMs this follows from Karush-Kuhn-Tucker conditions; other applications obtain it from their formulations.
Problem: The resulting Curse of Support makes prediction expensive because each test point must be compared with all training points contributing to the learned representation.Support sizes are predicted to grow unboundedly with training-set size, making this cost problematic for large datasets.
Problem: Large training sets can improve generalization while simultaneously slowing predictive routines.This creates a trade-off between statistical benefit and prediction cost.
Existing responses: Sparsity-promoting SVM regularizers and support-vector reduction have yielded empirical returns but have not systematically addressed other kernel algorithms or the underlying curse.The limitation concerns the scope and systematic treatment of the problem.

2 Related Work

Prior work uses randomized or structured embeddings to approximate nonlinear kernels in explicit feature spaces, but coverage has expanded unevenly across kernel families. This paper targets positive definite dot product kernels and extends the approach to compositional kernels, including homogeneous polynomial kernels.

Embedding approaches: Rahimi and Recht used Bochner’s theorem to embed translation-invariant kernel spaces into low-dimensional Euclidean spaces with small additive inner-product distortion.Their randomized maps approximate K(x,y) through an explicit Euclidean dot product with high probability.
Embedding approaches: Subsequent work generalized explicit feature maps to group-invariant, intersection, and RBF-related kernel families.These approaches broadened the kernel classes handled by randomized or structured embeddings.
Alternative approaches: Other approaches construct task-dependent embeddings or low-rank Gram-matrix approximations, whereas this work is most closely related to direct feature-map constructions.The related methods differ in whether they depend on a task or approximate the Gram matrix directly.
This paper: This paper constructs randomized maps Z: R^d → R^D for positive definite dot product kernels K(x,y)=f(⟨x,y⟩), preserving kernel values through Euclidean inner products with high probability.The construction relies on characterizing functions that generate positive definite kernels.
This paper: The method extends to compositional kernels K_co(x,y)=K_dp(K(x,y)) and includes homogeneous polynomial kernels outside the treatment described for homogeneous kernels by Vedaldi and Zisserman.The extension permits an arbitrary positive definite inner kernel K inside a dot product kernel K_dp.

3 A Characterization of Positive Definite Dot Product Kernels

The paper characterizes dot product kernels that remain positive definite across Euclidean spaces and Hilbert spaces through non-negative Maclaurin expansions. This characterization supplies the theoretical basis for the feature-map constructions, while domain and boundedness assumptions delimit its use.

Characterization: Schoenberg’s result underlies the construction by characterizing functions on the real line that generate positive definite dot product kernels.The paper observes that the unit-sphere restriction is not essential for the relevant characterization.
Proof ingredients: Non-negative combinations, products, and continuous limits of positive definite kernels remain positive definite.These closure properties support the sufficiency argument for kernels defined by non-negative Maclaurin expansions.
Scope and usefulness: Functions with non-negative Gegenbauer but not Maclaurin expansions may become indefinite beyond a finite dimensionality threshold.The paper therefore treats the stronger Maclaurin condition as more useful for constructions spanning all finite-dimensional spaces.
Scope and assumptions: Because dot product kernels are unbounded on non-compact domains, the analysis confines data to a compact domain Ω⊆B1(0,R) and assumes f is defined and differentiable on a suitable interval.If f has only a finite-radius domain around zero, input scaling can be used to define a related kernel.
Characterization: Positive definiteness over all finite-dimensional Euclidean spaces is equivalent to positive definiteness over Hilbert spaces.The equivalence is established in Lemma 4 by embedding finite sets from ℓ2 into finite-dimensional Euclidean spaces and applying Schoenberg’s theorem.
Characterization: A function f yields positive definite kernels over all finite-dimensional Euclidean spaces exactly when it is analytic with a Maclaurin expansion containing only non-negative coefficients.This is stated as Corollary 5.

4 Random Feature Maps

The paper constructs randomized feature maps for dot product kernels by sampling polynomial degrees and random sign projections, then proves unbiasedness and uniform approximation guarantees over compact domains.

Random Feature Maps: The feature map samples N from an external exponential-tail distribution and uses N independent Rademacher vectors to estimate polynomial terms.The distribution is P[N = n] = 1/p^(n+1) for p > 1; p = 2 is suggested in practice.
Random Feature Maps: Positive Maclaurin coefficients enable real-valued embeddings, while negative coefficients would require pseudo-Euclidean feature spaces.The coefficient positivity preserves positive definiteness of the resulting dot product kernels.
Random Feature Maps: The one-dimensional estimator is unbiased, and concatenating D independent copies preserves the kernel expectation while reducing variance.For all x, y in the domain, E[Z(x)Z(y)] = K(x, y), and the multidimensional map is scaled by 1/√D.
Random Feature Maps: The external distribution bounds the estimator, allowing Hoeffding bounds to control deviations of the randomized linear kernel.Without this distribution, the estimator can depend on the unbounded sampled degree N, preventing the needed bounded-variable argument.
Uniform Approximation: Lipschitz control and covering arguments extend pointwise approximation to uniform approximation over the entire compact domain.The analysis bounds the error function’s Lipschitz constant and applies an epsilon-net argument before establishing the main theorem.
Uniform Approximation: The required embedding dimension depends on input dimension, accuracy, confidence, and kernel-specific domain parameters, with stronger non-logarithmic kernel dependence than translation-invariant results.The kernel-specific dependence reflects the unbounded nature of dot product kernels and the use of absolute deviation guarantees.
An Alternative Feature Map: An approximate feature map for a compositional kernel yields an (epsilon + epsilon_1)-accurate estimate when the intermediate kernel approximation is epsilon_1-accurate.This provides the stated extension from dot product kernels to compositional kernels.

5 Generalizing to Compositional Kernels

The paper extends randomized feature-map constructions from dot product kernels to compositional kernels Kco(x, y) = Kdp(K(x, y)). Under boundedness, Lipschitz, and unbiasedness assumptions, concatenated randomized maps approximate the compositional kernel uniformly with high probability.

A compositional kernel Kco(x, y) = Kdp(K(x, y)) remains positive definite when Kdp and K are positive definite.This follows from classical results by FitzGerald et al. or from Schoenberg’s result together with Mercer’s theorem.
The construction assumes black-box access to feature maps for K that are bounded, Lipschitz on expectation, and unbiased estimators of K.These feature maps are used to construct randomized features for Kco.
The expected inner product of the constructed feature map equals the compositional kernel, providing an unbiased estimator before concentration analysis.The construction then bounds the feature map and studies its expected Lipschitz properties.
Uniform approximation over a compact domain is obtained by combining concentration on an ε-net with Lipschitz control of the estimation error.The analysis uses an ε-net over Ω and bounds the probability that the error function fails to be sufficiently Lipschitz.
Theorem 16 guarantees high-probability approximation under the stated kernel and feature-map conditions, with input-space dependence similar to the dot product-kernel case.The main non-logarithmic kernel-specific dependence is through C1, which reflects the largest possible oracle-feature value and relates to the range of K.

6 Experiments

Experiments evaluate RF and H0/1 feature maps on toy kernels and benchmark datasets, measuring approximation error, accuracy, training/testing times, and speedups. H0/1 generally improves accuracy at small D, while its higher feature-construction and testing costs create trade-offs at larger D.

The Heuristic H0/1: H0/1 estimates the constant and linear Maclaurin terms exactly, appending original features while using random features for higher-order terms.RF uses only random features; H0/1 combines original features with random features.
The Heuristic H0/1: H0/1 uses (d + D) test features instead of D, creating a small testing overhead relative to RF.Its feature maps also require more randomness when estimating higher-order terms.
Toy Experiments: H0/1 shows a sharper error drop than RF across the toy-kernel experiments as D increases.The experiments average absolute kernel-matrix entry errors over five runs across varying input dimensions and feature counts.
Toy Experiments: Error rates vary considerably across kernels because their value ranges differ, with Kh in [−1, 1], Kp up to 1024, and Ke up to 2.73.The feature-map errors vary similarly across these kernels.
UCI Dataset Experiments: On four benchmark datasets, H0/1 achieves much higher accuracy with small D, while its testing overhead becomes large as D increases.The extra feature dimension is modest, averaging d = 45 for the six datasets considered; training-time effects are less clear.
UCI Dataset Experiments: Both RF and H0/1 provide significant training and testing speedups with competitive accuracy, with H0/1 reaching this trade-off at lower D.In some cases, H0/1’s moderate accuracy reduction accompanies a spectacular increase in training and testing speed.