PATTERN-RECOGNITION AND VALIANTS LEARNING FRAMEWORK
The computational learning approach shows that the concept descriptions acquired from examples are approximately correct with a degree of probability that grows with the size of the training sample. On the other hand, the same problem has been widely investigated in the field of pattern recognition under a variety of problem settings. This paper surveys and compares some of the results obtained in both fields and analyzes the limits of their applicability. Moreover, new and tighter bounds for the growth function of some classes of Boolean formulas are presented.
computational learning theory induction of boolean classifiers inductive inference probability of error vapnik-chervonenkis inequality