Information Theory: KL Divergence

2020-01-15 | Tech

Assume there are two hypotheses $𝐻 1$ and $𝐻 2$ , r.v. $𝑋$ ranged in alphabets ${𝑎 1, \dots 𝑎 𝑘}$ . Under hypothesis $𝐻 𝑖$ , $𝑋$ has pdf $𝑝 (𝑋 = 𝑎 𝑗 | 𝐻 𝑖) = 𝑝 𝑖 (𝑎 𝑗)$ . According to Law of Total Probability, we have:

$𝑝 (𝐻 𝑖 | 𝑎 𝑘) = 𝑝 (𝐻 𝑖) 𝑝 𝑖 (𝑎 𝑘) 𝑝 1 (𝑎 𝑘) 𝑝 (𝐻 1) + 𝑝 2 (𝑎 𝑘) 𝑝 (𝐻 2)$

The formula can be transformed into:

$l o g 𝑝 2 (𝑎 𝑘) 𝑝 1 (𝑎 𝑘) = l o g 𝑝 (𝐻 2 | 𝑎 𝑘) 𝑝 (𝐻 1 | 𝑎 𝑘) - l o g 𝑝 (𝐻 2) 𝑝 (𝐻 1)$

which implies that, $l o g 𝑝 2 (𝑎 𝑘) 𝑝 1 (𝑎 𝑘)$ equals the difference of log likelihood ratio before and after conditioning $𝑋 = 𝑎 𝑘$ . We define $l o g 𝑝 2 (𝑎 𝑘) 𝑝 1 (𝑎 𝑘)$ be the discrimination information for $𝐻 2$ over $𝐻 1$ , when $𝑋 = 𝑎 𝑘$ . The expectation of discrimination information is KL divergence, denoted as:

$𝐷 𝐾 𝐿 (𝑃 2 | | 𝑃 1) = \sum 𝑘 𝑝 2 (𝑎 𝑘) l o g 𝑝 2 (𝑎 𝑘) 𝑝 1 (𝑎 𝑘)$

which sometimes denoted as $𝐼 (𝑝 2, 𝑝 1; 𝑋)$ , or simply $𝐼 (𝑝 2, 𝑝 1)$ if without ambiguity.

KL Divergence can be interpreted as a measure of expected information for $𝑋$ gained after distribution shifted from $𝑝 1$ to $𝑝 2$ , where $𝑝 1$ and $𝑝 2$ regarded as prior and post-prior distributions.

Further we may define the (symmetrised) divergence between $𝑝 2$ and $𝑝 1$ :

$𝐽 (𝑝 2, 𝑝 1; 𝑋) = 𝐷 𝐾 𝐿 (𝑝 2 | | 𝑝 1) + 𝐷 𝐾 𝐿 (𝑝 1 | | 𝑝 2) = 𝐽 (𝑝 1, 𝑝 2; 𝑋)$

Divergence $𝐽 (𝑝 2, 𝑝 1)$ is a measure of difference between two distributions satisfying

$𝐽 (𝑝 1, 𝑝 2) \geq 0$ and equality holds iff $𝑝 1 = 𝑝 2$ ;
$𝐽 (𝑝 1, 𝑝 2) = 𝐽 (𝑝 2, 𝑝 1)$ .

but not triangle inequality, and thus $𝐽 (\cdot, \cdot)$ is not a distance function.

#Generalization

We may generalize the definition to continuous variables as:

$𝐷 𝐾 𝐿 (𝑝 2 | | 𝑝 1) = \int 𝑝 2 (𝑥) l o g 𝑝 2 (𝑥) 𝑝 1 (𝑥) 𝑑 𝑥$

or multivariate cases:

$𝐷 𝐾 𝐿 (𝑝 2 (⃗ 𝑥) | | 𝑝 1 (⃗ 𝑥)) = \int 𝑝 2 (⃗ 𝑥) l o g 𝑝 2 (⃗ 𝑥) 𝑝 1 (⃗ 𝑥) 𝑑 ⃗ 𝑥$

or further, conditional cases:

$𝐷 𝐾 𝐿 (𝑝 2 (𝑋 | 𝑌) | | 𝑝 1 (𝑋 | 𝑌)) = \int 𝑝 2 (𝑦) 𝑝 2 (𝑥 | 𝑦) l o g 𝑝 2 (𝑥 | 𝑦) 𝑝 1 (𝑥 | 𝑦) 𝑑 𝑥 𝑑 𝑦$

#Relation to Shannon Entropy

For a discrete variable $𝑋$ , with distribution $𝑝$ , we have:

$𝐻 (𝑋) = l o g 𝑛 - 𝐷 𝐾 𝐿 (𝑝 | | 𝑣)$

where $𝑛$ is number of values $𝑋$ can take on, and $𝑣$ is the uniform distribution on those values. The lemma suggests that $𝐷 𝐾 𝐿 (𝑝 | | 𝑣)$ measures the information difference between $𝑝$ and a totally chaotic “bottom distribution”. From the perspective of transmission, KL divergence equals the length of additional bits required to encode a message, when the distribution of source alphabets shifts from $𝑝$ to $𝑣$ .

For a continuous variable $𝑋$ ranged within a finite set of volume $𝐿$ , we have:

$𝐻 (𝑋) = l o g 𝐿 - 𝐷 𝐾 𝐿 (𝑝 | | 𝑣)$

where $𝑣$ is a uniform distribution over the range of $𝑋$ . The interpretation is similar to discrete cases.

#Relation to Mutual Information

We can observe that

$𝐼 (𝑋; 𝑌) = 𝐷 𝐾 𝐿 (𝑃 (𝑋 𝑌) | | 𝑃 (𝑋) 𝑃 (𝑌))$

which suggests mutual information $𝐼 (𝑋; 𝑌)$ is the information difference when distribution of $(𝑋, 𝑌)$ shifted from $𝑃 (𝑋) 𝑃 (𝑌)$ to $𝑃 (𝑋, 𝑌)$ , i.e., from independent to dependent.

#Additional Properties of KL Divergence

Addictivity Assume $𝑋, 𝑌$ are independent, and $𝑃 (𝑥, 𝑦) = 𝑃 1 (𝑥) 𝑃 2 (𝑦)$ , $𝑄$ likewisely. We have

$𝐷 𝐾 𝐿 (𝑃 (𝑋, 𝑌) | | 𝑄 (𝑋, 𝑌)) = \int 𝑃 (𝑥, 𝑦) l o g 𝑃 (𝑥, 𝑦) 𝑄 (𝑥, 𝑦) 𝑑 𝑥 𝑑 𝑦 = \int 𝑃 1 (𝑥) 𝑃 2 (𝑦) l o g 𝑃 1 (𝑥) 𝑃 2 (𝑦) 𝑄 1 (𝑥) 𝑄 2 (𝑦) 𝑑 𝑥 𝑑 𝑦 = \int 𝑃 1 (𝑥) l o g 𝑃 1 (𝑥) 𝑄 1 (𝑥) 𝑑 𝑥 + \int 𝑃 2 (𝑦) l o g 𝑃 2 (𝑦) 𝑄 2 (𝑦) 𝑑 𝑦 = 𝐷 𝐾 𝐿 (𝑃 1 | | 𝑄 1) + 𝐷 𝐾 𝐿 (𝑃 2 | | 𝑄 2)$

Convexity Assume $𝑝 1, 𝑝 2, 𝑞 1, 𝑞 2, 𝑝, 𝑞$ are distributions, $0 \leq 𝜆 \leq 1$ . We have

which can be derived from $l o g 𝑥 \leq 𝑥 - 1$ when $0 < 𝑥 < 1$ . Similarly we have

which can be derived from the convexity of $l o g (\cdot)$ . Further we have

which can be proved using the Log Sum Inequality.

Invariance Assume $𝑈 = 𝑔 (𝑋)$ , then $𝐷 𝐾 𝐿 (𝑝 (𝑋) | | 𝑞 (𝑋)) = 𝐷 𝐾 𝐿 (𝑝 (𝑈) | | 𝑞 (𝑈))$ , i.e., the form of KL divergence remains invariant under transforms. Mutual information, however, does not have such property.

Author: hsfzxjy.
Link: https://i.hsfzxjy.site/information-theory-kl-divergence/.
License: CC BY-NC-ND 4.0.
All rights reserved by the author.
Commercial use of this post in any form is NOT permitted.
Non-commercial use of this post should be attributed with this block of text.

Information Theory