Information gain (decision tree)

In the context of decision trees in information theory and machine learning, information gain refers to 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. (In broader contexts, information gain can also be used as a synonym for either Kullback–Leibler divergence or mutual information, but the focus of this article is on the more narrow meaning below.)

Explicitly, the information gain of a random variable ${\displaystyle X}$ obtained from an observation of a random variable ${\displaystyle A}$ taking value ${\displaystyle a}$ is defined as:

$${\displaystyle {\mathit {IG}}(X,a)=D_{\text{KL}}{\bigl (}P_{X\mid a}\parallel P_{X}{\bigr )}}$$

In other words, it is the Kullback–Leibler divergence of ${\displaystyle P_{X}(x)}$ (the prior distribution for ${\displaystyle X}$) from ${\displaystyle P_{X\mid a}(x)}$ (the posterior distribution for ${\displaystyle X}$ given ${\displaystyle A=a}$).

The expected value of the information gain is the mutual information ${\displaystyle I(X;A)}$:

$${\displaystyle \operatorname {E} _{A}[{\mathit {IG}}(X,A)]=I(X;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.