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?” — and 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, and 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, and 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

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. 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. 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 — 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) — and 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, so 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 — 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?