Decision Trees

A decision tree is a supervised learning model that predicts a class label by routing an input example through a tree of questions.

The intuition (why trees feel natural)

Humans often make decisions by asking a sequence of questions:

• •“Is the email from someone I know?”
• •“Does it contain urgent language?”
• •“Is there an attachment?”

Each answer narrows possibilities. A decision tree does the same, but it learns which questions to ask from labeled data.

The structure (internal nodes, edges, leaves)

A classification decision tree consists of:

• •Root node: contains the whole training set.
• •Internal decision nodes: apply a test on a feature (e.g., xⱼ ≤ t).
• •Edges/branches: correspond to outcomes of the test.
• •Leaf nodes: store a prediction rule, usually a class label (and often class probabilities).

So the model is a recursive partitioning of the feature space: each split partitions the current region into subregions, and those can be split again.

Notation you’ll see throughout

Assume K classes. At a node v:

• •n = number of training examples at node v
• •nₖ = number of examples of class k at node v
• •pₖ = nₖ / n is the empirical class distribution at node v

We define a scalar impurity:

• •I(v) : impurity of node v (heterogeneity of its class distribution)

For a proposed split s that produces children v₁, …, v_m:

• •ΔI(s) = I(parent) − ∑ᵢ (nᵢ/n) I(vᵢ)

This ΔI(s) is the impurity reduction (also called information gain when using entropy).

What a leaf predicts

A leaf summarizes the class distribution of the training samples that reached it. Two common outputs:

1) Hard label (majority vote):

• •ŷ = argmaxₖ pₖ

2) Probabilities:

• •P(y = k | leaf) ≈ pₖ

Trees are attractive because this is both interpretable (you can print the rules) and fast at inference (a handful of comparisons).

A key mental model: partitioning the space

If your input is a feature vector x ∈ ℝᵈ, each internal node applies a constraint like xⱼ ≤ t. These constraints carve the space into axis-aligned rectangles (for continuous features). Each leaf corresponds to one region, and the tree assigns that region a label.

This is a big deal: decision trees are a way to build piecewise-constant decision boundaries without explicitly writing down complex formulas.

A tree learns by repeatedly asking: “If I split here, will the child nodes be more pure?” To answer that, we need a number that measures impurity.

Why impurity matters

At a node where the classes are mixed (say 50/50), prediction is uncertain. At a node that is almost all one class (say 99/1), prediction is easy.

So we want a function I(v) that is:

• •0 when pure (all examples in one class)
• •larger when mixed
• •symmetric across classes

Two classic choices are entropy and Gini impurity.

Entropy impurity

Given class probabilities p₁, …, p_K at a node:

H(v) = − ∑ₖ pₖ log₂ pₖ

Properties:

• •H = 0 when one pₖ = 1
• •maximum when distribution is uniform (pₖ = 1/K)

When you use entropy in a tree, the split criterion is often called information gain.

Information gain from a split

Suppose parent node has entropy H(parent). A split produces children with entropies H(vᵢ). Let nᵢ be child counts.

Weighted child entropy:

H(children) = ∑ᵢ (nᵢ/n) H(vᵢ)

Information gain:

IG(split) = H(parent) − H(children)

Notice this matches the general form:

ΔI(split) = I(parent) − ∑ᵢ (nᵢ/n) I(childᵢ)

with I = H.

Gini impurity

For class probabilities p₁, …, p_K:

G(v) = 1 − ∑ₖ pₖ²

Interpretation:

• •∑ₖ pₖ² is the probability that two independent draws from the node have the same class.
• •So 1 − ∑ₖ pₖ² is the probability they are different.

For binary classification with p = P(class=1) and (1−p) = P(class=0):

G = 1 − (p² + (1−p)²)

Derive it explicitly:

G = 1 − (p² + (1 − 2p + p²))

= 1 − (1 − 2p + 2p²)

= 2p − 2p²

= 2p(1 − p)

So Gini is a simple parabola peaking at p = 0.5.

Entropy vs Gini (what’s the difference?)

They behave similarly: both are 0 at purity, both peak at maximum mixing. In practice:

• •Gini is slightly cheaper to compute (no logs).
• •Entropy can be slightly more “sensitive” near extremes because of the log.

Most libraries let you choose. Either is fine as long as you understand the weighted impurity reduction idea.

Breathing room: what impurity is NOT

Impurity is not “error rate.” A node could have majority class 60% (so error rate 40%) and still have a certain entropy or Gini. Impurity measures heterogeneity, not misclassification under a fixed rule.

This distinction matters because impurity functions are designed to make greedy splitting work well.

A decision tree is usually trained with a greedy algorithm: at each node, choose the split that maximizes impurity reduction, then recurse.

Why greedy splitting?

The global problem—finding the best possible tree of a given size—is combinatorial and generally intractable for large datasets. Greedy splitting is a practical compromise:

1) At the current node, evaluate many candidate splits.

2) Pick the best local split (largest ΔI).

3) Recurse on children until a stopping rule.

This is why impurity functions matter so much: they are the local objective that guides the whole structure.

Candidate splits

For numeric (continuous) features

A common split form:

• •xⱼ ≤ t (left child)
• •xⱼ > t (right child)

Candidates t are often chosen from sorted unique feature values (or midpoints between them). If the sorted values are a₁ ≤ a₂ ≤ … ≤ a_M, midpoints are:

tᵣ = (aᵣ + aᵣ₊₁)/2

Each candidate threshold produces a partition; compute ΔI and choose max.

For categorical features

Common choices:

• •Multiway split: one branch per category.
• •Binary split: category ∈ S vs category ∉ S (CART typically prefers binary splits).

Binary splits over categories can be expensive if there are many categories (many possible subsets S).

Impurity reduction formula (the core computation)

At node v, with impurity I(v), consider split s producing children v₁,…,v_m.

Let nᵢ be the number of training examples going to child i, and n be parent size.

Weighted child impurity:

I_after(s) = ∑ᵢ (nᵢ/n) I(vᵢ)

Impurity reduction:

ΔI(s) = I(v) − I_after(s)

Choose:

s* = argmax_s ΔI(s)

This is the tree’s “learning signal.”

A useful interpretation: weighted average purity

Because the child impurities are weighted by nᵢ/n, the split prefers:

• •children that are pure, and
• •splits that don’t isolate a tiny pure group while leaving a large messy group (unless the improvement is still large).

Stopping conditions (when do we stop splitting?)

If you always split until every leaf is pure, you usually overfit. Common stopping rules:

• •Max depth: stop when depth reaches D
• •Min samples per leaf: stop if a child would have < m samples
• •Min impurity decrease: stop if best ΔI(s*) < ε
• •Pure node: stop if I(v) = 0

These constraints control complexity.

Leaf prediction (revisited, with probabilities)

At a leaf ℓ with counts nₖ:

pₖ = nₖ / n

Hard prediction:

ŷ = argmaxₖ pₖ

Probability output:

P(y = k | x in leaf ℓ) ≈ pₖ

Many implementations also apply smoothing (e.g., Laplace) to avoid 0 probabilities:

pₖ = (nₖ + α) / (n + Kα)

Computational note: how training scales

At a high level:

• •For each node, you scan candidate splits for each feature.
• •For numeric features, sorting once per feature can help compute many thresholds efficiently.

Practical implementations optimize heavily, but conceptually the cost is tied to:

• •number of features d
• •number of candidate thresholds per feature
• •number of nodes created

Breathing room: what the tree is really doing

It’s easy to get lost in formulas. Keep the picture:

• •Each split is a question.
• •Each question aims to produce child groups that are closer to “single-class.”
• •The process repeats.

The impurity reduction formula is just the arithmetic that turns “closer to single-class” into a number the algorithm can maximize.

Decision trees are popular because they’re simple to explain and surprisingly powerful. But their weaknesses are exactly why ensemble methods (random forests, boosting) are so important.

Strengths of decision trees

1) Interpretability

A tree yields explicit rules:

• •If x₂ ≤ 1.7 and x₅ ∈ {A, C} then predict class 1.

You can inspect paths, feature usage, and thresholds.

2) Minimal preprocessing

• •No need to normalize features.
• •Works with mixed feature types (numeric + categorical) in many implementations.
• •Can handle nonlinear boundaries via multiple splits.

3) Captures interactions

A split on x₁ followed by a split on x₂ naturally represents feature interactions:

• •“x₂ matters only when x₁ is large.”

Linear models require explicit interaction terms; trees get them structurally.

Weaknesses (and the motivations for fixes)

1) High variance (instability)

Small changes in the data can change early splits, which changes the entire tree.

This makes a single tree prone to overfitting, especially when allowed to grow deep.

2) Greedy splitting is myopic

Each split is locally optimal, not globally optimal. The tree can commit early to a split that seems good now but blocks better structure later.

3) Axis-aligned splits can be inefficient

A single split is xⱼ ≤ t. If the true boundary is diagonal, the tree may need many splits to approximate it.

Regularization strategies (before ensembles)

To tame overfitting, we control tree complexity:

• •Pre-pruning: stop early (max depth, min samples per leaf, min ΔI).
• •Post-pruning: grow a large tree, then prune back using a validation set or cost-complexity pruning.

Cost-complexity pruning (high-level idea)

You trade off fit and size:

Objective ≈ training_loss(tree) + λ · (#leaves)

Pruning removes subtrees that don’t justify their complexity.

Why trees unlock ensembles

Trees are strong “base learners” because:

• •They can fit complex patterns.
• •They are cheap to evaluate.

But because they are high variance, averaging many trees (bagging) stabilizes them.

Connection to Random Forests (preview)

Random forests reduce correlation between trees by:

• •Training each tree on a bootstrap sample (bagging)
• •Considering only a random subset of features at each split

The end result is a much more robust predictor.

Connection to Boosting (preview)

Boosting builds trees sequentially, where each tree focuses on correcting the errors of the previous ones. The trees are often shallow (stumps or small depth), and the ensemble forms a powerful model.

When to use a single decision tree

A single tree can be the right choice when:

• •Interpretability and rule extraction matter.
• •You need a quick baseline.
• •The dataset is small-to-medium and you can carefully regularize.

If predictive performance is the main goal, ensembles built from trees are often the next step.