I'm reading through a paper on feature selection: Feature Selection Based on Mutual Information: Criteria of Max-Dependency, Max-Relevance,and in-Redundancy but I'm unable to understand parts of the proof presented in section 2.3 where they are using information theory to prove that Max-Dependency is equivalent to the algorithm they present (mRMR).

I don't follow how they derive the equality for minimal redundancy...

step 3

... from ...

step 2

... and ...

enter image description here

(There is a similar step for the maximal relevance term which I also don't grasp)

My best understanding of what they are doing is that the entropy for each individual feature is found in the summation of the H(x_i) terms, and then the mutual information between all features is subtracted out in the J term, and that this is done (some how) through the chain rule, and then collection of the mutual information terms?

I don't have a strong back ground in information theory - so this is mostly conjecture. Hopefully some one with a stronger information theoretic background could elucidate this. Thanks.


1 Answer 1


For the equations you are reporting, $J(S_m) = I(S_{m-1}; x_m)$, i.e. $J(S_m)$ is the mutual information between $S_{m-1}$ and $x_m$. Since for any two random variables $X$ and $Y$

$I(X; Y) = H(X) + H(Y) - H(X; Y)$

the equation follows directly from the definition of mutual information (the chain rule does not apply here, since there is no need to deal with conditional entropy):

$\begin{gathered} H({S_{m - 1}},{x_m}) = H({S_m}) \\ = \sum\limits_{i = 1}^m {H({x_i})} - J({S_m}) \\ = \sum\limits_{i = 1}^m {H({x_i})} - I({S_{m - 1}};{x_m}) \\ = \sum\limits_{i = 1}^m {H({x_i})} - (H({S_{m - 1}}) + H({x_i}) - H({S_{m - 1}},{x_m})) \\ = \sum\limits_{i = 1}^m {H({x_i})} - (\sum\limits_{i = 1}^m {H({x_i})} - H({S_{m - 1}},{x_m})) \\ = H({S_{m - 1}},{x_m}) \\ \end{gathered}$

  • $\begingroup$ @lafuzz, you should accept the answer (if it's correct of course, or explain why it's not correct), otherwise people will not waste the time to answer your questions next time ;-) $\endgroup$ Nov 25, 2013 at 14:53
  • $\begingroup$ Sorry - didn't get a chance to check this again until today :) $\endgroup$
    – lafuzz
    Nov 25, 2013 at 17:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.