Rigorous learning curve bounds from statistical mechanics

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Rigorous learning curve bounds from statistical mechanics

Full text

Pdf (1.39 MB)

Source

Annual Workshop on Computational Learning Theory archive
Proceedings of the seventh annual conference on Computational learning theory table of contents

New Brunswick, New Jersey, United States

Pages: 76 - 87

Year of Publication: 1994

ISBN:0-89791-655-7

Authors

David Haussler	U.C. Santa Cruz, Santa Cruz, California
H. Sebastian Seung	AT&T Bell Laboratories, Murray Hill, New Jersey
Michael Kearns	AT&T Bell Laboratories, Murray Hill, New Jersey
Naftali Tishby	Hebrew University, Jerusalem, Israel

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 16, Downloads (12 Months): 31, Citation Count: 18

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/180139.181018 What is a DOI?

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Shun-ichi Amari , Naotake Fujita , Shigeru Shinomoto, Four types of learning curves, Neural Computation, v.4 n.4, p.605-618, July 1992 [doi>10.1162/neco.1992.4.4.605]
	2	Eric B. Baum , Yuh-Dauh Lyuu, The transition to perfect generalization in perceptrons, Neural Computation, v.3 n.3, p.386-401, Fall 1991
	3	Gyora M. Benedek , Alon Itai, Learnability with respect to fixed distributions, Theoretical Computer Science, v.86 n.2, p.377-389, Sept. 2, 1991 [doi>10.1016/0304-3975(91)90026-X]
	4	David Cohn , Gerald Tesauro, How tight are the Vapnik-Chervonenkis bounds?, Neural Computation, v.4 n.2, p.249-269, March 1992 [doi>10.1162/neco.1992.4.2.249]
	5	L. Devroye and G. Lugosi. Lower bounds in pattern recognition and learning. 1994. Preprint.
	6	R. M. Dudley. Centrallimit theorems for emplricalmeasures. Annals of Probability, 6(6):899-929, 1978.
	7	Andrzej Ehrenfeucht , David Haussler, A general lower bound on the number of examples needed for learning, Information and Computation, v.82 n.3, p.247-261, Sep. 1989 [doi>10.1016/0890-5401(89)90002-3]
	8	A. Engel and W. Fink. Statistical mechanics calculaOon of Vapnik Chervonenkis bounds for perceptrons. J. Phys., 26:6893-6914, 1993.
	9	A. Engel and C. van den Broeck. Systems that can learn from examples: replica calculation of uniform convergence bounds for the perceptron. Phys. Rev. Lett., 71:1772-1775, 1993.
	10	E. Gardner. The space of interactions in neural network models. J. Phys., A21:257-270, 1988.
	11	E. Gardner and B. Derrida. Three unfinished works on the optimal storage capacity of networks. J. Phys., A22:1983- 1994, 1989.
	12	Sally A. Goldman , Michael J. Kearns , Robert E. Schapire, On the sample complexity of weak learning, Proceedings of the third annual workshop on Computational learning theory, p.217-231, August 06-08, 1990, Rochester, New York, United States
	13	G. GySrgyi. First-order transition to perfect generalization in a neural network with binary synapses. Phys. Ray., A41:7097-7100, 1990.
	14	David Haussler, Decision theoretic generalizations of the PAC model for neural net and other learning applications, Information and Computation, v.100 n.1, p.78-150, Sept. 1992 [doi>10.1016/0890-5401(92)90010-D]
	15	David Haussler , Michael Kearns , Robert Schapire, Bounds on the sample complexity of Bayesian learning using information theory and the VC dimension, Proceedings of the fourth annual workshop on Computational learning theory, p.61-74, August 05-07, 1991, Santa Cruz, California, United States
	16	Esther Levin , Naftali Tishby , Sara A. Solla, A statistical approach to learning and generalization in layered neural networks, Proceedings of the second annual workshop on Computational learning theory, p.245-260, December 1989, Santa Cruz, California, United States
	17	Yuh-Dauh Lyuu , Igor Rivin, Tight bounds on transition to perfect generalization in perceptrons, Neural Computation, v.4 n.6, p.854-862, Nov. 1992 [doi>10.1162/neco.1992.4.6.854]
	18	Gale L. Martin , James A. Pittman, Recognizing hand-printed letters and digits using backpropagation learning, Neural Computation, v.3 n.2, p.258-267, Summer 1991 [doi>10.1162/neco.1991.3.2.258]
	19	D. Pollard. Convergence of Stochastic Processes. Springer- Verlag, 1984.
	20	D. B. Schwartz, V. K. Samalam, J. S. Denker, and S. A. Solla. Exhaustive learning. Neural Comput., 2:374-385, 1990.
	21	H. S. Setmg, H. Sompolinsky, and N. Tishby. Statistical mechanics of learning from examples. Physical Review, A45:6056-6091, 1992.
	22	Hans Ulrich Simon, General bounds on the number of examples needed for learning probabilistic concepts, Proceedings of the sixth annual conference on Computational learning theory, p.402-411, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168385]
	23	H. S. Seung , H. Sompolinsky , N. Tishby, Learning curves in large neural networks, Proceedings of the fourth annual workshop on Computational learning theory, p.112-127, August 05-07, 1991, Santa Cruz, California, United States
	24	H. Sompolinsky, N. Tishby, and H. S. Seung. Learning from examples in large neural networks. Phys. Rev. Lett., 65(13):1683-1686, 1990.
	25	Vladimir Vapnik , Esther Levin , Yann Le Cun, Measuring the VC-dimension of a learning machine, Neural Computation, v.6 n.5, p.851-876, Sept. 1994 [doi>10.1162/neco.1994.6.5.851]
	26	Vladimir Vapnik, Estimation of Dependences Based on Empirical Data: Springer Series in Statistics (Springer Series in Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 1982
	27	V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applicatwns, 16(2):264- 280, 1971.
	28	T. L. H. Watkin, A. Rau, and M. Biehl. The statistical mechanics of learning a rule. Rev. Mod. Phys., 65:499-556, 1993.

CITED BY 18

	Eric B. Baum , Dan Boneh , Charles Garrett, On genetic algorithms, Proceedings of the eighth annual conference on Computational learning theory, p.230-239, July 05-08, 1995, Santa Cruz, California, United States
	David Haussler , Manfred Opper, General bounds on the mutual information between a parameter and n conditionally independent observations, Proceedings of the eighth annual conference on Computational learning theory, p.402-411, July 05-08, 1995, Santa Cruz, California, United States
	Michael Kearns , Yishay Mansour , Andrew Y. Ng , Dana Ron, An experimental and theoretical comparison of model selection methods, Proceedings of the eighth annual conference on Computational learning theory, p.21-30, July 05-08, 1995, Santa Cruz, California, United States
	Lawrence K. Saul , Satinder P. Singh, Markov decision processes in large state spaces, Proceedings of the eighth annual conference on Computational learning theory, p.281-288, July 05-08, 1995, Santa Cruz, California, United States
	Joel Ratsaby , Ronny Meir , Vitaly Maiorov, Towards robust model selection using estimation and approximation error bounds, Proceedings of the ninth annual conference on Computational learning theory, p.57-67, June 28-July 01, 1996, Desenzano del Garda, Italy
	Lawrence K. Saul , Satinder P. Singh, Learning curve bounds for a Markov decision process with undiscounted rewards, Proceedings of the ninth annual conference on Computational learning theory, p.147-156, June 28-July 01, 1996, Desenzano del Garda, Italy
	Anthony M. Zador , Barak A. Pearlmutter, VC dimension of an integrate-and-fire neuron model, Proceedings of the ninth annual conference on Computational learning theory, p.10-18, June 28-July 01, 1996, Desenzano del Garda, Italy
	Jeong Han Kim , James R. Roche, On the optimal capacity of binary neural networks: rigorous combinatorial approaches, Proceedings of the eighth annual conference on Computational learning theory, p.240-249, July 05-08, 1995, Santa Cruz, California, United States
	Šarūnas Raudys , Dean M. Young, Results in statistical discriminant analysis: a review of the former Soviet union literature, Journal of Multivariate Analysis, v.89 n.1, p.1-35, April 2004
	Michael Kearns , Yishay Mansour , Andrew Y. Ng , Dana Ron, An Experimental and Theoretical Comparison of Model SelectionMethods, Machine Learning, v.27 n.1, p.7-50, April 1997
	Satinder Singh , Peter Dayan, Analytical Mean Squared Error Curves for Temporal DifferenceLearning, Machine Learning, v.32 n.1, p.5-40, July 1998
	Wray Buntine, A Guide to the Literature on Learning Probabilistic Networks from Data, IEEE Transactions on Knowledge and Data Engineering, v.8 n.2, p.195-210, April 1996
	Hanzhong Gu , Haruhisa Takahashi, Exponential or Polynomial Learning Curves? Case-Based Studies, Neural Computation, v.12 n.4, p.795-809, April 2000
	Eric B. Baum , Dan B. Boneh , Charles B. Garrett, Where Genetic Algorithms Excel, Evolutionary Computation, v.9 n.1, p.93-124, January 2001
	Michael Kearns, A bound on the error of cross validation using the approximation and estimation rates, with consequences for the training-test split, Neural Computation, v.9 n.5, p.1143-1161, July 1, 1997
	Thomas G. Dietterich, Approximate statistical tests for comparing supervised classification learning algorithms, Neural Computation, v.10 n.7, p.1895-1923, Oct. 1998
	Anthony M. Zador , Barak A. Pearlmutter, Vc dimension of an integrate-and-fire neuron model, Neural Computation, v.8 n.3, p.611-624, April 1, 1996
	K. -R. Müller , M. Finke , N. Murata , K. Schulten , S. Amari, A numerical study on learning curves in stochastic multilayer feedforward networks, Neural Computation, v.8 n.5, p.1085-1106, July 1, 1996