Higher Test Scores but Higher Variance? I am tuning hyper-parameters using 5-fold cross-validated grid search for various multiclass classifiers, and I keep running into the same issue that I can't quite wrap my head around.
The hyper-parameter configurations achieving the highest "test score" often have extremely low training error - suggesting overfitting.

The table above shows my results for tuning a decision tree, the test score of the configuration shown in the top row is slightly higher, but the train score is much higher. Obviously in this case the test scores are so close together that I can use either, but sometimes the difference is larger.
Plotting learning curves for each of the two configurations shown above makes the difference in variance very noticeable:


I'm having a hard time understanding why this is happening, and also reasoning which classifier is "better". If lower variance is the goal, should I be choosing the classifier configuration that produces the best test score, where the difference in train/test score is within a limit?
P.S. The same behaviour is shown for the results of an SVM - very high C values massively overfit (1.0 train scores) but tend to have better test scores than the classifiers with lower C values.
 A: Based on your screenshot 1, model depths are 10 and 20 and min sample split are 2 and 3.
If you have small number of columns (e.g. <10), it is likely that decision trees are not split further because it is already built-up before hit the depth restriction.  Hence max depth parameter has no effect on overfitting control.
Similarly, the min sample split is only 2 or 3, which means leaves will not be split further if obs number is less than 2 or 3.  Hence, your tree models put nearly each obs in each of leaves, which is over-fitted.  This may also be the reason that your training set score is about 0.99 when min sample split is 2 (assume this is the measure of accuracy that 1 means no errors).
No sure about the which model both plots are related to, hence I'd assume top plot is related to model 42.  After depth decreases to 10 and min sample split increase (a little bit) to 3, you can see that train score decreases while cross validated score increases which make more sense in terms of their moving direction. This is because better parameters chosen to control overfit.
Possible Solutions:


*

*Decrease tree depths depending on number of variables and your current model (42 and 36) actual tree depth.

*Increase min_sample_split to 20 or 30.  This is to make your classifier more general as oppose to fit to individual obs.

*Try random forest method which builds lots of trees (lots of weak learners to strong learner).

