Probabilistic structure discovery in time series data

David Janz, Brooks Paige, Tom Rainforth, Jan-Willem van de Meent, Frank Wood

TL;DR

This paper moves beyond greedy optimization for discovering Gaussian Process (GP) kernel structures by adopting a fully Bayesian approach. By inferring a posterior distribution over kernel compositions rather than just picking a single "best" one, the authors achieve significantly better-calibrated uncertainty estimates for time series forecasting.

What Problem Does This Paper Address?

Gaussian Processes are a staple of time series analysis because they provide both flexible regression and built-in uncertainty estimates. A key strength is their interpretability: by composing simple "base" kernels (like linear or periodic) through addition and multiplication, one can build a model that reflects specific data characteristics like trends and seasonality.

However, finding the right kernel structure is hard. Existing methods, such as Automatic Bayesian Covariance Discovery (ABCD), typically use a greedy search to find the single kernel structure that maximizes marginal likelihood. While efficient, this approach has two major flaws:

  1. Overconfidence: It ignores model uncertainty. By committing to one structure, the model often produces narrow, overconfident prediction intervals that fail to capture the true range of possibilities when extrapolating.
  2. Local Optima: Greedy search can easily get stuck, missing other plausible "explanations" (kernel structures) for the data.

Methods

The authors introduce a fully Bayesian framework to infer the distribution over both the kernel structure ($k$) and its hyperparameters ($\theta$).

  • Prior over Structures: They define a prior $p(k)$ using a Stochastic Context-Free Grammar (SCFG). This grammar allows for the hierarchical composition of base kernels—Linear (LIN), Squared Exponential (SE), Periodic (PER), and Rational Quadratic (RQ)—using addition and multiplication rules.
  • Inference via Population Monte Carlo (PMC): Instead of searching for one best model, the system maintains a population of "particles," where each particle represents a specific kernel structure and set of parameters.
  • Resample-Move Algorithm: To explore the model space, they use a two-step mutation process:
  • Structural Mutation: Randomly changing the kernel tree (e.g., replacing a base kernel or adding a new branch).
  • Parameter Update: Using Hamiltonian Monte Carlo (HMC) to efficiently sample the hyperparameters $\theta$ for a given structure.
  • Implementation: The approach is implemented in Anglican, a probabilistic programming language, which allows these complex sampling steps to be integrated into a larger modeling pipeline.

Datasets

The primary evaluation is performed on the Mauna Loa CO2 dataset, a standard benchmark in GP literature. The models are trained on data from 1957 to 1983 and tasked with extrapolating (predicting) the CO2 levels from 1984 to 2000.

Key Insights and Ideas

  • Better Calibration through Averaging: The core "aha moment" is that the predictive distribution becomes a weighted mixture of multiple GPs. If several different kernel structures explain the training data well but diverge in their future predictions, the Bayesian approach will naturally widen the uncertainty bands to account for this disagreement.
  • Capturing Multiple Modes: Figure 2 illustrates how different "particles" represent competing explanations. One might emphasize a rational quadratic component while another focuses on a specific periodic structure.
  • Interpretable Uncertainty: Unlike deep learning models where uncertainty is often a black-box metric, here the uncertainty is tied to human-readable kernel formulas, providing insight into why the model is uncertain (e.g., "I'm not sure if this trend is linear or quadratic").

Key Results

The paper demonstrates a clear qualitative and quantitative advantage over greedy optimization:

Figure 1: Regression of the Maunu Lao CO2 dataset [16]. Models are trained on data from 1957 through 1983 (red line); we compare the extrapolation to collected data from 1984 through 2000. Median plotted, 10-90 percentile region shaded. (1a) The learned best-fit model and model parameters using ABCD fits the training data closely, but yields overconfident predictions in the extrapolation. (1b) Averaging over multiple plausible models yields better-calibrated uncertainty estimates.
  • Greedy Optimization (Fig 1a): Fits the training data closely but produces very narrow uncertainty bands in the extrapolation phase. These bands fail to encompass the actual observed data points in the later years, indicating overconfidence.
  • Bayesian Inference (Fig 1b): By averaging over multiple plausible models, the 10-90 percentile region is much wider and better calibrated, successfully capturing the true data trajectory during extrapolation.

Limitations and Future Work

  • Computational Cost: While not explicitly detailed in a table, a population-based sampling approach (PMC + HMC) is inherently more computationally expensive than a greedy search. Scaling this to very large datasets or extremely complex grammars may require further optimization.
  • Grammar Design: The results depend on the choice of base kernels and grammar rules. Future work could involve learning the grammar itself or expanding the library of base kernels to handle more diverse time series phenomena.

Summary updated

Abstract

Existing methods for structure discovery in time series data construct interpretable, compositional kernels for Gaussian process regression models. While the learned Gaussian process model provides posterior mean and variance estimates, typically the structure is learned via a greedy optimization procedure. This restricts the space of possible solutions and leads to over-confident uncertainty estimates. We introduce a fully Bayesian approach, inferring a full posterior over structures, which more reliably captures the uncertainty of the model.
BibTeX
@misc{janz2016probabilistic,
  author = {David Janz and Brooks Paige and Tom Rainforth and Jan-Willem van de Meent and Frank Wood},
  title = {{Probabilistic structure discovery in time series data}},
  year = {2016},
  eprint = {1611.06863},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1611.06863},
}
Figure