Mutual information and entropy to prove minimal Relevance Maximum Dependency

Question

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...

... from ...

... and ...

(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.

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}$