Information gain (decision tree)

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Information gain" decision tree – news · newspapers · books · scholar · JSTOR (December 2009) (Learn how and when to remove this message)

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 ${\displaystyle X}$ obtained from an observation of a random variable ${\displaystyle A}$ taking value ${\displaystyle A=a}$ is defined as:

$${\displaystyle IG_{X,A}{(X,a)}=D_{\text{KL}}{\left(P_{X}{(x|a)}\|P_{X}{(x|I)}\right)}}$$

i.e. the Kullback–Leibler divergence of ${\displaystyle P_{X}{(x|I)}}$ (the prior distribution for ${\displaystyle x}$) from ${\displaystyle P_{X|A}{(x|a)}}$ (the posterior distribution for ${\displaystyle x}$ given ${\displaystyle a}$).

The expected value of the information gain is the mutual information ⁠${\displaystyle I(X;A)}$⁠ of ${\displaystyle X}$ and ${\displaystyle A}$ – i.e. the reduction in the entropy of ${\displaystyle X}$ achieved by learning the state of the random variable ${\displaystyle 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 when applied in the area of machine learning is known as decision tree learning. Usually an attribute with high mutual information should be preferred to other attributes.^[why?]