Improved sample size bounds for PAB-decisions
Stefan Pölt · 1994
Recently, Anoulova, Fischer, Polt, and Simon [1] applied Valiant's PAC-learning model to the field of statistical pattern recognition. They presented a sample- and time-efficient algorithm for learning nearly optimal classifiers with high confidence. In this context, they introduced the probably almost Bayes (PAB) decision model, which is a special case of Haussler's distribution independent model [2]. It turns out, that Haussler's method of approximately minimizing the empirical risk leads to NP-complete problems. Therefore the two different methods offer a trade-off between time-efficiency and robustness (distribution independency). In this paper, we generalize the basic PAB-decision model, essentially improve the upper bounds on sample size in [1], and give first lower bound results. Furthermore, we consider a new class of distribution functions, represented by probabilistic automata. 1 INTRODUCTION There are several papers extending the PAC-learning model of Valiant to the field o...