What exactly is the bias when using training / validation / testing data? So reading through this article, my understanding of training, validation, and testing datasets in the context of machine learning is 


*

*training data: data sample used to fit the parameters of a model

*validation data: data sample used to provide an unbiased evaluation of a model fit on the training data while tuning model hyperparameters. The evaluation becomes more biased as skill on the validation dataset is incorporated into the model configuration.

*test data: data sample used to provide an unbiased evaluation of a final model fit on the training data


What I am confused about is what exactly is the bias that is referred to in the validation and testing datasets? I am fairly certain the source of that bias is the training data, but it is not clear to me what exactly is the cause of that bias?
My best guess is that the training data may not be completely representative of the whole population of the data, so the ability of the model to generalize to unseen data may be compromised as that data only knows the training data. Is this guess accurate or is there something more I am missing?
 A: Yes, the bias lies in the model's success metrics, biased because of the potential for overfitting. The data you observe are shaped not only by the substantive relations you are attempting to model but by a range of other factors specific to the conditions under which this dataset was collected. Your modeling may exploit those peculiarities but attribute the resulting predictive ability to your predictor variables. There is uncertainty in the given dataset for which you cannot account without reference to something outside the dataset itself. Validating and testing with completely independent datasets offer a means to account for (some of) that uncertainty.
A: Bias refers to one component of the error of your model. The other component is variance, and there is a trade-off between the two.
Bias comes essentially from the assumptions you (or your model) make about the data. For example, in linear regression you assume linearity, normal distribution of errors, and homoscedasticity.
Variance, on the other hand, comes essentially from the noise in your data. As you make your model more flexible, e.g. allowing for non-linearities, it becomes capable of capturing more complex relationships in the data, but, at the same time, more susceptible to picking up noise instead of true relationships.
For more details, you may take a look at Wikipedia or search for bias variance tradeoff.
A: 
what exactly is the bias that is referred to in the validation and testing datasets?

That bias refers to systematically under- or overestimating the predictive performance of the model. In other words, the figure of merit (e.g. some error) you calculate is systematically off. 
In this particular situation (hyperparameter tuning) we're concerned with optimistic bias, i.e. systematically thinking the model is better than it is.
The cause
explanation 1: optimization ("validation") set is part of training data
Training the final model here has two stages, the low-level training and the hyperparameter optimization. Both cause the model to adapt to the available training data, in the first stage this is what we refer to as training set, in the second stage training set + validation set. 
Since these data sets are finite (and possibly even small), there are limits to how representative they can be, and also to how much they can guard against overfitting. Yes, the optimization/validation set is better than using the training set for error estimation, but there are limits to how much better it can be. And hyperparameter optimization can push beyond these limits.
So yes, your "best guess" is right. But: this is not an unlucky accident, this is systematic: there is always some model complexity where this effect kicks in as long as your data sets doesn't comprise the whole population.
explanation 2: skimming variance
A second perspective on this phenomenon is that the optimization/hyperparameter tuning may be "skimming variance".
We tune the hyperparameters by testing a number of hyperparameter sets and then selecting the best model. The best model is identified by its test error on the optimization (validation) set. But this figure of merit (test error) is itself subject to bias and variance. If the optimization set is independent of the training set, bias is zero - but there will always be variance uncertainty. The more, the smaller the optimization set, and the more unstable the model at the particular hyperparameter set is.
This means: the larger the variance uncertainty on the optimization error and the more hyperparamter sets we test, the larger is the risk to find some combination of training and optimization data and hyperparameters that looks very good although true error isn't all that great because of variance uncertainty on the test results. Unless we find a way to effectively guard against this uncertainty, we're prone to choose such a solution. 
Thus our optimization heuristic favors such lucky combinations (which is what I call skimming variance), the test error variance uncertainty which is in itself not directed will be converted into a systematic error: we favor models that look better than they are, i.e. optimization error measurements that are overoptimistic.


So how does one guarantee independence between the validation / optimization dataset and the trianing dataset if they are drawn from a larger dataset? Is it enough to just only for their intended tasks and not "mix" them together (training for training, etc.)? 

No, training set for training only, ... is necessary but not sufficient. 
It is also important to make sure these data sets are independent before any calculations start. That is, to identify possible clustering/data hierarchy/nested influencing factors and take them into account. As an example, I often work with data hat contains repeated measurements e.g. for the same patient. Independence is only achieved if such a data set is split into test and training patient, not test and training rows. So this aspect of independence can only be achieved with detailed knowledge about the data generating process, because that's where you need to spot influencing factors that lead to such a clustered/nested data structure.

Also, what ways are there to guard against "lucky" hyperparameters combinations with the training data?



*

*Keep the number of hyperparameter combinations that are compared to each other as low as possible, e.g. use available external knowledge about algorithm and data to restrict the hyperparameter search space. Also a coarser grid will have fewer comparisons.

*Get a rough guesstimate of the uncertainty on your figure of merit due to the number of test cases in your optimization set (for classificationf figures of merit such as accuracy, that's possible by back-of-the-envelope calculation (see our paper below), for regression you'll need preliminary experiments/calculations). This gives a hard limits to your ability to tune hyperparameters.

*model stability is important as it is related to model complexity, which is one of the tuning goals. You can also measure this (2nd paper below). If you find substantial instability, there's two things that you can do:   


*

*you can reduce the uncertainty on the figure of merit that comes from this source of variance by evaluating more surrogate models for that hyperparameter combination, i.e. more train/optimization (validation) splits - e.g. more out-of-bootstrap iterations or more repetitions/iterations of [inner] cross validation.

*You can decide that you anyways need to go for lower complexity as you don't want to have an unstable model as result of the optimization.


*The result will be something like an extension to the one-standard-error heuristic.

*out-of-bootstrap or cross validation for the inner split (train vs. optimization (validation) set) is much better here than a single split as it combines both more tested cases with evaluating more surrogate models. 

Two of our papers that are relevant in this context:


*

*Beleites, C. and Neugebauer, U. and Bocklitz, T. and Krafft, C. and Popp, J.: Sample size planning for classification models. Anal Chim Acta, 2013, 760, 25-33.
DOI: 10.1016/j.aca.2012.11.007
accepted manuscript on arXiv: 1211.1323

*Beleites, C. & Salzer, R.: Assessing and improving the stability of chemometric models in small sample size situations Anal Bioanal Chem, 2008, 390, 1261-1271.
DOI: 10.1007/s00216-007-1818-6
