Is it ok to keep/discard rules based on the holdout set?

Question

We have a POC project that is looking for rules that fit our data (eg "when a=1 and b=2 and c=3 then X=6" sort of thing). We split our data into 6 sets, and we use the first 5 sets as K-fold training sets where we say "only keep the rules where the accuracy of the rule on each of the 5 parts is within 5% of the accuracy of the other 4 combined". This gives us a bunch of rules. Then we validate each of these rules against the holdout set to see if it generalizes.

My view is that if the majority (over 90%) of the rules are failing on the holdout set then the way we are finding these rules is too overfitted and that the remaining 10% that pass validation are probably just passing by coincidence but won't perform well on future data. My colleague's view is that if we keep the 10% that passed then these are the ones that have shown to perform well on unseen data and we will have a good set of rules.

What is the standard accepted practice in this scenario? And are there any other tests one can do to say if our methodology is flawed or not?

Answer 1

Is it ok to keep/discard rules based on the holdout set?

It would not be valid to perform model selection based on the holdout set if you're also using that set to estimate/report the generalization performance of your learning algorithm. Doing this would make the performance estimate overoptimistically biased.

What is the standard accepted practice in this scenario?

Performance should be evaluated using a separate, independent set of data that hasn't been used for training or model selection. Model selection may also use a separate subset of the data than training, depending on the model selection procedure. Using simple holdout, the data would be split into training, validation, and test sets. The validation set is used for model selection and the test set is used to estimate generalization performance. Alternatively, nested cross validation could be used.

It's possible for model selection to overfit the validation set, even though it contains data that hasn't been seen by the training procedure. For example, see Cawley and Talbot (2010) and this question. This is more likely to happen when searching over a larger set of models, or when the validation set is smaller. Nested cross validation would be preferred over simple holdout in this setting, because the training, validation, and test sets would effectively be larger. But, it still might not be enough to save things--in that case the only recourse is to gather more data or search a simpler/more restricted set of models.

are there any other tests one can do to say if our methodology is flawed or not?

You might try randomly permuting the outputs in the dataset, which destroys the information between input and output. Then, try to fit the permuted data. Any fitting here is, by construction, overfitting. You'd want to see that your model selection procedure correctly rejects overfit models.

References:

Cawley and Talbot (2010). On Over-fitting in Model Selection and Subsequent Selection Bias in Performance Evaluation.