Decision trees and validation
A binary classification tree is grown until every terminal node contains observations of only one class.
Explain why its training error may be misleading as an estimate of future error.
Is a validation set useful? Explain with a concrete choice of tuning parameter and an explicit selection procedure.
Describe the geometry of the decision regions for a tree that splits one numerical predictor at a time.
Repeated splitting can fit peculiarities of the training sample and can isolate observations, so a low training error can coexist with high variance and with poor performance on new data. Perfect purity is impossible when identical predictor vectors have conflicting labels, unless the fitting rule does something beyond ordinary deterministic splits.
A validation set is useful. Grow candidate subtrees along a cost-complexity pruning path on the training data, predict the validation labels, and choose a pruning parameter using validation loss. Refit as appropriate with that setting fixed, then evaluate on an untouched test set. Depth, leaf size, and split thresholds are other tuning choices. A tree’s greedy split fitting does not itself choose predictive complexity.
Each split is an axis-aligned threshold. A leaf is an intersection of half-spaces, hence an axis-aligned rectangular region, possibly unbounded. A class region can be a union of several such leaves.