A Sparse Nonlinear Bayesian Online Kernel Regression

M. Geist, Olivier Pietquin, Gabriel Fricout2008 · DOI

TL;DR

This paper introduces a novel online kernel regression method that efficiently approximates nonlinear functions from noisy data. It achieves sparsity in kernel selection and quantifies uncertainty in predictions, making it suitable for applications where understanding prediction confidence is crucial.

What Problem Does This Paper Address?

Engineers often need to estimate unknown functions from observed data, a task known as function approximation or generalization. While many methods exist, they typically rely on batch processing (requiring all data upfront) and often use linear parameterizations. Furthermore, existing approaches rarely quantify the uncertainty reduction gained from acquiring more data, which can be vital for decision-making. This paper tackles the challenge of developing an online method that can incrementally learn from new data, handle nonlinear functions, achieve sparsity (using fewer resources), and provide robust uncertainty estimates.

Methods

The proposed approach combines several key techniques:

  • Dictionary Method for Sparsity: Before online learning begins, a preprocessing step uses a dictionary method to identify a sparse set of "basis" kernels. This effectively selects a compact representation of the function's underlying structure, reducing the number of kernels needed for regression.
  • Bayesian Filtering Framework: The core of the online learning is built upon a Bayesian filtering framework. This allows for sequential estimation of the function's parameters (represented as a hidden state) and maintains a probability distribution over these parameters, thus quantifying uncertainty.
  • Sigma Point Kalman Filter (SPKF): To handle the nonlinear nature of the problem, the authors employ a Sigma Point Kalman Filter. This is a nonlinear extension of the Kalman filter that approximates probability distributions by deterministically selecting "sigma points." This is more computationally efficient than methods that linearize nonlinear functions.
  • State-Space Representation: The problem is framed as a state-space model where the parameters of the kernel regression are the hidden state, and the observed data points are the observations.

Datasets

The paper uses a synthetic dataset for evaluation:

  • Cardinal Sine (sinc(x)) function: This function is used as a benchmark for regression. The data consists of noisy observations of this function sampled from a uniform distribution over X = [-10, 10].

Key Insights and Ideas

  • Sparsity via Dictionary Learning: The dictionary method effectively pre-selects a compact set of kernels, leading to a sparse representation without needing to tune kernel parameters online. This is a significant advantage for computational efficiency.
  • Online Learning with Uncertainty: The Bayesian filtering approach, specifically using SPKF, allows for continuous updates as new data arrives, while simultaneously providing a confidence interval for predictions. This is crucial for applications where knowing "how sure" the model is matters.
  • Bridging Batch and Online: The method cleverly separates the sparse kernel selection (offline) from the online regression, offering the benefits of both approaches.
  • Generalizability: The framework is presented as extendable to other kernel types and potentially non-stationary functions.

Key Results

  • Improved RMSE: The proposed algorithm achieved a lower Root Mean Square Error (RMSE) compared to several state-of-the-art batch and online methods, including SVM, RVM, and MCMC, on the cardinal sine regression task. For instance, with 50 samples, the RMSE was 0.0676 ± 0.0176, and with 200 samples, it was 0.0397 ± 0.0065.
  • Fewer Kernels: The method achieved these results with a significantly smaller number of kernels (an average of 9.6 kernels for 200 samples) compared to methods like SVM (28.0 kernels).
  • Quantifiable Uncertainty: The paper demonstrates the ability to derive confidence intervals for predictions, which are shown to be larger in regions where samples are less frequent, reflecting the model's uncertainty.

Limitations and Future Work

  • Offline Sparsification: The dictionary computation for kernel selection is currently an offline process. The authors aim to extend this to an online sparsification procedure.
  • Artificial Process Noise: The choice of artificial process noise for the filter is still an open research problem. The authors suggest exploring more efficient methods for estimating this noise.
  • Extension to Noisy Mappings: The framework could be extended to scenarios where only a noisy known nonlinear mapping of the function of interest is available, rather than directly observing the function's output.
  • Parameter Tuning: While the paper notes that parameters were not finely tuned, further investigation into optimal parameter selection could yield even better results.

Summary updated

Abstract

©2008 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
BibTeX
@misc{geist2008sparse,
  author = {M. Geist and Olivier Pietquin and Gabriel Fricout},
  title = {{A Sparse Nonlinear Bayesian Online Kernel Regression}},
  year = {2008},
  doi = {10.1109/advcomp.2008.7},
}
Figure