"Bounds for Predictive Errors in the Statistical Mechanics of
Supervised Learning"
Manfred Opper and David Haussler, in Physical Review Letters, No. 20,
Vol. 75, 1995, pp. 3772-3775.
Abstract:
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. This performance
measure is equivalent to the mutual information between the data and
the parameter that specifies the rule to be learnt. Both bounds match
asymptotically, when the number m of observed data grows
large. Under mild conditions, 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 suitable distance in the space of rules.