Cross-validation
From Wikipedia, the free encyclopedia
Cross-validation, sometimes called rotation estimation[1] [2] [3], is the statistical practice of partitioning a sample of data into subsets such that the analysis is initially performed on a single subset, while the other subset(s) are retained for subsequent use in confirming and validating the initial analysis.
The initial subset of data is called the training set; the other subset(s) are called validation or testing sets.
The theory of cross-validation was inaugurated by Seymour Geisser. It is important in guarding against testing hypotheses suggested by the data ("Type III error"), especially where further samples are hazardous, costly or impossible (uncomfortable science) to collect.
Contents |
[edit] Common types of cross-validation
[edit] Holdout validation
Holdout validation is not cross-validation in the common sense, because the data are never crossed over. Observations are chosen randomly from the initial sample to form the validation data, and the remaining observations are retained as the training data. Normally, less than a third of the initial sample is used for validation data.[4]
[edit] K-fold cross-validation
In K-fold cross-validation, the original sample is partitioned into K subsamples. Of the K subsamples, a single subsample is retained as the validation data for testing the model, and the remaining K − 1 subsamples are used as training data. The cross-validation process is then repeated K times (the folds), with each of the K subsamples used exactly once as the validation data. The K results from the folds then can be averaged (or otherwise combined) to produce a single estimation.
[edit] Leave-one-out cross-validation
As the name suggests, leave-one-out cross-validation (LOOCV) involves using a single observation from the original sample as the validation data, and the remaining observations as the training data. This is repeated such that each observation in the sample is used once as the validation data. This is the same as a K-fold cross-validation with K being equal to the number of observations in the original sample, though efficient algorithms exist in some cases, for example with kernel regression and with Tikhonov regularization.
[edit] Error estimation
The parameter estimation error can be computed. Common error metrics are the Mean squared error (MSE) and the Root mean squared error (RMSE), respectively the estimated variance and standard deviation of the cross validation.
[edit] Using a Validation Set
The validation set is independent from the training AND testing set, it is frequently not discussed under the cross-validation topics, because cross-validation refers usually to just the training/testing split including 10-fold,etc.
The validation set is needed in case you want to watch out for overfitting for example, or in case you want to choose the best input parameters for a classifier model. In that case you split the data in 3 parts: training + test + validation, then do the following:
1) Use the training data in a cross-validation scheme like 10-fold or 2/3 - 1/3 to simply estimate the average quality (e.g. accuracy, F1-score, or error rate of a classifier)
2) Leave an additional subset of data (the validation set) to use to adjust these additional parameters or adjust the structure (such as # of layers or neurons in a neural network, # of nodes in a decision tree, etc) of the model, for example: you can use the validation set to decide when to stop growing the decision tree, thus to test for overfitting; or to choose the best parameters such as in Rocchio or SVM classifiers: in this case you obtain a model with a given set of parameters based on the training set, then estimate the quality using the validation set. Repeat this for many parameter/structure choices and select the choice with best quality on the validation set
3) Finally take this best choice of parameters+model from step 2 and use it to estimate the quality on the test data
as you can see that you use:
- the training to compute the model,
- the validation set to choose the best parameters of this model (in case there are "additional" parameters tat cannot be computed based on training)
- the test data as the final "judge" to get an estimate of the quality on new data that was used neither to train the model, nor to determine its underlying parameters or structure or complexity of this model
See related topic: Early stopping
[edit] References
- ^ Kohavi, Ron (1995). "A study of cross-validation and bootstrap for accuracy estimation and model selection". Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence 2 (12): 1137–1143.(Morgan Kaufmann, San Mateo)
- ^ Chang, J., Luo, Y., and Su, K. 1992. GPSM: a Generalized Probabilistic Semantic Model for ambiguity resolution. In Proceedings of the 30th Annual Meeting on Association For Computational Linguistics (Newark, Delaware, June 28 - July 02, 1992). Annual Meeting of the ACL. Association for Computational Linguistics, Morristown, NJ, 177-184
- ^ Devijver, P. A., and J. Kittler, Pattern Recognition: A Statistical Approach, Prentice-Hall, London, 1982
- ^ Tutorial 12. Decision Trees Interactive Tutorial and Resources. Retrieved on 2006-06-21.
[edit] See also
[edit] External links
- Naive Bayes implementation with cross-validation in Visual Basic (includes executable and source code)
- A generic k-fold cross-validation implementation (free open source; includes a distributed version that can utilize multiple computers and in principle can speed up the running time by several orders of magnitude.)
