K-fold cross validation

Tôi xin giới thiệu một kĩ thuật đánh giá sai số (trung bình). Và việc đánh giá sai số này đc đưa vào ứng dụng trong việc chọn tham số bằng phương pháp gird search method . Cụ thể thì tôi sẽ giới thiệu sau. Và tôi sẽ làm rõ vì sao hướng tiếp cận K-fold cross validation có điểm tốt gì?

K-fold cross validation is used in the field of machine learning to determine how accurately a learning algorithm will be able to predict data that it was not trained on. When using the k-fold method, the training dataset is randomly partitioned into k groups. The learning algorithm is then trained k times, using all of the training set data points except those in the kth group. The form of the algorithm is as follows:

* Divide the training set into k partitions.
* For each k:

* Make T the dataset that contains all training data points except those in the kth group.
* Train the algorithm using T as the training set.
* Test the trained algorithm, using the kth set as the test set. Record the number of errors.

* Report the mean error over all k test sets.

K-fold cross validation is extremely useful, if the correct value of k is chosen. It is less ‘wasteful’ of data than test set cross validation, and less ‘expensive’ than leave-one-out cross validation. In general, if the correct value of k is used, k-fold cross validation provides the best estimate cross validation error.

Unfortunately, there is no theoretically ‘perfect’ way of determining the appropriate k value. Using the value k = 10 seems to be a good rule of thumb, although the true best value differs for each algorithm and each dataset. It is interesting to note that when k is allowed to increase until it is the size of the total dataset, k-fold cross validation behaves identically to leave-one-out cross validation.

from link

Bài báo liên quan link


2 Responses to “K-fold cross validation”

  1. vanchanh123 Says:

    Tìm grid-search software

  2. vanchanh123 Says:

    Cross-validation (statistics)
    From Wikipedia, the free encyclopedia
    Jump to: navigation, search

    Cross-validation, sometimes called rotation estimation,[1][2][3] is a technique for assessing how the results of a statistical analysis will generalize to an independent data set. It is mainly used in settings where the goal is prediction, and one wants to estimate how accurately a predictive model will perform in practice. One round of cross-validation involves partitioning a sample of data into complementary subsets, performing the analysis on one subset (called the training set), and validating the analysis on the other subset (called the validation set or testing set). To reduce variability, multiple rounds of cross-validation are performed using different partitions, and the validation results are averaged over the rounds.

    Cross-validation is important in guarding against testing hypotheses suggested by the data (called “Type III errors”[4]), especially where further samples are hazardous, costly or impossible to collect (see uncomfortable science).

    * 1 Purpose of cross validation
    * 2 Common types of cross-validation
    o 2.1 K-fold cross-validation
    o 2.2 k × 2 cross-validation
    o 2.3 Repeated random sub-sampling validation
    o 2.4 Leave-one-out cross-validation
    * 3 Measures of fit
    * 4 Applications
    * 5 Statistical properties
    * 6 Computational issues
    * 7 Relationship to other forms of validation
    * 8 Limitations and misuse
    * 9 Notes and references
    * 10 See also

    [edit] Purpose of cross validation

    Suppose we have a model with one or more unknown parameters, and a data set to which the model can be fit (the training data set). The fitting process optimizes the model parameters to make the model fit the training data as well as possible. If we then take an independent sample of validation data from the same population as the training data, it will generally turn out that the model does not fit the validation data as well as it fits the training data. This is called overfitting, and is particularly likely to happen when the size of the training data set is small, or when the number of parameters in the model is large. Cross-validation is a way to predict the fit of a model to a hypothetical validation set when an explicit validation set is not available.

    Linear regression provides a simple illustration of overfitting. In linear regression we have real response values Y1, …, Yn, and vector covariates X1, …, Xp. We can use least squares to fit a hyperplane a + b1X1 + … + bpXp between the Y and X data, and then assess the fit using the mean squared error (MSE)

    \sum_i (Y_i – a – b_1X_{1i} – \cdots – b_pX_{pi})^2/n,

    where Xji is the value of variable Xj corresponding to the ith response value Yi.

    It can be shown under mild assumptions that the expected value of the MSE for the training set is (n − p − 1)/(n + p + 1) < 1 times the expected value of the MSE for the validation set (the expected value is taken over the distribution of training sets). Thus if we fit the model and compute the MSE on the training set, we will get an optimistically biased assessment of how well the model will fit an independent data set. This biased estimate is called the in-sample estimate of the fit, whereas the cross-validation estimate is an out-of-sample estimate.

    Since in linear regression it is possible to mathematically compute the factor (n − p − 1)/(n + p + 1) by which the training MSE underestimates the validation MSE, cross-validation is not practically useful in that setting. However in most other regression procedures (e.g. logistic regression), there is no simple formula to make this adjustment. Cross-validation is a generally applicable way to predict the performance of a model on a validation set using computation in place of mathematical analysis.
    [edit] Common types of cross-validation
    [edit] K-fold cross-validation

    In K-fold cross-validation, the original sample is randomly 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. The advantage of this method over repeated random sub-sampling is that all observations are used for both training and validation, and each observation is used for validation exactly once. 10-fold cross-validation is commonly used.[5]

    [edit] k × 2 cross-validation

    This is a variation on k-fold cross-validation. For each fold, we randomly assign data points to two sets d0 and d1, so that both sets are equal size (this is usually implemented as shuffling the data array and then splitting in two). We then train on d0 and test on d1, followed by training on d1 and testing on d0.

    This has the advantage that our training and test sets are both large, and each data point is used for both training and validation on each fold. In general, k = 5 (resulting in 10 training/validation operations) has been shown to be the optimal value of k for this type of cross-validation[citation needed].
    [edit] Repeated random sub-sampling validation


    [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. Leave-one-out cross-validation is usually very expensive from a computational point of view because of the large number of times the training process is repeated.
    [edit] Measures of fit

    [edit] Applications

    Cross-validation can be used to compare the performances of different predictive modeling procedures. For example, suppose we are interested in optical character recognition, and we are considering using either support vector machines (SVM) or k nearest neighbors (KNN) to predict the true character from an image of a handwritten character. Using cross-validation, we could objectively compare these two methods in terms of their respective fractions of misclassified characters. If we simply compared the methods based on their in-sample error rates, the KNN method would likely appear to perform better, since it is more flexible and hence more prone to overfitting compared to the SVM method.

    [edit] Statistical properties



    The variance of F* can be large.[7][8] For this reason, if two statistical procedures are compared based on the results of cross-validation, it is important to note that the procedure with the better estimated performance may not actually be the better of the two procedures (i.e. it may not have the better value of EF). Some progress has been made on constructing confidence intervals around cross-validation estimates,[7] but this is considered a difficult problem.
    [edit] Computational issues

    [edit] Relationship to other forms of validation

    In "true validation," or "holdout validation," a subset of observations is chosen randomly from the initial sample to form a validation or testing set, and the remaining observations are retained as the training data. Normally, less than a third of the initial sample is used for validation data.[9] This would generally not be considered to be cross-validation since only a single partition of the data into training and testing sets is used.
    [edit] Limitations and misuse

    Cross-validation only yields meaningful results if the validation set and test set are drawn from the same population. In many applications of predictive modeling, the structure of the system being studied evolves over time. This can introduce systematic differences between the training and validation sets. For example, if a model for predicting stock values is trained on data for a certain five year period, it is unrealistic to treat the subsequent five year period as a draw from the same population. As another example, suppose a model is developed to predict an individual's risk for being diagnosed with a particular disease within the next year. If the model is trained using data from a study involving only a specific population group (e.g. young people or males), but is then applied to the general population, the cross-validation results from the training set could differ greatly from the actual predictive performance.

    If carried out properly, and if the validation set and training set are from the same population, cross-validation is nearly unbiased. However there are many ways that cross-validation can be misused. If it is misused and a true validation study is subsequently performed, the prediction errors in the true validation are likely to be much worse than would be expected based on the results of cross-validation.

    These are some ways that cross-validation can be misused:

    * By using cross-validation to assess several models, and only stating the results for the model with the best results.

    * By performing an initial analysis to identify the most informative features using the entire data set – if feature selection or model tuning is required by the modeling procedure, this must be repeated on every training set. If cross-validation is used to decide which features to use, an inner cross-validation to carry out the feature selection on every training set must be performed.


    [edit] Notes and references

    1. ^ Geisser, Seymour (1993). Predictive Inference. New York: Chapman and Hall. ISBN 0412034719.
    2. ^ 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. http://citeseer.ist.psu.edu/kohavi95study.html. (Morgan Kaufmann, San Mateo)
    4. ^ Mosteller, Frederick (1948). "A k-sample slippage test for an extreme population". Annals of Mathematical Statistics 19 (1): 58–65. doi:10.1214/aoms/1177730290. MR0024116. JSTOR 2236056.
    5. ^ GJ, McLachlan; K.A. Do, C. Ambroise (2004). Analyzing microarray gene expression data. Wiley.
    6. ^ Picard, Richard; Cook, Dennis (1984). "Cross-Validation of Regression Models". Journal of the American Statistical Association 79 (387): 575–583. doi:10.2307/2288403. http://www.jstor.org/stable/2288403.
    7. ^ a b Efron, Bradley; Tibshirani, Robert (1997). "Improvements on cross-validation: The .632 + Bootstrap Method". Journal of the American Statistical Association 92 (438): 548–560. doi:10.2307/2965703. MR1467848. JSTOR 2965703.
    8. ^ Stone, M (1977). "Asymptotics for and against cross-validation". Biometrika 64 (1): 29–35. doi:10.1093/biomet/64.1.29. MR0474601. JSTOR 2335766.
    9. ^ "Tutorial 12". Decision Trees Interactive Tutorial and Resources. Archived from the original on 2006-06-23. http://web.archive.org/web/20060623055814/http://decisiontrees.net/node/36. Retrieved 2006-06-21.

    [edit] See also

    * Resampling (statistics)
    * Bootstrap aggregating (bagging)
    * Bootstrapping (statistics)


Leave a Reply


WordPress.com Logo


Twitter picture


Facebook photo


Google+ photo


Connecting to %s

%d bloggers like this: