# Assessing model performance of stochastic algorithm

I'm looking at how I currently evaluate my classification models and wondering if it could be improved. I've got a stochastic algorithm (Genetic Programming), which for non-classification problems is run ~50 times on each problem to get an overview for how it performs.

Currently I'm implementing repeated 10-fold stratified cross-validation. For standard deterministic modeling techniques this assesses the algorithm over various splits of the data. With my GP classifiers I have an additional source of variability alongside variability due to how the dataset was split; as the RNG seed for each run will be different.

Is repeated 10-fold cross-validation a useful measure of my model's performance or would it be better to use a different technique such as bootstrapping and run this multiple times? An alternative approach would be to use repeated CV with 50 repeats, but make each repeat use the same folds. Therefore I've got the CV reducing variance due to the splitting of the data folds, and the 50 repeats minimising variation from the stochastic model. However this would be very computationally expensive!

I'd recommend to measure both ways.

As you say, you have two sources of variation/instabity here:

• variability due to different initializtion and
• instability wrt. the training cases

The usual way of repeating cross validation with new splits will measure the both sources of variance together. But of course it is of high practical importance to know whether you'd need to get more cases or a more stable algorithm in order to improve your classification. This means that you should actually measure the variance for constant training set with new seeds as well.

I'd start with a moderate size (10 * 5 fold * 10 repeated executions maybe) for the computations and then have a look whether variance due to GP seed is in the same order of magnitude as the variance due to training set composition. It may very well be that one source of variance is >> the other. You could then either save a lot of computations by showing that the smaller source of variance is negligible, or concentrate your work to improve the classifier onto the important source of variation. Once you know what is going and and are satisfied with the total set-up you can spend the time on a larger calculation with more repetitions.

At least for the data I work with, there is no practical difference between out-of-bootstrap and repeated CV (given the same number of surrogate models is evaluated).

• I ran tests to determine which was the greater source of variation by running experiments keeping the EA seed constant and running 30 repeats of 10-fold CV. To measure variance due to the EA RNG I ran repeats of 10-fold CV using the same folds for each run but allowing the EA RNG to be different each time. From the results the variance due to data sampling is ~2.5 * variance due to the GP seed. For future experiments I think I'll go with 30 repeats of 10-fold CV, to focus on the data sampling but still provide enough runs to show the impact of the EA seed. Apr 14, 2015 at 11:48
• Depending on your EA, a (slightly) different training set may lead to behaviour of the EA like with a different seed (in addition to the "outer" variation in the data - e.g. some EAs take a different path for reordered but otherwise equal training data. If that could be the case, you can allow the seed to change for the repeats of the CV and then express as Var due to CV + Var due to EA RNG = f * Var due to EA RNG or Var_CV = (f - 1) Var EA RNG. In any case, your experiments show that both are in the same order of magnitude, which indicates a good, balanced working point. Apr 14, 2015 at 16:23