Timezone: »

 
Poster
Log-Linear-Time Gaussian Processes Using Binary Tree Kernels
Michael K. Cohen · Samuel Daulton · Michael A Osborne

Wed Nov 30 02:00 PM -- 04:00 PM (PST) @ Hall J #842
in Poster Session 4 »
Gaussian processes (GPs) produce good probabilistic models of functions, but most GP kernels require $O((n+m)n^2)$ time, where $n$ is the number of data points and $m$ the number of predictive locations. We present a new kernel that allows for Gaussian process regression in $O((n+m)\log(n+m))$ time. Our "binary tree" kernel places all data points on the leaves of a binary tree, with the kernel depending only on the depth of the deepest common ancestor. We can store the resulting kernel matrix in $O(n)$ space in $O(n \log n)$ time, as a sum of sparse rank-one matrices, and approximately invert the kernel matrix in $O(n)$ time. Sparse GP methods also offer linear run time, but they predict less well than higher dimensional kernels. On a classic suite of regression tasks, we compare our kernel against Mat\'ern, sparse, and sparse variational kernels. The binary tree GP assigns the highest likelihood to the test data on a plurality of datasets, usually achieves lower mean squared error than the sparse methods, and often ties or beats the Mat\'ern GP. On large datasets, the binary tree GP is fastest, and much faster than a Mat\'ern GP.
Keywords: Gaussian Processes · Probabilistic Methods · Scalable Gaussian processes
[ Paper]  [ Poster]  [ OpenReview] 

Author Information

Michael K. Cohen (University of Oxford)
Michael K. Cohen

I'm studying a DPhil with Mike Osborne at Oxford. My research focuses on the expected behavior of generally intelligent artificial agents. I am interested in designing agents that we can expect to behave safely.

Samuel Daulton (Meta, University of Oxford)

Research Scientist at Meta, PhD Candidate at Oxford. My research focuses on Bayesian optimization.

Michael A Osborne (U Oxford)

More from the Same Authors