Information gain in decision trees

In information theory and machine learning, information gain is an alternative synonym for Kullback–Leibler divergence.

In particular, the information gain about a random variable X obtained from an observation that a random variable A takes the value A=a is the Kullback-Leibler divergence D_KL( p(x|a) || p(x|I) ) of the prior distribution p(x|I) for x from the posterior distribution p(x|a) for x given a.

The expected value of the information gain is the mutual information I(X;A) 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. Usually an attribute with high information gain should be preferred to other attributes.

General definition

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

$IG(Ex,a) = H(Ex) - H(Ex|a)$

Formal definition

Let $Attr$ be the set of all attributes and $Ex$ the set of all training examples, $value(x,a)$ with $x\in Ex$ defines the value of a specific example $x$ for attribute $a\in Attr$, $H$ specifies the entropy, and $|x|$ is the number of elements in the set $x$. The information gain for an attribute $a\in Attr$ is defined as follows:

$IG(Ex,a) = H(Ex)-\sum_{v\in values(a)}\frac{|\{x\in Ex|value(x,a)=v\}|}{|Ex|} \cdot H(\{x\in Ex|value(x,a)=v\})$

The information gain 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.

Drawbacks

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 we are 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 credit card number. This attribute has a high information gain, 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 credit card number is unlikely to generalize to customers we haven't seen before (overfitting).

Information gain ratio is sometimes used instead. This biases the decision tree against considering attributes with a large number of distinct values. However, attributes with very low information values then appeared to receive an unfair advantage. In addition, methods such as permutation tests have been proposed to correct the bias.

Constructing a decision tree using information gain

A decision tree can be constructed top-down using the information gain in the following way:

1. begin at the root node
2. determine the attribute with the highest information gain which is not already used as an ancestor node
3. add a child node for each possible value of that attribute
4. attach all examples to the child node where the attribute values of the examples are identical to the attribute value attached to the node
5. if all examples attached to the child node can be classified uniquely add that classification to that node and mark it as leaf node
6. go back to step two if there are unused attributes left, otherwise add the classification of most of the examples attached to the child node

References

• [1] Mitchell, Tom M., Machine Learning. The Mc-Graw-Hill Companies, Inc., 1997