Doing cross-validation when diagnosing a classifier through learning curves

Question

I have a theoretical question on the correct way to make learning curves to diagnose a classifier. To see a generic example of these curves one can refer to this (min 34 onward) lecture by Andrew Ng or this example from scikit. There is sparse information on the topic elsewhere -- that is my reason to ask experts here.

My understanding on the matter can be briefly summarized in the procedure below.

1. Make a train/test split of the data set. The test set is held constant over the next steps.
2. Derive a training set subsample of size N and train your classifier on it.
3. Evaluate your classifier performance on the test set you derived at step #1 to get a point for the test error curve. Evaluate performance on the training subsample from step #2 you just trained the classifier on to get a point on the training error curve.
4. Increase your subsample size N (unless you hit the training set size limit) by some delta and repeat from step #2.
5. Plot the curves to see whether bias or variance prevails.

One of the assumptions of the procedure above (as per my understanding) is that you hold the test set fixed. But what is about the classifier itself? Say, we are training classification trees where I can tune a bunch of hyperparameters like node size, depth, obs. per terminal node, splitting criterion, etc. Or kNN where k is a model tuning parameter. In both examples the classifier with some preset parameter values may even be nonsensical for some N-sized subsamples (say, setting obs. per leaf that is too large for small N or vise versa or nearest neighbors that are surely an overfit as my subsample size N gets larger and larger). This leads to the idea of doing an extra CV step between #1 and #2 to choose proper (for the given sample size) hyperparameters of the classifier. But this essentially leads to a "different" classifier I employ at each step of the above procedure.

So, this left me with the following questions.

1. In general, is doing CV between the lines of the above procedure appropriate? Again, it seems natural that e.g. I don't want to report a classifier overfit (based on the train/test error curves convergence behavior) at full sample size by growing a huge tree just because I set min node size equals 2 in the very beginning and never adjusted it having a larger subsample later on.
2. In case I'm allowed to tune classifiers inside the loop of the procedure, are there any parameters I should/must avoid tuning? Say, what if CV suggests different SVM kernels at various Ns and I definitely end up with a classifier that is different from the one I started with?
3. Lastly, if I'm not allowed to CV, how do I cope with at least nonsensical k>N in kNN?

It would be interesting to hear your thoughts as I probably completely miss something. Thanks!

Answer 1

As implemented, the learning curve generation code is trying to jointly optimize your parameters and hyperparameters for each size. In that sense, the learning curve is meant to show the "best" it can do at each possible size rather than to hold any particular parameters constant.

If you want to hold the parameters constant, you want to manually generate your hyperparameter permutations from one of the grid search iterators and then generate the learning curves inside of a loop over all those hyperparameter permutations.

It's a great question though and I agree that it's something that's not discussed enough.