148 Model Selection and Validation
This theorem tells us that the error on the validation set approximates the
true error as long asHis not too large. However, if we try too many methods
(resulting in|H|that is large relative to the size of the validation set) then we’re
in danger of overfitting.
To illustrate how validation is useful for model selection, consider again the
example of fitting a one dimensional polynomial as described in the beginning
of this chapter. In the following we depict the same training set, with ERM
polynomials of degree 2, 3, and 10, but this time we also depict an additional
validation set (marked as red, unfilled circles). The polynomial of degree 10 has
minimal training error, yet the polynomial of degree 3 has the minimal validation
error, and hence it will be chosen as the best model.11.2.3 The Model-Selection Curve
The model selection curve shows the training error and validation error as a func-
tion of the complexity of the model considered. For example, for the polynomial
fitting problem mentioned previously, the curve will look like: