Lower bounds in pattern recognition and learning

摘要

Lower bounds are derived for the performance of any pattern recognition algorithm, which, using training data, selects a discrimination rule from a certain class of rules. The bounds involve the Vapnik-Chervonenkis dimension of the class, and L, the minimal error probability within the class. We provide lower bounds when L = 0 (the usual assumption in Valiant's theory of learning) and L > 0.