10-fold cross validation, why having a validation set? I have my data stratified in 10 folders. So far I was using 9 of them to train the model, and the remaining one for testing it. A sudden thought just crossed my mind saying "you might be cheating". Authors of previous papers related to my problem used "10-fold cross validation with a single training fold used as an intermittent validation set". So they used 8 folders for training, 1 for validating and 1 for testing. I don't understand what is the purpose of the validation folder used in each of the 10 "iterations" of their cross validation proccedure.  


*

*Would it be reasonable to think that they changed the hyperparameters in each of the 10 iterations (where at the same time they were also changing the training and validation data, since that is what K-fold cross validation does), and then they went with the set of hyperparameters that gave the best test accuracy during that process?


Another general thing that I don't quite understand is, why setting the hyperparameters to best fit the validation set is right, and doing that for the test set is wrong, if they both come from the same distribution? Both are the same way of cheating the way I see it.
 A: Let me chime in from a different point of view:
"Cross validation" and "validation set" are concepts that are orthogonal/independent in the sense that:


*

*Validation set is about asking how many/which separate data subsets do I need?

*Whereas cross validation is one possible answer to the question how do I generate/split my data to produce these subsets?



The original purpose of validation sets (1.), was, well, validation (or rather verification), i.e. measuring the generalization performance of the already trained model. 
In that sense, yes, you do need a validation set. Note though, that this validation set I'm talking about has a totally different purpose of @Jai's validation set (see below).
Cross validation (2) is one very widely applied scheme to split your data so as to generate pairs of training and validation sets. Alternatives range from other resampling techniques such as out-of-bootstrap validation over single splits (hold out) all the way to doing a separate performance study once the model is trained. 
At some point, there was the necessity to do some fine-tuning of hyperparameters. Unfortunately, instead of saying: fine, our new training algoritm internally does an optimization on generalization error, and therefore we split the training set again into a hyperparameter optimization set and a normal parameter fit set, the former valiation set was used for optimization. Because that is really part of the training, another set to estimate the final model's performance was needed. I.e. a set that does what the validation set used to do. This needed another name, and bekame known as test set.
In my experience this historic naming scheme train-validate-test creates a lot of confusion, particularly in fields where verification and validation were already established terminology for studying/demonstrating the predictive performance of methods. 
Personally, I therefore prefer to speak 


*

*either of training-optimization-verification or

*of training and verification/validation pointing out that inside your training you can do whatever further splits you like.
This point of view has the advantage, that it is much easier to see which set of hyperparameters should be used when doing the final training with the whole data set.
Maybe this also helps to explain:

why setting the hyperparameters to best fit the validation set is right, and doing that for the test set is wrong, if they both come from the same distribution? Both are the same way of cheating the way I see it.

The idea is that during training you are allowed (and supposed) to find out as much as possible about this distribution. Validation/verification then is to prove how much about this distribution was actually learned. And hyperparameter tuning really is part of the training.
Another analogy to the training-optimization-verification splitting is school: training when a concept is explained to you. You then may do some test exams to to challenge and fine-tune your understanding of the concept. Finally there is an exam to demonstrate the learned ability. Even if you do another round of fine-tuning your concept after the exam, the mark is set. The same with a model, just that we know for many practically relevant situations that there is much higher danger of overfitting with our models, so we just don't accept any claim of improvement over the validation (exam) without proof (another validation, re-taking the exam). 
Now for each of these splitting steps, you need to decide how to do this. Doing single splits leads to the fixed train-optimize-verify (aka train-validate-test) approach. Doing cross validation for both is called nested or double cross validation. Your intermittent cross validation corresponds to doing cross validation for the (train+optimize) vs. verify split, and a single split for train vs. optimize. 


Would it be reasonable to think that they changed the hyperparameters in each of the 10 iterations (where at the same time they were also changing the training and validation data, since that is what K-fold cross validation does), and then they went with the set of hyperparameters that gave the best test accuracy during that process?

No, this is not a good idea
A valid approach would be in each fold to optimize training, and record the test results. This basically corresponds to a cross validation of a training procedure that does a single split into train and optimization data sets internally.   
A: The key thing you want to acces is how well your model can generalize.
Let's take a look at the usual workflow:
You have a training set which you use to continuously update the internal parameters of your model to minimize some error/loss function. Your model usually does very well after a certain time to give very good results for the training data, which is not suprising since that is the set used for setting the parameters. It does thereofre not make sense to use the error on the training data to judge your model.
To acces if you are done training yet you normally use a testing dataset. After a certain amount of updating steps you run your model on your test dataset. This will give a first impression of how well your model generalizes. If you have 0 error during training and a high error on this test dataset, then you are overfitting and need to rethink.
If everything goes well however you train until the error on your test dataset satisfies you or is not improving anymore.
However by doing so, the test dataset was part of the training process and using the error on your test dataset would be (as you say) "cheating" as the test dataset does not contain data that is completely unseen by your model. 
That is why you need data that is completely new and unseen to truly acces how well your model actually does when given data that it has never seen before. The error on this validation set is what you want to be as low as possible which is why you would update the hyper parameters to give the lowest error on the validation set.
Appendix: comming back to your second question. why is it not cheating to use a validation set that comes from the same distribution than the rest of the data?
Think about it this way: You want your model to learn a relationship between input data and output data. Let's  assume you have an image classifier that classifies images into the categories "cat", "dog" and "mouse". Now when you have a large set of images and then are able to perform well on both training and validation set, then you can assume, that your classifier has learned a relationship between the images and the correct classification.
The kind of problmen that is probably also in your head is another one:
What if all cat pictures come from my mother who has a black cat, all dog pictures are from my brother that has an albino dog and the mouse pictures are all of grey mice. Then you would have a problem because since your model will just learn to look for black, grey or white content in the image.
But that is a problem of biased data and cross validation does not claim to be able to detect it.
A: If you use a single set of parameters, then CV is enough.
If you also have to optimize hyperparameters, then you need a stacked approach.


*

*Choose a test set, and put it aside.

*Split the remaining data ("development set") into train and validation, for example using CV.

*Optimize hyperparameters on this set only. You are now overfitting by model selection, and the performance estimate of CV is too optimistic.

*Choose the final hyperparameters.

*Get the test set you put aside before.

*Train the model on the entire development set using the final hyperparameters, and test it on the test set, to get a more accurate prediction of your classifier performance.


By changing parameters until you get the best CV performance, you are indeed "cheating". You optimize parameters based on the evaluation score.
The reason why you need a clean (unused) test set is to really estimate how good it will work on new data. This is very important for business users (and researchers frequently are too sloppy here, as they won't lose money). If the new model is falsely-evaluated to improve sales by 5%, but it actually decreases sales by 5% because of overfitting hyperparameters, this can cost you money. Keeping a clean test data set helps getting a more reliable prediction of what could happen in the future.
It is even better if you can test on data that did not even exist at training time yet (fresh users). And in some cases it is beneficial to take time into account: always train on the older data, test on the newer data, because your future data is probably more similar to the newer data.
A: In general, the idea is to have 3 sets: one each to train, validate and test your data.
The test set, you really don't wanna touch before all other parameters and hyperparameters are fixed.
You use the training data to fit your model and the validation set to see how different hyperparameter settings play out - meaning that you still compare different settings.
Only once you settle for a model and setting, it makes sense to evaluate it.
If you optimize hyperparameters on the test set, you falsify your performance evaluation.
As for the k-fold cross validation, this still makes sense for the training | validation split. Just keep the test data out of it.
A: *

*It is essential to have validation set

*Here are the reasons of why is it essential to have validation set:
1] It does not waste training time because after few steps if the model does not perform well on validation set then you can just stop the training instead of waiting for the whole training to get completed
2] It is so obvious that if your model does not do good on validation set then it will definitely won't work on test set so it kind of tells you in advance whether the model overfit or not and the model's performance
3] The hyper-parameter tuning should always be done by evaluating model on validation set and not test set. If you used your testing set for hyper parameter tuning even though the test set was not included in training still it will be considered that you cheated because you used your testing set as training set
4] Now if hyper-parameter tuning is done seeing the testing set then the model will work on that particular testing set very well but won't generalize to other data in the real world or any other test set
5] To avoid test set to be a part of training set the idea of validation set came up

*Why to use k-fold-cross validation set?
1] K-fold cross validation is usually used when the data is very less
2] Suppose you only have 18 training samples then in this case you can not afford to make a validation data set because already your training set is very less
3] In such cases k-fold cross-validation is used
4] In K-fold Cross-validation for every step the validation set changes

*Just keep in mind that during training stage for any reason you used any information from the test set then you have cheated and if you have done so there is no guarantee how well your model will perform in the production even though the model performed well on the particular test set

*So yes, you can tune your hyper-parameters according to the validation set even though the validation set changes in k-fold cross validation

*But let's just consider what you said that is it really fine on tuning your hyper-parameterrs based on validation set that changes after every step ?

*So, for k-fold cross validation suppose your k value is 10 and the number of steps for training is 100

*So for every step the validation set chosen will be different but remember after the 11th step the validation set that was used in the 1st step will be repeated 

*Which means after every 10 step of training the validation set will be repeated and hence it is fine to tune your hyper-parameter based on validation set even in k-fold cross validation settings

*And it really does not matter both validation set and test set comes from the same distribution

*Remember that your model will only see the data samples coming from the same distribution. By this what I mean is that even in production the model will be used to classify from the distribution it was trained on

*So the training, validation and testing all of them belong to the same distribution and the idea is to make your model learn that distribution based on only training set because you do not have all the samples in the world that belong to that particular distribution

