Probabilistic kernel least mean squares algorithms

Il Memming Park, Sohan Seth, Steven Van Vaerenbergh

TL;DR

This paper provides a formal Bayesian foundation for the Kernel Least Mean Squares (KLMS) algorithm, revealing it to be an approximate Kalman filter that discards its own uncertainty. By leveraging this state-space interpretation, the authors derive principled extensions that handle "forgetting" in non-stationary environments and adapt the algorithm for count data (Poisson) and binary classification (Logistic).

What Problem Does This Paper Address?

Adaptive filtering is essential for real-time learning in changing environments. The Kernel Least Mean Squares (KLMS) algorithm is a popular choice because it is computationally efficient and handles nonlinearities well. However, it has three major drawbacks:

  1. Infinite Growth: Naive implementations grow in memory size with every new data point.
  2. Limited Scope: It is designed for regression (continuous outputs) and doesn't naturally handle discrete labels or count data.
  3. The "Tracking Hack": While KLMS is often used to track moving targets by keeping a constant learning rate, this is usually treated as a heuristic "hack" rather than a theoretically grounded method.

The authors aim to bridge the gap between the simple, stochastic gradient descent (SGD) roots of KLMS and the rigorous framework of Bayesian state-space modeling.

Methods

The researchers re-derive KLMS from a Bayesian filtering perspective. They show that the standard KLMS update rule is mathematically equivalent to finding the Maximum A Posteriori (MAP) estimate of a state-space model where the weights undergo a "random walk" (diffusion).

Key methodological innovations include:

  • Approximate Inference: To keep the algorithm's complexity at $O(n)$, they assume the posterior distribution is a delta function at the MAP estimate, effectively "forgetting" the covariance (uncertainty) at each step.
  • fKLMS (Forgetful KLMS): They replace the random walk with an Ornstein-Uhlenbeck process. This introduces a leakage factor ($\lambda$) that causes old observations to decay exponentially, allowing for principled pruning of the model to keep it compact.
  • Generalized Observation Models: They swap the standard Gaussian likelihood (mean squared error) for Poisson and Bernoulli likelihoods. They demonstrate that even with these non-linear models, the update remains a simple one-dimensional optimization problem for a single scalar coefficient ($\alpha_k$) at each time step.

Datasets

The authors evaluated their extensions using several scenarios:

  • Synthetic Non-stationary Data: A spatio-temporal Gaussian process with additive noise to test tracking performance.
  • Neural Simulation: A drifting "tuning curve" (common in neuroscience) to test the Poisson-KLMS extension.
  • Binary Classification: A shifting circular boundary to test the Logistic-KLMS extension.
  • Real-world Wireless Data: Data from a wireless communication testbed (MIMO system) featuring a nonlinear Rayleigh fading channel to compare prediction errors (NMSE) against existing methods like NORMA and QKLMS.

Key Insights and Ideas

  • KLMS is a Kalman Filter in Disguise: The most significant "aha moment" is that the constant learning rate in LMS/KLMS isn't just a trick—it corresponds to the ratio between diffusion variance and noise variance in a non-stationary model.
  • The Cost of Efficiency: The linear time complexity of KLMS comes from a specific sacrifice: it ignores the covariance of the weights. This means the algorithm treats all directions in the feature space as equally uncertain.
  • Principled Forgetting: By modeling the weights as a process that leaks toward the origin, "forgetting" becomes a natural part of the math rather than an ad-hoc pruning rule. This allows the model to stay small without losing accuracy on the most recent, relevant data.

Key Results

  • Superior Tracking: The "forgetful" extension (fKLMS) outperformed standard KLMS and Quantized KLMS (QKLMS) on non-stationary tasks, achieving lower normalized mean squared error (e.g., -3.93 dB vs -3.33 dB in simulations).
  • Versatility: The Poisson and Logistic extensions successfully tracked shifting distributions that standard KLMS simply cannot handle.
  • Hardware Validation: In the wireless testbed experiment, fKLMS and QKLMS showed similar high performance, significantly outperforming linear methods (NLMS) and older regularized kernels (NORMA).

Limitations and Future Work

  • Loss of Confidence: Because the algorithm discards the covariance matrix to remain fast, it cannot provide "confidence intervals" or uncertainty estimates for its predictions.
  • Hyperparameter Sensitivity: The model introduces new parameters (like diffusion variance $\sigma^2_d$ and the forgetting factor $\lambda$). The paper does not provide an automated way to tune these in real-time, suggesting Expectation-Maximization (EM) or sampling methods as future research directions.
  • Theoretical Convergence: While the Gaussian version has frequentist convergence guarantees, the authors note that formal convergence proofs for the Poisson and Logistic variants are still needed.

Summary updated

Abstract

The kernel least mean squares (KLMS) algorithm is a computationally efficient nonlinear adaptive filtering method that “kernelizes” the celebrated (linear) least mean squares algorithm. We demonstrate that the least mean squares algorithm is closely related to the Kalman filtering, and thus, the KLMS can be interpreted as an approximate Bayesian filtering method. This allows us to systematically develop extensions of the KLMS by modifying the underlying state-space and observation models. The resulting extensions introduce many desirable properties such as “forgetting”, and the ability to learn from discrete data, while retaining the computational simplicity and time complexity of the original algorithm.
BibTeX
@inproceedings{park2014probabilistic,
  author = {Il Memming Park and Sohan Seth and Steven Van Vaerenbergh},
  title = {{Probabilistic kernel least mean squares algorithms}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2014},
  url = {https://openreview.net/forum?id=b8Be3aq_xjR},
}

Loading related content...

Figure