Classification accuracy based on observed margin. (English) Zbl 0912.68178

Shawe-Taylor, J.

Algorithmica 22, No. 1-2, 157-172 (1998).

Summary: Following recent results [(*) J. Shawe-Taylor, P. Bartlett, R. Williamson and M. Anthony, Structural Risk Minimization over Data-Dependent Hierarchies, NeuroCOLT Technical Report NC-TR-96-51, ftp://ftp.dcs.rhbnc.ac.uk/pub/neurocolt/tech\(_-\)reports.] 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 used to give greater certainty of correct classification in the distribution independent model. Hence, generalization analysis is possible at three distinct phases, a priori using a standard pac analysis, after training based on properties of the chosen hypothesis (*), and finally in this paper at testing based on properties of the test example. The results also 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 test 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”.

MSC:

68T05

Learning and adaptive systems in artificial intelligence

Keywords:

agnostic learning; fat-shattering dimension; large margin