"Rigorous Learning Curve Bounds from Statistical Mechanics"
David Haussler, Michael Kearns, and H. Sebastian Seung
Abstract:
In this paper we introduce and investigate a mathematically rigorous
theory of learning curves that is based on ideas from statistical
mechanics. The advantage of our theory over the well-established
Vapnik-Chervonenkis theory is that our bounds can be considerably
tighter in many cases, and are more reflectve of the true behavior
(functional form) of learning curves. This behavior can often exhibit
dramatic properties such as phase transitions, as well as power law
asymptotics not explained by the VC theory. The disadvantages of our
theory are that its application requires knowledge of the input
distribution, and it is limited so far to finite cardinality function
classes. We illustrate our results with many concrete examples of
learning curve bounds derived from our theory.