|
Abstract : |
We present a bound on the generalisation error of linear classiers in terms of a rened margin quantity on the training set. The result is obtained in a PAC-Bayesian framework and is based on geometrical arguments in the space of linear classiers. The new bound constitutes an exponential improvement of the so far tightest margin bound by Shawe-Taylor et al. [?] and scales logarithmically in the inverse margin. Even in the case of less training examples than input dimensions suciently large margins lead to non-trivial bound values and for maximum margins to a vanishing complexity term. Furthermore, the classical margin is too coarse a measure for the essential quantity that controls the generalisation error: the volume ratio between the whole hypothesis space and the subset of, |
