2015

Thoughts on Massively Scalable Gaussian Processes

Wilson, Andrew Gordon, Dann, Christoph, Nickisch, Hannes

Understand

We introduce a framework and early results for massively scalable Gaussian processes (MSGP), significantly extending the KISS-GP approach of Wilson and Nickisch (2015).

The MSGP framework enables the use of Gaussian processes (GPs) on billions of datapoints, without requiring distributed inference, or severe assumptions.
In particular, MSGP reduces the standard $O(n^3)$ complexity of GP learning and inference to $O(n)$, and the standard $O(n^2)$ complexity per test point prediction to $O(1)$.
MSGP involves 1) decomposing covariance matrices as Kronecker products of Toeplitz matrices approximated by circulant matrices.

Built on

On stationary processes in the plane
Whittle, P. (1954) · 1954
Earlier work this paper cites.
A unifying view of sparse approximate gaussian process regression
Quiñonero-Candela, J. and Rasmussen, C. (2005a) · 1959
Earlier work this paper cites.
A unifying view of sparse approximate Gaussian process regression
Quiñonero-Candela, J. and Rasmussen, C. E. (2005b) · 1959
Earlier work this paper cites.
Cubic convolution interpolation for digital image processing
Keys, R. G. (1981) · 1981
Earlier work this paper cites.
A proposal for Toeplitz matrix calculations
Strang, G. (1986) · 1986
Earlier work this paper cites.
An optimal circulant preconditioner for Toeplitz systems
Chan, T. F. (1988) · 1988
Earlier work this paper cites.
Optimal and superoptimal circulant preconditioners
Tyrtyshnikov, E. (1992) · 1992
Earlier work this paper cites.
Discovering hidden features with gaussian processes regression
Vivarelli, F. and Williams, C. K. (1998) · 1998
Earlier work this paper cites.
Truncated covariance matrices and Toeplitz methods in Gaussian processes
Storkey, A. (1999) · 1999
Earlier work this paper cites.
Using the Nyström method to speed up kernel machines
Williams, C. and Seeger, M. (2001) · 2001
Earlier work this paper cites.
Toeplitz and circulant matrices: A review
Gray, R. M. (2005) · 2005
Earlier work this paper cites.

Similar

Time-series Gaussian process regression based on Toeplitz computation of O ⁡ ( N 2 ) O(N^{2}) operations and O ⁡ ( N ) O(N) -level storage
Zhang, Y., Leithead, W. E., and Leith, D. J. (2005) · 2005
Cited alongside, same era.
Gaussian processes for Machine Learning
Rasmussen, C. E. and Williams, C. K. I. (2006) · 2006
Cited alongside, same era.
Sparse Gaussian processes using pseudo-inputs
Snelson, E. and Ghahramani, Z. (2006) · 2006
Cited alongside, same era.
Random features for large-scale kernel machines
Rahimi, A. and Recht, B. (2007) · 2007
Cited alongside, same era.
Flexible and efficient Gaussian process models for machine learning
Snelson, E. (2007) · 2007
Cited alongside, same era.
Fast Gaussian process methods for point process intensity estimation
Cunningham, J. P., Shenoy, K. V., and Sahani, M. (2008) · 2008
Cited alongside, same era.
Asymptotic theory for maximum likelihood estimation in stationary fractional Gaussian processes, under short-, long- and intermediate memory
Lieberman, O., Rosemarin, R., and Rousseau, J. (2009) · 2009
Cited alongside, same era.
Sparse spectrum Gaussian process regression
Lázaro-Gredilla, M., Quiñonero-Candela, J., Rasmussen, C., and Figueiras-Vidal, A. (2010) · 2010
Cited alongside, same era.
Gaussian processes for machine learning (GPML) toolbox
Rasmussen, C. E. and Nickisch, H. (2010) · 2010
Cited alongside, same era.
Efficient variational inference in large-scale Bayesian compressed sensing
Papandreou, G. and Yuille, A. L. (2011) · 2011
Cited alongside, same era.

Then

Scalable Inference for Structured Gaussian Process Models
Saatchi, Y. (2011) · 2011
Later among the works it cites.
Matrix computations
Golub, G. H. and Van Loan, C. F. (2012) · 2012
Later among the works it cites.
Gaussian processes for big data
Hensman, J., Fusi, N., and Lawrence, N. (2013) · 2013
Later among the works it cites.
Fastfood-computing Hilbert space expansions in loglinear time
Le, Q., Sarlos, T., and Smola, A. (2013) · 2013
Later among the works it cites.
Circulant embedding of approximate covariances for inference from Gaussian data on large lattices
Guinness, J. and Fuentes, M. (2014) · 2014
Later among the works it cites.
Covariance kernels for fast automatic pattern discovery and extrapolation with Gaussian processes
Wilson, A. G. (2014) · 2014
Later among the works it cites.
Fast kernel learning for multidimensional pattern extrapolation
Wilson, A. G., Gilboa, E., Nehorai, A., and Cunningham, J. P. (2014) · 2014
Later among the works it cites.
Distributed gaussian processes
Deisenroth, M. P. and Ng, J. W. (2015) · 2015
Closest in time.
Kernel interpolation for scalable structured Gaussian processes (KISS-GP)
Wilson, A. G. and Nickisch, H. (2015) · 2015
Closest in time.
A la carte - learning fast kernels
Yang, Z., Smola, A. J., Song, L., and Wilson, A. G. (2015) · 2015
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…