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

Published 1 January 1996Open access

Sean B. Holden

Citations19

TL;DR

This paper addresses the following question: if the authors have n training examples what is the probability that the leave-one-out cross-validation estimate differs from the actual error probability by more than a constant c?

Abstract

Article Free Access Share on PAC-like upper bounds for the sample complexity of leave-one-out cross-validation Author: Sean B. Holden Department of Computer Science, University College London, Gower Street, London WC1E 6BT, United Kingdom Department of Computer Science, University College London, Gower Street, London WC1E 6BT, United KingdomSearch about this author Authors Info & Claims COLT '96: Proceedings of the ninth annual conference on Computational learning theoryJanuary 1996Pages 41–50https://doi.org/10.1145/238061.238067Published:01 January 1996Publication History 9citation527DownloadsMetricsTotal Citations9Total Downloads527Last 12 Months36Last 6 weeks6 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Keywords

Computer ScienceEngineering

A study of cross-validation and bootstrap for accuracy estimation and model selection

10,733 Citations1995Ron Kohavi

The results indicate that for real-word datasets similar to the authors', the best method to use for model selection is ten fold stratified cross validation even if computation power allows using more folds.

Journal of the ACMLearnability and the Vapnik-Chervonenkis dimension

1,852 Citations1989Anselm Blumer, Andrzej Ehrenfeucht +2 more

This paper shows that the essential condition for distribution-free learnability is finiteness of the Vapnik-Chervonenkis dimension, a simple combinatorial parameter of the class of concepts to be learned.

View PDF

Neural ComputationWhat Size Net Gives Valid Generalization?

1,555 Citations1989Eric B. Baum, David Haussler

It is shown that if m O(W/ ∊ log N/∊) random examples can be loaded on a feedforward network of linear threshold functions with N nodes and W weights, so that at least a fraction 1 ∊/2 of the examples are correctly classified, then one has confidence approaching certainty that the network will correctly classify a fraction 2 ∊ of future test examples drawn from the same distribution.

IEEE Transactions on Information TheoryBibliography on estimation of misclassification

307 Citations1974Godfried Toussaint

Articles, books, and technical reports on the theoretical and experimental estimation of probability of misclassification are listed for the case of correctly labeled or preclassified training data.

IEEE Transactions on Information TheoryDistribution-free performance bounds for potential function rules

227 Citations1979Luc Devroye, T. Wagner

It is shown that the mean-square difference between the probability of error for the nde and its deleted estimate is bounded by A/ \sqrt{n} where A is an explicitly given constant depending only on M and the potential function.

Computational learning theory: an introduction

207 Citations1992Martin Anthony, Norman Biggs

This volume is relatively self contained as the necessary background material from logic, probability and complexity theory is included, and will form an introduction to the theory of computational learning, suitable for a broad spectrum of graduate students from theoretical computer science and mathematics.

An experimental and theoretical comparison of model selection methods

170 Citations1995Michael Kearns, Yishay Mansour +2 more

View PDF

Information and ComputationPredicting {0, 1}-Functions on Randomly Drawn Points

152 Citations1994David Haussler, N. Littlestone +1 more

Pattern Recognition LettersRecent advances in error rate estimation

132 Citations1986David J. Hand

Different types of error rates are described and the state of the art of error rate estimation at the time of Toussaint's survey is briefly summarised, and the two major advances, namely bootstrap and average conditional error rates estimation methods, and their extensions, are described in detail.

IEEE Transactions on Information TheoryDistribution-free inequalities for the deleted and holdout error estimates

119 Citations1979Luc Devroye, T. Wagner

In the discrimination problem the random variable \theta, known to take values in {1,\ldots,M} , is estimated from the random vector X taking values in {\bfR}^{d} .