Decision Trees: Entropy, Gini & Info Gain

Last lesson left every classifier so far speaking in weight vectors — correct, but unreadable. Here is the model that answers the wish for one a person can follow by finger.

A decision tree asks a sequence of plain yes/no questions — “is this feature above that threshold?” Each answer sends a sample down a branch, until it lands at a leaf that names a class. Is income below ₹30,000? Then is debt above ₹10,000? Then refuse. No dot products, no margins; just questions, the way a human would reason.

The whole art is which question to ask first. The rest of the lesson is that one decision made precise. At every node the tree picks the split leaving its two children as pure as possible — each child dominated by a single class — because a pure child is a confident answer.

But “pure” is a feeling until you put a number on it. That number is an impurity measure. This same split-on-best-gain idea powers the random forests and gradient-boosted trees that still win most tabular-data contests, so the arithmetic here is the engine inside tools you will actually ship.

Measuring impurity

Both of the standard measures answer one question, in different currencies: if I reached into this node and pulled out a sample at random, how uncertain am I about its label? Both read zero when every sample shares a class. Both peak when the classes are evenly mixed and the node tells you nothing at all.

For a node where class i holds a fraction pᵢ of the samples, two measures dominate GATE:

• Entropy H = −Σ pᵢ·log2(pᵢ) — measured in bits, roughly the number of yes/no questions you would need to pin down one sample’s class. A pure node (p = 1) has H = 0; a 50/50 binary node has H = 1 (maximal disorder).
• Gini G = 1 − Σ pᵢ² — a pure node has G = 0; a 50/50 node has G = 0.5. It is the sklearn default, being slightly cheaper than a logarithm.

A split is then judged by how much it cuts impurity:

Information gain = H(parent) − Σ (weighted) H(child), where each child is weighted by the fraction of samples it receives.

Higher gain means a better split.

That word weighted is doing far more work than it looks, and skipping it is the single most expensive habit on this topic. Suppose a parent of 20 samples, 10 positive and 10 negative, so H(parent) = 1.

A lazy split peels off one lone positive sample into its own child and leaves the other 19 together. That tiny child is perfectly pure — H = 0. The big child is [9 pos, 10 neg], still almost evenly mixed, with H ≈ 0.998.

Average the two child entropies as equals and you get 0.499, suggesting a gain of about 0.5 — a fantastic split. Weight them by how many samples each actually received, and the picture collapses:

weighted H = (1/20)·0 + (19/20)·0.998 = 0.948
IG         = 1 − 0.948 = 0.052

Barely five hundredths of a bit. The purity of the small child is real but nearly worthless, because it settled the fate of one sample out of twenty. Weighting by sample count is precisely what stops a tree from congratulating itself for splitting off crumbs.

Below, add axis-aligned cuts and watch each one carve a region, recolour by majority class, and drop the Gini impurity — the greedy best cut is hinted in green.

How GATE asks this

The bread-and-butter version is a NAT: you are handed a parent node and one proposed split into two children (with class counts), and asked for the information gain — or just the entropy or Gini of a single node. Numbers are kept clean (3/1 splits, 9/1 splits, 50/50 nodes) so the arithmetic is doable in a minute.

Conceptual MCQ/MSQ questions probe the rest of the ceiling: a pure node has impurity 0, higher gain is the better split, and a fully grown tree overfits (high variance).

Worked example — information gain of a split

A parent node has 10 positive and 10 negative samples. A candidate split sends them to child A = [9 pos, 1 neg] and child B = [1 pos, 9 neg], each holding 10 samples. What is the information gain?

Step 1 — parent entropy. The parent is a perfect 50/50:

H(parent) = −0.5·log2(0.5) − 0.5·log2(0.5)
          = −0.5·(−1) − 0.5·(−1) = 1.0

Step 2 — child entropy. Child A is p = 0.9 and 0.1. Using log2(0.9) ≈ −0.152 and log2(0.1) ≈ −3.322:

H(A) = −0.9·log2(0.9) − 0.1·log2(0.1)
     = −0.9·(−0.152) − 0.1·(−3.322)
     = 0.137 + 0.332 = 0.469

Child B is the mirror image (p = 0.1, 0.9), so H(B) = 0.469 as well.

Step 3 — weighted child entropy. Each child holds half the samples (weight 10/20 = 0.5):

Weighted H = 0.5·0.469 + 0.5·0.469 = 0.469

Step 4 — information gain.

IG = H(parent) − Weighted H = 1.0 − 0.469 = 0.531

So this split buys 0.531 bits — a large gain, exactly because it turns a useless 50/50 node into two nearly pure children. The same arithmetic in Python:

from math import log2

def entropy(counts):
    n = sum(counts)
    return -sum((c/n) * log2(c/n) for c in counts if c)   # skip 0-count classes

h_parent = entropy([10, 10])
h_a      = entropy([9, 1])
h_b      = entropy([1, 9])
weighted = 0.5 * h_a + 0.5 * h_b
gain     = h_parent - weighted

print(f"H(parent) = {h_parent:.3f}")
print(f"H(child)  = {h_a:.3f}")
print(f"info gain = {gain:.3f}")

H(parent) = 1.000
H(child)  = 0.469
info gain = 0.531

In one breath

A decision tree classifies by a readable cascade of yes/no questions, choosing at each node the split that most reduces impurity. Impurity is measured by entropy H = −Σ pᵢ log2 pᵢ (0 for pure, 1 bit for a 50/50 binary node) or Gini G = 1 − Σ pᵢ² (0 for pure, 0.5 for 50/50).

It ranks splits by information gain = parent impurity minus the sample-weighted child impurity, always taking the largest. Left to grow unchecked, it drives training impurity to zero by memorising noise. Depth limits or pruning are what keep it from overfitting.

Practice

A question to carry forward

The tree was a detour — a readable, rule-based model that owes nothing to weights or geometry. But it came at a price: greedy axis-aligned cuts, a tendency to overfit, and no kinship at all with the brain that first inspired the word “learning.” So return, one last time, to the linear-score family — and ask the question that cracks the whole field open.

Every linear classifier so far was fitted: solved by a normal equation, or descended on a loss. None of them learned in the plain sense of watching its own mistakes and correcting.

What is the simplest unit that does exactly that? It sees a point it got wrong, nudges itself a little toward getting it right, and repeats, with no calculus and no probability anywhere. Here is the thread onward: that humble self-correcting unit is the literal ancestor of every neural network.

What is its one update rule, and what is the one kind of problem it can never solve, no matter how long it runs?