A GENERAL FRAMEWORK FOR SUPERVISED LEARNING - PROBABLY ALMOST BAYESIAN ALGORITHMS

The paper proposes the concept of Probably Almost Bayesian (PAB) algor ithms generalizing a definition given by Valiant in his theory of the learnable. PAB algorithms are defined as algorithms that probably appr oximate the Bayesian optimum when the training set size tends to infin ity, in polynomial time with respect to the training set size. We pres ent this concept in the framework of the decision theory and we suppor t this definition by giving examples of such algorithms, particularly in the field of artificial neural networks.