Cross Validation how to determine when to Early Stop?

Question

When using "K-Fold Cross Validtion" for Neural Net, do we:

1. Pick and save initial weights of the network randomly (let's call it $W_0$)
2. Split data into $N$ equal chunks
3. Train model on $N-1$ chunks, validating against the left-out chunk (the $K$'th chunk)
4. Get validation error and revert the weights back to $W_0$
5. shift $K$ by 1 and repeat from 3.
6. Average-out the validtion errors, to get a much better understanding of how network will generalize using this data.
7. Revert back to $W_0$ one last time, and train the network using the ENTIRE dataset

---

Question 1:

I realize 7 is possible, because we have a very good understanding of how network will generalize with the help of step 6. - Is this assumption correct?

Question 2:

Is reverting back to the initial $W_0$ a necessity, else we would overfit? (revert like we do in step 4. and 7.)

Question 3, most important:

Assume we've made it to step 7, and will train the model using ENTIRE data. By now, we don't intend to validate it after we will finish. In that case how do we know when to stop training the model during step 7?

Sure, we can train with same number of epochs as we did during Cross validation. But then how can we be sure that Cross Validation was trained with an appropriate number of epochs in the first place?

Please notice - during steps 3, 4, 5 we only had $K$'th chunk to evaluate Training vs Validation loss. $K$'th chunk is very small, so during the actual Cross-Validation it was unclear when to Early-Stop... To make things worse, it will be even more difficult in case of Leave-One-Out (also know as All-But-One), where K is simply made from a single training example

Answer 1

First, I would like to emphasize, that cross-validation on itself does not give you any insights about overfitting. This would require comparing training and validation errors over the epochs. Typically you make such comparison with your eye and you can start with one train/validation split.

Question 1: By getting validation error N times, you develop a reasonable (whether it is very or not very good is a question) understanding of how your network will perform (= what error it will give) on the new unseen data.

Often you do cross validation as a part of grid search of hyper-parameters. Then averaging errors at step 6 is mainly for choosing the best hyper-parameters: you believe that the hyper-parameters are best if the corresponding network produces the smallest average validation error. Simultaneously this error is your estimation on what error the final model will give you on the new data.

If you want, you can proceed with your exploration and compare validation errors (for one and the same hyper-parameter set) with each other, calculate standard deviation in order to get further insights.

The concept "model generalizes well" is more related to the absence of overfitting. To make this conclusion, you need to compare train and validation errors. If they are close to each other, then the model generalizes well. This is not directly related to cross validation.

Question 2: The only purpose to take the whole dataset is to train the model on more data. And more data is always good. On the other side, if you are happy with one of the models produced during cross-validation, you can take it.

Question 3: You can take the number of epochs as one of the parameters in grid-search of hyper-parameters. This search usually goes with cross-validation inside. When at step 7 you take the whole data set, you take more data. Thus, overfitting, if at all, at this stage can only be reduced. If it bothers you, that each chunk is small, replace K-fold cross validation with, for example, K times 50/50 train/test splits. And I would never worry about leave-one-out. It was developed for small (very small) datasets. For Neural Net to be good, you typically need large or very large dataset.

Answer 2

To Q1: I think the answer is yes, but the performance is not guaranteed to generalize to new unseen data, if the data is not sampled from the same underlying distribution. Or if a lot of information has "leaked" through model selection, configuration, early stopping etc.. (I saw a synthetic example recently where the information totally "broke out", in a case of feature selection.)

Generalization is closely related to overfitting. As long as you will not apply the trained model to the training data in the future, "overfitting" to the training data should be of no concern, as long as you get good generalization to the validation data. Good generalization implies the overfitting is not severe. Good generalization is the big goal.

For Q2, I think it is in principle most correct to start from scratch, to avoid any bias toward local minima that overfit to a subset. I don't think the initial weights have to be the same for every training run, though. I just reinitialize them to random values. The training process is noisy anyway.

For Q3: I have the same question. First: Adding a grid dimension is very expensive, as it multiplies the number of training runs by the number of points along the new dimension. Random fluctuations between runs matter more the more runs you are comparing too. Adding an epochs dimension also seems unnecessary, as the validation loss in each "fold" of the CV can inform early stopping. The problem is, as you state, that the final training has no validation loss.

I guess one candidate solution (as you outline) is to log the number of epochs (before early stopping) for all the folds, and fix the number of epochs to the average multiplied by (N-1)/N, to let the fresh model train for just as many steps as the folds did on average. Round up or down? Down protects against overfitting, possibly at the cost of accepting some underfitting. Maybe instead multiply each fold's number of epochs with (N-1)/N first, round them and then calculate the median (could be halfway between numbers) or the mode. Or model the rounded values as a sample from some discrete probability distribution and obtain the mode of that distribution. Starting to reek overkill for something which nevertheless does not guarantee success.