Hilbert Space Embeddings of Predictive State Representations | Byron Boots et al. | ResearchPod

Transcript: Hilbert Space Embeddings of Predictive State Representations

Alex: You can predict a robot’s motion without first inventing its hidden states. Byron Boots, Arthur Gretton, and Geoffrey Gordon propose learning directly from actions and observations, including continuously varying measurements. Their method paper, “Hilbert Space Embeddings of Predictive State Representations,” reports competitive or better predictions across several benchmarks.

Sam: Predicting from observations sounds useful, but the practical question is what this changes. Who would reach for this approach?

Alex: Researchers learning models of controlled systems from sensory data, especially when the underlying state is not directly visible. Think of a robot arm observed through a depth camera. The promise is to learn how future observations depend on actions, without requiring labels for hidden states. We’ll unpack that idea, compare it with earlier approaches, and ask how much the experiments establish.

Sam: Let’s start with the state itself. If it isn’t a hidden physical description, what does the model actually remember?

Alex: It remembers predictions. A predictive state representation defines state through the expected outcomes of future observable experiments. Each experiment specifies actions to take and observations that might follow. The paper calls these experiments “tests,” and calls the past sequence of actions and observations a “history.”

Sam: So state means what the system might do next, given what we’ve already seen. But surely you cannot store every possible future experiment?

Alex: You need a sufficient collection, called a core set. Its predictions contain enough information to derive predictions for all other tests. That is the defining assumption. Instead of retaining the entire history, you retain this predictive summary.

Sam: That explains the representation. Why did continuous measurements make earlier versions difficult to learn?

Alex: Many learning algorithms assumed a modest number of discrete actions and observations. With continuous measurements, exact values rarely repeat. You cannot reliably estimate a separate probability for every action and observation combination. Earlier continuous approaches used kernel density estimation or particular families of distributions, with drawbacks including slow statistical convergence and difficult numerical integration.

Sam: Hidden-state models already address partially observed systems. What advantage do the authors claim over learning one of those?

Alex: Predictive states are defined entirely through observable quantities. Earlier spectral learning methods recovered discrete predictive models by manipulating observed moments, avoiding local search. The authors contrast that with expectation maximization, a common hidden-state learning procedure that can converge slowly or reach bad local optima. This paper extends the predictive approach beyond small discrete spaces.

Hilbert Space Embeddings of Predictive State Representations

Byron Boots, Arthur Gretton, Geoffrey J. Gordon

Sep 26, 2013·8:40·arxiv·Original Paper

Predictive State Representations (PSRs)Hilbert space embeddings of distributionsReproducing Kernel Hilbert Space (RKHS)Conditional embedding operatorsDynamical systemsReproducing Kernel Hilbert Spaces (RKHS)

Listen

9 min

Summary

Understanding Dynamical Systems

Predictive State Representations (PSRs) offer a powerful way to model dynamical systems by tracking the probabilities of future observable events (tests) based on past experiences (histories). Unlike latent-variable models like Hidden Markov Models, which rely on unobserved states, PSRs are defined entirely by observable data, making them statistically consistent and easier to learn. However, traditional PSR algorithms struggle with continuous actions and observations because they often require data-heavy density estimation or discrete binnings that fail for complex, high-dimensional systems.

The Hilbert Space Approach

This paper generalizes PSRs to handle continuous systems by leveraging Hilbert space embeddings. Instead of tracking discrete probabilities, the authors embed distributions of tests and histories into Reproducing Kernel Hilbert Spaces (RKHSs). By representing the state as a nonparametric conditional embedding operator, the model can capture near-arbitrary continuous stochastic processes.

Filtering with Kernel Bayes' Rule

To update the model as new actions and observations arrive, the authors apply a kernelized version of Bayes' rule. This allows for recursive state updates directly within the Hilbert space. By using the "kernel trick," the authors demonstrate how to perform this filtering efficiently using Gram matrices, effectively bypassing the need to store infinite-dimensional operators explicitly. The result is a highly flexible model that can learn from continuous sensory data without needing labels for latent variables.

Performance and Significance

Experiments on synthetic nonlinear systems, real-world robotic slot car telemetry, and robot arm end-effector tracking demonstrate that HSE-PSRs consistently outperform competing methods like Kernelized Linear Dynamical Systems (K-LDS) and Input-Output HMMs. This approach provides a robust, principled framework for learning control-dependent dynamics in scenarios where traditional parametric assumptions are invalid.

Key Terms and Definitions

Predictive State Representation (PSR) — A model for stochastic processes that uses a set of predictions about future observable events as the state.
Hilbert Space Embedding — A mapping of probability distributions into a high-dimensional feature space (RKHS) where distributions can be treated as points or operators.
Kernel Bayes' Rule (KBR) — A technique for performing Bayesian updates within an RKHS, allowing for the calculation of conditional distributions without explicit density estimation.
Core Set of Tests — A set of future action-observation sequences whose predicted success probabilities are sufficient to determine the predictions of all other possible future sequences.
Reproducing Kernel Hilbert Space (RKHS) — A Hilbert space of functions where evaluation is a continuous linear functional, allowing the use of the kernel trick to handle complex, nonlinear relations.

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.

Hilbert Space Embeddings of Predictive State Representations: Research Paper Podcast