Computationally Efficient Low-Rank Algorithms for Gaussian Process Regression

Abstract

Gaussian Process Regression (GPR) is a Bayesian non-parametric method widely used in machine learning for supervised learning. Compared to neural networks and support vector regressions, prediction using GPR provides one with a posterior distribution. Further, the training of GPR can be done efficiently by exact optimization of the marginal likelihood with implicit regularization. However, both the training and prediction require the inversion of an N ×N kernel matrix (time complexity O(N^3)), which limits the scalability of GPR for big datasets (N > 10^4). In this research, we develop algorithms to scale GPR without sacrificing accuracy. Our training algorithm uses the thin-QR decomposition of the low-rank matrix used in the Nyström approximation. The limitations of the Nyström method are eliminated by restricting the prediction in the subspace spanned by the orthogonal matrix of this decomposition. To improve the prediction accuracy, we propose two algorithms that augment the neighbors of a test point. These algorithms leverage the general structure of the problem through the low-rank approximation and improves its accuracy further by exploiting locality at each test input. Results on synthetic and real-world datasets show that our algorithms achieve an accuracy comparable to the full kernel matrix at lower ranks than other competing methods. Thus, our algorithms provide faster training and prediction while at the same time reducing storage requirements.