A PAC-Bayesian study of linear classifiers: why SVMs work
In this paper we present a bound on the generalisation error of linear classi ers in terms of a re ned margin quantity on the training set. The result is obtained by a fundamentally di erent reasoning than in the classical PAC framework. We show that the generalisation error of a classi er can be bounded purely by geometrical arguments. In contrast to the classical results our bound does not contain awkward constants (see, e.g. [10, p. xxi]) and is an exponential improvement of the result in [8] by scaling inverse logarithmically in the margin. In the form presented the result is an improvement of a result in [3]. A much more rigorous analysis shows that even in the case of having less examples than input dimensions we can bene t from large margins. Furthermore it is shown that the margins is too coarse a measure for the real quantity controlling the generalisation error: the volume of the consistent classi ers to the volume of the whole hypothesis space. In case of ellipsoidal shapes of the input space the minimal real valued output on the training set (margin) is largely a ected by a few points on the longest principal axis. Instead of considering the eigenvalue spectrum of the Gram matrix (see, e.g. [7]) we show that a simple rescaling of the single margins at each training point su ces to compensate the e ect of kernels. An appealing feature of our bound is that the capacity term vanishes for maximally large margins independent on the number of training examples. This will never be the case in classical PAC bounds.