What is the reasons for a model to have a high cross validation score and yet underperforms on unseen data?

Question

I have a model that is based on an experiment collected on 100 subjects. We are testing the model as follows:

1. Record raw data from the subjects
2. For each subject, compute the feature from the raw data (thus, we obtain 100 datasets with 25 features)
3. Reserve the data of one subject for model validation
4. Combine the remaining 99 datasets into one large dataset (thus, we obtain a dataset with up to 1 million rows and 25 columns)
5. The obtained large dataset is used to train a model and evaluate it using a 10-folds cross-validation.
6. Use the reserved dataset (see step 3) to validate the model obtained in step 5 above

Unfortunately, the model's performance is very confusing to me (is this an overfitting? a data leakage?) :

1. The cross-validated model achieves 99.9% accuracy and 99.7% recall)
2. However, when the same model is tested using the validate test set (see step 3), I get a very low accuracy (40.2% recall and 39.8% precision)

What could be the reason for this discrepancy? Any suggestions on how this could be improved?

NOTE: This question was originally posted here but I was asked to move it to this forum instead.

Answer 1

If I understand you correctly, you do an

• outer leave-one-subject out cross (?) validation and
• inner 10-fold cross validation.

Three things come to my mind:

• the most obvious is as @Sandro says: if the inner cross validation doesn't again split by subject, it will not detect if the model overfits on the training patients. Wasn't exactly this overfitting (or the corresponding clustering by subject in the data) the reason to go for subject-wise splitting in the outer validation?
• If the inner cross validation does (correctly) use subject-wise splitting, you can still run into overfitting, e.g. if you run an aggressive hyperparameter optimization that ends up picking an unstable overfit model.
• If I did not understand you outer validation procedure correctly and instead of doing an outer subject-wise cross validation you are actually validating using only a single subject: you cannot conclude anything further than that you found a subject that isn't predicted well by the model you obtain: there could be a large variation of performance between subjects, and testing n = 1 subject doesn't even allow to get a guesstimate of that variance.
  In that case, do an outer cross validation with subject-wise splitting.