CLASSIFICATION ACCURACY BASED ON OBSERVED MARGIN

Following recent results [10] showing the importance of the fat-shatte ring dimension in explaining the beneficial effect of a large margin o n generalization performance, the current paper investigates how the m argin on a test example can be used to give greater certainty of corre ct classification in the distribution independent model. Hence, genera lization analysis is possible at three distinct phases, a priori using a standard pac analysis, after training based on properties of the ch osen hypothesis [10], and finally in this paper at testing based on pr operties of the test example. The results also show that even if the c lassifier does not classify all of the training examples correctly, th e fact that a new example has a larger margin than that on the misclas sified test examples, can be used to give very good estimates for the generalization performance in terms of the fat-shattering dimension me asured at a scale proportional to the excess margin. The estimate reli es on a sufficiently large number of the correctly classified training examples having a margin roughly equal to that used to estimate gener alization, indicating that the corresponding output values need to be ''well sampled.''