Search

In this paper, the relationships between the eigen-values of the m x m Gram matrix K for a kernel K(.,.) corresponding to a sample [x.sub.1], . [x.sub.m] drawn from a density p(x) and the eigenvalues of the corresponding continuous eigen-problem is analyzed. The differences between the two spectra are bounded and a performance bound on kernel principal component analysis (PCA) is provided showing that good performance can be expected even in very-high-dimensional feature spaces provided the sample eigenvalues fall sufficiently quickly. Index Terms--Concentration bounds, Gram matrices, kernel methods, principal components analysis (PCA), Rademacher complexity, spectra of random matrices, statistical learning theory.

Generalization bounds depending on the margin of a classifier are a relatively recent development. They provide an explanation of the performance of state-of-the-art learning systems such as support vector machines (SVMs) [1] and Adaboost [2]. The difficulty with these bounds has been either their lack of robustness or their looseness. The question of whether the generalization of a classifier can be more tightly bounded in terms of a robust measure of the distribution of margin values has remained open for some time. The paper answers this open question in the affirmative and, furthermore, the analysis leads to bounds that motivate the previously heuristic soft margin SVM algorithms as well as justifying the use of the quadratic loss in neural network training algorithms. The results are extended to give bounds for the probability of failing to achieve a target accuracy in regression prediction, with a statistical analysis of ridge regression and Gaussian processes as a special case. The analysis presented in the paper has also lead to new boosting algorithms described elsewhere. Index Terms--Generalization, margin, margin distribution, neural networks, probably approximately correct (pac) learning, ridge regression, soft margin, statistical learning, support vector machines (SVMs).