Algorithmic stability and sanity-check bounds for leave-one-out cross-validation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Algorithmic stability and sanity-check bounds for leave-one-out cross-validation

Full text

Pdf (1.66 MB)

Source

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

Nashville, Tennessee, United States

Pages: 152 - 162

Year of Publication: 1997

ISBN:0-89791-891-6

Authors

Michael Kearns	AT&T Labs Research
Dana Ron	MIT Laboratory for Computer Science

Sponsors

AT&T Labs :
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence
Vanderbilt University : Vanderbilt University

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 23, Citation Count: 16

Additional Information:

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/267460.267491 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	L. Devroye, L. Gyrijfi, and G. Lugosi. A Probabilistic Theory of Pattern Recognition. Springer Verlag, 1996.
	2	L. P. Devroye and T. J. Wagner. Distribution-free inequalities for the deleted and holdout error estimates. IEEE Transactions on Information Theory, IT-25(2):202-207, 1979.
	3	L. P. Devroye and T. J. Wagner. Distribution-free performance bounds for potential function rules. IEEE Transactions on Information Theory, IT-25(5):60 l-604, 1979.
	4	Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
	5	S. Geman and D. Geman. Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 6:721-741,1984.
	6	David Haussler , Michael Kearns , H. Sebastian Seung , Naftali Tishby, Rigorous learning curve bounds from statistical mechanics, Machine Learning, v.25 n.2-3, p.195-236, Nov./Dec. 1996 [doi>10.1007/BF00114010]
	7	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]
	8	S. B. Holden. Cross-validation and the PAC learning model. Research Note RN/96/64, Dept. of CS, Univ. College, London, 1996.
	9	Sean B. Holden, PAC-like upper bounds for the sample complexity of leave-one-out cross-validation, Proceedings of the ninth annual conference on Computational learning theory, p.41-50, June 28-July 01, 1996, Desenzano del Garda, Italy [doi>10.1145/238061.238067]
	10	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 [doi>10.1162/neco.1997.9.5.1143]
	11	Michael J. Kearns , Robert E. Schapire , Linda M. Sellie, Toward Efficient Agnostic Learning, Machine Learning, v.17 n.2-3, p.115-141, Nov./Dec. 1994 [doi>10.1007/BF00993468]
	12	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]
	13	Ron Kohavi. A study of cross-validation and bootstrap for accuracy estimation and model selection. In the International Joint Conference on Artifcal Intelligence, 1995.
	14	A.J. Miller. Subset Selection in Regression. Chapman and Hall, 1990.
	15	W. H. Rogers and T. J. Wagner. A fine sample distributionfree performance bound for local discrimination rules. The Annals of Statistics, 6(3):506-514, 1978.
	16	H. S. Seung, H. Sompolinsky, and N. Tishby. Statistical mechanics of learning from examples. Physical Review, A45:6056-6091,1992.
	17	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

CITED BY 16

	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
	Avrim Blum , Adam Kalai , John Langford, Beating the hold-out: bounds for K-fold and progressive cross-validation, Proceedings of the twelfth annual conference on Computational learning theory, p.203-208, July 07-09, 1999, Santa Cruz, California, United States
	Claude Nadeau , Yoshua Bengio, Inference for the Generalization Error, Machine Learning, v.52 n.3, p.239-281, September 2003
	Gaétan Monari , Gérard Dreyfus, Local overfitting control via leverages, Neural Computation, v.14 n.6, p.1481-1506, June 2002
	Miyoung Shin , Amrit L. Goel, Empirical Data Modeling in Software Engineering Using Radial Basis Functions, IEEE Transactions on Software Engineering, v.26 n.6, p.567-576, June 2000
	Tom Bylander, Estimating Generalization Error on Two-Class Datasets Using Out-of-Bag Estimates, Machine Learning, v.48 n.1-3, p.287-297, 2002
	Shashi Kumar , Sanjeev Kumar , Prakash , Ravi Shankar , M. K. Tiwari , Shashi Bhushan Kumar, Prediction of flow stress for carbon steels using recurrent self-organizing neuro fuzzy networks, Expert Systems with Applications: An International Journal, v.32 n.3, p.777-788, April, 2007
	G. Y. Chen , W. F. Xie, Pattern recognition with SVM and dual-tree complex wavelets, Image and Vision Computing, v.25 n.6, p.960-966, June, 2007
	Ricco Rakotomalala , Jean-Hughes Chauchat , Francois Pellegrino, Accuracy estimation with clustered dataset, Proceedings of the fifth Australasian conference on Data mining and analystics, p.17-22, November 29-30, 2006, Sydney, Australia
	Byoung-Jun Park , Witold Pedrycz , Sung-Kwun Oh, An approach to fuzzy granule-based hierarchical polynomial networks for empirical data modeling in software engineering, Information and Software Technology, v.50 n.9-10, p.912-923, August, 2008
	Jeoung-Nae Choi , Sung-Kwun Oh , Witold Pedrycz, Structural and parametric design of fuzzy inference systems using hierarchical fair competition-based parallel genetic algorithms and information granulation, International Journal of Approximate Reasoning, v.49 n.3, p.631-648, November, 2008
	Zoran Bosnić , Igor Kononenko, Estimation of individual prediction reliability using the local sensitivity analysis, Applied Intelligence, v.29 n.3, p.187-203, December 2008
	Zoran Bosnić , Igor Kononenko, Comparison of approaches for estimating reliability of individual regression predictions, Data & Knowledge Engineering, v.67 n.3, p.504-516, December, 2008
	Amit Dhurandhar , Alin Dobra, Semi-analytical method for analyzing models and model selection measures based on moment analysis, ACM Transactions on Knowledge Discovery from Data (TKDD), v.3 n.1, p.1-51, March 2009
	G. Y. Chen , G. Dudek, Auto-correlation wavelet support vector machine, Image and Vision Computing, v.27 n.8, p.1040-1046, July, 2009
	Zoran Bosnić , Igor Kononenko, An overview of advances in reliability estimation of individual predictions in machine learning, Intelligent Data Analysis, v.13 n.2, p.385-401, April 2009