Greedy forward selection algorithms to Sparse Gaussian Process Regression

This paper considers the basis vector selection issue invloved in forward selection algorithms to sparse Gaussian Process Regression (GPR). Firstly, we re-examine a previous basis vector selection criterion proposed by Smola and Bartlett [20], referred as loss-smola and give some new formulae to implement this criterion for the full-greedy strategy more efficiently in O(n²k_max) time instead of the original O(n²k² _max), where n is the number of training examples and kmax Lt n is the maximally allowed number of selected basis vectors. Secondly, in order to make the algorithm linearly scaling in n, which is quite preferable for large datasets, we present an approximate version loss-sun to loss-smola criterion. We compare the full greedy algorithms induced by the loss-sun and loss-smola criteria, respectively, on several medium-scale datasets. In contrast to loss-smola, the advantage associated with loss-sun criterion is that it could lead to an algorithm which scales as O(n²k_max) time and O(nk_max) memory if coupled with the sub-greedy scheme. Our criterion is similar to a matching pursuit approach, referred as loss-keert proposed very recently by Keerthi and Chu but with different motivations. Numerical experiments on a number of large-scale datasets have demonstrated that our proposed method is always better than loss-keert in both generalization performance and running time. Finally, we discuss the drawbacks of the sub-greedy strategy and present two approximate full-greedy strategies, which can be applied to all three basis vector selection criteria discussed in this paper.