Unit 3.1 · about 5 h
144 / 324CART: split objectives, impurity, stopping and pruning
Trees decide by recursive splits, so every later ensemble inherits their split logic, their variance and their failure modes. If you cannot score a split by hand, forest and boosting diagnostics stay magic.
- derive
- implement
You can now
- Compute weighted Gini, entropy and variance reduction for a candidate split by hand and name the winning split.
- Implement a CART-style best-split scan with a stated tie rule, stopping conditions and leaf predictions, and differential-test it against sklearn on small data.
- Predict how
max_depth,min_samples_splitandccp_alphachange bias, variance and tree size.
Covers
- CART classification and regression split objectives
- Gini, entropy, information gain and variance reduction
- Stopping, pruning and deterministic split ties
Study, in this order
4 steps
- HoML Chapter 5: growing and regularizing treesHands-On Machine Learning with Scikit-Learn and PyTorch - nonlinear classical models
Book Chapter 5, from Training and Visualizing a Decision Tree through Decision Trees Have a High Variance (printed pp. 179-193). Notebook 05 cells: Training and Visualizing a Decision Tree, Making Predictions, Estimating Class Probabilities, Regularization Hyperparameters, Regression, Sensitivity to axis orientation, Decision Trees Have High Variance
- sklearn decision trees: split search, criteria and complexityscikit-learn - neighbors, SVMs, trees and ensembles
1.10.7 Mathematical formulation with 1.10.7.1 Classification criteria and 1.10.7.2 Regression criteria; 1.10.4 Complexity for fit and predict cost
- sklearn decision trees: CART scope, tips and pruningscikit-learn - neighbors, SVMs, trees and ensembles
1.10.6 CART versus ID3 and C4.5 (binary splits, no categorical support); 1.10.5 Tips on practical use; 1.10.9 Minimal Cost-Complexity Pruning with the weakest-link rule and
ccp_alpha - ISLP Chapter 8: regression and classification treesISLP - tree-based methods and support vector machines
Sections 8.1.1 and 8.1.2 (pp. 331 to 341): recursive binary splitting, Gini versus entropy similarity, and classification error reserved for pruning
Focus on
- Split quality is the weighted child impurity \(G = (n_L/n) H(L) + (n_R/n) H(R)\). The parent impurity is the same for every candidate at a node, so minimizing \(G\) is the same as maximizing the impurity decrease.
- sklearn tries midpoints between sorted distinct values with greedy exhaustive search, while Deep-ML 138 scores the raw values: the same four points yield threshold 3.0 under sklearn and 2.5 in problem 138.
- Gini and entropy are numerically close and either works for growing; ISLP reserves the classification error rate for pruning toward accuracy.
ccp_alphapenalizes leaf count and prunes the weakest link first, which produces the nested candidate path that cross-validation then selects from.
Reproduce closed-book
X = [0, 1, 2, 3] with y = [0, 0, 1, 1] at max_depth = 1.Traps
- Equal impurity does not mean a unique split. With two identical feature columns, sklearn picks feature 1 under seeds 0 and 1 but feature 0 under seed 42, so your scanner must define first-wins and test it.
- A child can be less pure than its parent: the A, B child has Gini 0.5 against the parent 0.32. Only the weighted sum has to decrease.
- HoML Chapter 5 never sets
criterion, so every tree there is Gini. Request entropy explicitly, and remember the 138-versus-sklearn threshold convention before comparing answers.
Practice
Deep-ML 138: Find the Best Gini-Based Split for a Binary Decision Tree
Implement find_best_split(X, y); the visible tests check (0, 2.5) on the 4-point split and (0, 1) on the all-pure tie
The visible tests pin thresholds to sorted unique values (2.5, not the sklearn midpoint 3.0) with first minimum in feature-then-value order winning. Implement that convention, not sklearn midpoints.
Deep-ML 20: Decision Tree Learning
Implement learn_decision_tree(examples, attributes, target_attr); the visible tests check the two-attribute PlayTennis tree and a single-attribute tree
Splits use entropy with information gain, values in sorted order, first attribute on ties and alphabetical leaf on ties.
Self-test
-
A node holds 3 positives and 1 negative. What are its Gini impurity and its entropy in bits?
\(\text{Gini} = 1 - 0.75^2 - 0.25^2 = 0.375\). \(\text{Entropy} = -(0.75 \log_2 0.75 + 0.25 \log_2 0.25) = 0.311 + 0.5 = 0.811\) bits. -
Why does ISLP call the error rate weak for growing but prefer it for pruning?
Growing needs sensitivity to purity shifts that leave the majority label unchanged. Pruning selects the final tree for accuracy, which is exactly what the error rate measures. -
The same data and code give different trees under a new
random_state. Is that a bug?No. Tied splits can resolve differently across seeds, as the identical-feature test shows. Fix the seed for reproducibility and define your own deterministic tie rule. -
One leaf holds one vote for each of three classes. What does sklearn predict and with what probabilities?
It predictsclasses_[0], the lowest index, with probabilities \(\left[\begin{smallmatrix}1/3&1/3&1/3\end{smallmatrix}\right]\). Argmax takes the first maximum.
Completion criterion
Stop when
Your hand table gives 0.32, 0.2 and 0.3, your scanner matches sklearn on two small sets, and both Deep-ML problems pass.
Mark passed, then open 3.2 Only mark this when you can do it without notes.Leads to
- 3.2 Bagging, random forests and out-of-bag estimates Grow forests from the trees you just built.
- 3.3 AdaBoost and gradient boosting Fit the same splits to residuals and reweighted data.
Resources for this unit
- Hands-On Machine Learning with Scikit-Learn and PyTorch - nonlinear classical models Read Chapters 3, 5 and 6 and the online Appendix C notebook as the first pass through performance measures, trees, ensembles and SVMs, running notebooks 03, 05 and 06 alongside. Vary depth, estimators, learning rate, k, C and RBF width under fixed splits.
- scikit-learn - neighbors, SVMs, trees and ensembles Check official estimator constraints, complexity, preprocessing needs, missing-value behavior and probability caveats. Do not use library calls as the mechanism implementation.
- ISLP - tree-based methods and support vector machines Use Chapters 8 and 9 with their Python labs for the statistical account of trees, bagging, random forests, boosting and SVMs that the notebooks leave implicit, and for model-choice and feature-importance arguments.
Also in this section
- Deep-ML - tree, ensemble and kernel problems Use 138 Best Gini-Based Split, 20 Decision Tree Learning, 307 Bagging Classifier, 21 Pegasos Kernel SVM and 280 RBF Kernel as unit checks after the local implementation passes. Their tests were read in review; each card states what they pin, including tie and update-order conventions.
- Probabilistic Machine Learning, Chapter 16: exemplar-based methods Read Sections 16.1 to 16.1.3 for the KNN decision rule, the curse of dimensionality with the growing-hypercube example, and the speed section on k-d trees, hashing and approximate search.
- XGBoost parameters and sklearn estimator interface Read the tree-booster parameter list for
eta, depth, sampling and regularization names and defaults, and the sklearn page for early stopping witheval_set. - LightGBM parameters Read
learning_rate,num_leaves,max_depth,min_data_in_leaf,feature_fraction,bagging_fractionwithbagging_freq,lambda_l2and early stopping defaults. - CatBoost common parameters and categorical features Read
iterations,learning_rate,l2_leaf_reg,depth,grow_policy,subsample,rsm,boosting_type,use_best_modelandone_hot_max_sizedefaults, plus native categorical handling.