Analysis of complexity bounds for pac-learning with random sets
E.M. Oblow, V. R. R. Uppuluri · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 1991
Learnability in Valiant's pac-learning formalism is reformulated in terms of expected (average) error instead of confidence and error parameters. A finite-domain, random set formalism is introduced to develop algorithm-dependent, distribution-specific analytic error estimates. Two random set theorems for finite concept-spaces are presented to facilitate these developments. Analyses are carried out for several illustrative problems with worst-case and semi-uniform distributions of learning examples. Analytic bounds on the sample size needed to achieve a specified average error are established. Useful approximations for these bounds and a worst-case distribution are also derived. Conclusions are drawn about the potential value of average-error bounds in improving the stated efficiency of pac-learning algorithms. 16 refs., 5 figs., 1 tab.