The Kernel Kalman Rule Ñ Efficient Nonparametric Inference with Recursive Least Squares

AAAI 2017

TL;DR

This paper introduces the Kernel Kalman Rule (KKR), a novel method for nonparametric inference in high-dimensional systems. KKR offers a computationally efficient and numerically stable alternative to existing Kernel Bayes' Rule (KBR) methods, achieving improved estimation accuracy in challenging nonlinear filtering tasks.

What Problem Does This Paper Address?

State estimation and prediction in complex, partially observable, and high-dimensional systems (like robotics) is a significant challenge. While traditional methods like the Kalman Filter work well for linear systems with Gaussian noise, they struggle with nonlinearities and high dimensions. Existing nonparametric methods, which embed probability distributions into reproducing kernel Hilbert spaces (RKHS), offer a promising avenue. However, these methods often rely on the Kernel Bayes' Rule (KBR), which suffers from poor computational scalability with the number of samples and can be numerically unstable. This paper aims to bridge this gap by providing a more efficient and robust nonparametric inference technique.

Methods

The core contribution is the Kernel Kalman Rule (KKR). The derivation of KKR is inspired by the recursive least squares (RLS) estimation framework, specifically drawing parallels to the Kalman filter's innovation update. Instead of directly manipulating complex kernel operators as in KBR, KKR minimizes a squared error objective in an RKHS. This leads to update equations for the mean embedding that are unbiased and have minimum variance.

Key aspects of the method include:

  • Kernel Trick: The method leverages the kernel trick to perform computations in a potentially infinite-dimensional RKHS using finite-dimensional kernel matrices.
  • Representer Theorem: This theorem is used to derive algorithms that only involve products and inversions of finite kernel matrices, making computations tractable.
  • Kernel Kalman Filter (KKF): By combining KKR with the kernel sum rule, the authors formulate the KKF for filtering tasks. This filter is more general than previous kernel-based filters and can handle partially observable systems.
  • Subspace Kernel Kalman Rule (subKKR): To further improve scalability for very large datasets, a subspace version is introduced. This method uses a subset of samples to span a feature space while using all training samples to estimate models, striking a balance between representation compactness and data utilization.

Datasets

The paper evaluates the proposed methods on:

  • Simulated 4-link pendulum task: Used for evaluating filtering performance.
  • Human motion capture data set (HuMoD): Used for testing the model on real-world, complex human motion data, including walking and running sequences with varying speeds and subject acceleration.
  • Simulated Gaussian distribution: Used for an initial experiment to compare KKR and KBR in a controlled setting.

No new benchmarks were introduced; rather, existing datasets were used to compare against established methods.

Key Insights and Ideas

  • RLS as a foundation for nonparametric inference: The paper demonstrates that the principles of recursive least squares can be effectively adapted to the RKHS setting, leading to a more stable and efficient inference mechanism than KBR.
  • KKR's computational advantage: By reformulating the problem in terms of RLS, KKR avoids the computationally expensive and potentially unstable inversions of large, complex kernel operators inherent in KBR.
  • KKF's generality: The Kernel Kalman Filter (KKF) offers a more flexible framework for nonlinear filtering, capable of handling partially observable systems, which is a significant improvement over some prior kernel-based filters.
  • Subspace KKR for scalability: The subspace approach is crucial for handling truly massive datasets, showing that efficient nonparametric inference doesn't necessarily require using all data points for every computation.

Key Results

  • Improved Estimation Accuracy: In experiments with a simulated Gaussian distribution, KKR achieved estimation accuracy comparable to maximum likelihood estimators and significantly outperformed KBR, which showed limited improvement with more updates.
  • Computational Efficiency: Table 1 shows that KKR is an order of magnitude faster than KBR for performing updates. The subKKR maintains computational efficiency even when using significantly more data points for learning.
  • Effective Filtering: The KKF and subKKF demonstrated superior performance in nonlinear filtering tasks (pendulum and quad-link) compared to other nonparametric methods, reaching performance levels close to traditional EKF and UKF.
  • Human Motion Prediction: The subKKF successfully reconstructed subject velocity from motion capture data, even in challenging scenarios with subject acceleration.

Limitations and Future Work

  • Hyper-parameter Optimization: While KKR makes hyper-parameter optimization more feasible than KBR, it remains crucial for achieving optimal performance, especially with complex kernels.
  • Learning Transition Dynamics: The paper assumes the conditional operator (representing system dynamics) is known. Future work could involve learning these dynamics within the RKHS, potentially using expectation-maximization algorithms, especially when information about the latent state is missing.
  • Recovering State-Space Distribution: The paper notes that recovering a valid state-space distribution from the learned mean map and covariance is an active research area, and suggests that various existing methods can be used with KKR for this purpose.

Summary updated

BibTeX
@inproceedings{2017kernel,
  title = {{The Kernel Kalman Rule Ñ Efficient Nonparametric Inference with Recursive Least Squares}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
}

Loading related content...

Figure