Information Gain

The formula

Gain = H(parent) − [ (nᴱ/n)·H(left) + (nᵣ/n)·H(right) ]

The weights matter. A child holding two points and a child holding eighteen do not deserve an equal say, so each child's entropy is weighted by the share of the data that landed in it. Without that weighting, a split that peels off one lucky point would look like a triumph.

Gain is never negative, and it is zero when the split changes nothing — when both sides have the same label mix as the parent, the question told you nothing you did not already know.

How much did that question help?

Information gain measures how much a split reduces uncertainty. It is the difference between the entropy before a question is asked and the average entropy afterwards.

IG = H(parent) − Σ (nᵢ / n) H(childᵢ)

The weighting matters: a child holding 90% of the rows counts nine times as much as one holding 10%. Without it, a split that isolates two rows into a pure group would look brilliant.

Worked through on 14 samples, 9 yes and 5 no:

Parent entropy: −(9/14)log₂(9/14) − (5/14)log₂(5/14) = 0.940 bits.

Split on Outlook, giving three groups:

Weighted entropy = (5/14)(0.971) + (4/14)(0) + (5/14)(0.971) = 0.694.

Information gain = 0.940 − 0.694 = 0.246 bits.

The Overcast branch is the interesting one: entropy zero, a completely pure group, and the tree can stop there and make a leaf. That is what a genuinely useful question looks like.

How a tree uses it

At every node the algorithm loops over every feature and, for numeric features, every candidate threshold. For each candidate it computes the information gain, and it keeps the best. Then it repeats on each child.

This is a greedy procedure: it takes the locally best split without considering whether a slightly worse split now would enable a much better one later. Finding the globally optimal tree is computationally intractable, and in practice greedy splitting works well enough that nobody minds.

Splitting continues until a stopping rule fires — a pure node, a maximum depth, too few samples to split, or no split producing a worthwhile gain.

Gini and entropy pick the same split the overwhelming majority of the time. This is not a decision worth agonising over; depth and minimum leaf size matter far more.

The bias towards high-cardinality features

Information gain has a systematic flaw: it favours features with many distinct values, because splitting into many small groups almost guarantees pure children.

The extreme case makes it obvious. Split on a customer ID column and every branch has exactly one row, every child is pure, and the information gain is maximal. The tree has learned a lookup table and will generalise to nothing.

Two corrections:

• Gain ratio divides the gain by the entropy of the split itself, which is large when a feature produces many branches. C4.5 introduced this specifically for the problem.
• Binary splits. CART, and therefore scikit-learn, only ever splits into two groups, which limits how much a high-cardinality feature can exploit the bias.

The same bias affects the feature importances a tree reports. Impurity-based importance inflates high-cardinality columns, which is why permutation importance — measured on held-out data — is the more trustworthy ranking.

Score every split

A small dataset, every candidate split scored by information gain. The winning split is the one that leaves the least uncertainty behind.

import numpy as np

# five features, one label; only feature 0 is genuinely informative
rng = np.random.default_rng(0)
n = 400
X = rng.integers(0, 2, size=(n, 5))
y = np.where(rng.random(n) < np.where(X[:, 0] == 1, 0.9, 0.15), 1, 0)

def entropy(labels):
    if len(labels) == 0:
        return 0.0
    p = np.bincount(labels, minlength=2) / len(labels)
    p = p[p > 0]
    return -(p * np.log2(p)).sum()

before = entropy(y)
print("entropy before any split: %.4f bits" % before)
print()
for col in range(5):
    left, right = y[X[:, col] == 0], y[X[:, col] == 1]
    after = (len(left) * entropy(left) + len(right) * entropy(right)) / n
    print("  split on feature %d: entropy after %.4f  ->  gain %.4f"
          % (col, after, before - after))
print()
print("gain is never negative and is near zero for a feature that tells you")
print("nothing. a decision tree tries every column like this and keeps the best.")

Guided tour

1. Look at the parent. Twenty students, 11 passed and 9 failed, so entropy before any split is 0.993 bits — almost a full bit, because the classes are nearly balanced and knowing nothing else you would be nearly guessing.
2. Split badly on purpose. Drag Threshold down to 1.5. One student goes left and nineteen go right, so the right-hand child still reads 11 pass / 8 fail — almost exactly the parent — and the gain collapses to 0.060 bits. You learned something about one student and nothing about the rest.
3. Now press Find The Best Split. The threshold jumps from 4.5 to 6.5, the peak of the gain curve. Everyone who studied more than six hours passed, so that child is pure — entropy exactly 0.000 — and the gain climbs from 0.181 to 0.414 bits.
4. Read the curve. The lower panel plots gain at every candidate threshold. It is jagged rather than smooth, because moving the threshold changes nothing at all until it crosses an actual data point. This is why trees only ever consider midpoints between observed values.
5. Switch features. Change Split On Feature to attendance and press Find The Best Split again. The best it can manage is 0.145 bits at 82.5% — a third of what hours bought. That comparison — best gain from feature 1 against best gain from feature 2 — is precisely the choice the tree makes at each node.
6. Find a worthless split. Push the threshold to either extreme so that one side is empty. The gain drops to 0.000: a split that separates nothing tells you nothing.

Gini, and why the choice barely matters

Many implementations measure impurity with the Gini index, 1 − Σ pᵢ², rather than entropy. Both are zero for a pure node and maximal for an even mix; Gini avoids a logarithm and is marginally cheaper. In practice the two pick the same split the overwhelming majority of the time, and scikit-learn's default of Gini is a performance decision, not a statistical one.

Entropy has the better story though: it is measured in bits, and gain is literally the number of bits of uncertainty the answer removed.

Where raw gain misleads

• High-cardinality features. Split on a column of unique IDs and every child holds one row, so every child is pure and the gain is maximal — on a feature with no predictive value whatsoever. Gain ratio, which divides by the entropy of the split itself, exists to punish exactly this.
• Greed. The tree takes the best split now, never the pair of splits that would be best together. It is a greedy algorithm, and greedy is not optimal — XOR-shaped data defeats the first split entirely.
• Overfitting. Keep splitting and gain stays non-negative all the way down to one point per leaf, at which point the tree has memorised the training set. Depth limits, minimum samples per leaf and pruning are all answers to this.
• Instability. Two candidate splits with nearly equal gain make the tree's choice a coin flip, and a different sample flips it. This variance is exactly what bagging was built to average away.

Summing up

Information gain is the drop in entropy a split buys: the parent's entropy minus the size-weighted average of its children's. The weighting is what stops a tiny lucky child from looking impressive, and the gain is zero exactly when the split leaves the label mix unchanged. A decision tree builds itself by evaluating this quantity for every feature and every candidate threshold and taking the largest, which also explains its known weaknesses — the measure rewards splitting on high-cardinality columns, the search is greedy rather than globally optimal, and nothing in the gain itself ever tells you to stop.

Beyond trees: mutual information

Information gain, computed between a feature and the target rather than inside a tree, is exactly mutual information — how much knowing one variable reduces uncertainty about the other.

That makes it a general-purpose feature-selection tool with one clear advantage over correlation: it detects any dependence, not just linear ones.

from sklearn.feature_selection import mutual_info_classif, mutual_info_regression

scores = mutual_info_classif(X, y, random_state=0)
for name, s in sorted(zip(feature_names, scores), key=lambda t: -t[1])[:10]:
    print(f"{name:<25} {s:.4f}")

A feature with a perfect parabolic relationship to the target has a correlation near zero and high mutual information. If you rank features by correlation alone, you will discard it.

Three cautions. Mutual information is estimated, not computed exactly, for continuous variables — the estimate depends on binning or nearest-neighbour parameters. It scores features one at a time, so it misses combinations that only matter together. And a high score does not mean a model can use the feature, only that the information is present.

Common mistakes

• Forgetting to weight the children. An unweighted average makes a tiny pure branch look decisive.
• Letting an ID-like column into the features. It will win every split and learn nothing.
• Reading impurity-based importance as truth. It is biased towards high-cardinality features and splits credit arbitrarily between correlated ones.
• Growing without a stopping rule. A tree that splits until every leaf is pure has memorised the training data.
• Assuming entropy is better than Gini because it looks more principled. They agree nearly always, and Gini is cheaper.
• Using information gain on continuous targets. Regression trees use variance reduction instead.

Questions people ask

What is a good information gain? There is no absolute scale — it is relative to the parent's entropy and to what the other candidate splits achieve. A gain of 0.05 bits from a parent at 0.1 is excellent; from a parent at 1.0 it is marginal.

Can information gain be negative? No. The weighted average entropy of the children can never exceed the parent's, so the gain is zero at worst.

Why does my tree pick a feature I think is useless? Usually because it has many distinct values, or because it correlates with something that genuinely matters. Check the cardinality first.

How does this handle missing values? Implementations vary: C4.5 distributes the row fractionally across branches, CART uses surrogate splits, and LightGBM learns a default direction per split.

Is information gain used outside decision trees? Yes — as mutual information for feature selection, in text analysis for identifying discriminative terms, and in active learning to choose the most informative example to label next.

Does it work with more than two classes? Yes. The entropy formula sums over however many classes there are; nothing else changes.

Recap in one screen

• Information gain is the entropy before a split minus the weighted average entropy after it.
• Weighting by branch size is essential, or small pure branches dominate.
• Trees choose the highest-gain split greedily at every node, then repeat.
• The measure is biased towards features with many distinct values — gain ratio and binary splits correct for it.
• Computed against the target, it is mutual information, which detects non-linear dependence that correlation misses.