<p>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$ </p>

<p>$I(X; Y) = H(X) + H(Y) - H(X; Y)$</p>

<p>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):</p>

<p>$\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}$</p>

CC BY-SA 3.0
2013-11-25T14:53:37.917Z
@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 ;-)
Massimo Cafaro
CC BY-SA 3.0
2013-11-25T17:31:21.703Z
Sorry - didn't get a chance to check this again until today :)
lafuzz
CC BY-SA 3.0
2013-11-24T19:59:23.937Z
2013-11-24T19:59:23.937Z
Massimo Cafaro
<p>I'm reading through a paper on feature selection: <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.231.7844&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">Feature Selection Based on Mutual Information: Criteria of Max-Dependency, Max-Relevance,and in-Redundancy
</a> 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). </p>

<p>I don't follow how they derive the equality for minimal redundancy...</p>

<p><img src="https://i.sstatic.net/iXTy6.gif" alt="step 3"></p>

<p>... from ... </p>

<p><img src="https://i.sstatic.net/9o2T9.gif" alt="step 2"></p>

<p>... and ...</p>

<p><img src="https://i.sstatic.net/69FQY.gif" alt="enter image description here"></p>

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

<p>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? </p>

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

<machine-learning><it.information-theory>
Mutual information and entropy to prove minimal Relevance Maximum Dependency
lafuzz
# Mutual information and entropy to prove minimal Relevance Maximum Dependency

(Asked by: username_0 on 2013-11-23)

I'm reading through a paper on feature selection: [Feature Selection Based on Mutual Information: Criteria of Max-Dependency, Max-Relevance,and in-Redundancy](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.231.7844&rep=rep1&type=pdf) 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](https://i.sstatic.net/iXTy6.gif)

... from ...

![step 2](https://i.sstatic.net/9o2T9.gif)

... and ...

![enter image description here](https://i.sstatic.net/69FQY.gif)

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

**Tags:** machine-learning, it.information-theory


---

## 1 answers

### Answer by username_1 on 2013-11-24. Score: 1 | Accepted answer

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

> **Comments:**
> **username_1**: @username_0, 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 ;-)  
> **username_0**: Sorry - didn't get a chance to check this again until today :)  

---

