mutual information for feature selection

Question

I'm having difficulty (again) understanding mutual information for feature selection.

Here's some R code:

library(infotheo)

#variables
response = c(0,0,0,0,0,0,0,1,0,1)
var_1 = c(1,2,3,4,5,6,7,10,9,10)
var_2 = c(1,2,3,4,5,6,7,8,9,10)

#case 1
mutinformation( var_1, response )
[1] 0.5004024

#case 2
mutinformation( var_2, response )
[1] 0.5004024

When a 10 appears in var_1 it always corresponds with a 1 in response, whereas in var_2 there's no relationship at all.

Question: Shouldn't var_1 have a higher mutual information with response than var_2?

Answer 1

I think that your confusion about the results comes from the same problem, which I had when I was studying the mutual information: you are trying to interpret results having in mind (a) the ability to predict one signal from another and (b) forgetting the statistical ingredient, which is always present in the mutual information calculations. In that sense the "mutual information" name is to some extent misleading, since you might think: OK, if I know one signal and can predict the other with 100% certainty, these signals should have highest mutual information. But this is not the case. Let me give you two examples to illustrate this claim.

1. Consider two signals $x_i$ and $y_i$ which have a functional dependence

$$y_i = \sin(x_i)$$

If you know $x_i$ you can predict $y_i$ with 100% certainty, but if you know $y_i$, you cannot find $x_i$ since the equation has infinite number of solutions. So, if mutual information was a measure of mutual dependence, it would have been non-symmetric: it would have given high value for mutual dependence $y(x)$ and low value for mutual dependence $x(y)$. But the mutual information is symmetric

$$I(x_i, y_i) = I(y_i, x_i)$$

and therefore is not a measure of how certain is dependence of one variable from the other.

2. Another example. Imagine two signals with a perfect functional dependence

$$y_i = x_i$$

where $x_i = \{0, 1\}$. First, assume that $x_i$ is distributed uniformly

$$p(x_i = 0) = \frac{1}{2}\ , \quad p(x_i = 1) = \frac{1}{2}$$

Then the joint distribution matrix will be

$$p(x_i, y_i) = \pmatrix{\frac{1}{2} & 0 \\ 0 & \frac{1}{2}}$$

and the mutual information will give you the highest value for all 2 by 2 probability matrices

$$I(x_i, y_i) = {\rm entropy}(x_i) = {\rm entropy}(y_i) = \log(2) \approx 0.693$$

which is exactly what you expect from mutual information even if you consider it as a measure of mutual dependence. But what if we take non-uniformly distributed random variable $x_i$?

$$p(x_i = 0) = \frac{1}{10}\ , \quad p(x_i = 1) = \frac{9}{10}$$

The joint probability matrix is then

$$\pmatrix{\frac{1}{10} & 0 \\ 0 & \frac{9}{10}}$$

and mutual information is

$$I(x_i,y_i) = \frac{1}{10} \log(10) + \frac{9}{10} \log \left( \frac{10}{9} \right) = {\rm entropy}(x_i) = {\rm entropy}(y_i) \approx 0.325$$

Notice that we still have a perfect prediction ability: given $x_i$ we know for sure the value of $y_i$ and vice versa. But the mutual information is much less now. What have happened? The answer again is simple: the mutual information is not a measure of mutual dependence, but the measure of mutual entropy. The entropy decreased, so did the mutual information.

That is why I personally dislike the name "mutual information" and prefer my own naming convention: mutual entropy. But I do understand where the name comes from - the entropy is indeed the measure of information, contained in the signal. In the first example $x_i$ had maximal entropy $\log(2)$ and was perfectly correlated with $y_i$, that is why their mutual entropy was also $\log(2)$. In the second example the perfect correlation remained, but the entropy of each signal decreased and their mutual entropy decreased also.

Finally, to the example from your question. Signal response has only two possible values, $0$ and $1$. Its entropy is

$$S(response) = \frac{8}{10} \log\left(\frac{10}{8}\right) + \frac{2}{10} \log\left(\frac{10}{2}\right) = 0.5004$$

The signals var_1 and var_2 are much richer and have higher entropies, but the mutual entropies $I(response, var_1)$ and $I(response, var_2)$ cannot be higher than entropies of each ingredient - they can share only what they have. So we should look if var_1 or var_2 can decrease the entropy of response. But this is not the case: from var_1 and var_2 we can always infer the value of response. That is why the mutual information values are the same in both cases and equal to the entropy of response.

I said that I dislike the term "mutual information", but I am not saying that it is wrong - it is just not very intuitive and the reasoning in terms of mutual information is not very intuitive also. Imagine that we have two transmitters: one transmitter is sending only 0's and 1's (response), the other is sending values from 1 to 10 (var_1 or var_2). The second transmitter can send much more information, than the first one (because the entropy of the signal is larger). But we say: imagine that they are sending the same message to some distant planet, just encode it differently. Then the second transmitter is sending a lot of extra (i.e. useless) information: when it is enough to send only value $0$, var_1 sends 8 different values - $1,2,3,4,5,6,7,9$. This is extra and not needed, but still we can reconstruct signal response from var_1. The same is for var_2 - we can reconstruct the signal response from var_2, only that var_2 uses even more useless information - it uses 2 different values - $8$ and $10$ in order to encode the value of 1. Still we can reconstruct the signal response, and that is why the mutual information values are the same and are equal to the value of entropy (information) of response.

P.S. I do acknowledge that some of my arguments are pure hand-waving.