Spectra and generalisation
Seminar Room 2, Newton Institute Gatehouse
The talk briefly reviews generalisation bounds for Support Vector Machines and poses the question of whether the spectrum of the empirical covariance matrix can be used to improve the quality of the bounds. Early results in this direction are surveyed before introducing a recent bound on the number of dichotomies of a graph in terms of the spectrum of the graph Laplacian. This result gives a bound on transductive algorithms that minimise the cut size of the classification. The result is then generalised to other bilinear forms and hence applied to Support Vector Classification. In order to obtain an inductive bound the eigenvalues of the true covariance must be estimated from those of a sample covariance matrix. Possible improvements in the quality of the bound are discussed.