BOUNDS FOR PREDICTIVE ERRORS IN THE STATISTICAL-MECHANICS OF SUPERVISED LEARNING

Within a Bayesian framework, by generalizing inequalities known from statistical mechanics, we calculate general upper and lower bounds for a cumulative entropic error, which measures the success in the supervised learning of an unknown rule from examples. Both bounds match asymptotically, when the number rn of observed data grows large. We find that the information gain from observing a new example decreases universally like d/m. Here d is a dimension that is defined from the scaling of small volumes with respect to a distance in the space of rules.