Model Selection

Model Selection

1. The Problem

Given many candidate models (different algorithms, parameters, attribute subsets), which one should be deployed? Model selection is the estimate-then-compare-then-tune process of choosing the model that will generalise best on unseen data, balancing accuracy against complexity.

 Training data
      |
      +--> [ candidate model 1 (e.g. ID3, depth 4, attrs A,B,C) ] --\
      +--> [ candidate model 2 (e.g. naive Bayes, all attrs)     ] ---+--> evaluation on
      +--> [ candidate model 3 (e.g. SVM, RBF kernel)            ] --/     VALIDATION data
      +--> ...                                                            |
                                     choose best generalisation  <-------+
                                              |
                                   retrain on all data -> deployed model

2. Underfitting, Overfitting and the Bias–Variance Trade-off

	Underfitting (high bias)	Overfitting (high variance)
Symptom	Poor accuracy on both training and test data	Excellent training accuracy, poor test accuracy
Cause	Model too simple, too few attributes, pruned too much	Model too complex, noise modelled, too few training tuples, too many attributes
Cure	More attributes/features, more complex model, less pruning, longer training	Pruning, more training data, regularisation, simpler model, ensembling, attribute selection

Error decomposition:

Typical U-shaped validation curve:

 error
   |\                              /
   | \   underfitting            /  overfitting
   |  \  (high bias)           /    (high variance)
   |   \__________ lowest test error
   |        training error keeps falling ......
   +--------------------------------------------> model complexity
       small tree                        deep tree (all leaves pure)

3. Training vs Validation vs Test Data

Subset	Purpose	Rule
Training	Fit the parameters (split thresholds, weights)	Should not be used to compare models
Validation	Tune hyperparameters (tree depth, $k$, threshold) and select the model	Used repeatedly during development
Test	Final, single, unbiased performance report	Touched once, at the end

If the validation set is used for selection, the winner's validation accuracy is optimistically biased → report the test-set accuracy instead. For small datasets, use nested cross-validation (inner loop tunes, outer loop estimates error).

4. Occam's Razor

"Given two models of similar generalisation error, prefer the simpler one." Simplicity = fewer parameters, fewer attributes, shallower tree, smaller rule set, smoother decision boundary. Simpler models are less likely to overfit and are usually more interpretable; the principle is formalised by minimum description length (MDL):

The best model minimises total description length. C4.5's pessimistic pruning and cost-complexity pruning are practical applications of this idea:

where $R(T)$ is the tree error and $|T|$ the number of leaves.

5. Hyperparameter Tuning

Method	How it works	Note
Manual / grid search	Exhaustive over a specified grid (max_depth ∈ {2,4,6,8}, k ∈ {1,3,5,7})	Simple, exponential cost
Random search	Sample combinations randomly	Often better than grid search for the same budget
Bayesian optimisation	Model the objective as a Gaussian process, choose the next configuration by expected improvement	Efficient for expensive models
Early stopping	Watch validation error; stop when it starts rising	Neural nets, gradient boosting
Regularisation	Add a penalty term: $L_1$ (lasso, sparse feature selection) / $L_2$ (ridge, weight shrinkage)

|
| Validation-curve comparison | Plot training and validation error against a complexity parameter | Reveals the sweet spot |

6. Comparing and Ranking Models Statistically

• Simple comparison of accuracy on the same test set/ folds; look at the standard deviation across folds, not just the mean.
• Confidence interval for accuracy (normal approximation for large $n$):

• Paired t-test on $k$-fold accuracies (see previous topic) for two models.
• ANOVA or Friedman test with Nemenyi post-hoc test for multiple models over multiple datasets.
• If false-positive and false-negative costs differ, choose by expected cost, not accuracy:

7. Practical Model Selection Checklist

1. Define the business objective and the performance measure (accuracy, $F_1$, AUC, RMSE, MAPE, cost).
2. Fix a stratified test set and never touch it until the end.
3. Try a few algorithm families (e.g. decision tree, naive Bayes, k-NN, SVM, ensemble) — not just one.
4. Perform attribute selection and preprocessing consistently inside each CV fold.
5. Tune hyperparameters with a validation set or inner CV.
6. Probe the complexity curve to locate underfitting vs overfitting.
7. Apply Occam's razor among statistically indistinguishable models; favour interpretability for the domain.
8. Check the learning curve (error vs training-set size) to see whether more data would help.
9. Report final performance with confidence intervals on the untouched test set; document the pipeline (metadata / model card) for reproducibility.

8. Exam Points

• Explain the need for model selection; distinguish training, validation and test data — 5-7 marks.
• Explain overfitting and underfitting with a graph and the bias–variance decomposition — 7-10 marks (very frequent).
• State and explain Occam's razor; relate it to MDL and cost-complexity pruning — 5 marks.
• Explain any three hyperparameter tuning strategies — 5 marks.
• Why must the test set not be used for tuning? — 3 marks.