PAC-like upper bounds for the sample complexity of leave-one-out cross-validation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

PAC-like upper bounds for the sample complexity of leave-one-out cross-validation

Full text

Pdf (932 KB)

Source

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

Desenzano del Garda, Italy

Pages: 41 - 50

Year of Publication: 1996

ISBN:0-89791-811-8

Author

Sean B. Holden

Department of Computer Science, University College London, Gower Street, London WC1E 6BT, United Kingdom

Sponsors

Univ degli Studi de Milano : Universite degli Studi de Milano
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): 0, Downloads (12 Months): 8, Citation Count: 3

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Request Permissions 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/238061.238067 What is a DOI?

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	Martin Anthony , Norman Biggs, Computational learning theory: an introduction, Cambridge University Press, New York, NY, 1992
	2	Eric B. Baum , David Haussler, What size net gives valid generalization?, Neural Computation, v.1 n.1, p.151-160, Spring 1990 [doi>10.1162/neco.1989.1.1.151]
	3	Sean B. Holden and Peter J. W. Rayner. Generalization and PAC learning: Some new results for the class of generalized single layer networks. IEEE Transactzons on Neural Networks, 6(2):368- 380, March 1995.
	4	D. Haussler , N. Littlestone , M. K. Warmuth, PREDICTING {0,1}-FUNCTIONS ON RANDOMLY DRAWN POINTS, University of California at Santa Cruz, Santa Cruz, CA, 1990
	5	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]
	6	Sean B. Holden , Mahesan Niranjan, On the practical applicability of VC dimension bounds, Neural Computation, v.7 n.6, p.1265-1288, Nov. 1995 [doi>10.1162/neco.1995.7.6.1265]
	7	Anselm Blumer , A. Ehrenfeucht , David Haussler , Manfred K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM (JACM), v.36 n.4, p.929-965, Oct. 1989 [doi>10.1145/76359.76371]
	8	D J Hand, Recent advances in error rate estimation, Pattern Recognition Letters, v.4 n.5, p.335-346, Oct. 1986 [doi>10.1016/0167-8655(86)90054-1]
	9	G.T. Toussaint. Bibliography on estimation of misclassification. IEEE Transactions on Informatwn Theory, 20:472-479, 1974.
	10	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 [doi>10.1145/225298.225301]
	11	Luc P. Devroye and T. J. Wagner. Distribution-free performance bounds for potential function rules. IEEE Transactions on Information Theory, IT- 25(5):601-604, September 1979.
	12	Luc P. Devroye and T. J. Wagner. Distribution-free inequalities for the deleted and holdout error estimates. IEEE Transactzons on Informatzon Theory, 25(2):202-207, March 1979.
	13	Joel Ratsaby and Ronny Meir. Finite sample size results for robust model selection; application to neural networks. Technical Report NC-TR-96-006, Faculty of Electrical Engineering, Technion, Haifa 32000, Israel, January 1996. Published in the NeuroCOLT technical report series.
	14	Avrim Blum, 1996. Private communication.
	15	Ron Kohavi. A study of cross-validation and bootstrap for accuracy estimation and model selection. In Chriss S. Mellish, editor, Proceedings of the ldth Internatwnal Joint Conference on Artzficial Intelligence, pages 1137-1143. Morgan Kaufmann Publishers, Inc., 1995.

CITED BY 3

	Michael Kearns , Dana Ron, Algorithmic stability and sanity-check bounds for leave-one-out cross-validation, Proceedings of the tenth annual conference on Computational learning theory, p.152-162, July 06-09, 1997, Nashville, Tennessee, United States
	Michael Kearns , Dana Ron, Algorithmic stability and sanity-check bounds for leave-one-out cross-validation, Neural Computation, v.11 n.6, p.1427-1453, Aug. 15, 1999
	Martin Anthony , Sean B. Holden, Cross-validation for binary classification by real-valued functions: theoretical analysis, Proceedings of the eleventh annual conference on Computational learning theory, p.218-229, July 24-26, 1998, Madison, Wisconsin, United States