Test accuracy higher than training. How to interpret? I've a dataset containing at most 150 examples (split into training & test), with many features (higher than 1000). I need to compare classifiers and feature selection methods which perform well on data. So, I'm using three classification methods (J48, NB, SVM) and 2 feature selection methods (CFS, WrapperSubset) with different search methods (Greedy, BestFirst).
While comparing, I'm looking at training accuracy (5-fold cross-folding) and test accuracy.
Here is one of the results of J48 and CFS-BestFirst:
{ "accuracyTraining" : 95.83, "accuracyTest" : 98.21 }
Many results are like this, and on the SVM there are many results that indicate that test accuracy is much higher than training (training: 60%, test: 98%)
How can I meaningfully interpret these kind of results? If it was lower, I would say it's overfitting. Is there something to be said about bias and variance in this case by looking all the results? What can I do to make this classification meaningful, such as re-selecting training and test sets or just using cross-validation on all data?
I have 73 training & 58 test instances. Some answers didn't have this info when they were posted. 
 A: Assuming that there is no glitch in the implementation of the algorithms, let us look at the problem.
Imagine taking a small subset from your training data and running your learning algorithm on it. It'll obviously do very well. It's always possible to extract a subset that achieves close to 98% accuracy.
Now is your test data very similar to this subset? If yes, then you need to go and collect more data, hopefully a bit more varied. From a Bias-Variance point of view, I would say that your variance is high.
A: I think a first step is to check whether the reported training and test performance are in fact correct.


*

*Is the splitting during the 5-fold cross validation done in a way that yields statistically independent cv train/test sets?  E.g. if there are repeated measurements in the data, do they always end up in the same set?

*95.83% accuracy in a 5-fold cv of 150 samples is in line with 5 wrong out of 130 training samples for the 5 surrogate models, or 25 wrong cases for 5 * 130 training samples.  

*98.21% test accuracy is more difficult to explain: during one run of the cv, each case should be tested once. So the possibly reported numbers should be in steps of 100%/150. 98.21% corresponds to 2.68 wrong cases (2 and 3 wrong out of 150 test cases gives 98.67 and 98.00% accuracy, respectively).

*If you can extract your model, calculate the reported accuracies externally. 

*What are the reported accuracies for random input?

*Do an external cross validation: split your data, and hand over only the training part to the program. Predict the "external" test data and calculate accuracy. Is this in line with the program's output?

*Make sure the reported "test accuracy" comes from independent data (double/nested cross validation): if your program does data driven optimization (e.g. choosing the "best" features by comparing many models), this is more like at training error (goodness of fit) than like a generalization error.


I agree with @mbq that training error is hardly ever useful in machine learning. But you may be in one of the few situations where it actually is useful: If the program selects a "best" model by comparing accuracies, but has only training errors to choose from, you need to check whether the training error actually allows a sensible choice.
@mbq outlined the best-case scenario for indistinguishable models. However, worse scenarios happen as well: just like test accuracy, training accuracy is also subject to variance but has an optimistic bias compared to the generalization accuracy that is usually of interest. This can lead to a situation where models cannot be distinguished although they really have different performance. But their training (or internal cv) accuracies are too close to distinguish them because of their optimistic bias. E.g. iterative feature selection methods can be subject to such problems that may even persist for the internal cross validation accuracies (depending on how that cross validation is implemented).  
So if such an issue could arise, I think it is a good idea to check whether a sensible choice can possibly result from the accuracies the program uses for the decision. This would mean checking that the internal cv accuracy (which is supposedly used for selection of the best model) is not or not too much optimistically biased with respect to an externally done cv with statistically independent splitting. Again, synthetic and/or random data can help finding out what the program actually does.
A second step is to have a look whether the observed differences for statistically independent splits are meaningful, as @mbq pointed out already.  
I suggest you calculate what difference in accuracy you need to observe with your given sample size in order to have a statistically meaningful difference. 
If your observed variation is less, you cannot decide which algorithm is better with your given data set: further optimization does not make sense.
A: How to interpret a test accuracy higher than training set accuracy.
Most likely culprit is your train/test split percentage.  Imagine if you're using 99% of the data to train, and 1% for test, then obviously testing set accuracy will be better than the testing set, 99 times out of 100.  The solution here is to use 50% of the data to train on, and 50% to evaluate the model.
Accuracy on the training set might be noise, depending on which ML algorithm you are using.  The training set accuracy doesn't evaluate the correctness of your model on unseen rows.  One strategy is to ignore the training set accuracy.
To get a clearer picture of which hyper-parameter choices to your model such (train/test split, iterations, convergence criteria, learning rate alpha, etc) are most responsible for your model having superior accuracy on test set, then run your model 100 times for every hyper parameter choice, then average the differences between training accuracy and testing accuracy.
Another strategy is to bag up your models into a list of N-models all of which were trained on a 50/50 train test split.  Then all of the models have access to all of the data, and yet also none of the models have the ability to observe more than 50% of the training data.  The average result is the correct one, then your training accuracy and testing accuracy will be much closer to equal.
A: There are a few serious problems with the way you have gone about this.  First of all, data splitting is unreliable unless the total sample size is huge.  You would get different results if you split again.  Among other things you are not considering confidence intervals on accuracy estimates.  Second, 5-fold cross-validation is not sufficiently precise.  It may be necessary to repeat it 100 times to achieve adequate precision.  Third, you have chosen as an accuracy score a discontinuous improper scoring rule (proportion classified correctly).  Such an improper scoring rule will lead to selection of the wrong model.
A: You have too many features (1000) for the number of samples that you have (150). You need to increase your samples or decrease your number of features. 
They say usually number of features ^2 = number of samples needed. So you need at least million samples. 
A: I had the same problem with Caret package R, however, note that what we obtain by the end of training is usually the range of performance of the models trained on the cross-validated dataset. So you need to predict the training data set again with the best model (Model$bestTune) and obtain metrics (e.g. RMSE, AUC and etc) again then by predicting again you can obtain test data, when you compare these two you'll see the training stage has better performance metrics
A: That can be happen using any ML algorithm and even custom classifiers. Try different k-fold cross validation schemes i.e. 2 or 10 fold as well. With higher k, it is expected that test error reduced. 
