The Role of Simplicity in Learning Theory

Science values simplicity. All other things being equal, a simple explanation is preferable to a complex one. Bayesians assign higher prior probability to simple theories. But is it really true that a simple theory is a-priori more likely than a complex one? It turns out that one can justify a preference for simplicity independent of Bayesian assumptions. The justification involves only the law of large number and the observation that the number of simple theories is limited. This talk will present this justification and go on to describe more general "laws of large numbers" that justify more sophisticated methods of evaluating the accuracy of predictive rules.