Hilbert Space Embeddings of Predictive State Representations

Byron Boots, Geoffrey J. Gordon, Arthur Gretton

TL;DR

This paper introduces HSE-PSRs, a framework that generalizes Predictive State Representations (PSRs) to continuous and high-dimensional domains using kernel methods. By embedding probability distributions into Reproducing Kernel Hilbert Spaces (RKHS), the authors create a model that learns complex dynamical systems from observable data without the local optima issues of latent-variable models like HMMs.

What Problem Does This Paper Address?

In machine learning, we often need to model "partially observable" systems—think of a robot that only sees a portion of its environment. Traditionally, we use Hidden Markov Models (HMMs), which track a "latent" (hidden) state. However, HMMs are notoriously hard to train because they rely on heuristics like Expectation-Maximization (EM), which often get stuck in local optima.

Predictive State Representations (PSRs) offer a clever alternative: instead of a hidden state, they represent the "state" as a set of predictions about future observable events (called "tests") given the past ("histories"). Because PSRs are defined entirely by observables, they can be learned more efficiently and reliably.

The catch? Traditional PSRs only work well for discrete, low-dimensional data. If you have a continuous stream of video or sensor data, you’ll likely never see the exact same observation twice, causing standard PSR learning algorithms to fail. This paper bridges that gap.

Methods

The authors leverage Hilbert Space Embeddings of distributions to create a nonparametric version of PSRs.

  1. Mean Maps & Covariance Operators: Instead of tracking individual probabilities, they map entire distributions of tests and histories into an infinite-dimensional feature space (the RKHS).
  2. Kernel Bayes’ Rule (KBR): To update the system's state as new actions are taken and observations are received, they use a "kernelized" version of Bayes' rule. This allows for Bayesian inference directly in the Hilbert space without ever needing to perform explicit density estimation or numerical integration.
  3. The "Kernel Trick": While the operators are theoretically infinite-dimensional, the authors provide a Gram Matrix formulation. This allows the model to be trained and updated using finite-dimensional matrices derived from the training data.
  4. Linearity in the RKHS: Even if the underlying system dynamics are highly nonlinear, the relationships between the embedded distributions in the RKHS are linear, making the math much more tractable.

Datasets

The authors evaluated their HSE-PSR model on three distinct benchmarks:

  • Synthetic Nonlinear System: A benchmark dynamical system with complex, oscillating state equations.
  • Slot Car Racing: Real-world data from a 1:32 scale slot car. Observations included 3D acceleration and orientation (IMU data), while the control input was the car's velocity.
  • Robot Arm (Barrett WAM): A high-dimensional task involving predicting the 3D position of a robot's end-effector based on 640x480 depth camera images and joint angles.

Key Insights and Ideas

  • State as an Operator: In this framework, the "state" is not a single vector but a conditional embedding operator. It essentially encodes the mapping from any future sequence of actions to the expected distribution of future observations.
  • Fixing HSE-HMMs: Previous attempts to use kernel methods for HMMs (HSE-HMMs) relied on awkward density estimation and couldn't handle actions. HSE-PSRs solve this by using the more robust Kernel Bayes' Rule and incorporating control inputs (actions) naturally.
  • No Parametric Assumptions: Unlike many continuous-state models that assume everything is Gaussian, HSE-PSRs are nonparametric. They can represent nearly any distribution, limited only by the choice of kernel.
  • Observable Consistency: The model maintains the core PSR advantage: it is learned entirely from sequences of actions and observations, avoiding the "hidden variable" trap.

Key Results

The HSE-PSR consistently outperformed or matched state-of-the-art baselines, including Kernelized Linear Dynamical Systems (K-LDS) and Input-Output HMMs.

  • Superior Accuracy: On the synthetic and slot car datasets, HSE-PSRs achieved the lowest Mean Squared Error (MSE) across long prediction horizons.
  • Handling High-Dimensionality: The robot arm experiment was the most impressive. While standard LDS and K-LDS models became unstable or produced poor predictions when faced with raw depth images, the HSE-PSR remained stable and provided significantly more accurate 3D position tracking.
  • Efficiency: By using the Gram Matrix formulation, the model could be updated recursively, making it suitable for filtering in real-time systems.

Limitations and Future Work

  • Scaling with Data: Like most kernel methods, the "state vector" size grows with the number of training samples. For very long trajectories, the model would eventually become computationally prohibitive without some form of "sparsification" or "budgeted" kernel approach.
  • Kernel Selection: The authors used the "median trick" for setting kernel bandwidth. While effective, the performance of the model is sensitive to these hyperparameters, and more automated ways to select kernels for dynamical systems would be a valuable next step.
  • Blind Policies: The current learning theory assumes data is collected via a "blind" policy. Extending this to more active, exploratory data collection could make the model even more robust for reinforcement learning applications.

Summary updated

Abstract

Predictive State Representations (PSRs) are an expressive class of models for controlled stochastic processes. PSRs represent state as a set of predictions of future observable events. Because PSRs are defined entirely in terms of observable data, statistically consistent estimates of PSR parameters can be learned efficiently by manipulating moments of observed training data. Most learning algorithms for PSRs have assumed that actions and observations are finite with low cardinality. In this paper, we generalize PSRs to infinite sets of observations and actions, using the recent concept of Hilbert space embeddings of distributions. The essence is to represent the state as a nonparametric conditional embedding operator in a Reproducing Kernel Hilbert Space (RKHS) and leverage recent work in kernel methods to estimate, predict, and update the representation. We show that these Hilbert space embeddings of PSRs are able to gracefully handle continuous actions and observations, and that our learned models outperform competing system identification algorithms on several prediction benchmarks.
BibTeX
@inproceedings{boots2013hilbert,
  author = {Byron Boots and Geoffrey J. Gordon and Arthur Gretton},
  title = {{Hilbert Space Embeddings of Predictive State Representations}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2013},
  url = {https://openreview.net/forum?id=4CXQW5brXYf},
}

Loading related content...

Figure