Information gain (decision tree)

Short description: Gain from observing another random variable

In information theory and machine learning, information gain is a synonym for Kullback–Leibler divergence; the amount of information gained about a random variable or signal from observing another random variable. However, in the context of decision trees, the term is sometimes used synonymously with mutual information, which is the conditional expected value of the Kullback–Leibler divergence of the univariate probability distribution of one variable from the conditional distribution of this variable given the other one.

The information gain of a random variable X obtained from an observation of a random variable A taking value [math]\displaystyle{ A=a }[/math] is defined[math]\displaystyle{ IG_{X, A}{(X,a)} = D_\text{KL}{\left(P_X{(x|a)} \| P_X{(x|I)}\right)}, }[/math] the Kullback–Leibler divergence of the prior distribution [math]\displaystyle{ P_{X}{(x|I)} }[/math] for x from the posterior distribution [math]\displaystyle{ P_{X|A}{(x|a)} }[/math] for x given a.

The expected value of the information gain is the mutual information [math]\displaystyle{ I(X; A) }[/math] of X and A – i.e. the reduction in the entropy of X achieved by learning the state of the random variable A.

In machine learning, this concept can be used to define a preferred sequence of attributes to investigate to most rapidly narrow down the state of X. Such a sequence (which depends on the outcome of the investigation of previous attributes at each stage) is called a decision tree and applied in the area of machine learning known as decision tree learning. Usually an attribute with high mutual information should be preferred to other attributes.

General definition

In general terms, the expected information gain is the reduction in information entropy Η from a prior state to a state that takes some information as given:

[math]\displaystyle{ IG(T,a) = \Eta{(T)} - \Eta{(T|a)}, }[/math]

where [math]\displaystyle{ \Eta{(T|a)} }[/math] is the conditional entropy of [math]\displaystyle{ T }[/math] given the value of attribute [math]\displaystyle{ a }[/math].

This is intuitively plausible when interpreting entropy Η as a measure of uncertainty of a random variable [math]\displaystyle{ T }[/math]: by learning (or assuming) [math]\displaystyle{ a }[/math] about [math]\displaystyle{ T }[/math], our uncertainty about [math]\displaystyle{ T }[/math] is reduced (i.e. [math]\displaystyle{ IG(T,a) }[/math] is positive), unless of course [math]\displaystyle{ T }[/math] is independent of [math]\displaystyle{ a }[/math], in which case [math]\displaystyle{ \Eta(T,a) = \Eta(T) }[/math], meaning [math]\displaystyle{ IG(T,a) = 0 }[/math].

Formal definition

Let T denote a set of training examples, each of the form [math]\displaystyle{ (\textbf{x},y) = (x_1, x_2, x_3, ..., x_k, y) }[/math] where [math]\displaystyle{ x_a\in \mathrm{vals}(a) }[/math] is the value of the [math]\displaystyle{ a^{\text{th}} }[/math] attribute or feature of example [math]\displaystyle{ \textbf{x} }[/math] and y is the corresponding class label. The information gain for an attribute a is defined in terms of Shannon entropy [math]\displaystyle{ \Eta( - ) }[/math] as follows. For a value v taken by attribute a, let [math]\displaystyle{ S_a{(v)} = \{\textbf{x}\in T|x_a=v\} }[/math]be defined as the set of training inputs of T for which attribute a is equal to v. Then the information gain of T for attribute a is the difference between the a priori Shannon entropy [math]\displaystyle{ \Eta(T) }[/math] of the training set and the conditional entropy [math]\displaystyle{ \Eta{(T|a)} }[/math].

[math]\displaystyle{ \Eta(T|a)= \sum_{v\in \mathrm{vals}(a)} {\frac{|S_a{(v)}|}{|T|} \cdot \Eta\left(S_a{\left(v\right)}\right)}. }[/math]

[math]\displaystyle{ IG(T,a) = \Eta(T) - \Eta(T|a) }[/math]

The mutual information is equal to the total entropy for an attribute if for each of the attribute values a unique classification can be made for the result attribute. In this case, the relative entropies subtracted from the total entropy are 0. In particular, the values [math]\displaystyle{ v \in vals(a) }[/math] defines a partition of the training set data T into mutually exclusive and all-inclusive subsets, inducing a categorical probability distribution [math]\displaystyle{ P_{a}{(v)} }[/math] on the values [math]\displaystyle{ v \in vals(a) }[/math] of attribute a. The distribution is given [math]\displaystyle{ P_{a}{(v)} := \frac{|S_a{(v)}|}{|T|} }[/math]. In this representation, the information gain of T given a can be defined as the difference between the unconditional Shannon entropy of T and the expected entropy of T conditioned on a, where the expectation value is taken with respect to the induced distribution on the values of a.[math]\displaystyle{ \begin{alignat}{2} IG(T,a) &= \Eta(T) - \sum_{v\in \mathrm{vals}(a)} {P_a{(v)} \Eta\left(S_a{(v)}\right)} \\ &= \Eta(T) - \mathbb{E}_{P_a}{\left[\Eta{(S_a{(v)})}\right]} \\ &= \Eta(T) - \Eta{(T|a)}. \end{alignat} }[/math]

Another Take on Information Gain, with Example

For a better understanding of information gain, let us break it down. As we know, information gain is the reduction in information entropy, what is entropy? Basically, entropy is the measure of impurity or uncertainty in a group of observations. In engineering applications, information is analogous to signal, and entropy is analogous to noise. It determines how a decision tree chooses to split data. The leftmost figure below is very impure and has high entropy corresponding to higher disorder and lower information value. As we go to the right, the entropy decreases, and the information value increases.

Entropy diagram

A simple decision tree

Now, it is clear that information gain is the measure of how much information a feature provides about a class. Let's visualize information gain in a decision tree as shown in the right:

The node t is the parent node, and the sub-nodes t_L and t_R are child nodes. In this case, the parent node t has a collection of cancer and non-cancer samples denoted as C and NC respectively. We can use information gain to determine how good the splitting of nodes is in a decision tree. In terms of entropy, information gain is defined as:

Gain = (Entropy of the parent node) – (average entropy of the child nodes)

(i)

To understand this idea, let's start by an example in which we create a simple dataset and want to see if gene mutations could be related to patients with cancer. Given four different gene mutations, as well as seven samples, the training set for a decision can be created as follows:

Samples	Mutation 1	Mutation 2	Mutation 3	Mutation 4
C1	1	1	1	0
C2	1	1	0	1
C3	1	0	1	1
C4	0	1	1	0
NC1	0	0	0	0
NC2	0	1	0	0
NC3	1	1	0	0

In this dataset, a 1 means the sample has the mutation (True), while a 0 means the sample does not (False). A sample with C denotes that it has been confirmed to be cancerous, while NC means it is non-cancerous. Using this data, a decision tree can be created with information gain used to determine the candidate splits for each node.

For the next step, the entropy at parent node t of the above simple decision tree is computed as:

H(t) = −[p_C,t log₂(p_C,t) + p_NC,t log₂(p_NC,t)]

where,

probability of selecting a class ‘C’ sample at node t, p_C,t = n(t, C) / n(t),

probability of selecting a class ‘NC’ sample at node t, p_NC,t = n(t, NC) / n(t),

n(t), n(t, C), and n(t, NC) are the number of total samples, ‘C’ samples and ‘NC’ samples at node t respectively.

Using this with the example training set, the process for finding information gain beginning with [math]\displaystyle{ \Eta{(t)} }[/math] for Mutation 1 is as follows:

p_{C, t} = 4/7

p_{NC, t} = 3/7

[math]\displaystyle{ \Eta{(t)} }[/math] = −(4/7 × log₂(4/7) + 3/7 × log₂(3/7)) = 0.985

Note: [math]\displaystyle{ \Eta{(t)} }[/math] will be the same for all mutations at the root.

The relatively high value of entropy [math]\displaystyle{ \Eta{(t)} = 0.985 }[/math] (1 is the optimal value) suggests that the root node is highly impure and the constituents of the input at the root node would look like the leftmost figure in the above Entropy Diagram. However, such a set of data is good for learning the attributes of the mutations used to split the node. At a certain node, when the homogeneity of the constituents of the input occurs (as shown in the rightmost figure in the above Entropy Diagram), the dataset would no longer be good for learning.

Moving on, the entropy at left and right child nodes of the above decision tree is computed using the formulae:

H(t_L) = −[p_C,L log₂(p_C,L) + p_NC,L log₂(p_NC,L)]

H(t_R) = −[p_C,R log₂(p_C,R) + p_NC,R log₂(p_NC,R)]

where,

probability of selecting a class ‘C’ sample at the left child node, p_C,L = n(t_L, C) / n(t_L),

probability of selecting a class ‘NC’ sample at the left child node, p_NC,L = n(t_L, NC) / n(t_L),

probability of selecting a class ‘C’ sample at the right child node, p_C,R = n(t_R, C) / n(t_R),

probability of selecting a class ‘NC’ sample at the right child node, p_NC,R = n(t_R, NC) / n(t_R),

n(t_L), n(t_L, C), and n(t_L, NC) are the total number of samples, ‘C’ samples and ‘NC’ samples at the left child node respectively,

n(t_R), n(t_R, C), and n(t_R, NC) are the total number of samples, ‘C’ samples and ‘NC’ samples at the right child node respectively.

Using these formulae, the H(t_L) and H(t_R) for Mutation 1 is shown below:

H(t_L) = −(3/4 × log₂(3/4) + 1/4 × log₂(1/4)) = 0.811

H(t_R) = −(1/3 × log₂(1/3) + 2/3 × log₂(2/3)) = 0.918

Following this, average entropy of the child nodes due to the split at node t of the above decision tree is computed as:

H(s,t) = P_LH(t_L) + P_RH(t_R)

where,

probability of samples at the left child, P_L = n(t_L) / n(t),

probability of samples at the right child, P_R = n(t_R) / n(t),

Finally, H(s,t) along with P_L and P_R for Mutation 1 is as follows:

P_L = 4/7

P_R = 3/7

H(s, t) = (4/7 × 0.811) + (3/7 × 0.918) = 0.857

Thus, by definition from equation (i):

(Information gain) = H(t) - H(s,t)

After all the steps, gain(s), where s is a candidate split for the example is:

gain(s) = 0.985 – 0.857 = 0.128

The newly created tree with the root node split based on Mutation 3. Mutation 3 had the highest information gain, so it was selected as the split.

Using this same set of formulae with the other three mutations leads to a table of the candidate splits, ranked by their information gain:

Mutation	Gain(s)
3	0.522
4	0.292
1	0.128
2	0.006

The mutation that provides the most useful information would be Mutation 3, so that will be used to split the root node of the decision tree. The root can be split and all the samples can be passed though and appended to the child nodes. A tree describing the split is shown on the left.

The samples that are on the left node of the tree would be classified as cancerous by the tree, while those on the right would be non-cancerous. This tree is relatively accurate at classifying the samples that were used to build it (which is a case of overfitting), but it would still classify sample C2 incorrectly. To remedy this, the tree can be split again at the child nodes to possibly achieve something even more accurate.

To split the right node, information gain must again be calculated for all the possible candidate splits that were not used for previous nodes. So, the only options this time are Mutations 1, 2, and 4.

Note: [math]\displaystyle{ \Eta{(t)} }[/math] is different this time around since there are only four samples at the right child.

P_{C, t} = 1/4

P_{NC, t} = 3/4

[math]\displaystyle{ \Eta{(t)} }[/math] = -(1/4 × log₂(1/4) + 3/4 × log₂(3/4)) = 0.811

The updated tree with the right child node split based on Mutation 4.

From this new [math]\displaystyle{ \Eta{(t)} }[/math], the candidate splits can be calculated using the same formulae as the root node:

Mutation	Gain(s)
4	0.811
1	0.311
2	0.123

Thus, the right child will be split with Mutation 4. All the samples that have the mutation will be passed to the left child and the ones that lack it will be passed to the right child.

To split the left node, the process would be the same, except there would only be 3 samples to check. Sometimes a node may not need to be split at all if it is a pure set, where all samples at the node are just cancerous or non-cancerous. Splitting the node may lead to the tree being more inaccurate and in this case it will not be split.

The tree would now achieve 100% accuracy if the samples that were used to build it are tested. This isn't a good idea, however, since the tree would overfit the data. The best course of action is to try testing the tree on other samples, of which are not part of the original set. Two outside samples are below:

Testing the decision tree with two new samples.

Samples	Mutation 1	Mutation 2	Mutation 3	Mutation 4
NC10	0	1	0	0
C15	1	1	0	0

By following the tree, NC10 was classified correctly, but C15 was classified as NC. For other samples, this tree would not be 100% accurate anymore. It could be possible to improve this though, with options such as increasing the depth of the tree or increasing the size of the training set.

Advantages

Information gain is the basic criterion to decide whether a feature should be used to split a node or not. The feature with the optimal split i.e., the highest value of information gain at a node of a decision tree is used as the feature for splitting the node.

The concept of information gain function falls under the C4.5 algorithm for generating the decision trees and selecting the optimal split for a decision tree node. Some of its advantages include:

• It can work with both continuous and discrete variables.
• Due to the factor –[p ∗ log(p)] in the entropy definition as given above, leaf nodes with a small number of instances are assigned less weight and it favors dividing rest of the data into bigger but homogeneous groups. And thus, as we dig deeper into the depth of the tree, the dataset becomes more homogeneous. This approach is usually more stable and chooses the most impactful features on the nodes.

Drawbacks and Solutions

Although information gain is usually a good measure for deciding the relevance of an attribute, it is not perfect. A notable problem occurs when information gain is applied to attributes that can take on a large number of distinct values. For example, suppose that one is building a decision tree for some data describing the customers of a business. Information gain is often used to decide which of the attributes are the most relevant, so they can be tested near the root of the tree. One of the input attributes might be the customer's membership number, if they are a member of the business's membership program. This attribute has a high mutual information, because it uniquely identifies each customer, but we do not want to include it in the decision tree. Deciding how to treat a customer based on their membership number is unlikely to generalize to customers we haven't seen before (overfitting). This issue can also occur if the samples that are being tested have multiple attributes with many distinct values. In this case, it can cause the information gain of each of these attributes to be much higher than those without as many distinct values.

To counter this problem, Ross Quinlan proposed to instead choose the attribute with highest information gain ratio from among the attributes whose information gain is average or higher. This biases the decision tree against considering attributes with a large number of distinct values, while not giving an unfair advantage to attributes with very low information value, as the information value is higher or equal to the information gain.

See also

• Information gain more broadly
• Decision tree learning
• Information content, the starting point of information theory and the basis of Shannon entropy
• Information gain ratio
• ID3 algorithm
  • C4.5 algorithm
• Surprisal analysis

Further reading

• Nowozin, Sebastion (2012-06-18). "Improved Information Gain Estimates for Decision Tree Induction". arXiv:1206.4620v1.
• Shouman, Mai (2011). "Using decision tree for diagnosing heart disease patients.". Proceedings of the Ninth Australasian Data Mining Conference 121: 23–30. https://crpit.scem.westernsydney.edu.au/confpapers/CRPITV121Shouman.pdf. 
• Mitchell, Tom M. (1997). Machine Learning. The Mc-Graw-Hill Companies, Inc.. ISBN 978-0070428072. https://www.cs.cmu.edu/~tom/mlbook.html.