PaperlayerView exact revision on arXiv

Source-linked AI summary

A la Carte - Learning Fast Kernels

Zichao Yang, Alexander J. Smola, Le Song, Andrew Gordon Wilson

arXiv:1412.6493v1cs.LGstat.ML

TL;DR

Kernel learning faces a speed–flexibility tradeoff, despite the value of expressive kernels for large modern datasets. This paper learns kernel properties through lightly parametrized Fastfood expansions, including grouped spectral frequencies. The proposed methods are reported to perform well across diverse problems in predictive accuracy, runtime, and memory consumption.

  • Problem

    Kernel methods trade scalability for flexibility, while fast expansions often require choosing a kernel in advance even when the suitable kernel may be unknown or unavailable in closed form.

    Source: §1 · p. 1

  • Method

    The paper develops kernel-learning methods based on Fastfood expansions that learn spectral properties, including properties of groups of frequencies, with light parametrization.

    Source: §1 · pp. 1–2

  • Results

    The proposed methods show impressive performance across a large, diverse collection of problems in predictive accuracy, training and test runtime, and memory consumption.

    Source: §6 · p. 15

  • Takeaways & Limitations

    The work demonstrates that kernel methods can be simultaneously scalable and expressive.

    Source: §6 · p. 15

    The framework assumes an efficient Fastfood basis expansion for kernels of interest and a Q-component mixture model for kγ.

    Source: §4.1 · pp. 5–6

Abstract

from arXiv · show

Kernel methods have great promise for learning rich statistical representations of large modern datasets. However, compared to neural networks, kernel methods have been perceived as lacking in scalability and flexibility. We introduce a family of fast, flexible, lightly parametrized and general purpose kernel learning methods, derived from Fastfood basis function expansions. We provide mechanisms to learn the properties of groups of spectral frequencies in these expansions, which require only O(mlogd) time and O(m) memory, for m basis functions and d input dimensions. We show that the proposed methods can learn a wide class of kernels, outperforming the alternatives in accuracy, speed, and memory consumption.

1 Introduction

Kernel methods face a tradeoff between speed and flexibility, even though expressive kernel learning is especially valuable on large datasets. This work introduces flexible, scalable kernel-learning methods and reports advantages in accuracy, speed, and memory consumption.

1 Introduction

  • Expressive kernel learning is most needed on large modern datasets, yet kernel methods typically trade speed for flexibility.Learning a kernel can lead to slow, expensive function classes, while many fast classes are not adaptive.Source: §1 · p. 1
  • Spectral kernels can require many basis functions and hyperparameters, whereas Random Kitchen Sinks and Fastfood provide efficient expansions only for kernels chosen in advance [Wilson and Adams, 2013; Rahimi and Recht, 2009; Le et al., 2013].A suitable kernel may be difficult to know a priori or unavailable in closed form.Source: §1 · p. 1
  • The proposed family includes flexible kernels, including a novel piecewise radial kernel.Source: §1 · p. 1
  • The methods learn groups of Fastfood spectral frequencies with few parameters, allowing many basis functions without overfitting and without requiring specially structured inputs.Individually tuning every frequency can overfit and create local optima and computational limits.Source: §1 · p. 2
  • Across a wide range of real datasets, the four proposed methods show major advantages in accuracy, speed, and memory consumption.Source: §1 · p. 2

2 Related Work

Prior work offers either fixed fast kernel expansions or more flexible approaches with computational or structural constraints. This paper proposes learning both the weights and properties of Fastfood expansions, including through grouped spectral frequencies and flexible kernel families.

2 Related Work

  • Weighted sums of Random Kitchen Sinks expansions learn mixture weights from data while leaving the underlying, a priori chosen kernels fixed [Rahimi and Recht, 2009].Source: §2 · p. 2
  • Lu et al. [2014] separately train logistic models on distinct Random Kitchen Sinks expansions, then learn their weights by stochastic gradient descent, enabling parallelization.They report promising acoustic-modeling performance, sometimes outperforming deep neural networks.Source: §2 · p. 2
  • Lázaro-Gredilla et al. [2010] optimize all spectral-frequency locations in Random Kitchen Sinks within sparse spectrum Gaussian process regression.Source: §2 · p. 2
  • Fastfood approximates Random Kitchen Sinks sampling with fast matrix operations, using O(m log d) computations and O(m) memory for m basis functions and d input dimensions [Le et al., 2013].Its expansions perform similarly to Random Kitchen Sinks while being more efficient to compute.Source: §2 · p. 2
  • Spectral mixture kernels model spectral densities with scale-location mixtures of Gaussians, while GPatt extends scalable learning to incomplete grids but requires at least partial grid structure for efficiency [Wilson and Adams, 2013; Wilson et al., 2014].The spectral mixture kernels can require arbitrarily many basis functions and many free hyperparameters.Source: §2 · pp. 2–3
  • This work learns both the weights and properties of Fastfood expansions, including group-level spectral properties, Gaussian spectral mixtures, and novel piecewise linear radial kernels.The framework is presented as general purpose and does not require special data structure; the paper focuses on regression while noting extension to classification and non-Gaussian likelihoods without additional methodological innovation.Source: §2 · p. 3

3 Kernel Methods

Kernel methods represent predictions through kernel functions rather than directly manipulating potentially infinite-dimensional feature maps. Fastfood approximations use structured random matrices to construct efficient features, with scaling encoding spectral properties that can be adjusted for kernel customization.

3.1 Basic Properties

  • Mercer's theorem guarantees a feature map, while the representer theorem expresses the regularized-risk minimizer as a linear combination of kernel functions [Mercer, 1909; Kimeldorf and Wahba, 1970, Schölkopf et al., 2001].The kernel is required to be symmetric with positive-semidefinite finite Gram matrices.Source: §3.1 · p. 3
  • The kernel expansion becomes burdensome as the number of datapoints grows, motivating approximate explicit feature maps for the kernel.The approximation seeks a fast, memory-efficient feature representation.Source: §3.1 · p. 3, §3.2 · p. 3

3.2 Fastfood

  • For translation-invariant kernels, the spectral approach represents the kernel through a distribution over frequencies; Random Kitchen Sinks approximate the integral by sampling that distribution [Rahimi and Recht, 2009].For a Gaussian kernel, the spectral distribution is Gaussian.Source: §3.2 · pp. 3–4
  • Fastfood replaces spectral sampling with a combination of efficiently computable matrices chosen to provide randomness while retaining fast computation [Le et al., 2013].The Hadamard matrix admits O(d log d) multiplication, and its recursive construction supports that fast operation.Source: §3.2 · p. 4
  • Fastfood uses binary sign decorrelation and a random permutation, while its Gaussian matrix has iid N(0,1) diagonal entries; the resulting rows are iid Gaussian but not independent.The binary signs give zero mean in expectation over B, and reservoir sampling can generate the permutation through in-place swaps.Source: §3.2 · p. 4
  • The diagonal scaling matrix encodes kernel spectral properties, and adjusting it customizes kernels without losing the decomposition's computational benefits.The scaling uses the length of a frequency drawn from the spherically symmetric distribution defined by ρ(ω).Source: §3.2 · p. 4

4 `A la Carte

The section makes Fastfood expansions learnable across a range of kernel families, using spectral adjustments that can be grouped to limit the cost of optimizing individual frequencies.

4 `A la Carte

  • The `a la Carte` framework adjusts Fastfood spectra to learn a wide range of translation-invariant kernels, with grouped frequency parameters offering expressive but lightly parameterized models.Optimizing every frequency individually can be expensive and susceptible to over-fitting and undesirable local optima.Source: §4 · p. 5

4.1 Learning the Kernel

  • Gaussian-process learning uses an assumed Fastfood feature expansion and optimizes kernel parameters and noise variance through the negative log marginal likelihood.The exposition focuses on regression, while noting the methods can also be used for classification and non-Gaussian likelihoods.Source: §4.1 · pp. 5–6, §4.2 · p. 6

4.2 Marginal Likelihood

  • When Qm < n, the feature expansion is computationally preferable to standard Gaussian-process kernel representations, which require O(n^3) computations and O(n^2) memory.The solution stores O(Qm) parameters regardless of the number of inputs, and predictive-variance computation requires O(Q^2m^2n) computations.Source: §4.2 · p. 7

4.3 Gaussian Spectral Mixture Models

  • Gaussian spectral mixtures learn component weights, dispersion, and frequency locations by marginal likelihood optimization, and their expansion can approximate any translation-invariant kernel.The method can use about 10 rather than 104 free parameters compared with individually learning all md spectral frequencies.Source: §4.3 · pp. 7–8

4.4 Piecewise Linear Radial Kernel

  • The piecewise linear radial kernel provides rotation-invariant spectral flexibility and permits direct frequency sampling without computing the inverse Fourier transform.Its nonnegative hat-function basis can be mixed to approximate any radial kernel; equidistant inverse-CDF locations are chosen to reduce sampling variance.Source: §4.4 · pp. 8–10

4.5 Fastfood Kernels

  • FSARD learns Fastfood's scaling matrix to vary the spectral properties and approximate any radial kernel, while FSGBARD also optimizes the Gaussian and binary decorrelation matrices.Both retain the Hadamard matrix, preserving Fastfood's computational benefits.Source: §4.5 · p. 10

5 Experiments

The experiments evaluate the proposed kernel-learning methods on diverse UCI regression problems, including datasets with more than 2 million datapoints. Across the comparisons, GM and PWL lead in predictive accuracy while remaining competitive in runtime and memory.

5 Experiments

  • The evaluation spans diverse UCI regression problems and scales to more than 2 million datapoints.The authors note that Gaussian processes are generally intractable beyond 10^4 datapoints.Source: §5 · p. 10

5.1 Experimental Details

  • The comparison uses practical basis-function counts and leaves Q and m untuned, while allowing SSGPR a significantly larger parametrization.For GM and PWL, Q and m vary by dataset grouping; all other methods use Qm basis functions.Source: §5.1 · p. 12, Table 1
  • On smaller datasets, GM and PWL generally outperform the alternatives; on larger datasets, exact RBF and ARD kernels are intractable.The table reports RMSE across datasets, using exact kernels for small datasets and Fastfood expansions for medium and large datasets.Source: §5.1 · pp. 13–14, Table 1
  • GM and PWL continue to improve as basis functions increase, whereas SSGPR and FSGBARD become more susceptible to over-fitting.More basis functions add optimization parameters for SSGPR and, to a lesser extent, FSGBARD and FSARD, but not for GM and PWL.Source: §5.1 · p. 14
  • Across experiments, GM and PWL outperform alternatives in accuracy while requiring similar memory and runtime to the less expressive FARD model.The comparison covers average normalized log predictive accuracy, training time, test time, and memory.Source: §5.1 · p. 14, Figure 3 · p. 14, Figure 4 · p. 15
  • SSGPR ranks third in accuracy but requires more memory and training and testing time than the other models; FSGBARD is similarly accurate and more efficient.Without log transformation, GM is an average predictive-accuracy outlier and SSGPR is a memory outlier.Source: §5.1 · p. 15

6 Discussion

The paper presents kernel methods that combine scalability, expressiveness, and light parametrization by learning properties of groups of spectral frequencies in Fastfood expansions. It concludes that scalable and expressive kernel methods can be achieved together, while identifying automatic allocation of frequencies across groups as future work.

6 Discussion

  • The proposed methods learn properties of groups of spectral frequencies in Fastfood basis expansions with flexible, scalable, general-purpose, lightly parametrized methods.The authors report strong performance across predictive accuracy, training and test runtime, and memory consumption on a diverse collection of problems.Source: §6 · p. 15
  • Future work could automatically learn how many spectral frequencies to assign to each group.Source: §6 · p. 15
  • The authors conclude that kernel methods can be simultaneously scalable and expressive.They frame scalability and flexibility as linked goals: expressive methods are wanted for the largest datasets.Source: §6 · p. 15
Loading 1412.6493v1…