Confidence estimates of classification accuracy on new examples

Lecture notes in computer sciencePublished 1 January 1997

John Shawe‐Taylor

DOI10.1007/3-540-62685-9_22

Source URL

Citations5

SJR quartileQ2

SJR score0.35

SNIP0.55

TL;DR

The results show that even if the classifier does not classify all of the training examples correctly, the fact that a new example has a larger margin than that on the misclassified examples, can be used to give very good estimates for the generalization performance in terms of the fat shattering dimension measured at a scale proportional to the excess margin.

Abstract

Following recent results [6] showing the importance of the fat shattering dimension in explaining the beneficial effect of a large margin on generalization performance, the current paper investigates how the margin on a test example can be used to give greater certainty of correct classification in the distribution independent model. The results show that even if the classifier does not classify all of the training examples correctly, the fact that a new example has a larger margin than that on the misclassified examples, can be used to give very good estimates for the generalization performance in terms of the fat shattering dimension measured at a scale proportional to the excess margin. The estimate relies on a sufficiently large number of the correctly classified training examples having a margin roughly equal to that used to estimate generalization, indicating that the corresponding output values need to be 'well sampled'. If this is not the case it may be better to use the estimate obtained from a smaller margin.

Keywords

Computer Science

The Nature of Statistical Learning Theory

39,279 Citations1995Vladimir Vapnik

A training algorithm for optimal margin classifiers

11,594 Citations1992Bernhard E. Boser, Isabelle Guyon +1 more

A training algorithm that maximizes the margin between the training patterns and the decision boundary is presented, applicable to a wide variety of the classification functions, including Perceptrons, polynomials, and Radial Basis Functions.

Information science and statisticsEstimation of Dependences Based on Empirical Data

2,238 Citations2006Vladimir Vapnik

IEEE Transactions on Information TheoryThe sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network

1,187 Citations1998Peter L. Bartlett

Results in this paper show that if a large neural network is used for a pattern classification problem and the learning algorithm finds a network with small weights that has small squared error on the training patterns, then the generalization performance depends on the size of the weights rather than the number of weights.

Bayesian methods for adaptive models

629 Citations1992David Mackay

The Bayesian framework for model comparison and regularisation is demonstrated by studying interpolation and classification problems modelled with both linear and non-linear models, and it is shown that the careful incorporation of error bar information into a classifier's predictions yields improved performance.

IEEE Transactions on Information TheoryStructural risk minimization over data-dependent hierarchies

527 Citations1998John Shawe‐Taylor, Peter L. Bartlett +2 more

A result is presented that allows one to trade off errors on the training sample against improved generalization performance, and a more general result in terms of "luckiness" functions, which provides a quite general way for exploiting serendipitous simplicity in observed data to obtain better prediction accuracy from small training sets.

Journal of the ACMScale-sensitive dimensions, uniform convergence, and learnability

346 Citations1997Noga Alon, Shai Ben-David +2 more

View PDF

Discrete Applied MathematicsA result of Vapnik with applications

79 Citations1993Martin Anthony, John Shawe‐Taylor

A new proof of a result due to Vapnik is given, and its implications for the theory of PAC learnability are discussed, with particular reference to the learnability of functions taking values in a countable set.