Over-fitting and Under-fitting of a Model

1. Definitions

• Over-fitting: the model learns the training data too well. Besides the true underlying pattern it also memorises the random noise, outliers and accidental regularities peculiar to that sample. It gives an extremely low (often zero) error on the training data but a large error on unseen data, i.e. it fails to generalise.
• Under-fitting: the model is too simple to capture the structure present in the data. It does not learn even the training relationship, so it has high error both on the training set and on the test set. Such a model has high bias.

2. When do they happen?

Over-fitting occurs when:

1. The model is far too complex for the amount of data - e.g. a fully grown, unpruned decision tree that creates one leaf per record, a very high-degree polynomial, or a neural network with far more parameters than samples.
2. Training continues too long, or the same data is reused with constant hyper-parameter tuning (the test data is indirectly used for training).
3. The training data is small, noisy, unrepresentative or contains outliers that the model tries to explain.
4. No validation, pruning or regularisation is used.

Under-fitting occurs when:

1. The model is too simple to represent the data - e.g. a decision stump, a linear model fitted to clearly non-linear data, a tree with too few levels.
2. Too few or uninformative features are used, or useful features are discarded.
3. Training stops too early (premature stopping), or the regularisation strength is set too high.
4. The learning algorithm itself cannot express the true relationship (a high-bias model).

3. Bias-variance view

Total prediction error = Bias + Variance + irreducible noise; the goal is the sweet spot where this sum is minimum.

 Error
  |  \___                     __--  training error
  |      \____          ____--
  |           \____--~~     gap between the two curves
  |            ^   ^          = over-fitting
  |            |   validation error
  +------------+--------------------------------> Model complexity
          under-fitted   good fit     over-fitted

4. Detection and control

• Detect: split the data into training and validation sets (k-fold cross-validation) and compare the two error curves; plot a learning curve (error vs. amount of training data).
• Cure over-fitting: collect more training data, post-pruning / pre-pruning of the tree, regularisation, dropout and early stopping, feature selection, ensemble methods such as bagging and random forests, or a simpler model.
• Cure under-fitting: use a richer model, add better features, train longer, reduce regularisation.