5
$\begingroup$

I'm going through "Elements of Information Theory" by Cover and Thomas and there the conditional entropy is proven to be equal to: \begin{align}H(Y\mid X)=-\sum_{x\in\mathcal{X}} \sum_{y\in\mathcal{Y}} p(x,y) \log_2p(y \mid x).\end{align}

Another well known formula is the formula for mutual information: \begin{align}I(X;Y)&=\sum_{x\in\mathcal{X}} \sum_{y\in\mathcal{Y}} p(x,y)\log_2\frac{p(x,y)}{p(x)p(y)} \\ &=E_{p(x,y)}\log_2\frac{p(X,Y)}{p(X)p(Y)} \\ &=D_{KL}(p(x,y)\parallel p(x)p(y)).\end{align}

Following the same reasoning I thought that we could also write (since $p(y\mid x)=p(x,y)/p(x)$): \begin{align}H(Y\mid X)&=-\sum_{x\in\mathcal{X}} \sum_{y\in\mathcal{Y}} p(x,y) \log_2 \frac{p(x,y)}{p(x)}\\ &=-E_{p(x,y)}\log_2\frac{p(X,Y)}{p(X)}\\ &=-D_{KL}(p(x,y)\parallel p(x)).\end{align}

Is my reasoning correct?

I can't seem to find that equality listed anywhere. Wikipedia lists a couple of other identities which relate Kullback-Libler divergence and conditional entropy, but no mention of this, so I suspect that I am mistaken somewhere.

$\endgroup$
3
  • $\begingroup$ Related, almost duplicate: Does it make sense to calculate the KL-divergence between a joint distribution and a marginal distribution? $\endgroup$
    – leonbloy
    Apr 6, 2017 at 21:59
  • $\begingroup$ @leonbloy Correct me if I'm wrong, but In the answer to that question you seem to confirm that this equality holds, i.e. there is no problem with KL distance not being defined as $p(A)$ isn't a distribution, however here in the comments to Stelios answer you confirmed that it isn't a valid distribution so KL distance isn't defined. Which reasoning is true? $\endgroup$
    – Blaza
    Apr 6, 2017 at 22:35
  • $\begingroup$ well, that's embarrasing... ;-) My comment here is (I think) right, I'll update the other answer. $\endgroup$
    – leonbloy
    Apr 6, 2017 at 22:44

2 Answers 2

4
$\begingroup$

The last equality in your derivation is not correct. Note that the KL divergence $D_\text{KL}(p\|q)$ is only meaningful when the two distributions involved, $p$ and $q$, are defined over the same space. A quantity such as $D_\text{KL}(p(x,y)\|p(x))$ makes no sense as it involves the pdf $p(x,y)$, which is defined over $\mathcal{X}\times \mathcal{Y}$, and the pdf $p(x)$, which is defined over $\mathcal{X}$.

$\endgroup$
2
  • $\begingroup$ Oh, right, I was being careless. I thought that we could just see $p(x)$ as a function on $\mathcal{X}\times \mathcal{Y}$ which ignores the second argument, so the expectation result holds, but it isn't a distribution over that set. Thanks for the answer! $\endgroup$
    – Blaza
    Apr 6, 2017 at 16:57
  • 1
    $\begingroup$ Of course, one might object that one still could thought the function $p(x)$ as defined in $\mathcal{X}\times \mathcal{Y}$, only that it does not depend on the variable $y$ (same as , say, $g(x,y)=x^2$ is a valid function over the $x-y$ plane). But then $p(x)$ would not sum up to $1$, hence it would not be a valid probability function - which is required by the definition of Kullback-Libler divergence. $\endgroup$
    – leonbloy
    Apr 6, 2017 at 21:59
2
$\begingroup$

Your proposal immediately has to be false since conditional Shannon entropy is nonnegative and so is KL divergence. So you can't expect one to nontrivially be the negative of the other. You have also misidentified the last line as a KL divergence when it is not. This is fixable by factoring out a distribution: say $\mathcal{Y}$ is finite alphabet and $q$ is some distribution on $\mathcal{Y}.$ Now:

\begin{align} H(Y\mid X)&=-\sum_{x\in\mathcal{X}} \sum_{y\in\mathcal{Y}} p(x,y) \log \frac{p(x,y)}{p(x)}\\ &=-\mathbb{E}_{(X,Y)\sim p(x,y)}\left[\log\frac{p(X,Y)}{p(X)}\right]\\ &= -\mathbb{E}_{(X,Y)\sim p(x,y)}\left[\log q(Y) + \log \frac{p(X,Y)}{p(X)q(Y)}\right]\\ &=H(p,q)-D(p(x,y)\| p(x)q(y)). \end{align}

You can reasonably make sense of this formula if you know how cross entropy $H(p,q)$ (and KL divergence) are related to how many (and how many more) bits it takes to encode a source pretending it was from distribution $q$ when really it was from distribution $p$.

Going another direction, $H(Y|X)=\mathbb{E}_{X\sim p(x)}[D(\mathbf{1}_{\{y_1=y_2\}}p(y_1|X=x)\|p(y_1|X=x)p(y_2|X=x))]$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .