PaperlayerView exact revision on arXiv

Source-linked AI summary

Streaming Sparse Gaussian Process Approximations

Thang D. Bui, Cuong V. Nguyen, Richard E. Turner

arXiv:1705.07131v2stat.ML

TL;DR

Streaming GP models need to update their posterior and hyperparameters as data arrive, but existing approaches do not provide a satisfactory principled framework for doing so. This paper develops online sparse approximations that learn hyperparameters and optimise pseudo-inputs; it reports stronger performance than existing approaches across a range of regression datasets and promising binary-classification results.

  • Problem

    Existing sparse GP approaches lack a satisfactory framework for streaming data that updates both the posterior and hyperparameters while leveraging previously processed observations.

    Source: §1 · pp. 1–2

  • Method

    The framework uses pseudo-points to summarize old data and incrementally updates the approximate posterior, hyperparameters, and pseudo-input locations as new data arrive.

    Source: §1 · p. 2, §2 · pp. 2–3

  • Results

    The approach outperforms existing methods on a wide range of regression datasets and shows promising results on a binary-classification dataset.

    Source: §5 · p. 8

  • Takeaways & Limitations

    The framework extends online GP inference methods with principled hyperparameter learning and pseudo-input optimisation.

    Source: §1 · p. 2, §3.3 · p. 5

Abstract

from arXiv · show

Sparse pseudo-point approximations for Gaussian process (GP) models provide a suite of methods that support deployment of GPs in the large data regime and enable analytic intractabilities to be sidestepped. However, the field lacks a principled method to handle streaming data in which both the posterior distribution over function values and the hyperparameter estimates are updated in an online fashion. The small number of existing approaches either use suboptimal hand-crafted heuristics for hyperparameter learning, or suffer from catastrophic forgetting or slow updating when new data arrive. This paper develops a new principled framework for deploying Gaussian process probabilistic models in the streaming setting, providing methods for learning hyperparameters and optimising pseudo-input locations. The proposed framework is assessed using synthetic and real-world datasets.

1 Introduction

Sparse pseudo-point approximations reduce GP training and prediction costs while retaining accuracy, but existing methods lack a satisfactory framework for streaming data. This paper introduces principled online updates that learn hyperparameters and optimise pseudo-input locations.

1 Introduction

  • Pseudo-points reduce GP training and prediction costs from O(N^3) and O(N^2) to O(NM^2) and O(M^2), respectively, with M ≪ N.Mini-batch stochastic optimisation can further scale GPs to datasets with millions of points.Source: §1 · p. 1
  • Streaming GP methods need to update a previously fitted model as new data arrive, leveraging earlier data and computation when only current data are accessible.Retraining from scratch is intractable in practical settings, while using only recent data discards potentially informative older observations.Source: §1 · pp. 1–2
  • The proposed framework supports principled online hyperparameter learning and pseudo-input optimisation, extending earlier online VFE and EP approaches.It recovers Csató and Opper’s methods as special cases; their original work did not treat learning, and pseudo-inputs had previously been optimised with hand-crafted heuristics.Source: §1 · p. 2

2 Background

Sparse variational free energy (VFE) approximations use a small set of pseudo-points to make GP inference and learning computationally tractable. Standard stochastic optimisation is poorly suited to streaming data because it assumes random subsampling and repeated access to training data.

2 Background

  • The VFE bound can bring the approximate posterior closer to the exact posterior and can approximate the marginal likelihood for hyperparameter learning.Maximizing the bound with respect to q(f) reduces its KL divergence from the exact posterior.Source: §2 · p. 2
  • A sparse VFE approximation parameterizes the posterior using M pseudo-points that summarize the observations, making a tractable lower bound possible.The approximation sets q(f) = p(f\u0305u|u, θ)q(u), with q(u) a variational distribution over the pseudo-points.Source: §2 · p. 2
  • VFE learning has O(NM^2) complexity and prediction costs O(M^2) per test point, but good performance requires adapting pseudo-input locations across the training data.Stochastic optimisation can instead estimate the uncollapsed bound from a small random subset and update q(u) using noisy gradients.Source: §2 · p. 3
  • Stochastic mini-batch optimisation is ill-suited to streaming data because it assumes random sampling, repeated dataset access, and typically one gradient update per batch.Sequentially arriving data may not be iid; processing each batch only once can also risk forgetting older data without delicately tuned learning rates.Source: §2 · p. 3

3 Streaming sparse GP (SSGP) approximation using variational inference

The streaming framework propagates information from earlier data through a compact pseudo-point approximation, allowing online posterior and hyperparameter updates when only new observations are directly accessible.

3 Streaming sparse GP (SSGP) approximation using variational inference

  • The framework updates the posterior and hyperparameters as data arrive, propagating the effect of old data through the previous posterior while adapting pseudo-inputs to newly revealed regions.Only current data points need to be accessed directly; the approach is described as extensible to more complex nonlinear models.Source: §3 · p. 3

3.1 Online variational free energy inference and learning

  • The VFE update approximates the old likelihood from the previous posterior, then projects the updated distribution into a tractable pseudo-data form that can use different pseudo-input locations.Equations (7) and (8) give the online posterior update and hyperparameter-learning recipe, with complexity and memory overhead of the same order as uncollapsed stochastic variational inference.Source: §3.1 · p. 4

3.2 Online α-divergence inference and learning

  • Replacing the KL divergence with an α-divergence yields an analytically tractable online approximation that recovers the variational case as α → 0.In the toy time-series figure, α = 0.01 is virtually identical to VFE.Source: §3.2 · pp. 4–5, Figure 1 · p. 5

3.3 Connections to previous work and special cases

  • The online α-divergence method generalizes a forward filtering pass of Power-EP to streaming data and recovers EP at α = 1 and VFE as α → 0 when hyperparameters and pseudo-inputs are fixed.For fixed hyperparameters and pseudo-inputs, the VFE method is equivalent to streaming variational Bayes; with updated hyperparameters it differs by propagating old likelihood approximations rather than the prior.Source: §3.3 · p. 5

4 Experiments

Experiments evaluate SSGP’s speed, memory use, and accuracy against exact GP, sparse GP, and stochastic variational inference, using synthetic and real datasets. The results cover online hyperparameter learning, regression performance, memory use, and a preliminary non-Gaussian classification task.

4.1 Synthetic data

  • On synthetic data, variational inference adapts pseudo-inputs to new regions, while higher α methods can clump them and perform poorly; SSGP also tracks good hyperparameters with sufficient pseudo-points.The authors therefore focus on the variational case for the rest of the paper.Source: §4.1 · p. 6

4.2 Speed versus accuracy

  • On time-series data, SSGP significantly outperforms the other methods in MLL and RMSE after sufficient training data arrive, while more pseudo-points improve performance but slow the algorithm.Figure 2 plots MLL and RMSE against accumulated running time; GP and SGP show little improvement because they model only the last 3,000 examples.Source: §4.2 · p. 6, Figure 2 · p. 7

4.4 Binary classification

  • On the banana classification benchmark, SSGP performs well in a non-iid streaming setting and achieves the performance of batch sparse variational inference.The approximate posterior is obtained by numerically optimizing the uncollapsed variational free energy.Source: §4.4 · p. 7

4.2 Speed versus accuracy

  • On spatial data, SSGP achieves better RMSE than the baselines but worse MLL.Figure 3 reports results for 400 and 600 pseudo-points.Source: §4.2 · p. 6, Figure 3 · p. 8

4.3 Memory usage versus accuracy

  • On Terrain data, SSGP uses small memory while achieving MLL and RMSE comparable to or better than GP and SGP.The comparison uses batch size 750 and 600 pseudo-points; baseline training windows were chosen to roughly match SSGP’s memory use.Source: §4.3 · p. 7, Figure 4 · p. 8

5 Summary

The paper presents an online GP inference and learning framework that unifies existing methods and extends them to sequential posterior updates and principled hyperparameter optimization. It reports improved regression results across a range of datasets, promising binary-classification results, and identifies fuller non-Gaussian evaluation as future work.

5 Summary

  • The framework unifies disparate methods and extends them with principled sequential updates of the approximate posterior and online hyperparameter optimization.The authors report that it outperforms existing approaches on a wide range of regression datasets and shows promising results on binary classification.Source: §5 · p. 8
  • More thorough investigation of models with non-Gaussian likelihoods is left for future work.Source: §5 · p. 8
  • The authors expect the framework to be particularly useful in sequential decision-making problems such as active learning, Bayesian optimization, and reinforcement learning.Source: §5 · p. 8

Appendices

The appendices clarify variational-bound derivations and compare streaming approaches, while identifying input-space coverage as a boundary for pseudo-point approximations. They also explain how function mismatch can inflate learned observation noise.

A.1 Can the variational lower bound be derived using Jensen’s inequality?

  • The variational lower bound can be derived either by applying Jensen’s inequality to the log marginal likelihood or by rearranging a non-negative KL divergence.The paper uses the latter derivation, as do some recent papers.Source: §A.1 · p. 10

A.2 Comparison to [9]

  • [9] does not provide hyperparameter learning, and its framework does not support that extension; this makes fair comparison difficult.The paper also distinguishes its pseudo-input optimisation from the heuristics in, which were improved upon in batch settings.Source: §A.2 · p. 10

A.3 Are SVI or the stream-based method performing differently due to different approximations?

  • Conventional SVI performs poorly in streaming settings because its learning rates need dataset- and iteration-specific tuning to revisit new data without forgetting old data.The paper reports that its uncollapsed method performs as well as its collapsed version given sufficient updates, without this tuning.Source: §A.3 · p. 10

A.4 Are pseudo-points appropriate for streaming settings?

  • Pseudo-point approximations require coverage of the data’s input space, which can make them inappropriate for very long time-series or very high-dimensional inputs.A moving window may help, but its utility depends on the task; the paper assumes all input regions must be modelled.Source: §A.4 · p. 10

A.5 A possible explanation on why all models including full GP regression tend to learn bigger noise variances

  • Function mismatch can inflate learned observation noise because learned functions may differ more from the training data than the true function does.The learned noise accommodates that mismatch.Source: §A.5 · p. 10

A.6 Are the hyperparameters learned in the time-series and spatial data experiments?

The experiments learn hyperparameters and pseudo-inputs using online variational free energy. The appendix also explains a performance decline when a memory window misses parts of the input space and outlines the variational posterior update.

A.6 Are the hyperparameters learned in the time-series and spatial data experiments?

  • Hyperparameters and pseudo-inputs are optimised using online variational free energy, a central distinction from.Source: §A.6 · p. 10

A.7 Why is there a non-monotonic behaviour in fig. 4 in the main text?

  • Performance can decrease when the GP or SGP memory window can no longer cover all observed data and misses parts of the input space.Source: §A.7 · p. 10

B.1 The variational lower bound

  • The new posterior approximation retains the sparse form and is obtained by minimising KL divergence; its free-energy bound includes terms that account for the old likelihood.The old likelihood is incorporated through the approximate posterior and prior.Source: §B.1 · p. 11

B.2 Derivation of the optimal posterior update and the collapsed bound

This appendix derives and implements posterior updates and prediction for streaming sparse GPs, then develops a Power-EP alternative. Its approximate marginal likelihood supports hyperparameter and pseudo-input optimisation.

B.2 Derivation of the optimal posterior update and the collapsed bound

  • The optimal posterior update is obtained by minimising free energy with respect to q(b), and the negative variational free energy gives a lower bound on log marginal likelihood.The derivation includes a normalisation constraint for q(b).Source: §B.2 · pp. 11–12

B.3 Implementation

  • The appendix presents numerically stable forms for practical implementation of the preceding results.Source: §B.3 · p. 12

B.3.1 The variational free energy

  • The variational free-energy expression is simplified using matrix determinant and inversion lemmas.The displayed expression includes determinant and quadratic terms.Source: §B.3.1 · pp. 12–13

B.3.2 Prediction

  • The optimal approximate distribution is rewritten in natural parameters to give predictive covariance and mean at test points.Source: §B.3.2 · p. 13

C Power-EP for streaming sparse Gaussian process regression

  • Power-EP approximates the streaming posterior using contributions from the old pseudo-output distribution and the new-data likelihood, assuming hyperparameters change little between updates.The approximation mirrors the form of the exact posterior.Source: C Power-EP for streaming sparse… · p. 13

C.1 q1(b)

  • The Power-EP update matches separate posterior contributions from the old pseudo-output and new observations to their corresponding factors at convergence.The q1(b) contribution comes from a; q2(b) comes from y.Source: §C.1 · p. 14, §C.2 · p. 16

C.3 Approximate posterior

C.4 Approximate marginal likelihood

  • The Power-EP approximate marginal likelihood can optimise hyperparameters and pseudo-inputs, and tends to variational free energy as α tends to 0.Source: §C.4 · pp. 16–17

C.5 Implementation

This appendix gives implementation forms for the Power-EP approximate marginal likelihood and prediction. It uses a determinant lemma for the likelihood expression and presents predictive mean and covariance.

C.5 Implementation

  • The appendix provides numerically stable forms for practical implementation of the preceding Power-EP results.Source: §C.5 · p. 17

C.5.1 The Power-EP approximate marginal likelihood

  • The Power-EP approximate marginal likelihood expression is simplified using the matrix determinant lemma.Source: §C.5.1 · pp. 17–18

C.5.2 Prediction

  • The optimal approximate distribution is rewritten in natural parameters to express predictive covariance and mean at test points.Source: §C.5.2 · p. 18

D Equivalence results

With hyperparameters and pseudo-inputs fixed, streaming sparse inference recovers the corresponding batch solutions; synthetic and classification experiments also assess hyperparameter learning and online performance. Additional results examine varied data order and the special case in which pseudo-points are added at each new input.

D Equivalence results

  • With fixed hyperparameters and pseudo-inputs, adding pseudo-points at each new input makes the streaming method return the true posterior and marginal likelihood.The equivalence is demonstrated against exact GP regression with pseudo-points at the training inputs.Source: D Equivalence results · p. 18, Figure 7 · p. 20
  • With hyperparameters and pseudo-inputs fixed, streaming variational inference matches the batch variational solution, as illustrated by the cumulative marginal-likelihood comparison.The batch variational approximation is identical to the optimal approximation obtained by grouping all data batches together.Source: D Equivalence results · p. 18, Figure 6 · p. 19

E.1 Hyperparameter learning on synthetic data

  • With enough pseudo-points, the streaming method learns good hyperparameters and performs comparably to full GP regression, though shorter lengthscales require more pseudo-points.All models, including full GP regression, tend to learn larger noise variances than the ground truth.Source: §E.1 · p. 19

E.2 Learning and inference on a toy time series

  • Toy time-series experiments show online regression in both non-iid and iid streaming settings.The results are presented for variational inference and Power-EP with α = 0.5.Source: §E.2 · p. 19

E.3 Binary classification

  • On the banana binary-classification task, streaming inference in both non-iid and iid settings reaches the performance of batch sparse variational inference.The batch comparison is shown in the right-most plots.Source: §E.3 · p. 19

E.4 Sensitivity to the order of the data

  • Classification errors were evaluated as data arrived in different orders, and the reported results were consistent with those in the main text.The order-sensitivity experiment used more, smaller mini-batches.Source: §E.4 · p. 20, Table 1 · p. 20

E.5 Additional plots for the time-series and spatial datasets

The additional plots show hyperparameter traces, online regression and classification predictions, and performance curves for time-series and spatial datasets. They vary streaming setting, batch size, and pseudo-point count across the displayed experiments.

Time-series and spatial datasets

  • Time-series and spatial plots track mean marginal log-likelihood and RMSE against batch count, with results varying by batch size and pseudo-point count.Time-series plots use batch sizes 300 and 500 with M = 100 or 200; spatial plots use M = 400 or 600.Source: §E.5 · p. 20, Figure 14 · p. 24, Figure 15 · p. 25

Hyperparameter traces

  • Figures 8 and 9 show learned hyperparameters on time-series datasets generated from GPs with exponentiated quadratic kernels and lengthscales 0.5 and 0.8; their y-axes show differences from ground truth.Source: Figure 8 · p. 21, Figure 9 · p. 21

Toy time-series regression

  • Toy time-series regression plots compare variational inference and Power-EP with α = 0.5 in non-iid and iid settings.They mark data points, pseudo-points, predictive means, and confidence intervals.Source: Figure 10 · p. 22, Figure 11 · p. 23

Binary classification

  • Binary-classification plots show predictions for non-iid and iid streaming, with full-training sparse variational inference at the right.The right-most plot is the full-training comparison in each setting.Source: Figure 12 · p. 23, Figure 13 · p. 24

Related papers

Loading 1705.07131v2…