TY - GEN

T1 - Rigorous learning curve bounds from statistical mechanics

AU - Haussler, David

AU - Seung, Hyunjune Sebastian

AU - Kearns, Michael

AU - Tishby, Naftali

N1 - Funding Information:
We are grateful to Haim Sompolinsky and Vladimir Vapnik for enlightening conversations and helpful comments. We would also like to thank Chris van den Broeck for organizing the Workshop on Statistical Mechanics of Generalization at Alden Biesen. We are grateful for the support of NSF grant IRI-9123692 and the U.S.-Israel BSF grant 90-0189.

PY - 1994/7/16

Y1 - 1994/7/16

N2 - 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 also more reflective 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.

AB - 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 also more reflective 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.

UR - http://www.scopus.com/inward/record.url?scp=80051745292&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80051745292&partnerID=8YFLogxK

U2 - 10.1145/180139.181018

DO - 10.1145/180139.181018

M3 - Conference contribution

AN - SCOPUS:80051745292

T3 - Proceedings of the Annual ACM Conference on Computational Learning Theory

SP - 76

EP - 87

BT - Proceedings of the 7th Annual Conference on Computational Learning Theory, COLT 1994

PB - Association for Computing Machinery

T2 - 7th Annual Conference on Computational Learning Theory, COLT 1994

Y2 - 12 July 1994 through 15 July 1994

ER -