Rigorous learning curve bounds from statistical mechanics

David Haussler, Michael Kearns, H. Sebastian Seung, Naftali Tishby

Research output: Contribution to journalArticle

35 Scopus citations

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 also more reflective of the true behavior 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.

Original languageEnglish (US)
Pages (from-to)195-236
Number of pages42
JournalMachine Learning
Volume25
Issue number2-3
StatePublished - Dec 1 1996
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Artificial Intelligence

Keywords

  • Learning curves
  • Phase transitions
  • Statistical mechanics
  • VC dimension

Fingerprint Dive into the research topics of 'Rigorous learning curve bounds from statistical mechanics'. Together they form a unique fingerprint.

  • Cite this

    Haussler, D., Kearns, M., Sebastian Seung, H., & Tishby, N. (1996). Rigorous learning curve bounds from statistical mechanics. Machine Learning, 25(2-3), 195-236.