Mathematical learning theory: a formalized, axiomatic, abstract approach

An abstract formalism is presented wherein a mathematical learning theory is explored. Numerous examples from the literature are presented. demonstrating how our axiomatic framework formally unifies diverse examples of pattern recognition. Our principal result, the adaptive learning theorem, discusses the expected waiting time of different learning machines. Roughly speaking it states that all algorithms for the induction of boolean relationships between a dependent binary parameter and a finite preassigned set of independent parameters have asymptotically identical average rates of learning. We also give a lower bound for the average learning speed as well as necessary and sufficient conditions for a machine to achieve it. We discuss applications of our methods to classical pattern recognition problems as well as possible application to more complicated research problems. Our principal mathematical innovation is a fruitful correspondence between probability spaces and labeled tree representations