Writing / Machine learning notes / Decision trees & pruning

Decision trees,
from splits to pruning.

Learn a sequence of questions from data. Understand the impurity calculations, grow a tree, and decide which branches deserve to stay.

A decision tree divides a prediction problem into smaller questions. Each answer sends an observation into a smaller region; a leaf supplies the prediction. We will derive how the questions are chosen, why a deeper tree can fit training data better, and how validation and pruning control its complexity.

These notes join the decision-tree lecture and its pruning continuation, including their handwritten examples, the weather calculation, entropy versus error, efficient pruning counts, and the closing random-forest sketch. Original numerical examples and interactive tools make the intermediate steps visible. The previous chapter's projections supply a useful contrast: tree splits operate along the supplied feature axes, so the representation still matters.

Reading route: sections 1–8 explain the model and split criterion. Sections 9–13 grow and analyze trees. Sections 14–20 develop overfitting and pruning, with a complete interactive example. Sections 21–22 connect ensembles and practical choices. Practice and revision then test the same material.

1. Why ask a sequence of small questions?

Lecture connection: interpretable decisions, fraud/insurance/customer applications, and comparison with other decision boundaries.

A classifier such as shared-covariance GDA or logistic regression uses a score that combines features. A usual classification tree instead asks questions such as “is this sender already known?” or “is this measurement at most 3?” A complete path records the conditions that led to one prediction. A small tree can therefore make its decision procedure easy to inspect.

The lecture motivates this with fraud detection, insurance and credit decisions, and customer analysis. It also asks how to assess a model against legal constraints. A readable path helps inspection, but a tree can still use inappropriate features, proxies, or biased observations. Tree structure alone cannot establish that a decision is fair, causal, or legally compliant.

For the lecture's credit-law example, the official Regulation B notification provision requires specific principal reasons for the adverse actions it covers. This illustrates why understanding the actual decision factors can matter. It does not make a particular model family automatically compliant or prohibit another family just because its explanation is harder.

Tree learning is supervised: training observations include inputs and target labels or responses. Its partition can grow in complexity as more splits are permitted, which is why it is commonly called nonparametric. A fitted tree still has learned thresholds, a topology, and leaf values. Classification trees generally fit the input-to-label relationship directly; they need not build a generative density for each class.

2. Read the structure and see the regions

Lecture connection: internal tests and labeled leaves, the spam sketch, and axis-parallel decision boundaries.

The root is the first node. An internal node applies a test. An edge records an answer, and a leaf returns a prediction. A binary split has two children; a categorical multiway split can have more. The depth of the root is zero, and a path's depth counts its edges.

For a numerical test, we will send \(x_j\le t\) left and \(x_j>t\) right. This convention resolves equality. Prediction evaluates only one path. For example, a spam rule could first check whether the sender is known, then inspect a domain category, and then a content feature. This is an illustrative rule structure; the tests must be learned and validated before claiming predictive performance.

Each numerical test cuts the current node's region with a hyperplane perpendicular to one coordinate axis. Descendant cuts act only inside that region. Intersecting all path conditions gives an axis-parallel rectangle in two dimensions, or a hyperrectangle in d dimensions, possibly unbounded. The region predicted as one class can be a union of several leaves.

A path is a conjunction: all its tests must be satisfied. Multiple paths reaching the same class combine by an OR. For the pictured lower-left class-0 leaf, a rule is \((x_1\le2.5)\land(x_2\le3.5)\Rightarrow0\). A class boundary need not be one straight line, even though each individual test is simple.

3. Let the feature type determine the possible questions

Lecture connection: binary values, ordinal categories, non-ordinal categories, one-hot encoding, subsets, and thresholds.

A binary feature offers a direct two-way test. For an ordinal category, such as an ordered grade, a threshold can group the lower ordered values against the higher ones. Its order must be defined; alphabetical spelling is not a measurement scale.

A nominal feature, such as a domain category, has no natural order. Choices include one child per value, one value versus the rest, or a subset-versus-complement test \(x_j\in C\). One-hot encoding supplies binary indicators, but it changes the available one-step questions. Coding red=0, green=1, blue=2 and blindly thresholding the code imposes an arbitrary order.

With r nominal categories, there are \(2^{r-1}-1\) distinct nonempty binary partitions after identifying a subset with its complement. Searching every grouping can be costly. An ordinal feature has only r−1 gaps between adjacent distinct values. The split family is part of the model, not a detail to leave unspecified.

For a real-valued feature, sort the values observed at the current node. Every gap between two distinct consecutive values gives a candidate partition; a midpoint is a convenient representative threshold. Equal feature values must travel together. Different thresholds inside the same empty gap give the same training partition, although they can route a future observation differently.

The same numerical feature can be tested again farther down a path to refine an interval. A categorical feature already fixed to one value by an ancestor offers no further split there. Missing values and categories unseen during fitting need an explicit policy, such as a learned missing-value route or a documented fallback; the basic complete-data formulas do not supply one automatically.

4. What should a leaf predict?

Let S be the training observations reaching a node, \(n=|S|>0\), and \(n_c\) the number with class c. The empirical class distribution is:

This is also the categorical maximum-likelihood estimate obtained by the constrained count calculation from the Naive Bayes chapter, now applied to labels within a leaf. For a constant predicted class a, the training error count is n−nₐ. Therefore equal-cost classification selects a majority class:

Specify a deterministic tie rule; the binary teaching tools here choose class 0 when the counts tie. Estimated leaf probabilities are empirical proportions, not guaranteed calibrated population probabilities. A tiny pure leaf can report an extreme estimate from very little evidence. Smoothing or a different cost-sensitive prediction rule changes the leaf estimator or decision rule and should be stated explicitly.

A node receiving no observations has no empirical distribution to estimate. A sensible tree-building routine rejects a split with an empty child; a fallback leaf for an unseen categorical branch must inherit an explicitly chosen prediction, rather than divide by zero.

5. Measure impurity with Gini

Lecture connection: class proportions, pure endpoints, the binary maximum, and the K-class extension.

An impurity measure summarizes how mixed the labels are at a node. For K classes, Gini impurity is:

To interpret it, imagine drawing a true label and, independently, a guessed label from the same node distribution. The chance of a match is \(\sum_c\hat p_c^2\); Gini is the chance they differ. It is not the error of the deterministic majority-label classifier.

For binary labels with positive proportion p, the formula becomes \(G(p)=1-p^2-(1-p)^2=2p(1-p)\). It is zero at p=0 or 1 and reaches 1/2 at p=1/2. Differentiating gives \(G'(p)=2-4p\) and \(G''(p)=-4\): the curve is concave.

For K classes, \(\sum_c(p_c-1/K)^2\ge0\) implies \(\sum_c p_c^2\ge1/K\). Hence \(G\le1-1/K\), with equality for the uniform class distribution. A pure node has G=0. The maximum changes with the number of classes; binary plots should not be read as having the same maximum for every K.

6. Derive entropy from label surprise

Lecture connection: binary and multiclass entropy, ideal code lengths, uncertainty, and the entropy curve.

A rare label carries more surprise than a common one. Assign an event of probability p the self-information \(-\log_2p\) bits. This convention makes the surprise of two independent events additive, since \(-\log_2(pq)=-\log_2p-\log_2q\). Average over the node's label distribution:

Use \(0\log_20=0\), the continuous limit as p approaches zero. A class that never appears contributes zero; evaluating log0 directly in a program is unnecessary. For a binary node:

The endpoints are zero. In the interior, \(h'(p)=\log_2((1-p)/p)\), and \(h''(p)=-1/[\ln2\,p(1-p)]<0\). Thus the maximum is h(1/2)=1 bit. The multiclass maximum is \(\log_2K\), attained at equal proportions. One way to see the bound is to apply concavity of log to the weighted average \(\sum_{p_c>0}p_c\log_2(1/p_c)\le\log_2 K_+\le\log_2 K\), where K₊ is the number of positive-probability classes.

The lecture relates entropy to coding class labels. The real-valued ideal length −log₂p does not always equal the length of a one-label binary prefix code, which must use integer lengths. Entropy is the ideal average/asymptotic coding rate; block or arithmetic coding can approach it. For tree splitting, the expected surprise formula is the quantity we calculate.

7. A split is good when the weighted children are purer

Lecture connection: information gain and branch-size weighting in binary and multiway splits.

A candidate test partitions S into disjoint nonempty children \(S_1,\ldots,S_B\). Let \(w_b=|S_b|/|S|\). A randomly selected observation from S reaches child b with probability wᵦ, so the expected child impurity uses those weights:

For entropy, this is information gain. For Gini it is a Gini decrease. The parent term is common to all candidates at that node, so maximizing gain is the same as minimizing weighted child impurity. An unweighted average would give a small and a large child equal influence, answering a different question.

Parent class proportions are weighted averages of child proportions. Entropy and Gini are concave, meaning their value at an average distribution is at least the corresponding average of their values. Therefore a valid split has nonnegative empirical gain, up to numerical rounding. In binary notation:

The vertical gap between the curve and the weighted child point is the gain. A split can contain a child that is more mixed than the parent while still improving the weighted average. Empirical gain need not mean that the feature will improve unseen predictions; searching many tests can find chance patterns.

For binary Gini, expanding the squares gives an especially useful identity:

It measures how much the child class proportions differ. For entropy, the same reduction is the empirical mutual information between the label and the selected branch. This is a statement about the observed node sample; interpreting it as a population dependence requires more evidence.

8. Why immediate classification accuracy can miss a useful split

Lecture connection: the 40-positive/80-negative example and the entropy-versus-error comparison.

The majority-error impurity is \(M(S)=1-\max_c p_c\), which is min(p,1−p) for binary labels. It measures a leaf's deterministic error rate. Unlike entropy and Gini, its binary curve is linear on each side of 1/2. Child proportions can move apart while remaining on the same side, producing no reduction in immediate majority error.

The lecture's parent has 40 positives and 80 negatives. Its candidate children contain [28+,42−] and [12+,38−]. All three majority predictions are class 0. Before splitting there are 40 errors; afterward there are 28+12=40. The weighted misclassification decrease is zero.

Entropy still falls: the parent is h(1/3)≈0.918296 bits; the children have h(0.4)≈0.970951 and h(0.24)≈0.795040. Their weighted average is about 0.897655, so gain is about 0.020641 bits. Gini decreases from 4/9 to 0.432, giving about 0.012444. The children are differently composed even though their current majority labels agree.

The next-level tests in the lecture separate the remaining classes into pure leaves. This explains why a criterion sensitive to changing proportions can be useful while growing a tree. It does not guarantee that every positive-gain split helps generalization or that greedy growth finds the best complete tree.

9. Grow recursively, making the stopping rules explicit

Lecture connection: GrowTree pseudocode, feature/threshold search, stopping, and the handwritten training-cost estimate.

Begin with a leaf that predicts the node's majority. If splitting is permitted, compare all valid candidate tests at that node, choose the best, partition the observations, and repeat separately in each child. This is top-down greedy growth: the current choice uses its immediate impurity reduction, without exhaustively optimizing every possible future subtree.

Grow(S, depth):
    compute class counts and a majority prediction
    if S is pure or a stopping condition applies:
        return a leaf with that prediction
    enumerate permitted tests with nonempty, sufficiently large children
    if no permitted test remains:
        return the majority leaf
    choose the test with the best impurity decrease
    if the specified gain rule rejects it:
        return the majority leaf
    return a test node whose children are Grow(child_sample, depth + 1)

The lecture's abbreviated algorithm assumes that a useful split exists whenever the node is impure. Real data can contain identical feature vectors with different labels, or no remaining permitted test. Those cases require a majority leaf. No deterministic tree using only those features can perfectly separate contradictory copies.

Gain ties need a reproducible choice. The numerical split workbench chooses the smaller threshold among tied best candidates. A minimum gain rule also needs a precise inequality: allowing a zero-gain step differs from requiring strictly positive gain, especially for feature interactions.

What does the training-time estimate assume?

At a node with n observations and d numerical features, sorting each feature and scanning its candidate gaps costs about \(O(dn\log n)\) for fixed class count, using cumulative class counts so each gap is evaluated efficiently. Recomputing full child histograms from scratch for every threshold would add avoidable work.

If nodes are re-sorted, observations at each depth form disjoint samples, so a depth-L tree has an upper-bound accounting of roughly \(O(dNL\log N)\). The handwritten complexity expression should be read with its depth and search assumptions stated, not as a universal guarantee of a small perfectly classifying tree. Maintaining sorted orders can improve this accounting; exhaustive nominal-category grouping is a different search problem. Prediction follows one root-to-leaf path and costs O(L) ordinary feature tests, rather than visiting every node.

10. Reproduce the lecture's categorical examples

The early two-attribute comparison starts with 29 positives and 35 negatives, giving entropy about 0.993651 bits. Attribute A₁ creates counts [21+,5−] and [8+,30−]; A₂ creates [18+,33−] and [11+,2−]. Weighted child entropies are approximately 0.727776 and 0.872219, so gains are 0.265875 and 0.121432 bits. A₁ is preferred by entropy gain. Comparing a single child's purity would not reproduce this decision.

The weather root

The repeated weather example has 14 observations: 9 play and 5 no-play. We use play as the positive label. Its root entropy is:

For wind, weak has [6+,2−] and strong has [3+,3−]. The child entropies are about 0.811278 and 1. Therefore:

Now recalculate within each child. Overcast becomes a play leaf. Among sunny observations, high humidity has [0+,3−] and normal humidity [2+,0−], so humidity makes both children pure and gains the sunny node's whole entropy h(2/5)≈0.970951. Among rainy observations, weak wind has [3+,0−] and strong wind [0+,2−], so wind makes both children pure. The child decision is conditioned on its path, not chosen by reusing the original root ranking unchanged.

This yields five pure leaves for the training weather sample. It demonstrates recursive fitting; it is not evidence of zero population error or proof that a different sample would select the same tree.

11. Search numerical thresholds on a complete small sample

For an original one-feature example, let x=1,…,8 and labels y=[0,0,1,1,1,0,0,1]. The parent has four positives and four negatives, so entropy is 1 bit. Midpoint candidates are 1.5,2.5,…,7.5. At t=2.5 the left child has [0+,2−] and the right [4+,2−]:

That is the largest entropy gain among these candidates. The left leaf predicts 0 and the right predicts 1. At t=4.5, both children remain evenly mixed and gain is zero. A minimum child size can exclude a candidate even when its gain is large.

Try increasing the minimum child size, changing the impurity criterion, or making every label identical. Pure labels give zero gain for every permitted split, so a normal growth procedure would stop even though the tool can still illustrate a zero-gain partition. Conflicting labels at identical x values cannot be separated by a threshold.

12. A regression leaf predicts a mean, and splits reduce SSE

Lecture connection: the regression question and splitting by mean squared error.

For a real-valued response, a constant leaf value a is fitted by squared error. Differentiate its loss:

The second derivative is 2n>0. A candidate split is scored by parent SSE minus the sum of child SSEs, or by an equivalent consistently weighted MSE. For a binary split:

Derive it by writing each \(y_i-\bar y_S=(y_i-\bar y_b)+(\bar y_b-\bar y_S)\) within child b. The cross terms vanish because deviations from a child's mean sum to zero. This is the same within/between decomposition used with means and covariance earlier in the notes.

For x=1,…,6 and responses [1,2,2,8,9,8], the parent mean is 5 and SSE is 68. Splitting at 3.5 gives leaf means 5/3 and 25/3, with child SSEs 2/3 each. Total SSE becomes 4/3; reduction is 200/3. The per-observation MSE changes from 68/6 to (4/3)/6=2/9.

13. Expressive trees still face a greedy-search limit

Lecture connection: Boolean representability, exponential tree size, and the hypothesis-space search diagram.

For d binary features, a tree can test all features in succession and put the desired truth-table label at each of its 2ᵈ leaves. Thus every Boolean function can be represented. A complete depth-d tree has \(2^{d+1}-1\) total nodes; some functions, such as parity under ordinary single-feature tests, need exponential-size trees.

Expressibility is different from finding a small good tree efficiently. The greedy split at one node maximizes a local criterion. Searching all topologies and tests would be a much larger problem, and the lecture's hypothesis-space diagram explicitly warns that greedy search need not return a globally optimal tree.

A strict positive-gain stopping rule stops at the XOR root. Allowing a zero-gain step can cross that interaction, but also allows unhelpful growth on noise. Depth alone does not resolve the choice if the growth algorithm refuses the initial step. Pre-pruning and search rules therefore impose a bias about which patterns can be found.

14. Better training fit can mean worse prediction

Lecture connection: training versus distribution error, accuracy against tree size, and validation control.

For a classifier h, training error is the observed fraction of wrong labels. Population error is the probability of a mistake on a fresh draw from the task distribution:

The lecture describes overfitting by comparing h with an alternative h′: h fits training better but has larger population error. We cannot usually inspect R(h) exactly; validation and test samples estimate predictive behavior with sampling uncertainty.

If a majority leaf is split and each child predicts its own training majority, training errors cannot increase: \(\sum_b\max_c n_{bc}\ge\max_c\sum_b n_{bc}\). Deepening the tree can isolate mislabeled observations or chance patterns, producing small unusual regions. That extra capacity need not improve new-data accuracy.

Use training data to grow the model, validation data to select depth, pruning, and other settings, and a final untouched test set to evaluate the selected procedure. Repeatedly optimizing a tree on the same validation set can overfit that set too. Cross-validation can help compare settings, with the whole fitting and selection procedure placed inside the appropriate folds.

15. Stop growth early: pre-pruning

Lecture connection: gain, depth, sample count, leaf-count thresholds, complexity penalties, and significance testing.

Pre-pruning constrains which splits may be made during growth. Common controls include a maximum depth, a maximum number of leaves, a minimum number of samples before attempting a split, a minimum number in each child, and a minimum impurity decrease. A minimum split sample count and a minimum child size are different conditions; a node can have many observations but no threshold that creates two sufficiently large children.

A local gain threshold can use the conditional node gain ΔI or the whole-training-sample weighted decrease \((n/N)\Delta I\). The latter gives small deep nodes less influence. State the convention when comparing thresholds. A model-size penalty can also discourage growth, although a post-pruning search over complete subtrees is a separate procedure developed below.

The lecture's statistical-significance option

A contingency-table test can ask whether branch membership and class labels show evidence of dependence. With observed branch/class counts \(O_{bc}\), the independence model expects \(E_{bc}=n_b n_c/n\). Pearson's statistic is:

With independent observations and suitable expected counts, its reference degrees of freedom are (B−1)(K−1), after accounting for actual nonempty categories. For a fixed two-child, two-class table [9,1] and [1,9], every expected count is 5, and the statistic is 12.8. A significance level defines a cutoff rather than making a gain value itself a p-value.

Searching many candidate features or thresholds before reporting a nominal test changes the selection problem; a naive one-test significance claim is not automatically valid for the chosen winner. Sparse expected cells also need care. This is an optional stopping strategy, not a universal replacement for predictive validation. Early stopping can miss interactions, as XOR already showed.

16. Grow first, then compare a subtree with a replacement leaf

Lecture connection: post-pruning, reduced-error pruning, cached training/validation counts, and the efficiency question.

Post-pruning starts from a grown tree and removes selected subtrees. Reduced-error pruning compares predictions on a validation set. For a candidate internal node v, replace its whole subtree by a leaf whose class is the majority among the training observations reaching v. Compare that candidate with the current subtree on validation observations reaching v. The rest of the tree routes and predicts those outside observations as before.

Accept a replacement when the specified validation criterion improves, or remains equal if the tie rule favors a smaller tree. The replacement label is fitted from training counts. Taking a new majority from validation labels would change what is being fitted and invalidate the intended hold-out comparison.

Answer the lecture's efficiency question

Route each validation observation through the fixed initial tree once. At every visited node, record its validation counts \(V_{v,c}\). Store training counts as well, giving a fixed replacement class \(m_v=\arg\max_c N_{v,c}\). A replacement leaf gets \(V_{v,m_v}\) validation observations correct.

For a bottom-up variant, let \(C_v^*\) be the best correct count obtainable by pruning the subtree rooted at v. At an existing leaf, use its fixed prediction. At an internal node:

On a tie, choose the leaf. If the node is retained, each child's already chosen version supplies its predictions. Validation observations in different child regions are disjoint, so correct counts add. By induction from the leaves upward, this dynamic-programming variant finds the highest validation accuracy among prunings of the fixed initial tree with these fixed replacement labels. This claim is about that restricted search space and additive accuracy objective; it does not prove optimality among newly grown trees or for population error.

For M validation observations and depth L, routing costs O(ML), followed by a linear pass over the initial nodes for fixed class count. Cached counts avoid rerunning the whole validation set for every candidate. Other greedy pruning orders are possible and should be specified. A node with no validation observations gives no evidence about its predictive advantage; a tie-to-leaf choice there expresses a simplicity convention.

17. Calculate every pruning of a small tree

The following invented initial tree tests x≤4 at its root. Its left child tests x≤2; its right child tests x≤6. Thus it has four leaves A,B,C,D, from left to right. Training and validation counts are separate:

The full tree makes 2+1+2+1=6 training errors out of 40 and 4+4+1+1=10 validation errors out of 20. Each root child aggregates to training counts [9+,11−], so either replacement child leaf predicts 0. The root aggregates to [18+,22−] and also predicts 0.

Replacing the left subtree raises its training errors from 3 to 9, but lowers its validation errors from 8 to 5. The full tree's totals become 12 training errors and 7 validation errors. Replacing the right subtree instead raises its validation errors from 2 to 5, so it is rejected by validation accuracy.

These are all five prunings of this fixed binary tree. Once the left subtree has been replaced, replacing the root worsens validation error from 7 to 10 and is rejected. Replacing the root before inspecting descendants would tie the original full tree's validation accuracy and could discard the better left-pruned option. This is why the search order and comparison procedure matter.

18. Trade fit against size with a complexity penalty

Lecture connection: impurity plus a penalty for node count; the following subtree derivation makes the risk and size conventions explicit.

Another way to control size is to define a cost for a whole tree T:

Here \(\mathcal L(T)\) is its set of leaves. In the worked example, R(T) is the training misclassification rate. Another implementation may use a weighted leaf-impurity sum \(\sum_\ell(n_\ell/N)I(S_\ell)\), or SSE for regression. Those choices change the cost and the useful numerical scale of α. Unweighted sums of leaf impurities answer a different question.

The lecture writes a penalty for total nodes rather than leaves. Both are size penalties, but their parameter values are not identical. For a full binary tree, total nodes equal \(2|\mathcal L|-1\), so \(R+\beta|\text{nodes}|=R+2\beta|\mathcal L|-\beta\). Minimizers agree with a leaf penalty α=2β; the constant −β does not affect selection. That conversion assumes every internal node has exactly two children.

Compare complete subtree costs

For the five candidates above, the training risks are 0.15,0.30,0.30,0.45,0.45. The full-tree and root-leaf lines cross when:

Checking all five candidates shows that the full tree minimizes this cost for α<0.10; the root leaf minimizes it for α>0.10. At equality, the stated smaller-tree tie rule selects the root. The validation-best left-pruned tree is never the cost optimum for this particular training risk. The objectives need not choose the same subtree.

Derive an effective penalty for removing a branch

For an internal node v with current descendant subtree Tᵥ, compare keeping all its leaves with replacing it by one leaf. Using contributions weighted by the whole training sample's N, equality occurs at:

This is the increase in fitted risk per leaf removed. Weakest-link cost-complexity pruning removes the branch with the smallest effective value and updates the remaining tree. In the example, each child branch has effective α=(9−3)/40=0.15, while the root has (18−6)/(40×3)=0.10, so the root is the first weakest link. This explains the two-tree cost path.

The lecture lists complexity control alongside early stopping; a penalty can discourage a split during growth, while minimal cost-complexity post-pruning searches prunings of a grown tree. They are different algorithms. Select the penalty by validation or cross-validation; minimizing the training-plus-size criterion alone does not measure future error.

19. Explore validation decisions and complexity costs separately

This workbench uses the fixed initial tree and training counts from section 17. Edit its validation counts, inspect any pruning, or apply the best validation choice. The cost-based action instead minimizes training error rate plus α per leaf. Predictions and replacement labels always use the fixed training counts.

At the defaults, validation chooses the left-pruned tree and α=0.05 chooses the full tree. Change α to 0.10 to see the smaller-tree cost tie. Change validation evidence in A and B to see when keeping their distinguishing split becomes useful. The tool compares all five possible prunings; it does not refit the original thresholds or grow new branches.

20. Convert paths to rules, then prune conditions carefully

Lecture connection: root-to-leaf conjunctions and rule-based post-pruning.

A root-to-leaf path gives a rule such as \(A\land B\land C\Rightarrow1\). Rule pruning considers removing one or more conditions: deleting B gives \(A\land C\Rightarrow1\). The rule then covers at least as many inputs, including some that did not reach the original leaf.

Evaluate the broadened rule on the designated selection data under a specified rule-selection criterion. Removing a logically redundant condition leaves coverage unchanged; removing a useful one may improve robustness or create errors. It is not equivalent to simply deleting the last tree node, because a condition high on the path can be removed from one rule while retained in another.

Original tree paths are mutually exclusive and collectively cover the input space when routing is fully defined. Independently pruned rules can overlap, predict conflicting labels, or leave cases without a matching rule. An ordered rule list, conflict-resolution policy, and default prediction may therefore be needed. Evaluate the resulting complete classifier, including those policies, rather than assuming each separately simplified rule preserves the original tree's behavior.

21. The closing bridge: randomized trees and forests

Lecture connection: repeatedly sample examples/features, build trees, and combine them; the distinctions below make the sampling procedure explicit.

The final handwritten sketch grows many trees after randomly choosing observations and features. It motivates an ensemble whose members differ. A fixed feature subset chosen once per tree is a random-subspace construction. In the common Breiman-style random forest, each tree uses a bootstrap training sample, and a fresh random subset of candidate features is considered at each split. These are distinct randomization conventions; the lecture's shorthand should not conceal where the subset is drawn.

Bootstrap sampling draws observations with replacement, usually N draws for N training observations, so some observations repeat and others are absent from a tree's sample. Classification can combine class votes; regression averages predictions. Averaging class probabilities and taking a majority of hard class labels are different aggregation rules and should be specified. A hundred trees is an example setting, not the definition of a forest. Deep growth still needs feasible stopping rules when no valid split remains.

Optional foundation: why correlation matters when averaging

Suppose B real-valued tree predictions at one input have the same variance σ² and common pairwise correlation ρ. Expand the variance of their mean, counting B diagonal terms and B(B−1) covariance terms:

For independent predictions, averaging reduces this variance by B. With positive correlation, the expression approaches ρσ². The calculation explains a motivation for diversity; it is not a formula for classification error, and the common-variance/common-correlation assumptions need not hold exactly in a fitted forest.

A bootstrap draw omits a given training observation with probability \((1-1/N)^N\), approaching e⁻¹. Predictions for that observation from only trees that omitted it are called out-of-bag predictions. Their evaluation can be useful, but it must still respect the intended sampling and model-selection procedure. Full forest tuning, boosting, and ensemble comparisons deserve further notes beyond this introductory sketch.

22. Practical choices and connections

Feature count and memorization: a nominal identifier with one unique value per training observation can make every child pure and receive maximum empirical entropy gain. That does not make the identifier predictive for new observations. Minimum child size, validation, and suitable feature handling address different parts of the problem. Gain-ratio and other criteria are further methods with their own tradeoffs, rather than guarantees that high-cardinality bias disappears.

Scaling and representation: a positive affine unit conversion preserves numerical order and maps a threshold to an equivalent threshold. Trees therefore do not need feature standardization merely to put magnitudes on the same scale. Their axis-aligned split family still depends on the feature representation: a rotation such as PCA can change how many simple cuts describe a boundary.

Probabilities and costs: majority prediction assumes equal misclassification costs. Class imbalance and unequal costs can require a different prediction or training objective. Leaf proportions, smoothing, and probability calibration are separate choices. A large or stable-looking tree diagram alone does not establish accurate probabilities.

Stability and importance: small data changes can switch a nearly tied best split near the root and change many descendants. Feature-importance summaries based on training impurity reduction describe the fitted procedure and can favor features offering many candidate splits. They do not prove causation. Held-out evaluation and the task's meaning still matter.

Algorithm families: ID3-style information-gain growth, binary CART-style trees, regression trees, and different pruning procedures make different choices. State the test family, impurity, stopping rules, leaf prediction, and pruning objective explicitly. The lecture's formulas teach those components; they do not imply every library implements the same combination.

23. Practice: calculate the split and justify the pruning

These are original questions for these notes. State the class-count convention, criterion, sample-size weights, routing inequality, and selection dataset before calculating. A smaller impurity or a smaller tree is meaningful only relative to its stated objective.

24. Explain trees and pruning in an interview

25. Revision: keep the criterion and dataset explicit

Mastery checklist

Saved in this browser where local storage is available.

• I can trace a path, state equality routing, and draw its region.
• I can choose valid tests for binary, ordinal, nominal and numerical features.
• I can derive leaf probabilities, majority labels and regression means.
• I can derive Gini and entropy and state their multiclass maxima.
• I can calculate weighted gain and explain why it is nonnegative.
• I can explain entropy improvement with zero immediate accuracy gain.
• I can reproduce the weather gains and continue within its children.
• I can search distinct numerical gaps and respect minimum child sizes.
• I can explain regression SSE reduction, XOR, search limits and cost assumptions.
• I can separate training, validation and final test roles.
• I can compare pre-pruning, reduced-error and rule-pruning decisions.
• I can use cached counts for a bottom-up pruning calculation.
• I can derive a cost-complexity crossover and distinguish node/leaf penalties.
• I can explain forest randomization, bootstrap sampling and averaging assumptions.

26. Sources and further learning

These personal notes expand Rahul Garg's decision-tree and pruning lectures (Lectures 31–32), including handwritten feature-type examples, training complexity, Gini extensions, validation-count pruning, and the closing forest sketch. The supplied teaching slides credit Greg Grudic, Thomas G. Dietterich, Tom Mitchell, Longin Jan Latecki and Piyush Rai; several impurity illustrations credit Sebastian Raschka. The lecture's weather and count examples are recalculated in prose; the scientific figures here are original.

The derivation details, numerical threshold sample, regression data, generated overfitting illustration, complete five-subtree pruning example, workbenches, practice questions and interview explanations are original teaching additions. The coding-rate qualification, bottom-up fixed-label recurrence, weakest-link derivation, significance-test assumptions, node/leaf conversion, and ensemble covariance calculation make the surrounding assumptions explicit. The forest material is introductory, rather than a claim to cover a full ensemble-learning course.

• Primary coverage: both supplied decision-tree lectures, including annotations and their repeated examples.
• Scikit-learn: Decision Trees — supplementary reference for classification/regression criteria and minimal cost-complexity pruning. The teaching tools are independent implementations and use the risk conventions stated here.
• Leo Breiman: Random Forests — primary reference for the forest construction and its data/feature randomization.
• CFPB: Regulation B, notifications — source for the limited credit-explanation context discussed at the start.

Further learning: fuller ensemble methods, calibration, resampling, and statistical model assessment can build on these foundations. The probability, likelihood, covariance, and representation chapters remain linked where they are used here.