Do I need to use nested cross validation to select the best algorithm?

Question

Suppose I want to compare the performance of several classification algorithms on a data set to choose the best algorithm to use with that data set. To do this, I run logistic regression, k-nearest neighbors, and naive Bayes using k-fold cross validation on the data set. Based on the results from the k-fold cross validations, I select the algorithm that produced the most accurate result and train it on the entire data set to obtain the final model. My questions are:

• Is this a valid method of choosing between machine learning algorithms, or do I have to use nested cross validation instead?
• Would the best k-fold cross validation result be an upwardly biased estimate?

Answer 1

This depends on whether you use your same k-fold cross-validation also to tune your methods, like choosing the k for k-nearest neighbours, or variable selection and the like. If you fix the k for NN in advance and run one plain version of the two other algorithms, a single k-fold without nesting should do for selecting the best. If you do model selection also "within" these methods, nesting will avoid a bias that favours more flexible methods.

Regarding the second question, your prediction loss estimate from k-fold CV may be biased in both directions: Loss may be over-estimated because k-fold is based on fewer observations than if you use all of them, but it may also be under-estimated, because if you choose the best, model selection bias will occur (although if you just compare between three plain models without any further selection model selection bias may be close to zero, at least if the best model has some distance to the others). Nested CV will avoid model selection bias for this, however there will still be bias in the other direction, so it's probably not worthwhile here.