Fast Sparse Gaussian Process Methods: The Informative Vector Machine

We present a framework for sparse Gaussian process (GP) methods which uses forward selection with criteria based on information-theoretic principles, previously suggested for active learning. Our goal is not only to learn d-sparse predictors (which can be evaluated in O(d) rather than O(n), d much smaller than n, n the number of training points), but also to perform training under strong restrictions on time and memory requirements. The scaling of our method is at most O(n d^2), and in large real-world classification experiments we show that it can match prediction performance of the popular support vector machine (SVM), yet can be significantly faster in training. In contrast to the SVM, our approximation produces estimates of predictive probabilities ("error bars"), allows for Bayesian model selection and is less complex in implementation.

Bayesian Gaussian Process Models: PAC-Bayesian Generalisation Error Bounds and Sparse Approximations

Matthias Seeger

Non-parametric models and techniques enjoy a growing popularity in the field of machine learning, and among these Bayesian inference for Gaussian process (GP) models has recently received significant attention. We feel that GP priors should be part of the standard toolbox for constructing models relevant to machine learning in the same way as parametric linear models are, and the results in this thesis help to remove some obstacles on the way towards this goal. In the first main chapter, we provide a distribution-free finite sample bound on the difference between generalisation and empirical (training) error for GP classification methods. While the general theorem (the PAC-Bayesian bound) is not new, we give a much simplified and somewhat generalised derivation and point out the underlying core technique (convex duality) explicitly. Furthermore, the application to GP models is novel (to our knowledge). A central feature of this bound is that its quality depends crucially on task knowledge being encoded faithfully in the model and prior distributions, so there is a mutual benefit between a sharp theoretical guarantee and empirically well-established statistical practices. Extensive simulations on real-world classification tasks indicate an impressive tightness of the bound, in spite of the fact that many previous bounds for related kernel machines fail to give non-trivial guarantees in this practically relevant regime. In the second main chapter, sparse approximations are developed to address the problem of the unfavourable scaling of most GP techniques with large training sets. Due to its high importance in practice, this problem has received a lot of attention recently. We demonstrate the tractability and usefulness of simple greedy forward selection with information-theoretic criteria previously used in active learning (or sequential design) and develop generic schemes for automatic model selection with many (hyper)parameters. We suggest two new generic schemes and evaluate some of their variants on large real-world classification and regression tasks. These schemes and their underlying principles (which are clearly stated and analysed) can be applied to obtain sparse approximations for a wide regime of GP models far beyond the special cases we studied here.

University of Edinburgh2003

Tractable Approaches to Learning and Planning in High Dimensions

Leonidas Lefakis

The continuous increase, witnessed in the last decade, of both the amount of available data and the areas of application of machine learning, has lead to a demand for both learning and planning algorithms that are capable of handling large-scale problems. Thus scalability has become an important characteristic of modern machine learning algorithms. In this thesis we concentrate on tractable approaches to both learning and planning, capable of solving problems in high-dimensional spaces. We investigate multiple forms of high-dimensionality, where dimensionality can refer to the number of samples to be processed, the number of samples available for training, the dimensionality of the feature space, or even the dimensionality of the state-space. We present work on classifier cascades, developing a novel framework for interpreting, training, and employing such structures of classifiers. A Boosting algorithm developed in this framework highlights its ability to jointly train the classifiers at the cascade nodes. The work presented on goal-planning also results in a novel framework, this time for automatic macro-action discovery in imitation learning, specifically addressing problems with large state-spaces as well as with observation signals of high-dimensionality. The proposed DPBoost algorithm is capable of solving very complex goal-planning tasks where previous state-of-the-art fails. Addressing computer hardware limitations, and in particular memory limitations, we propose a new learning framework, which we call reservoir learning, which attempts to directly account for this limited memory during the training process. In particular we propose to consider learning in the presence of a reservoir in which the learner may store samples. Based on Boosting we develop a novel strategy for populating this reservoir which avoids redundancy by taking into account the joint behavior of samples. Finally high-dimensionality is also addressed in its most typical setting, that is when the feature space is large. We propose novel feature selection algorithms in the context of classification. Based on information theoretic tools, these algorithms attempt to maximize the joint mutual information between the selected, continuous, variables and the, discrete, class label variable.

EPFL2014

Tractable Approaches to Learning and Planning in High Dimensions

Leonidas Lefakis

EPFL2014

Bayesian Gaussian Process Models: PAC-Bayesian Generalisation Error Bounds and Sparse Approximations

Matthias Seeger

University of Edinburgh2003