Evaluating unbiased errors on the Test set when cross validation scores are close I trained a few different models, (Perceptron, Stochastic Gradient Descent and Naive Bayes), each with different parameters. I then scored their accuracy on a cross validation set.
The scores on the best parameter Perceptron, SGD and NB models were 93%, 91% and 94% respectively. 
I didn't expect such similar results and I'm at a bit confused because I feel that the possibility of variance makes choosing the NB as the best model questionable.
Am I supposed to test all 3 on the test set and use the model with the best unbiased error? Or is that implicitly cherry picking the best model ?
 A: Run a 10-fold cross validation (or more fold depending on how many lines you have). You will be able to have a better idea of the error. You can even compute variances and quantiles of you performance and plot boxplots. If one of the model has a significative better performance, choose this one.
However you are talking about performance like 93% so I guess your score is the percentage of correct answer. It is not always the best way to evaluate a model, for example in unbalanced designs. You may check AUC, precision, recall, F1-score measures. It will also help you decide which model is the best one. 
A: 
I didn't expect such similar results and I'm at a bit confused because I feel that the possibility of variance makes choosing the NB as the best model questionable.

This doubt is entirely right.  


*

*Have a look at "model comparison" questions here.

*The proportions you look at (no. of correctly predicted cases / no. of tested cases) are subject to high variance, but you can e.g. calculate confidence intervals. There are also sample size calculations available.
E.g. in R, you could use binom::binom.confint to get a quick idea whether you have any chance to distinguish these models.  

*One possibility is to use other performance measures which are more suitable for optimization. Frank Harrell will tell you that you should get continuous predictions out of your models (instead of the hard class labels) and then use a proper scoring rule for that, e.g. Brier's score (mean squared error).

*Side note: In my field I've hardly seen any model selection that was justified from the variance point of view. 

Am I supposed to test all 3 on the test set and use the model with the best unbiased error? Or is that implicitly cherry picking the best model ?

That would be cherry picking and create an optimistic bias. Reserve the outermost testing for the final model.
The model selection is what the inner inner test set (in your terminology CV set, I'd rather call it optimization or selection set) is for. 
However, if this optimization set was already used for e.g. a hyperparameter optimization, its results may already be so optimistically biased that you can not rely on it for the selection. In that case, you'd need to do yet another split of your data. 
Here's what I'd do:


*

*the most important information that is missing here is your sample size (# independent cases). 

*From that, calculate e.g. confidence intervals (or binomial variance for a realistic range of "true p" values). Are they narrow enough to distinguish practically relevant differences for your application?

*Then, have a look at the necessary sample size for model comparison. A paired test to distinguish two proportions would be McNemar's test. Depending on how favorable the errors are distributed, a single comparison between 91% and 94% observed correct predictions will become significant at α = 5% level somewhere between roughly 200 (6 % "difficult cases" wrongly predicted by both model, the worse model has additional 3 % errors) and 700 tested cases (no common wrong prediction).
As you have the actual distribution of wrong predictions, use that.

*As your situation has 3 model comparisons, you should maybe think about multiple test correction, e.g. Bonferroni correction.

