A model for nonpolynomial decrease in error rate with increasingsample size

Much theoretical evidence exists for an inverse proportionality between the error rate of a classifier and the number of samples used to train it. Cohn and Tesauro (1992) have, however, discovered various problems which experimentally display an approximately exponential decrease in error rate. We present evidence that the observed exponential decrease is caused by the finite nature of the problems studied. A simple model classification problem is presented, which demonstrates how the error rate approaches zero exponentially or faster when sufficiently many training samples are used.