Black Box Quantiles for Kernel Learning

Anthony Tompkins, Ransalu Senanayake, Philippe Morere, Fabio RamosAISTATS 2019 · OpenReview

Introduction

In kernel-based machine learning, such as Gaussian Processes or Support Vector Machines, the choice of the kernel function is paramount. It defines the similarity between data points and encodes fundamental assumptions about the data's structure, including smoothness and periodicity. Traditionally, selecting an appropriate kernel has been an "art," requiring significant human expertise to manually choose or combine standard kernels like the Radial Basis Function (RBF) or Periodic kernels. This manual process is often inflexible and fails to capture the nuances of real-world data, particularly in dynamic environments like robotics.

To address these challenges, we introduce Black Box Quantiles (BBQ), a framework designed to automatically learn the "shape" of a kernel directly from data. By representing a kernel’s spectral measure as a parameterized quantile function, BBQ provides a flexible, end-to-end approach to discovering complex patterns without human intervention.

The BBQ Framework

The core of the BBQ method leverages Bochner’s Theorem, which establishes a correspondence between every stationary, positive-definite kernel and a probability measure in the spectral (frequency) domain. Rather than attempting to learn a probability density function (PDF)—which is constrained by the requirement to integrate to unity—BBQ parameterizes the quantile function $Q(p)$.

The BBQ framework: From QMC samples to learned feature vectors via a parameterized quantile function.

The quantile function is represented using learnable horizontal and vertical offsets, ensuring it remains non-decreasing through Monotonic Cubic Hermite Interpolation (PCHIP). This ensures the resulting kernel is always valid and positive-definite. To transform this learned quantile into a usable kernel, the framework employs Quasi-Monte Carlo (QMC) sampling (e.g., Sobol or Halton sequences) to construct Random Fourier Features (RFF). These features approximate the kernel more accurately and efficiently than standard Monte Carlo methods. The entire system is optimized by minimizing a loss function, such as Negative Log-Marginal Likelihood (NLML), allowing the kernel parameters to be learned alongside model weights.

Key Insights and Advantages

A primary advantage of parameterizing the quantile function over the PDF is mathematical stability; as long as the function is non-decreasing, it is guaranteed to represent a valid kernel. Furthermore, BBQ can automatically discover periodic patterns. By adjusting the "steps" in the quantile function, the model implicitly creates "spikes" in the spectral density, which correspond to periodicity in the input domain.

Approximation error comparison: QMC methods (Sobol, Halton) consistently outperform standard Monte Carlo (MC) sampling across varying numbers of features.

The integration of QMC is also pivotal. As shown in empirical evaluations, low-discrepancy sequences consistently provide lower approximation errors than standard random sampling, regardless of the number of features used. This efficiency allows BBQ to maintain a computational complexity of $O(M^2N)$, where $M$ is the number of features, making it significantly faster than traditional Spectral Mixture (SM) kernels that typically scale at $O(N^3)$.

Experimental Results

BBQ was evaluated across a variety of synthetic and real-world datasets, including the Mauna Loa CO2 and International Airline Passenger datasets, as well as high-dimensional regression tasks from the UCI repository.

  • Accuracy: BBQ consistently outperformed standard RBF kernels and matched or exceeded the performance of SM kernels in terms of Root Mean Square Error (RMSE) on extrapolation tasks.
  • Texture Synthesis: In complex visual tasks like the "Pores" texture reconstruction, BBQ successfully captured patterns that standard kernels could not.
  • Robustness: BBQ demonstrated greater stability during optimization compared to SM kernels, which are often sensitive to parameter initialization.

Limitations and Future Work

While BBQ is highly effective, its current implementation learns one quantile per dimension for multi-dimensional data, which may limit its ability to capture correlations between different input variables. Future research will explore the use of Copulas to model these dependencies and the development of non-stationary kernels to handle data with evolving patterns over time or space.

Summary updated

Abstract

Kernel methods have been successfully used in various domains to model nonlinear patterns. However, the structure of the kernels is typically handcrafted for each dataset based on the experience of...
BibTeX
@inproceedings{tompkins2019black,
  author = {Anthony Tompkins and Ransalu Senanayake and Philippe Morere and Fabio Ramos},
  title = {{Black Box Quantiles for Kernel Learning}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=cIVvuQmSUCV},
}
Figure