Information Gain

Definition

Information gain is the number of bits of uncertainty about the label that you remove by learning the value of one feature. You get it by subtracting: measure how mixed the labels are before the split, measure how mixed they are inside each group the split creates, average those by group size, and take the difference.

gain = H(parent) − Σ (nᵢ / n) × H(childᵢ)

The units are real. A gain of 0.3774 bits means that if you had to transmit the labels of 1,000 rows to someone who already knew this feature, the message would be 377 bits shorter. That is what the arithmetic on this page is for, and it is the part that almost never gets explained.

And here is what breaks if you take the number at face value: the highest possible information gain goes to the most useless possible feature. Split on a row ID and every child holds exactly one row, every child is therefore perfectly pure, and the gain equals the entire parent entropy — the maximum any feature can score. On the twelve-row table below, a ticket ID scores 0.9183 bits against 0.3774 for the column that genuinely predicts the outcome. This is not an edge case. It is why decision trees built with raw information gain fall over on any table containing a customer number, a timestamp or a postcode, and it is the reason gain ratio and Gini impurity exist at all.

How It Works

Entropy is how surprised you expect to be

Everything starts with one formula, from Shannon's 1948 A Mathematical Theory of Communication. For an outcome with probabilities p₁, p₂, …:

H = − Σ pᵢ log₂ pᵢ

Read log₂(1/pᵢ) as the surprise of outcome i — a one-in-eight event is worth 3 units of surprise, a certain event is worth 0 — and the formula is just the average surprise, each outcome weighted by how often it happens. Three cases pin the scale down:

A fair coin: H = −(0.5 log₂ 0.5 + 0.5 log₂ 0.5) = 1 bit. Maximum uncertainty for two outcomes.

A coin that lands heads 90% of the time: H = −(0.9 log₂ 0.9 + 0.1 log₂ 0.1) = 0.9 × 0.1520 + 0.1 × 3.3219 = 0.4690 bits. Less than half the uncertainty, because you can usually guess correctly. Push it to 99% heads and it falls to 0.0808 bits. Push it to 100% and it is exactly 0 — nothing left to learn.

A uniform choice among eight things: H = 8 × (1/8 × log₂ 8) = 3 bits.

The base-2 logarithm is what makes the answer come out in bits rather than nats or bans. Use natural log and every number on this page shrinks by a factor of ln 2 ≈ 0.693; the rankings are unchanged, which is why nobody's decision tree cares, but the interpretation below only works in base 2.

A bit is a yes/no question

That 3 bits for the eight-way choice is not a metaphor. It is the number of yes/no questions binary search needs: is it in the first four?, the first two of those?, this one or that one? — three questions, every time, guaranteed. Sixteen options take 4, and 1,024 take 10.

The unequal case is where the formula earns its keep. Take four outcomes with probabilities ½, ¼, ⅛, ⅛:

H = ½(1) + ¼(2) + ⅛(3) + ⅛(3) = 1.75 bits

Now design the questions by hand. Ask "is it A?" first — half the time you are done in one question. Otherwise ask "is it B?", then "is it C?". The expected number of questions is 0.5 × 1 + 0.25 × 2 + 0.125 × 3 + 0.125 × 3 = 1.75, exactly the entropy. This is Huffman coding, and Shannon's source coding theorem says you can never do better on average: entropy is a floor. 1,000 flips of that 90% coin can be encoded in about 469 bits rather than 1,000, and no scheme compresses them below 469.

So when a feature buys you 0.3774 bits, it has bought you 0.3774 of a yes/no question per row, in the same sense that binary search buys you one.

Before minus after

Information gain applies entropy twice. Compute H over the labels of all the rows — that is your uncertainty knowing nothing. Then partition the rows by the feature's value and compute H inside each group, weighting each by its share of the rows. The weighting is essential: a split that isolates two perfectly pure rows out of a thousand has bought you almost nothing, and the nᵢ/n factor says so by shrinking that child's contribution to 0.002 of the total.

The difference cannot be negative. Conditioning on a variable never increases expected entropy, so the worst a feature can do is 0 — split on a column whose values are unrelated to the label and each child reproduces the parent's class balance, leaving the weighted average exactly where it started. (The estimate from a finite sample does creep above zero, which is a real problem covered under Challenges.)

A worked split: twelve support tickets

Twelve tickets. The label is whether the ticket was escalated to a human engineer. Two candidate features — the channel it arrived on, and whether the customer attached a file — plus the ticket's own ID, which is here to make a point later.

The parent. Four of the twelve escalated, so p = 1/3 and 2/3:

H(parent) = −(1/3 log₂ 1/3 + 2/3 log₂ 2/3)
          = 0.3333 × 1.5850 + 0.6667 × 0.5850
          = 0.9183 bits

Candidate 1 — split on channel. Three children of four rows each. Phone escalates 3 of 4, chat 1 of 4, email 0 of 4.

H(phone) = −(3/4 log₂ 3/4 + 1/4 log₂ 1/4) = 0.8113
H(chat)  = −(1/4 log₂ 1/4 + 3/4 log₂ 3/4) = 0.8113
H(email) = 0                                        (all four agree)

weighted = 4/12(0.8113) + 4/12(0.8113) + 4/12(0) = 0.5409
gain     = 0.9183 − 0.5409 = 0.3774 bits

Candidate 2 — split on attachment. Seven tickets carry one, of which 3 escalated; five do not, of which 1 escalated.

H(yes) = −(3/7 log₂ 3/7 + 4/7 log₂ 4/7) = 0.9852
H(no)  = −(1/5 log₂ 1/5 + 4/5 log₂ 4/5) = 0.7219

weighted = 7/12(0.9852) + 5/12(0.7219) = 0.5747 + 0.3008 = 0.8755
gain     = 0.9183 − 0.8755 = 0.0428 bits

Channel wins, 0.3774 against 0.0428 — nearly nine times the gain — so ID3 makes it the root and pushes the attachment question down into whichever branch still needs it. Look at why it wins: the email child is pure, contributing a flat 0 to the weighted sum, and one third of the dataset is therefore fully resolved by a single question. The attachment split, by contrast, leaves a 3-of-7 child at 0.9852 bits — barely better than knowing nothing. A split is worth exactly what its children are not.

What 0.3774 bits buys you

Take 1,000 tickets with this class balance. Someone who has to learn every escalation outcome from scratch needs 1,000 × 0.9183 ≈ 918 bits. Someone who already has the channel column needs 1,000 × 0.5409 ≈ 541 bits. The channel feature paid for 377 of them, or 41% of the message.

That is the honest reading of an information gain: a compression ratio on the label, given the feature. It is also why gains look small in absolute terms and still matter — 0.0428 bits from the attachment column is a 4.7% reduction, which is not nothing, but you would not build a tree on it.

The same number is called mutual information

Information gain is H(Y) − H(Y|X), and that expression is the definition of the mutual information between the feature and the label. They are one quantity with two names, kept apart by which literature you are reading: decision trees say "gain" because it is scored per candidate split, information theory says "mutual information" because the quantity is symmetric — knowing the label tells you exactly as much about the channel as the channel tells you about the label. scikit-learn ships both spellings, DecisionTreeClassifier(criterion="entropy") and mutual_info_classif. The feature selection page works the same arithmetic as a standalone filter score, one column at a time, without a tree anywhere in sight.

Entropy or Gini — the choice that barely matters

The other standard impurity measure is Gini, 1 − Σ pᵢ², worked through in detail on the decision trees page. The two curves are close enough that the choice almost never changes an answer. Scale Gini by 2 so both peak at 1 for a 50/50 node, and they agree exactly at 0%, 50% and 100% class balance, with a maximum discrepancy of 0.109 in between, reached near a 90/10 split (entropy 0.469 against 0.360). On the ticket table both criteria rank the features the same way: Gini gain of 0.1944 for channel against 0.0254 for attachment, versus 0.3774 against 0.0428 in bits — different units, same order.

Gini is scikit-learn's default because it avoids a logarithm per candidate split, and that is the whole of the practical argument. The one thing worth knowing is that switching to Gini does not rescue you from the defect below: Gini hands a unique ID a gain of 0.4444, which is the entire parent Gini impurity and the maximum available. The bias belongs to impurity reduction itself.

Real-World Applications

ID3 and C4.5 are where the measure entered machine learning. Ross Quinlan's ID3 ("Induction of Decision Trees", Machine Learning 1(1):81–106, 1986) chose each split by maximising information gain, and did nothing else — no pruning, no continuous features, no missing-value handling. C4.5 (Morgan Kaufmann, 1993) is the same algorithm with the holes filled, and the headline change is that it replaced information gain with gain ratio precisely because of the high-cardinality problem. The IEEE ICDM panel's December 2006 list of the ten most influential data-mining algorithms opens with C4.5, ahead of k-means and SVMs; Weka's J48 is the open-source reimplementation still used in teaching and in a great deal of published research.

It is a live setting in every mainstream tree library. DecisionTreeClassifier(criterion= "entropy") in scikit-learn scores exactly the arithmetic above, as does the same argument on RandomForestClassifier and ExtraTreesClassifier. sklearn.feature_selection.mutual_info_classif computes the same quantity as a ranking score outside any tree. The impurity-based feature_importances_ array that people read off random forests and gradient boosting models is nothing but the total weighted impurity reduction each column earned across every node it split — which is why that array inherits the high-cardinality bias intact, and why permutation importance exists.

Choosing the next question is the version that has nothing to do with trees. Bayesian experimental design and active learning use the expected information gain of an action not yet taken: BALD (Houlsby, Huszár, Ghahramani and Lengyel, 2011) picks the unlabelled example whose label would most reduce the model's uncertainty about its own parameters, which is the same mutual information run forward on an expectation instead of backward on a table. Adaptive testing does the same thing to pick the next exam question, and diagnostic triage protocols do it to pick the next test to order.

Wordle solvers made this legible to a lot of people. With roughly 2,300 candidate answers, the puzzle holds log₂ 2300 ≈ 11.2 bits of uncertainty, and a solver scores each candidate guess by the expected entropy of the resulting colour pattern — the guess with the highest expected information gain. It is the same formula as the ticket table, applied to a partition of the answer list rather than a partition of the rows, and it is a useful sanity check on your intuition: a guess that always produces the same feedback earns 0 bits, however clever it looks.

Key Concepts

• The units survive the arithmetic. Entropy in bits, gain in bits, split information in bits. A gain of 0.3774 on a parent of 0.9183 means the feature removed 41% of the uncertainty, and that percentage is comparable across datasets in a way the raw bit count is not.
• Zero gain does not mean useless, it means useless alone. Two features can each score exactly 0 bits and still determine the label perfectly together — the XOR case worked through under feature selection. Scoring one column at a time cannot see it.
• Split information is the entropy of the split's shape, not of the labels: −Σ (nᵢ/n) log₂(nᵢ/n). An even three-way split scores log₂ 3 = 1.585 regardless of what the labels do; a 12-way split of 12 rows scores log₂ 12 = 3.585.

Challenges

The high-cardinality defect, in full. Take the ticket ID column and split on it. Twelve values, twelve children, one row each. Every child has exactly one label, so H(child) = 0 for all twelve, the weighted sum is 0, and:

gain(ticket_id) = 0.9183 − 0 = 0.9183 bits

That is the parent entropy in its entirety — the largest number any feature on this table can possibly produce, awarded to a column that is a database key. Nothing has gone wrong with the formula; information gain is measuring the training labels, and a lookup table does reproduce those perfectly. The defect is that a tree built this way is one node deep, twelve leaves wide, and predicts nothing about ticket T-113. This is overfitting expressed as a scoring bug, and any feature with many distinct values — timestamps, postcodes, order numbers, free-text hashes — triggers a weaker version of it.

Gain ratio, and how far it gets you. Quinlan's fix in C4.5 divides the gain by the split information, the entropy of the group sizes the split produces:

splitInfo = − Σ (nᵢ/n) log₂ (nᵢ/n)

channel    : 3 groups of 4  → splitInfo = log₂ 3 = 1.5850
attachment : 7 and 5        → splitInfo = 0.9799
ticket_id  : 12 groups of 1 → splitInfo = log₂ 12 = 3.5850

Dividing through:

Note what actually happened: the ID's runaway 2.4× lead over channel collapsed to a 7% lead — but it is still ahead. Twelve rows is simply too few for the correction to bite, and this is the honest version of a fix that is usually described as though it settles the matter. The mechanism is worth seeing: a unique ID always earns gain = H(parent), which is capped by the number of classes (at most 1 bit for a two-class problem), while its split information is exactly log₂ n and grows without limit. So its gain ratio decays as 1/log₂ n while channel's divisor stays pinned at log₂ 3 forever:

ticket_id on     12 rows: 0.9183 / 3.5850  = 0.2562
ticket_id on    120 rows: 0.9183 / 6.9069  = 0.1330
ticket_id on  1,200 rows: 0.9183 / 10.2288 = 0.0898
ticket_id on 12,000 rows: 0.9183 / 13.5507 = 0.0678

At any realistic dataset size the ID is beaten several times over. Gain ratio works — it just works asymptotically, and toy tables are where it looks weakest.

Gain ratio overcorrects at the other end. Split information sits in a denominator, so a nearly degenerate split with a tiny denominator produces an enormous ratio. Suppose a "region" column on the same table isolates T-101 by itself and leaves the other eleven together. The singleton child is pure, the eleven-row child is 3-of-11 at 0.8454 bits, so the gain is 0.9183 − 0.7749 = 0.1434 — well under channel's 0.3774. But its split information is only 0.4138, and 0.1434 / 0.4138 = 0.3465, which beats channel's 0.2381 outright. Quinlan knew: C4.5 only considers tests whose raw information gain is at least the average over all tests examined. Here the mean of 0.3774, 0.0428 and 0.1434 is 0.1879, so region is disqualified before its ratio is ever compared. If you implement gain ratio yourself and skip that constraint, you have swapped one bias for a worse one.

Sample entropy is biased upward, and small nodes are where trees live. A feature with no relationship to the label at all does not score 0 on real data — it scores positive, because chance imbalances in small groups look like structure. Draw twelve coin-flip labels and an unrelated three-valued feature at random, and the mean information gain over 200,000 draws is 0.158 bits: 42% of what the genuinely predictive channel column earned, from a column containing pure noise. The asymptotic size of that bias is (k−1)(c−1) / (2n ln 2) bits for a k-valued feature and c classes, which gives 0.0120 at n = 120 against a simulated 0.0123, and 0.0012 at n = 1,200. The bias falls as 1/n and rises with cardinality — the same two forces as the ID problem — and it is why the splits near the bottom of a deep tree, where nodes hold a handful of rows, are substantially noise. Depth limits and min_samples_leaf are the practical defence, and honest cross-validation is how you find out you needed them. It also explains why one-branch-per-category splitting compounds the problem: a six-value column divides the rows six ways in a single step, and every child then estimates its own splits from a sixth of the evidence.

Code Example

Entropy, information gain, split information and gain ratio, on the twelve tickets above. No dependencies beyond the standard library.

import math
from collections import Counter

# ticket_id, channel, attachment, escalated
rows = [
    ("T-101", "phone", "no",  1), ("T-102", "phone", "yes", 1),
    ("T-103", "phone", "yes", 1), ("T-104", "phone", "no",  0),
    ("T-105", "chat",  "yes", 1), ("T-106", "chat",  "yes", 0),
    ("T-107", "chat",  "no",  0), ("T-108", "chat",  "no",  0),
    ("T-109", "email", "yes", 0), ("T-110", "email", "yes", 0),
    ("T-111", "email", "yes", 0), ("T-112", "email", "no",  0),
]

def entropy(labels):
    n = len(labels)
    return -sum((c / n) * math.log2(c / n) for c in Counter(labels).values())

def children(rows, col):
    groups = {}
    for r in rows:
        groups.setdefault(r[col], []).append(r[-1])
    return list(groups.values())

def info_gain(rows, col):
    n = len(rows)
    after = sum(len(g) / n * entropy(g) for g in children(rows, col))
    return entropy([r[-1] for r in rows]) - after

def split_info(rows, col):
    n = len(rows)
    return -sum(len(g) / n * math.log2(len(g) / n) for g in children(rows, col))

parent = entropy([r[-1] for r in rows])
print(f"H(parent) = {parent:.4f} bits over {len(rows)} tickets\n")
print(f"{'feature':11} {'gain':>7} {'split info':>11} {'gain ratio':>11}")
for col, name in ((1, "channel"), (2, "attachment"), (0, "ticket_id")):
    g, s = info_gain(rows, col), split_info(rows, col)
    print(f"{name:11} {g:7.4f} {s:11.4f} {g / s:11.4f}")

# A column with one value per row always scores gain = H(parent) and split
# information = log2(n), so its gain ratio decays as 1/log2(n).
print()
for n in (12, 120, 1_200, 12_000):
    print(f"ticket_id on {n:>6} tickets: gain 0.9183, split info {math.log2(n):6.4f}"
          f", gain ratio {parent / math.log2(n):.4f}")

Output:

H(parent) = 0.9183 bits over 12 tickets

feature        gain  split info  gain ratio
channel      0.3774      1.5850      0.2381
attachment   0.0428      0.9799      0.0437
ticket_id    0.9183      3.5850      0.2562

ticket_id on     12 tickets: gain 0.9183, split info 3.5850, gain ratio 0.2562
ticket_id on    120 tickets: gain 0.9183, split info 6.9069, gain ratio 0.1330
ticket_id on   1200 tickets: gain 0.9183, split info 10.2288, gain ratio 0.0898
ticket_id on  12000 tickets: gain 0.9183, split info 13.5507, gain ratio 0.0678

Twenty-odd lines reproduce every number on this page, including the one that matters: ticket_id tops the gain column by a factor of 2.4 and is the only column in the table with no predictive content whatsoever. Delete the split_info function and you have written ID3; keep it and you have most of C4.5. The gap between those two is the whole reason the second algorithm was published.