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.
- 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).
- 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.
- 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.
- 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