What is the range of information gain ratio?

Question

I am wondering what the value range of information gain ratio is. I guess it is [0,1] but am not too sure about it.

Answer 1

tl;dr
Intuitively, the information gain ratio is the ratio between the mutual information of two random variables and the entropy of one of them. Thus, it is guaranteed to be in $[0,1]$ (except for the case in which it is undefined).


In the context of decision trees, let's denote:

• $Ex$ is the set of training examples
• $X$ is a randomly chosen example in $Ex$
• $a$ is some feature
• $A$ is the value of $a$ of $X$
• $C$ is the class of $X$
• $IG(Ex,a)$ is the information gain for splitting according to $a$
• $IV(Ex,a)$ is the information value (aka intrinsic value) of $a$
• $IGR(Ex,a)$ is the information gain ratio for splitting according to $a$
• $H(Y)$ is the entropy of $Y$ (for any random variable $Y$)
• $I(Y;Z)$ is the mutual information of $Y$ and $Z$ (for any two random variables $Y,Z$)

Then, by definition:

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

$IV(Ex,a)=H(A)$

$IGR(Ex,a)=\frac{IG(Ex,a)}{IV(Ex,a)}$

Thus:

$IGR(Ex,a)=\frac{H(C)-H(C|A)}{H(A)}$

First, if $H(A)=0$, then $IGR(Ex,a)$ is undefined. An example for such case is when $A$ is constant.

Now, let's assume that $H(A) \ne 0$.

As wikipedia mentions:

$I(C;A)=H(C)-H(C|A)$ and $I(A;C)=H(A)-H(A|C)$.

From the definition of mutual information, we can deduce that it's symmetric.

Thus, $H(C)-H(C|A)=I(C;A)=I(A;C)=H(A)-H(A|C)$

Therefore:

$IGR(Ex,a)=\frac{H(A)-H(A|C)}{H(A)}=1-\frac{H(A|C)}{H(A)}\le 1$
(The $\le 1$ is given by the non-negativity of entropy.)

We can also show that $IGR(Ex,a) \ge 0$, as explained here, and so it holds that $0 \le IGR(Ex,a) \le 1$.