Cross Validation — What, Why and How | Machine Learning
What is Cross Validation , Why it is used and What are the different types ?
What is Cross Validation and Why do we Need it ?
In a Supervised Machine Learning problem , we usually train the model on the dataset and use the trained model to predict the target, given new predictor values.
But, How do we know if the model we have trained on the dataset will producing effective and accurate results on the new input data.
We cannot conclude that the model has performed well based on the error rates or certain statistic measures (such as R square statistic) that we get from the dataset on which the model is trained.
The main problem is that there is no way of knowing if the model has high bias (underfitted) or high variance (overfitted) and how well the model will perform on new data just from the error rates from the model.
When it comes to predictive modeling, It’s the duty of the data scientist to ensure that the model is going to perform well on new data.
Cross Validation is a process that helps us do exactly this.
It is the process by which the machine learning models are evaluated on a separate set known as validation set or hold-out set with which the best hyper-parameters are found, so that we get the optimal model, that can be used on future data and which is capable of yielding the best possible predictions
One way of doing this is to split our dataset into 3 parts: Training Set, Validation or Hold-Out set and the Test Set.
before going further, familiarisation of concepts such as bias and variance is required.
Training , Validation and Testing Split
Training Set: The part of the Dataset on which the model is trained
Validation Set: The trained model is then used on this set to predict the targets and the loss is noted. The result is compared to the training set results to check for overfitting or underfitting and this is done repeatedly until certain optimal result is produced.
basically, we are training the model on the training set. but, the hyper-parameters are continuously updated and trained again until the model performs best on the cross-validation set. (By performing best, we are trying to minimize the validation set while also preventing overfitting)
Test Set: The fully trained model, after being evaluated by the validation or hold-out set is used on the test set to get the true test error and this error can be treated as a very good estimate of how the performance of the model will be on any new data
Why test set Shouldn’t be used more than Once ?
Why the test set shouldn’t be used more than once ? Why do we have to use a separate set for cross-validation and testing . why can’t we use the same set of data for both ?
All these questions are essentially are the same and have a common answer:
Using the test set more than once will eventually lead to bias (Not the bias that we usually refer to, in Machine Learning ) because the hyper parameters are being adjusted for optimal performance on the test set. In that case, we cannot use the test set to estimate how well the model will perform on new real life data.
“Meanwhile, the model is used multiple times on the validation set to find the best hyper-parameters. The best one is chosen out of it and is used on the test set”. Just emphasising this point.
Types of Cross-Validation
There are 3 main types of cross validation techniques
- The Standard Validation Set Approach
- The Leave One Out Cross Validation (LOOCV)
- K-fold Cross Validation
In all the above methods, The Dataset is split into training set, validation set and testing set. We will mostly be discussing about training and the validation set as the usage of testing set is common for all the 3 methods and is already mentioned above.
Note: In all the below approaches, the test set is already split and is separate. There’s just not going to be much mention of the test set as we concentrate more on the training set and the validation set
Standard Validation Set Approach
This is a very simple and standard approach and is used commonly. we randomly split the training and the validation set in different proportions from the original dataset.
The model is trained on the training set, evaluated on the validation set and retrained on the training set with different hyper-parameters. This is done until the best hyper-parameter is found the reduces the validation set loss and also does not lead to overfitting.
The model hyper-parameters that produce the best results on the cross validation set is chosen and then it’s performance is measured on a separate test set.
Disadvantages of this approach
- Initially, we randomly split the data into training and validation set. due to this, the validation error estimate of the test set may be somewhat highly variable and which observation goes into which set may be a factor that affects the model parameters.
- We know that more the data given to the model for training , the better. but, due to this split, the amount of data on which training happens, is reduced
Leave One Out Cross Validation
This method tries to overcome the disadvantages of the previous method and it takes an iterative approach.
First Iteration
In the first iteration, we use only the observation (x1,y1) as the entire validation set and train the model on the rest of the n-1 observations.
here, the validation set error E1 is calculated as (h(x1) — (y1))² ,where h(x1) is prediction for X1 from the model.
Second Iteration
We leave (x2,y2) as the validation set and train the model on the rest n-1 observations. E2 is calculated in a similar way to the first iteration but with the validation data of the second iteration.
The process is repeated for n iterations until each and every observation from the training set has been the validation set for exactly once.
This gives us a set of n error estimates
The total validation error was then calculated by taking the mean of the n error estimates we got above.
i.e,
(E1 + E2 + E3 + E4 + ….. + En)/n
This is how the validation set error is calculated in this method and as we are using all the observations except one, for training, more data is given to the model and the error estimate is also not highly variable as we take the mean of n error estimates.
Disadvantages of this approach
This is considered computationally expensive as we are fitting the model n times to get the validation error estimate just once.
K-fold Cross Validation
The K-fold cross validation aims to solve the problem of computation by reducing the number of times the model needs to train in-order to calculate the validation error once.
It is very similar to LOOCV validation approach, except it takes K observations to be part of the validation set instead of 1, for each iteration and the validation error is calculated on these k observations per each iteration, and finally, the mean of all these error rates are taken to be the true validation set error. By doing this, the number of times the model has to be trained on the training set is reduced to n/k.
Usually, this number K is chosen to be something like 5 or 10. but, it depends on the dataset size. if we have a lot of data, a bigger value for K can be used.
Conclusion
Often times in machine learning, we don’t want the model or algorithm that performs best on the training data. rather, we need a model that performs best on the test set and a model that is guaranteed to perform well on new input data.
Cross validation is a very important process that makes sure we are able to find such an algorithm or model.
Cross-Validation in Machine Learning: How to Do It Right
In machine learning (ML), generalization usually refers to the ability of an algorithm to be effective across various inputs. It means that the ML model does not encounter performance degradation on the new inputs from the same distribution of the training data.
For human beings generalization is the most natural thing possible. We can classify on the fly. For example, we would definitely recognize a dog even if we didn’t see this breed before. Nevertheless, it might be quite a challenge for an ML model. That’s why checking the algorithm’s ability to generalize is an important task that requires a lot of attention when building the model.
In this article we will cover:
- What is Cross-Validation: definition, purpose of use and techniques
- Different CV techniques: hold-out, k-folds, Leave-one-out, Leave-p-out, Stratified k-folds, Repeated k-folds, Nested k-folds, Time Series CV
- How to use these techniques: sklearn
- Cross-Validation in Machine Learning: sklearn, CatBoost
- Cross-Validation in Deep Learning: Keras, PyTorch, MxNet
- Best practices and tips: time series, medical and financial data, images
May be useful
What is cross-validation?
Cross-validation is a technique for evaluating a machine learning model and testing its performance. CV is commonly used in applied ML tasks. It helps to compare and select an appropriate model for the specific predictive modeling problem.
CV is easy to understand, easy to implement, and it tends to have a lower bias than other methods used to count the model’s efficiency scores. All this makes cross-validation a powerful tool for selecting the best model for the specific task.
There are a lot of different techniques that may be used to cross-validate a model. Still, all of them have a similar algorithm:
- Divide the dataset into two parts: one for training, other for testing
- Train the model on the training set
- Validate the model on the test set
- Repeat 1-3 steps a couple of times. This number depends on the CV method that you are using
As you may know, there are plenty of CV techniques. Some of them are commonly used, others work only in theory. Let’s see the cross-validation methods that will be covered in this article.
- Hold-out
- K-folds
- Leave-one-out
- Leave-p-out
- Stratified K-folds
- Repeated K-folds
- Nested K-folds
- Time series CV
Hold-out cross-validation
Hold-out cross-validation is the simplest and most common technique. You might not know that it is a hold-out method but you certainly use it every day.
The algorithm of hold-out technique:
- Divide the dataset into two parts: the training set and the test set. Usually, 80% of the dataset goes to the training set and 20% to the test set but you may choose any splitting that suits you better
- Train the model on the training set
- Validate on the test set
- Save the result of the validation
We usually use the hold-out method on large datasets as it requires training the model only once.
It is really easy to implement hold-out. For example, you may do it using sklearn.model_selection.train_test_split.
Still, hold-out has a major disadvantage.
For example, a dataset that is not completely even distribution-wise. If so we may end up in a rough spot after the split. For example, the training set will not represent the test set. Both training and test sets may differ a lot, one of them might be easier or harder.
Moreover, the fact that we test our model only once might be a bottleneck for this method. Due to the reasons mentioned before, the result obtained by the hold-out technique may be considered inaccurate.
k-Fold cross-validation
k-Fold cross-validation is a technique that minimizes the disadvantages of the hold-out method. k-Fold introduces a new way of splitting the dataset which helps to overcome the “test only once bottleneck”.
The algorithm of the k-Fold technique:
- Pick a number of folds – k. Usually, k is 5 or 10 but you can choose any number which is less than the dataset’s length.
- Split the dataset into k equal (if possible) parts (they are called folds)
- Choose k – 1 folds as the training set. The remaining fold will be the test set
- Train the model on the training set. On each iteration of cross-validation, you must train a new model independently of the model trained on the previous iteration
- Validate on the test set
- Save the result of the validation
- Repeat steps 3 – 6 k times. Each time use the remaining fold as the test set. In the end, you should have validated the model on every fold that you have.
- To get the final score average the results that you got on step 6.
To perform k-Fold cross-validation you can use sklearn.model_selection.KFold.
In general, it is always better to use k-Fold technique instead of hold-out. In a head to head, comparison k-Fold gives a more stable and trustworthy result since training and testing is performed on several different parts of the dataset. We can make the overall score even more robust if we increase the number of folds to test the model on many different sub-datasets.
Still, k-Fold method has a disadvantage. Increasing k results in training more models and the training process might be really expensive and time-consuming.
Leave-one-out cross-validation
Leave-one-out сross-validation (LOOCV) is an extreme case of k-Fold CV. Imagine if k is equal to n where n is the number of samples in the dataset. Such k-Fold case is equivalent to Leave-one-out technique.
The algorithm of LOOCV technique:
- Choose one sample from the dataset which will be the test set
- The remaining n – 1 samples will be the training set
- Train the model on the training set. On each iteration, a new model must be trained
- Validate on the test set
- Save the result of the validation
- Repeat steps 1 – 5 n times as for n samples we have n different training and test sets
- To get the final score average the results that you got on step 5.
For LOOCV sklearn also has a built-in method. It can be found in the model_selection library – sklearn.model_selection.LeaveOneOut.
The greatest advantage of Leave-one-out cross-validation is that it doesn’t waste much data. We use only one sample from the whole dataset as a test set, whereas the rest is the training set. But when compared with k-Fold CV, LOOCV requires building n models instead of k models, when we know that n which stands for the number of samples in the dataset is much higher than k. It means LOOCV is more computationally expensive than k-Fold, it may take plenty of time to cross-validate the model using LOOCV.
Thus, the Data Science community has a general rule based on empirical evidence and different researches, which suggests that 5- or 10-fold cross-validation should be preferred over LOOCV.
Leave-p-out cross-validation
Leave-p-out cross-validation (LpOC) is similar to Leave-one-out CV as it creates all the possible training and test sets by using p samples as the test set. All mentioned about LOOCV is true and for LpOC.
Still, it is worth mentioning that unlike LOOCV and k-Fold test sets will overlap for LpOC if p is higher than 1.
The algorithm of LpOC technique:
- Choose p samples from the dataset which will be the test set
- The remaining n – p samples will be the training set
- Train the model on the training set. On each iteration, a new model must be trained
- Validate on the test set
- Save the result of the validation
- Repeat steps 2 – 5 Cp n times
- To get the final score average the results that you got on step 5
You can perform Leave-p-out CV using sklearn – sklearn.model_selection.LeavePOut.
LpOC has all the disadvantages of the LOOCV, but, nevertheless, it’s as robust as LOOCV.
Stratified k-Fold cross-validation
Sometimes we may face a large imbalance of the target value in the dataset. For example, in a dataset concerning wristwatch prices, there might be a larger number of wristwatch having a high price. In the case of classification, in cats and dogs dataset there might be a large shift towards the dog class.
Stratified k-Fold is a variation of the standard k-Fold CV technique which is designed to be effective in such cases of target imbalance.
It works as follows. Stratified k-Fold splits the dataset on k folds such that each fold contains approximately the same percentage of samples of each target class as the complete set. In the case of regression, Stratified k-Fold makes sure that the mean target value is approximately equal in all the folds.
The algorithm of Stratified k-Fold technique:
- Pick a number of folds – k
- Split the dataset into k folds. Each fold must contain approximately the same percentage of samples of each target class as the complete set
- Choose k – 1 folds which will be the training set. The remaining fold will be the test set
- Train the model on the training set. On each iteration a new model must be trained
- Validate on the test set
- Save the result of the validation
- Repeat steps 3 – 6 k times. Each time use the remaining fold as the test set. In the end, you should have validated the model on every fold that you have.
- To get the final score average the results that you got on step 6.
As you may have noticed, the algorithm for Stratified k-Fold technique is similar to the standard k-Folds. You don’t need to code something additionally as the method will do everything necessary for you.
Stratified k-Fold also has a built-in method in sklearn – sklearn.model_selection.StratifiedKFold.
All mentioned above about k-Fold CV is true for Stratified k-Fold technique. When choosing between different CV methods, make sure you are using the proper one. For example, you might think that your model performs badly simply because you are using k-Fold CV to validate the model which was trained on the dataset with a class imbalance. To avoid that you should always do a proper exploratory data analysis on your data.
Repeated k-Fold cross-validation
Repeated k-Fold cross-validation or Repeated random sub-sampling CV is probably the most robust of all CV techniques in this paper. It is a variation of k-Fold but in the case of Repeated k-Folds k is not the number of folds. It is the number of times we will train the model.
The general idea is that on every iteration we will randomly select samples all over the dataset as our test set. For example, if we decide that 20% of the dataset will be our test set, 20% of samples will be randomly selected and the rest 80% will become the training set.
The algorithm of Repeated k-Fold technique:
- Pick k – number of times the model will be trained
- Pick a number of samples which will be the test set
- Split the dataset
- Train on the training set. On each iteration of cross-validation, a new model must be trained
- Validate on the test set
- Save the result of the validation
- Repeat steps 3-6 k times
- To get the final score average the results that you got on step 6.
Repeated k-Fold has clear advantages over standard k-Fold CV. Firstly, the proportion of train/test split is not dependent on the number of iterations. Secondly, we can even set unique proportions for every iteration. Thirdly, random selection of samples from the dataset makes Repeated k-Fold even more robust to selection bias.
Still, there are some disadvantages. k-Fold CV guarantees that the model will be tested on all samples, whereas Repeated k-Fold is based on randomization which means that some samples may never be selected to be in the test set at all. At the same time, some samples might be selected multiple times. Thus making it a bad choice for imbalanced datasets.
Sklearn will help you to implement a Repeated k-Fold CV. Just use sklearn.model_selection.RepeatedKFold. In sklearn implementation of this technique you must set the number of folds that you want to have (n_splits) and the number of times the split will be performed (n_repeats). It guarantees that you will have different folds on each iteration.
Nested k-Fold
Unlike the other CV techniques, which are designed to evaluate the quality of an algorithm, Nested k-fold CV is used to train a model in which hyperparameters also need to be optimized. It estimates the generalization error of the underlying model and its (hyper)parameter search.
Nested k-Fold cross-validation resampling | Source
The algorithm of Nested k-Fold technique:
- Define set of hyper-parameter combinations, C, for current model. If model has no hyper-parameters, C is the empty set.
- Divide data into K folds with approximately equal distribution of cases and controls.
- (outer loop) For fold k, in the K folds:
- Set fold k, as the test set.
- Perform automated feature selection on the remaining K-1 folds.
- For parameter combination c in C:
- (inner loop) For fold k, in the remaining K-1 folds:
- Set fold k, as the validation set.
- Train model on remaining K-2 folds.
- Evaluate model performance on fold k.
The inner loop performs cross-validation to identify the best features and model hyper-parameters using the k-1 data folds available at each iteration of the outer loop. The model is trained once for each outer loop step and evaluated on the held-out data fold. This process yields k evaluations of the model performance, one for each data fold, and allows the model to be tested on every sample.
It is to be noted that this technique is computationally expensive because plenty of models is trained and evaluated. Unfortunately, there is no built-in method in sklearn that would perform Nested k-Fold CV for you.
You can either implement it yourself or refer to the implementation here.
Time-series cross-validation
Traditional cross-validation techniques don’t work on sequential data such as time-series because we cannot choose random data points and assign them to either the test set or the train set as it makes no sense to use the values from the future to forecast values in the past. There are mainly two ways to go about this:
- Rolling cross-validation
Cross-validation is done on a rolling basis i.e. starting with a small subset of data for training purposes, predicting the future values, and then checking the accuracy on the forecasted data points. The following image can help you get the intuition behind this approach.
Rolling cross-validation | Source- Blocked cross-validation
The first technique may introduce leakage from future data to the model. The model will observe future patterns to forecast and try to memorize them. That’s why blocked cross-validation was introduced.
Blocked cross-validation | SourceIt works by adding margins at two positions. The first is between the training and validation folds in order to prevent the model from observing lag values which are used twice, once as a regressor and another as a response. The second is between the folds used at each iteration in order to prevent the model from memorizing patterns from one iteration to the next.
Cross-validation in Machine Learning
When is cross-validation the right choice?
Although doing cross-validation of your trained model can never be termed as a bad choice, there are certain scenarios in which cross-validation becomes an absolute necessity:
- Limited dataset
Let’s say we have 100 data points and we are dealing with a multi-class classification problem with 10 classes, this averages out to
10 examples per class. In an 80-20 train-test split, this number would go down even further to 8 samples per class for training. The smart thing to do here would be to use cross-validation and utilize our entire dataset for training as well as testing.
Read also
- Dependent data points
When we perform a random train-test split of our data, we assume that our examples are independent. It means that knowing some instances will not help us understand other instances. However, that’s not always the case, and in such situations, it’s important that our model gets familiar with the entire dataset which is possible with cross-validation.
- Cons of single metric
In the absence of cross-validation, we only get a single value of accuracy or precision or recall which could be an outcome of chance. When we train multiple models, we eliminate such possibilities and get a metric per model which results in robust insights.
- Hyperparameter tuning
Although there are many methods to tune the hyperparameters of your model such as grid search, Bayesian optimization, etc., this exercise can’t be done on training or test set, and a need for a validation set arises. Thus, we fall back to the same splitting problem that we have discussed above and cross-validation can help us out of this.
May be useful
Cross-validation in Deep Learning
Cross-validation in Deep Learning (DL) might be a little tricky because most of the CV techniques require training the model at least a couple of times.
In deep learning, you would normally tempt to avoid CV because of the cost associated with training k different models. Instead of doing k-Fold or other CV techniques, you might use a random subset of your training data as a hold-out for validation purposes.
For example, Keras deep learning library allows you to pass one of two parameters for the fit function that performs training.
- validation_split: percentage of the data that should be held out for validation
- validation_data: a tuple of (X, y) which should be used for validation. This parameter overrides the validation_split parameter which means you can use only one of these parameters at once.
The same approach is used in official tutorials of other DL frameworks such as PyTorch and MxNet. They also suggest splitting the dataset into three parts: training, validation, and testing.
- Training – a part of the dataset to train on
- Validation – a part of the dataset to validate on while training
- Testing – a part of the dataset for final validation of the model
Still, you can use cross-validation in DL tasks if the dataset is tiny (contains hundreds of samples). In this case, learning a complex model might be an irrelevant task so make sure that you don’t complicate the task further.
Best practices and tips
It’s worth mentioning that sometimes performing cross-validation might be a little tricky.
For example, it’s quite easy to make a logical mistake when splitting the dataset which may lead to an untrustworthy CV result.
You may find some tips that you need to keep in mind when cross-validating a model below:
- Be logical when splitting the data (does the splitting method make sense)
- Use the proper CV method (is this method viable for my use-case)
- When working with time series don’t validate on the past (see the first tip)
- When working with medical or financial data remember to split by person. Avoid having data for one person both in the training and the test set as it may be considered as data leak
- When cropping patches from larger images remember to split by the large image Id
Of course, tips differ from task to task and it’s almost impossible to cover all of them. That’s why performing a solid exploratory data analysis before starting to cross-validate a model is always the best practice.
Final thoughts
Cross-validation is a powerful tool. Every Data Scientist should be familiar with it. In real life, you can’t finish the project without cross-validating a model.
In my opinion, the best CV techniques are Nested k-Fold and standard k-Fold. Personally, I used them in the task of Fraud Detection. Nested k-Fold, as well as GridSeachCV, helped me to tune the parameters of my model. k-Fold on the other hand was used to evaluate my model’s performance.
In this article, we have figured out what cross-validation is, what CV techniques are there in the wild, and how to implement them. In the future ML algorithms will definitely perform even better than today. Still, cross-validation will always be needed to back your results up.
Hopefully, with this information, you will have no problems setting up the CV for your next machine learning project!
Кросс-валидация
Кросс-валидация или скользящий контроль — процедура эмпирического оценивания обобщающей способности алгоритмов. С помощью кросс-валидации эмулируется наличие тестовой выборки, которая не участвует в обучении, но для которой известны правильные ответы.
Содержание
Определения и обозначения
Пусть [math] X [/math] — множество признаков, описывающих объекты, а [math] Y [/math] — конечное множество меток.
[math]T^l = <(x_i, y_i)>_
, x_i \in X, y_i \in Y[/math] — обучающая выборка, [math]Q[/math] — мера качества,
[math]\mu: (X \times Y)^l \to A, [/math] — алгоритм обучения.
Разновидности кросс-валидации
Валидация на отложенных данных (Hold-Out Validation)
Обучающая выборка один раз случайным образом разбивается на две части [math] T^l = T^t \cup T^
[/math] 
После чего решается задача оптимизации:
[math]HO(\mu, T^t, T^
) = Q(\mu(T^t), T^ ) \to min [/math] , Метод Hold-out применяется в случаях больших датасетов, т.к. требует меньше вычислительных мощностей по сравнению с другими методами кросс-валидации. Недостатком метода является то, что оценка существенно зависит от разбиения, тогда как желательно, чтобы она характеризовала только алгоритм обучения.
Полная кросс-валидация (Complete cross-validation)
- Выбирается значение [math]t[/math] ;
- Выборка разбивается всеми возможными способами на две части [math] T^l = T^t \cup T^
[/math] .
Здесь число разбиений [math]C_l^
[/math] становится слишком большим даже при сравнительно малых значениях t, что затрудняет практическое применение данного метода. k-fold кросс-валидация
- Обучающая выборка разбивается на [math] k [/math] непересекающихся одинаковых по объему частей;
- Производится [math] k [/math] итераций. На каждой итерации происходит следующее:
- Модель обучается на [math] k — 1 [/math] части обучающей выборки;
- Модель тестируется на части обучающей выборки, которая не участвовала в обучении.
Каждая из [math]k[/math] частей единожды используется для тестирования. Как правило, [math]k = 10[/math] (5 в случае малого размера выборки).
[math]T^l = F_1 \cup \dots \cup F_k, |F_i| \approx \frac
, \\ CV_k = \frac<1> \sum_ Q(\mu(T^l \setminus F_i),F_i) \to min [/math] . t×k-fold кросс-валидация
- Процедура выполняется [math]t[/math] раз:
- Обучающая выборка случайным образом разбивается на [math]k[/math] непересекающихся одинаковых по объему частей;
- Производится [math] k [/math] итераций. На каждой итерации происходит следующее:
- Модель обучается на [math] k — 1 [/math] части обучающей выборки;
- Модель тестируется на части обучающей выборки, которая не участвовала в обучении.
[math]T^l = F_ <(1,1)>\cup \dots \cup F_ <(k,1)>= \dots = F_ <(1,t)>\cup \dots \cup F_<(k,t)>, |F_<(i,j)>| \approx \frac
[/math] , Кросс-валидация по отдельным объектам (Leave-One-Out)
Выборка разбивается на [math]l-1[/math] и 1 объект [math]l[/math] раз.
[math]LOO = \frac<1>
\sum_ Q(\mu(T^l \setminus p_i),p_i) \to min [/math] , где [math]p_i = (x_i, y_i)[/math] . Преимущества LOO в том, что каждый объект ровно один раз участвует в контроле, а длина обучающих подвыборок лишь на единицу меньше длины полной выборки.
Недостатком LOO является большая ресурсоёмкость, так как обучаться приходится [math]L[/math] раз. Некоторые методы обучения позволяют достаточно быстро перенастраивать внутренние параметры алгоритма при замене одного обучающего объекта другим. В этих случаях вычисление LOO удаётся заметно ускорить.
Случайные разбиения (Random subsampling)
Выборка разбивается в случайной пропорции. Процедура повторяется несколько раз.
Критерий целостности модели (Model consistency criterion)
Не переобученый алгоритм должен показывать одинаковую эффективность на каждой части.
Скользящий контроль
Скользящий контроль или кросс-проверка или кросс-валидация (cross-validation, CV) — процедура эмпирического оценивания обобщающей способности алгоритмов, обучаемых по прецедентам.
Фиксируется некоторое множество разбиений исходной выборки на две подвыборки: обучающую и контрольную. Для каждого разбиения выполняется настройка алгоритма по обучающей подвыборке, затем оценивается его средняя ошибка на объектах контрольной подвыборки. Оценкой скользящего контроля называется средняя по всем разбиениям величина ошибки на контрольных подвыборках.
Если выборка независима, то средняя ошибка скользящего контроля даёт несмещённую оценку вероятности ошибки. Это выгодно отличает её от средней ошибки на обучающей выборке, которая может оказаться смещённой (оптимистически заниженной) оценкой вероятности ошибки, что связано с явлением переобучения.
Скользящий контроль является стандартной методикой тестирования и сравнения алгоритмов классификации, регрессии и прогнозирования.
Содержание
Определения и обозначения
Пусть — множество описаний объектов, — множество допустимых ответов.
Задана конечная выборка прецедентов .
Задан алгоритм обучения — отображение , которое произвольной конечной выборке прецедентов ставит в соответствие функцию (алгоритм) .
Качество алгоритма оценивается по произвольной выборке прецедентов с помощью функционала качества . Для процедуры скользящего контроля не важно, как именно вычисляется этот функционал. Как правило, он аддитивен по объектам выборки:
где — неотрицательная функция потерь, возвращающая величину ошибки ответа алгоритма при правильном ответе .
Процедура скользящего контроля
Выборка разбивается различными способами на две непересекающиеся подвыборки: , где — обучающая подвыборка длины m, — контрольная подвыборка длины , — номер разбиения.
Для каждого разбиения n строится алгоритм и вычисляется значение функционала качества . Среднее арифметическое значений по всем разбиениям называется оценкой скользящего контроля:
Различные варианты скользящего контроля отличаются видами функционала качества и способами разбиения выборки.
Доверительное оценивание
Кроме среднего значения качества на контроле строят также доверительные интервалы.
Непараметрическая оценка доверительного интервала. Строится вариационный ряд значений , :
Утверждение 1. Если разбиения осуществлялись случайно, независимо и равновероятно, то с вероятностью значение случайной величины не превосходит .
Следствие 1. Значение случайной величины не превосходит с вероятностью .
В частности, для получения верхней оценки с надёжностью 95% достаточно взять разбиений.
Утверждение 2. Если разбиения осуществлялись случайно, независимо и равновероятно, то с вероятностью значение случайной величины не выходит за границы доверительного интервала .
Следствие 2. Значение случайной величины не выходит за границы вариационного ряда с вероятностью .
В частности, для получения двусторонней оценки с надёжностью 95% достаточно взять разбиений.
Параметрические оценки доверительного интервала основаны на априорном предположении о виде распределения случайной величины . Если априорные предположения не выполняются, доверительный интервал может оказаться сильно смещённым. В частности, если предположения о нормальности распределения не выполнены, то нельзя пользоваться стандартным «правилом двух сигм» или «трёх сигм». Джон Лангфорд в своей диссертации (2002) указывает на распространённую ошибку, когда правило двух сигм применяется к функционалу частоты ошибок, имеющему на самом деле биномиальное распределение. Однако биномиальным распределением в общем случае тоже пользоваться нельзя, поскольку в результате обучения по случайным подвыборкам вероятность ошибки алгоритма оказывается случайной величиной. Следовательно, случайная величина описывается не биномиальным распределеним, а (неизвестной) смесью биномиальных распределений. Аппроксимация смеси биномиальным распределением может приводить к ошибочному сужению доверительного интервала. Приведённые выше непараметрические оценки лишены этого недостатка.
Стратификация
Стратификация выборки — это способ уменьшить разброс (дисперсию) оценок скользящего контроля, в результате чего получаются более узкие доверительные интервалы и более точные (tight) верхние оценки.
Стратификация заключается в том, чтобы заранее поделить выборку на части (страты), и при разбиении на обучение длины m и контроль длины k гарантировать, что каждая страта будет поделена между обучением и контролем в той же пропорции .
Стратификация классов в задачах классификации означает, что каждый класс делится между обучением и контролем в пропорции .
Стратификация по вещественному признаку. Объекты выборки сортируются согласно некоторому критерию, например, по возрастанию одного из признаков. Затем выборка разбивается на k последовательных страт одинаковой (с точностью до 1) длины. При формировании контрольных выборок из каждой страты выбирается по одному объекту, либо с заданным порядковым номером внутри страты, либо случайным образом.
Разновидности скользящего контроля
Возможны различные варианты скользящего контроля, отличающиеся способами разбиения выборки.
Полный скользящий контроль (complete CV)
Оценка скользящего контроля строится по всем разбиениям. В зависимости от (длины обучающей выборки) различают:
- Частный случай при — контроль по отдельным объектам (leave-one-out CV);
Было показано (Li,1987) , что контроль по отдельным объектом является асимптотически оптимальным при некоторых условиях [1] , то есть:
- — класс сравниваемых моделей;
- — среднеквадратичная ошибка при выборе -ой модели;
- .
- Общий случай при . Здесь число разбиений становится слишком большим даже при сравнительно малых значениях , что затрудняет практическое применение данного метода. Для этого случая полный скользящий контроль используется либо в теоретических исследованиях (Воронцов,2004), либо в тех редких ситуациях, когда для него удаётся вывести эффективную вычислительную формулу. Например, такая формула известна для метода k ближайших соседей[1] , что позволяет эффективно выбирать параметр k. На практике чаще применяются другие разновидности скользящего контроля.
Случайные разбиения
Разбиения выбираются случайно, независимо и равновероятно из множества всех разбиений. Именно для этого случая справедливы приведённые выше оценки доверительных интервалов. На практике эти оценки, как правило, без изменений переносится и на другие способы разбиения выборки.
Контроль на отложенных данных (hold-out CV)
Оценка скользящего контроля строится по одному случайному разбиению, .
Этот способ имеет существенные недостатки:
- Приходится слишком много объектов оставлять в контрольной подвыборке. Уменьшение длины обучающей подвыборки приводит к смещённой (пессимистически завышенной) оценке вероятности ошибки.
- Оценка существенно зависит от разбиения, тогда как желательно, чтобы она характеризовала только алгоритм обучения.
- Оценка имеет высокую дисперсию, которая может быть уменьшена путём усреднения по разбиениям.
Следует различать скользящий контроль по отложенным данным и контроль по тестовой выборке. Если во втором случае оценивается вероятность ошибки для классификатора, построенного по обучающей подвыборке, то в первом случае — для классификатора, построенного по полной выборке (то есть доля ошибок вычисляется не для того классификатора, который выдается в качестве результата решения задачи).
Контроль по отдельным объектам (leave-one-out CV)
Является частным случаем полного скользящего контроля при , соотвественно, . Это, пожалуй, самый распространённый вариант скользящего контроля.
Преимущества LOO в том, что каждый объект ровно один раз участвует в контроле, а длина обучающих подвыборок лишь на единицу меньше длины полной выборки.
Недостатком LOO является большая ресурсоёмкость, так как обучаться приходится раз. Некоторые методы обучения позволяют достаточно быстро перенастраивать внутренние параметры алгоритма при замене одного обучающего объекта другим. В этих случаях вычисление LOO удаётся заметно ускорить.
Контроль по q блокам (q-fold CV)
Выборка случайным образом разбивается на q непересекающихся блоков одинаковой (или почти одинаковой) длины :
Каждый блок по очереди становится контрольной подвыборкой, при этом обучение производится по остальным блокам. Критерий определяется как средняя ошибка на контрольной подвыборке:
Это компромисс между LOO, hold-out и случайными разбиениями. С одной стороны, обучение производится только q раз вместо L. С другой стороны, длина обучающих подвыборок, равная с точностью до округления, не сильно отличается от длины полной выборки L . Обычно выборку разбивают случайным образом на 10 или 20 блоков.
Контроль по r×q блокам (r×q-fold CV)
Контроль по q блокам (q-fold CV) повторяется r раз. Каждый раз выборка случайным образом разбивается на q непересекающихся блоков. Этот способ наследует все преимущества q-fold CV, при этом появляется дополнительная возможность увеличивать число разбиений.
Данный вариант скользящего контроля, со стратификацией классов, является стандартной методикой тестирования и сравнения алгоритмов классификации. В частности, он применяется в системах WEKA и «Полигон алгоритмов».
Скользящий контроль в задачах прогнозирования
В задачах прогнозирования, динамического обучения, обучения с подкреплением и активного обучения прецеденты изначально линейно упорядочены по времени их появления. В этом случае варианты скользящего контроля не так разнообразны.
Контроль при нарастающей длине обучения
Обучающая подвыборка образуется всеми прошлыми объектами . Контрольная подвыборка образуется всеми будущими объектами , где — величина зедержки прогнозирования (обычно ). Момент «настоящего времени» n «скользит» по выборке данных:
где — минимальная длина обучающей выборки, требуемая для нормальной работы алгоритма обучения , .
Поскольку длина обучения увеличивается со временем, точность прогнозов может постепенно улучшаться. Этот побочный эффект является нежелательным, если скользящий контроль применяется для оценивания качества алгоритма обучения.
Контроль при фиксированной длине обучения
Отличается от предыдущего варианта только тем, что длина обучения m фиксируется, ограничивась последними m прецедентами ряда: . При этом полагают .
Недостатки скользящего контроля
- Задачу обучения приходится решать N раз, что сопряжено со значительными вычислительными затратами.
- Оценка скользящего контроля предполагает, что алгоритм обучения уже задан. Она ничего не говорит о том, какими свойствами должны обладать «хорошие» алгоритмы обучения, и как их строить. Такого рода подсказки дают, например, теоретические оценки обобщающей способности.
- Попытка использовать скользящий контроль для обучения, в роли оптимизируемого критерия, приводит к тому, что он утрачивает свойство несмещённости, и снова возникает риск переобучения.
- Скользящий контроль дает несмещенную точечную, но не интервальную оценку риска. В настоящее время не существует методов построения на основе скользящего контроля точных доверительных интервалов для риска, то есть математического ожидания потерь (в частности, вероятности ошибочной классификации).
Применения скользящего контроля
На практике скользящий контроль применяется для оптимизации некоторых критически важных параметров, как правило, определяющих структуру или сложность используемой модели алгоритма, и имеющих относительно небольшое число возможных значений.
- (inner loop) For fold k, in the remaining K-1 folds: