Probabilistic Programming with Gaussian Process Memoization

Ulrich Schaechtle, Ben Zinberg, Alexey Radul, Kostas Stathis, Vikash K. MansinghkaarXiv 2015 · arXiv

Introduction

Gaussian Processes (GPs) are a cornerstone of non-parametric regression, valued for their ability to provide principled uncertainty estimates. However, integrating GPs into complex, hierarchical probabilistic models remains a significant challenge. Traditionally, users must manually specify intricate covariance functions (kernels) and derive analytical posteriors—a process that is both error-prone and inflexible. Existing software often treats GPs as standalone regression tools rather than components of a larger probabilistic reasoning system.

This paper introduces gpmem, a novel "statistical memoizer" that embeds GPs directly into higher-order probabilistic programming languages (PPLs). By treating GPs as emulators that learn from function calls, the authors make GPs "first-class citizens," allowing them to be composed, nested, and reasoned about with unprecedented ease.

Methods: Gaussian Process Memoization

The core innovation is the concept of Gaussian Process Memoization. While traditional memoization caches exact function outputs to avoid redundant computation, gpmem returns a statistical emulator. This emulator, powered by a GP, provides a "best guess" and an uncertainty bound for inputs it hasn't yet encountered.

The authors implemented this in Venture, a general-purpose PPL. Venture is uniquely suited for this because it supports:

  • Foreign Interfaces: Allowing fast, optimized GP math (like Cholesky factorization) to run under the hood while maintaining high-level flexibility.
  • Stochastic Recursion: Necessary for building kernels using a "stochastic grammar" that can recursively combine simpler kernels into complex structures.
  • Inference Programming: Allowing users to mix different strategies, such as Metropolis-Hastings and gradient ascent, to tune GP hyper-parameters.

Compositional Structure Discovery

One of the most powerful applications of gpmem is the automatic discovery of data structure. By placing a prior over the structure of the kernel itself using a stochastic grammar, the system can infer whether a dataset is best described by linear trends, periodicities, or smooth variations.

Kernel composition and posterior predictive results. Top row (a-c) shows prior predictive samples from linear, periodic, and product kernels. Bottom row (d-f) shows the posterior predictive after observing data (marked with 'x').

As shown in the figure above, different kernels capture different aspects of the data. The product kernel ($K^{\text{linear}} \times K^{\text{periodic}}$) successfully captures the increasing amplitude of the periodic signal, a feat that would require manual derivation in traditional GP frameworks but is achieved here through simple composition.

Evaluation and Results

The authors evaluated gpmem on several benchmarks, including Mauna Loa CO2 concentrations and international airline passenger data.

Raw data for a synthetic benchmark showing a periodic signal with increasing amplitude.

Key findings include:

  • Robustness: The system successfully replicated classic results in outlier rejection by inferring hierarchical hyper-parameters with significantly less code than previous implementations (e.g., Neal, 1997).
  • Automated Statistician: For the Mauna Loa dataset, the system automatically discovered a complex "Linear + Periodic + Smooth + White Noise" kernel as the best fit.
  • Bayesian Optimization: A bandit formulation using Thompson sampling was implemented in fewer than 20 lines of code, effectively balancing exploration and exploitation.
  • Efficiency: Major applications like robust regression and structure learning shared a single 50-line library, demonstrating the extreme conciseness enabled by the gpmem abstraction.

Limitations and Future Work

While powerful, standard GP implementations scale at $O(n^3)$, making them computationally expensive for large datasets. Future work aims to incorporate low-rank approximations to improve scalability. Additionally, the authors propose generalizing the memoization idiom to other non-parametric models, such as Dirichlet or Wishart processes. Ultimately, this work paves the way for "time series search engines" where users can query large databases using natural language-like predicates to find specific patterns in sensor data.

Summary updated

BibTeX
@misc{schaechtle2015probabilistic,
  author = {Ulrich Schaechtle and Ben Zinberg and Alexey Radul and Kostas Stathis and Vikash K. Mansinghka},
  title = {{Probabilistic Programming with Gaussian Process Memoization}},
  year = {2015},
  eprint = {1512.05665},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1512.05665},
}
Figure