Probably almost Bayes decisions
Paul Fisher, Stefan Pölt, Hans Ulrich Simon · Conference on Learning Theory · 1991
We put Bayes decision theory into the framework of pac-learning as introduced by Valiant [Val84]. Unlike classical Boolean concept learning where functions f : {0, l} n → {0,1} are approximated, we assume here that f (x) is 0 (or 1) with a certain probability. We develop a theoretical framework for estimating functions and reduce the classification problem to the problem of estimating parameters. Within this framework it is shown that classifications based on n conditional independent Boolean features can efficiently be learned by examples. Our learning algorithm achieves with probability 1 — δ an error which comes arbitrarily close (up to an additive e) to the optimal one of a perfect Bayes decision. It requires examples. In the particular case of two state classification, learning can be performed on a single neuron. Moreover we relax the restriction of conditional independence to dependencies of bounded order k and show that in this case we need examples.