Rigorous learning curve bounds from statistical mechanics

David Haussler; Hyunjune Sebastian Seung; Michael Kearns; Naftali Tishby

doi:10.1145/180139.181018

Rigorous learning curve bounds from statistical mechanics

David Haussler, Hyunjune Sebastian Seung, Michael Kearns, Naftali Tishby

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

42 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 (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.

Original language	English (US)
Title of host publication	Proceedings of the 7th Annual Conference on Computational Learning Theory, COLT 1994
Publisher	Association for Computing Machinery
Pages	76-87
Number of pages	12
ISBN (Electronic)	0897916557
DOIs	https://doi.org/10.1145/180139.181018
State	Published - Jul 16 1994
Event	7th Annual Conference on Computational Learning Theory, COLT 1994 - New Brunswick, United States Duration: Jul 12 1994 → Jul 15 1994

Publication series

Name	Proceedings of the Annual ACM Conference on Computational Learning Theory
Volume	Part F129415

Other

Other	7th Annual Conference on Computational Learning Theory, COLT 1994
Country/Territory	United States
City	New Brunswick
Period	7/12/94 → 7/15/94

All Science Journal Classification (ASJC) codes

Software
Theoretical Computer Science
Artificial Intelligence

Access to Document

10.1145/180139.181018

Cite this

Haussler, D., Seung, H. S., Kearns, M., & Tishby, N. (1994). Rigorous learning curve bounds from statistical mechanics. In Proceedings of the 7th Annual Conference on Computational Learning Theory, COLT 1994 (pp. 76-87). (Proceedings of the Annual ACM Conference on Computational Learning Theory; Vol. Part F129415). Association for Computing Machinery. https://doi.org/10.1145/180139.181018

@inproceedings{c1c15f99df33455f9604b3e16a09ae85,

title = "Rigorous learning curve bounds from statistical mechanics",

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 (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.",

author = "David Haussler and Seung, {Hyunjune Sebastian} and Michael Kearns and Naftali Tishby",

note = "Publisher Copyright: {\textcopyright} 1994 ACM.; 7th Annual Conference on Computational Learning Theory, COLT 1994 ; Conference date: 12-07-1994 Through 15-07-1994",

year = "1994",

month = jul,

day = "16",

doi = "10.1145/180139.181018",

language = "English (US)",

series = "Proceedings of the Annual ACM Conference on Computational Learning Theory",

publisher = "Association for Computing Machinery",

pages = "76--87",

booktitle = "Proceedings of the 7th Annual Conference on Computational Learning Theory, COLT 1994",

}

Haussler, D, Seung, HS, Kearns, M & Tishby, N 1994, Rigorous learning curve bounds from statistical mechanics. in Proceedings of the 7th Annual Conference on Computational Learning Theory, COLT 1994. Proceedings of the Annual ACM Conference on Computational Learning Theory, vol. Part F129415, Association for Computing Machinery, pp. 76-87, 7th Annual Conference on Computational Learning Theory, COLT 1994, New Brunswick, United States, 7/12/94. https://doi.org/10.1145/180139.181018

Rigorous learning curve bounds from statistical mechanics. / Haussler, David; Seung, Hyunjune Sebastian; Kearns, Michael et al.
Proceedings of the 7th Annual Conference on Computational Learning Theory, COLT 1994. Association for Computing Machinery, 1994. p. 76-87 (Proceedings of the Annual ACM Conference on Computational Learning Theory; Vol. Part F129415).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Rigorous learning curve bounds from statistical mechanics

AU - Haussler, David

AU - Seung, Hyunjune Sebastian

AU - Kearns, Michael

AU - Tishby, Naftali

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 -

Rigorous learning curve bounds from statistical mechanics

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this