Information Gain

In one sentence: Information gain is a score for how much a yes-or-no question reduces our uncertainty about the class of each example, so a tree can ask the question that sorts its examples best.

$\mathrm{IG} = H(\text{parent}) - \sum_{k} \frac{n_k}{n}\, H(\text{child}_k)$

Read it out loud: “IG equals H of parent, minus the sum, over every child k, of n sub k over n, times H of child k. IG is the information gain. H is entropy, a mixing score measured in bits. n is the number of examples in the parent group, and n sub k is the number of examples that go to child number k. The capital sigma is the add-up sign, read as sum over k. Each n sub k over n is a fraction, the share of the examples that go to that child.”

Before you start

The ideas and signs this page uses, explained from zero. For powers of ten, Greek letters and other notation in general, see Math basics.

Entropy as uncertainty, $H$ , and the bit: Entropy, written $H$ , is a score for how uncertain or mixed a group is. A group where every example has the same class has entropy 0, because we already know the answer. A group split evenly between two classes has entropy 1. The unit is the bit: one bit is the amount of uncertainty removed by one fair yes-or-no answer, like the result of one coin flip.
The base-2 logarithm, $\log_2$: A logarithm answers the question: how many times must I multiply a base number to reach this number? The base-2 version, $\log_2$ , uses 2 as the base. So $\log_2 8 = 3$ , because $2 \times 2 \times 2 = 8$ , and $\log_2 1 = 0$ , because no multiplying is needed. A share between 0 and 1 gives a negative value, so $\log_2 0.5 = -1$ , because one halving of 1 gives 0.5. Entropy uses these values and then flips the sign.
The natural logarithm, $\ln$ , and nats: The natural logarithm, written $\ln$ , works the same way but uses the special number $e$ , about 2.718, as its base. Using $\ln$ instead of $\log_2$ changes the unit: the result is measured in nats instead of bits. One bit equals about 0.693 nats, so a number in nats cannot be compared directly with a number in bits.
The sum sign and subscripts, $\sum_k$ and $n_k$: The capital sigma, $\sum$ , means add up. $\sum_{k}$ says to add over every child $k$ . A small letter or number written below a symbol is a subscript: $n_k$ is the count for child number $k$ , and $H(\text{child}_k)$ is the entropy of that child. The plain letter $n$ is the count for the whole parent group, and the children’s counts add up to $n$ .
Fractions as weights, like $\frac{n_k}{n}$: A fraction is one number divided by another, written with a bar. $\frac{n_k}{n}$ is the number of examples sent to child $k$ , divided by the number in the parent. If the parent has 10 examples and a child gets 5, the fraction is $\frac{5}{10} = 0.5$ . This fraction is the weight of that child: how much of the whole group it holds.
Parent, child and split: A split is a question that divides one group, the parent, into smaller groups, called children. A split of 10 email messages might send 5 to one child and 5 to another. A split can have two children or more. Information gain compares the uncertainty of the parent with the uncertainty of the children after the split.

What each symbol means

Symbol	Meaning
$\mathrm{IG}$	Information gain, the drop in entropy caused by one split. It is measured in bits, because entropy is measured in bits. It is never negative, and it is never larger than the entropy of the parent. For a two-class group, a useful question gives a gain somewhere between 0 and 1 bit.
$H(\text{parent})$	The entropy of the parent group before the split, in bits. It measures how uncertain the classes are before we ask the question. For a group of 6 red and 4 blue, it is about 0.971 bits.
$H(\text{child}_k)$	The entropy of child group $k$ after the split, in bits, worked out with the same formula as the parent. A pure child has entropy 0 bits.
$H$	Entropy in bits, $H = -\sum_j p_j \log_2 p_j$ . It adds up, over the classes, each share times the base-2 logarithm of that share, and then flips the sign. It is 0 for a pure group and reaches $\log_2 K$ bits when the classes are evenly mixed.
$j$	The running number for the classes inside one group, used in the entropy formula. It counts from 1 up to the number of classes, and it has no unit.
$n$	The number of examples in the parent group before the split. It is a plain count with no unit. In the example it is 10 emails.
$n_k$	The number of examples the split sends to child $k$ . It is a plain count with no unit, and the counts for all the children add up to $n$ .
$k$	The running number for the child groups, counting $1, 2, \dots$ up to the number of children. It only names one child at a time and has no unit.
$\sum_{k}$	The add-up sign over every child $k$ . It tells us to add the weighted child entropies for all the children, which gives one total.

The formula piece by piece

$p_j$: Start with a share. $p_j$ is the fraction of examples in one group that belong to class $j$ . It is between 0 and 1 with no unit, and the shares of all the classes in one group add up to 1.
$\log_2 p_j$: The base-2 logarithm of that share: how many times we must multiply 2 by itself to reach $p_j$ . Because $p_j$ is 1 or less, this value is zero or negative. The minus sign in the next step turns the total positive.
$H = -\sum_j p_j \log_2 p_j$: The entropy of one group. Multiply each share by its logarithm, add the results over all the classes, and flip the sign. The answer is in bits: 0 for a pure group, and 1 for an even two-class mix.
$\frac{n_k}{n}$: The weight of child $k$ . It is the number of examples the split sends to that child, divided by the number in the parent. The weights of all the children add up to 1, so a child with more examples gets a bigger weight.
$\frac{n_k}{n}\, H(\text{child}_k)$: The weighted entropy of one child: its entropy times its weight. A large child that is still mixed adds a lot, while a small or pure child adds little.
$\mathrm{IG} = H(\text{parent}) - \sum_{k} \frac{n_k}{n}\, H(\text{child}_k)$: Information gain equals the entropy of the parent, minus the weighted average entropy of the children. It is the number of bits of uncertainty that the question removes.
$\mathrm{IG} = H(Y) - H(Y \mid X)$: The same quantity written in a second standard form. $H(Y)$ is the entropy of the class labels before the question. $H(Y \mid X)$ is the average entropy left after we know the answer to the question $X$ . The vertical bar means given. Outside decision trees this quantity is called mutual information.

What the formula is doing, and why

The input is one group of examples and one question that splits it. The output is one number, the information gain, measured in bits. It answers this: how much does knowing the answer to this question reduce our uncertainty about the class of each example? A gain of 0 means the question tells us nothing new about the classes.

Why a logarithm? A rare outcome is more surprising than a common one, and the more surprising an outcome is, the more it tells us. An outcome with share $p$ has a surprise of $\log_2 \frac{1}{p}$ bits, which grows as $p$ shrinks. Entropy is the average surprise, with each class weighted by its share. The logarithm of a share is negative, so the minus sign in front makes the entropy positive. Base 2 makes the unit a bit.

Why weight the children? A child is only part of the story. If we averaged the child entropies with equal weights, a child holding one example would count as much as a child holding nine. The weight $\frac{n_k}{n}$ gives each child a say in proportion to its size, so the average describes the whole parent group correctly.

Why subtract from the parent? The gain is the uncertainty removed. If the children are purer than the parent, their weighted average entropy is lower, and the gain is positive. If the class mix does not change at all, the gain is 0. For any split, the weighted average of the children cannot be bigger than the parent’s entropy, because splitting a group cannot make the average uncertainty larger. So the gain is never negative.

When it applies. The formula assumes the answer we want is a class label, such as spam or not spam. For a number as the target, such as a price, a tree uses a different measure, and this formula does not apply directly.

An everyday picture

Think of a game of twenty questions. The best question splits the remaining candidates close to evenly, so whatever the answer, a lot of uncertainty goes away. A question whose answer you already know removes nothing. Information gain scores each possible question this way, and the tree asks the highest-scoring question first.

Worked example: One question on ten emails

A mail sorter has 10 emails: 6 are spam and 4 are not spam. A question, does the subject line contain the word free, splits them. The left child gets 5 emails, all spam. The right child gets the other 5 emails: 1 spam and 4 not spam. We measure how much the question removes of the uncertainty about spam.

Measure the uncertainty before the question. The 10 emails have 6 spam and 4 not spam, so the shares are $0.6$ and $0.4$ . The entropy is $H(\text{parent}) = -(0.6 \log_2 0.6 + 0.4 \log_2 0.4)$ . The base-2 logarithms are negative, with $\log_2 0.6 \approx -0.737$ and $\log_2 0.4 \approx -1.322$ , and the minus sign makes the total positive: about $0.971$ bits.
Measure the left child. It holds 5 spam emails and no others, so one share is $1$ and the other is $0$ . A share of 0 adds nothing, because the convention is that $0 \log_2 0 = 0$ . The left child has entropy $0$ bits, since it is pure. Its weight is $\frac{5}{10} = 0.5$ , because it holds half of the emails.
Measure the right child. It holds 5 emails: 1 spam and 4 not spam. Its shares are $0.2$ and $0.8$ , so $H = -(0.2 \log_2 0.2 + 0.8 \log_2 0.8) \approx 0.722$ bits. It is still mixed, which is why its entropy is not zero. Its weight is also $\frac{5}{10} = 0.5$ .
Average the children, using the weights. Each child has weight 0.5, so the weighted average is $0.5 \times 0 + 0.5 \times 0.722 \approx 0.361$ bits. Multiplying each child’s entropy by its weight makes the average reflect where the emails went, instead of treating both children as equal.
Subtract to get the gain. The gain is the parent’s entropy minus the weighted average: $\text{IG} = 0.971 - 0.361 \approx 0.610$ bits. The question removes about 0.61 bits of uncertainty about spam, and a tree prefers questions with a bigger number.
Compare the gain with the starting uncertainty. The question removes $\frac{0.610}{0.971} \approx 0.628$ , or about 63 percent, of the uncertainty the 10 emails started with. That is a large share, because the left child is pure and carries no uncertainty at all.

Answer: The question removes about 0.61 bits of uncertainty about spam. The left child is pure spam, and the right child is mostly not spam. A decision tree would compute this gain for every other question it could ask, then choose the question with the largest gain.

The numbers in this example are recomputed by script every time the site is built.

Common mistakes

Forgetting the weights. The child entropies must be averaged with the weights $\frac{n_k}{n}$ , not with a plain average over the children.
Leaving out the parent entropy. The gain is the drop from the parent’s entropy, so the children’s entropy alone does not tell you the gain.
Favoring questions with many answers. A question that splits examples into many small groups can score well without generalizing to new examples. The C4.5 algorithm corrects this with a measure called gain ratio, which divides the gain by a penalty for how many pieces the split creates.
Mixing log bases. Entropy in bits uses $\log_2$ . Using the natural log, $\ln$ , gives nats, which are a different unit, and nats and bits cannot be compared directly.

Where you will meet it

The ID3 and C4.5 decision tree algorithms, which choose splits by information gain. C4.5 uses a version called gain ratio that corrects for splits with many branches.
Feature selection, where input features are ranked by how much they tell us about the class. In that setting the same quantity is called mutual information.
Decision tree libraries with an entropy option, such as scikit-learn when its split criterion is set to entropy.

Questions people ask

Why use log base 2?

Because one bit is the uncertainty removed by one fair yes-or-no answer. Base 2 makes entropy count in bits, which is the natural unit for yes-or-no questions like these.

Can information gain be zero?

Yes. If the children have the same class mix as the parent, the weighted average equals the parent’s entropy, so the gain is 0. Such a split tells the tree nothing new.

How does it compare with Gini impurity?

Both measure how mixed a group is, and both are used to pick tree splits. Entropy is measured in bits, while Gini uses the squares of the shares. The two often choose the same split. The Gini impurity page on this site covers the other measure.

Is information gain only for decision trees?

No. The same quantity is called mutual information. It measures how much knowing one thing tells you about another, and it is used in feature selection and in communication.

Gini Impurity: Gini impurity is a score for how mixed the kinds of items are in one group, where 0 means every item in the group is the same kind.
Shannon Entropy: Shannon entropy is one number, measured in bits, that says how unpredictable a source of messages is on average: the more predictable it is, the fewer bits its messages need.
Kullback-Leibler Divergence: KL divergence is a score for how far a guessed set of chances is from the real set of chances: zero means the guess matches the truth, and bigger numbers mean a worse guess.