NeuroCOLT workshop
on
Generalisation Bounds Less than 0.5
Windsor, 29 April - 2 May 2002
Cumberland Lodge

"A Compression Scheme for Gaussian Process Classifiers: The Informative Vector Machine"

Neil Lawrence and Ralf Herbrich

Kernel based learning algorithms allow the mapping of data-set into an infinite dimensional feature space in which a classification may be performed. As such kernel methods represent a powerful approach to the solution of many non-linear problems. However, kernel methods do suffer from one unfortunate drawback in that the central quantity, the Gram matrix, requires $m^2$ kernel computations where $m$ is the number of data-points. Many operations are therefore precluded (e.g.~matrix inverse $O(m^3)$) when data-sets containing more than about $10^4$ points are encountered. One approach to resolving these issues is to look for sparse representations of the data-set. In this talk we shall introduce an algorithm for constructing a sparse Gaussian Process Classifier (GPC). Our algorithm is, to our knowledge, the first sparsification of GPCs which can be viewed as a \emph{compression scheme}. Therefore, not only does it reduce computational complexity, but also it provides guarantees on its performance through compression bounds.