Conndence Estimates of Classiication Accuracy on New Examples Produced as Part of the Esprit Working Group in Neural and Computational Learning, Neurocolt 8556
Following recent results 5] showing the importance of the fat shattering dimension in explaining the beneecial eeect 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 classii-cation in the distribution independent model. The results show that even if the classiier does not classify all of the training examples correctly, the fact that a new example has a larger margin than that on the misclassiied 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 suuciently large number of the correctly classiied training examples having a margin roughly equal to that used to estimate generalization, indicating that the corresponding output values need to bèwell sampled'.