Decision trees and the meaning of an objective

Prerequisites: Conditional probability; train and test splits.

Learning objectives

• Compute weighted impurity.
• Distinguish fit from generalization.
• Recognize leakage in feature construction.

A tree partitions the input space

A classification tree asks a sequence of questions about features. Each leaf predicts a class, often using the class frequencies among training examples that reach it. Training chooses questions to improve an objective. The objective is a precise rule for comparing candidate trees, not a guarantee that the resulting predictions will be useful.

For a binary label with positive fraction p, Gini impurity is 1 - p² - (1-p)². A pure leaf has impurity zero. A balanced leaf has impurity 0.5. Evaluate a split using the size-weighted impurities of its children. Adding unweighted child scores would give a tiny leaf as much influence as a large one.

Work a split by hand

Suppose ten training examples contain six positive and four negative labels. The parent impurity is 1 - 0.6² - 0.4² = 0.48. A proposed question creates a left child with four positives and one negative, and a right child with two positives and three negatives. Their impurities are 0.32 and 0.48. Both contain five examples, so the weighted impurity is 0.4 and the decrease is 0.08.

Another question might isolate a single mislabeled example and improve training impurity slightly. Continuing until every leaf is pure can memorize noise. Restricting depth, requiring a minimum leaf size, or pruning can reduce this flexibility. Choose those settings using validation data, then evaluate the selected procedure on a separate test set.

The split is only as legitimate as the information

A feature must be available at the time the prediction will be made. Predicting loan default using a field recorded after collection activity starts can yield excellent offline accuracy and an unusable deployed model. Random splitting does not fix that temporal leakage. Define the prediction timestamp, the label observation window, and the feature availability window explicitly.

Trees can express nonlinear boundaries and interactions without assuming a linear relationship. They can also be unstable: a small data change can alter an early split and many downstream decisions. Ensembles reduce some variance, at the cost of more computation and a less compact explanation. A feature appearing near the root is not evidence that changing it will cause the label to change.

Report a baseline, class frequencies, the evaluation metric, and performance on relevant slices. An accuracy improvement on a heavily imbalanced dataset may hide worse recall for the rare class that matters most.

Practice problem

A node has eight examples, four positive and four negative. A split produces a pure child of two positives and another child with two positives and four negatives. Compute the weighted Gini impurity and improvement. Explain why this calculation cannot select the final model on its own.

Worked solution

The parent impurity is 0.5. The pure child contributes zero. The six-example child has positive fraction 1/3 and impurity 1 - 1/9 - 4/9 = 4/9. Weighting by 6/8 gives 1/3. The improvement is 1/2 - 1/3 = 1/6. This measures training-set purity for one split. It does not measure generalization, feature availability, calibration, or the cost of errors. Depth and other choices need validation; the final selected procedure needs a held-out evaluation.

Check your understanding

Why weight child impurity by child size?

• To make each example contribute equally.
• To force equally sized leaves.
• To remove the need for validation.
• To guarantee a causal split.

Explanation

Each child summarizes a different number of training examples.

Which feature is invalid for a prediction made at loan approval?

• Income known at application.
• Amount requested.
• A collection action recorded months later.
• Credit history available at approval.

Explanation

The later action was unavailable at the prediction time and leaks outcome information.

Primary reading

• Machine Learning course materials: Stanford CS229

Open the study and save your work →