Real World Challenge: Large difference between training and testing set accuracy

I have a classification dataset of ~100,000 rows and ~200 features. Within the dataset my predictor variable (Y) is an integer value between 0-55, therefore I am trying to predict 1 of 56 possible classes. I split my training/testing set into 80/20% and performed an extensive 10-fold cross validation exercise to tune the parameters and fit the final model. I end up a very high accuracy (and F1) score in the training set (~90%) but a very slow accuracy (and F1) score in the testing set (~10%).

EDIT 1: The training and testing set are split randomly. About 150 of the features are binary features (0 or 1) and the others are continuous values which I center and scale to be between 0 and 1.

I have tried numerous learning algorithms (SVM, NN, logistic regression, PCA + SVM) and believe that the 10-fold CV should have eliminated overfitting as best as possible. However, nothing that I try seems to yield any meaningfully different results.

Can anyone suggest new ways to increase accuracy of the testing set?

Caveats:

1) This is real world data so getting more of it is very expensive and time consuming.

2) We need these 56 classes so cannot simply eliminate any.

Thanks and any suggestions are appreciated.

• Just to be sure: you split the sets randomly into training and test? Then you realize the cross-validation only with data from the training set, right? And what is the range you're using for your parameters? Maybe you could find better parameters outside the range you have defined. – Jundiaius May 27 '14 at 14:54
• Thanks for the reply! Yes, the sets are split randomly. About 150 of the features are binary features (0 or 1) and the others are continuous values which I center and scale to be between 0 and 1. I am not sure I understand your last comment, can you please elaborate. – mike1886 May 27 '14 at 15:01
• When I say the parameters I mean the learning parameters, for example the regularization strength for the logistic regression. For what values you test them with your cross-validation? But I think that's not the problem anyway, otherwise your F-score for the training set should be small too. – Jundiaius May 27 '14 at 15:10
• Thanks for clarifying. I did a very large grid search for these parameters so I do not think that is the problem. I am pretty confident that the learning parameters are calculated correctly. – mike1886 May 27 '14 at 15:13

• Is your predictor variable (with the class labels) ordinal or nominal? If it is the former, how do you calculate accuracy? e.g. do you incorporate the fact that $Y_{predict} = 50$ is better than $Y_{predict}=10$, when $Y_{real} = 55$?