# Cross validation and parameter tuning

Can anyone tell me what exactly a cross-validation analysis gives as result? Is it just the average accuracy or does it give any model with parameters tuned?

Because, I heard somewhere that cross-validation is used for parameter tuning.

Cross-validation gives a measure of out-of-sample accuracy by averaging over several random partitions of the data into training and test samples. It is often used for parameter tuning by doing cross-validation for several (or many) possible values of a parameter and choosing the parameter value that gives the lowest cross-validation average error.

So the process itself doesn't give you a model or parameter estimates, but you can use it to help choose between alternatives.

However, if you use cross validation for parameter tuning, the out-samples in fact become part of your model. So you need another independent sample to correctly measure the final model's performance.

Employed for measuring model performance, cross validation can measure more than just the average accuracy:
A second thing you can measure with cross validation is the model stability with respect to changing training data: cross validation builds lots of "surrogate" models that are trained with slightly differing training sets. If the models are stable, all these surrogate models are equivalent, if training is unstable, the surrogate models vary a lot. You can quantify this "varies a lot" e.g. as variance of predictions of different surrogate models for the same sample (in iterated/repeated cross validation) or e.g. as variance of the surrogate models' parameters.

There are few ways you can overfit your models to the training data, some are obvious, some less so. First, and the most important one is overfitting of the training parameters (weights) to the data (curve fitting parameters in logistic regression, network weights in neural network etc.). Then you would model the noise in the data - if you overfit you don't only capture the underlying generating function, but also randomness due to sample size and the fact that sample is not a perfect representation of the population. This overfitting can be to a certain extent mitigated by penalizing certain attributes (in general complexity) of the model. This can be done by stopping the training once the performance on the train sample is no longer significantly improving, by removing some neurons from a neural network (called dropout), by adding a term that explicitly penalizes complexity of the model (https://ieeexplore.ieee.org/document/614177/) etc.). However these regularization strategies are themselves parametrized (when do you stop?, how many neurons to remove? etc.). In addition most machine learning models have a number of hyper-parameters that need to be set before the training begins. And these hyper-parameters are tuned in the parameter tuning phase.

That brings us to second, and more subtle type of overfitting: hyper-parameter overfitting. Cross-validation can be used to find "best" hyper-parameters, by repeatedly training your model from scratch on k-1 folds of the sample and testing on the last fold.

So how is it done exactly? Depending on the search strategy (given by tenshi), you set hyper-parameters of the model and train your model k times, every time using different test fold. You "remember" the average performance of the model over all test folds and repeat the whole procedure for another set of hyper-parameters. Then you choose set of hyper-parameters that corresponds to the best performance during cross-validation. As you can see, the computation cost of this procedure heavily depends on the number of hyper-parameter sets that needs to be considered. That's why some strategies for choosing this set have been developed (here I'm going to generalize what tenshi said):

1. Grid search: for each hyper-parameter you enumerate a finite number of possible values. Then the procedure is exhaustively done for all combinations of of enumerated hyper-parameters. Obviously, if you have continuous hyper-parameters, you cannot try them all.
2. Randomized grid search: similar to normal grid search, but this time you do not try out all combinations exhaustively, but instead sample a fixed number of times for all possible values. Note that here it is possible to not just enumerate possible values for a hyper-parameter, but you can also provide a distribution to sample from.
3. BayesianSearch - the combination of hyper-parameter values is chosen to maximize expected improvement of the score. For more: http://papers.nips.cc/paper/4522-practical-bayesian-optimization-of-machine-learning-algorithms.pdf. And a library that deals only with that: https://github.com/hyperopt/hyperopt . As it's not as easy to combine with sklearn as what tenshi recommended, use it only if you're not working with sklearn.
4. Other ways for guided search in hyper-parameter space. From my experience they are rarely used, so I won't cover them here.

However this is not the end of the story, as the hyper-parameters can (and will) also overfit the data. For most cases you can just live with it, but if you want to maximize the generalization power of your model, you might want to try and regularize the hyper-parameters as well. First, you can assess the performance on out-of-sample data a bit better by using nested grid search (details: http://scikit-learn.org/stable/auto_examples/model_selection/plot_nested_cross_validation_iris.html, discussion:Nested cross validation for model selection), or just use a validation set that is not used for hyper-parameter tuning. As for regularization in the hyper-parameter space, it's a more or less an open question. Some ideas include choosing not the best set of hyper-parameter values, but something closer to the middle; the reasoning goes as follows: best hyper-parameter values most likely overfit the data just because the perform better than the other of the train data, bad parameters are just bad, but the ones in the middle can possibly achieve better generalization than the best ones. Andrew Ng wrote a paper about it. Another option is limiting your search space (you're regularizing by introducing strong bias here - values outside of search space will never be selected obviously).

Side remark: using accuracy as a performance metric is in most cases a very bad idea, look into f1 and f_beta scores - these metrics will in most cases better reflect what you're actually trying to optimize in binary classification problems.

To summarize: cross-validation by itself is used to asses performance of the model on out-of-sample data, but can also be used to tune hyper-parameters in conjunction with one of the search strategies in hyper-parameters space. Finding good hyper-parameters allows to avoid or at least reduce overfitting, but keep in mind that hyper-parameters can also overfit the data.

k-fold cross-validation is used to split the data into k partitions, the estimator is then trained on k-1 partitions and then tested on the kth partition. Like this, choosing which partition should be the kth partition, there are k possibilities. Therefore you get k results of all k possibilities of your estimator.
iii. BayesSearchCV - Not part of scikit-learn but does Bayesian optimization for doing a randomized search and fit results.