Relative Entropy (or KL divergence)

Sources:

1. Elements of Information Theory
2. An Introduction to Single-User Information Theory

Definition

The relative entropy (or Kullback-Leibler divergence) $\mathrm{D}(p||q)$ measures the difference between the true distribution $p$ and the model distribution $q$ (typically a neural network). It's defined as:

The relative entropy (or Kullback-Leibler divergence, KL divergence) $\mathrm{KL}(p||q)$ is a 'measure' of the distance between the true distribution $p$ and the model distribution, e.g., a neural network, $q$. It's defined as: $$\begin{array}{rl}\mathrm{KL}(p\Vert q)& =\sum _{x\in \mathcal{X}}p(x)\log \frac{p(x)}{q(x)}\\ & ={\mathbb{E}}_{x\sim p}[\log \frac{p(x)}{q(x)}]\end{array}$$ where $\mathcal{X}$ is the sample space of r.v. $X$.

In the above definition, we use the convention that:

1. $0\log \frac{0}{0}=0$ and the convention (based on continuity arguments) that
2. $0\log \frac{0}{q}=0$ and $p\log \frac{p}{0}=\mathrm{\infty }$. Thus, if there is any symbol $x\in \mathcal{X}$ such that $p(x)>0$ and $q(x)=0$, then $D(p\Vert q)=\mathrm{\infty }$.

You may see some people use these symbols to represent relative entropy. They are interchangeable. $$D(p|q),\mathrm{KL}(p|q),{\mathrm{D}}_{\mathrm{KL}}(p|q),\cdots$$

Properties of Relative Entropy

1. In general, relative entropy is asymmetric $(D(p\Vert q)\ne D(q\Vert p))$, and does not satisfy the triangle inequality. Therefore, it is not a metric.
2. $D(p\Vert p)=0$.
3. $D(p\Vert q)\ge 0$ for all distributions $p,q$ with equality holding iff $p=q$.
4. $D(p(y\mid x)\Vert q(y\mid x))\ge 0$ with equality if and only if $p(y\mid x)=q(y\mid x)$ for all $y$ and $x$ such that $p(x)>0$.

Property (3) is proved using Jensen’s inequality.

Property (4) is proved using property (3).

Relative Entropy is Not Symmetric

In the following problem and solution, we give an counterexample of relative entropy's symmericity.

Relative entropy is not symmetric. Let the random variable $X$ have three possible outcomes $\{a,b,c\}$. Consider two distributions $p(x)$ and $q(x)$ on this random variable

Symbol	$p(x)$	$q(x)$
a	1/2	1/3
b	1/4	1/3
c	1/4	1/3

Calculate $H(p),H(q),D(p\Vert q)$ and $D(q\Vert p)$. Verify that in this case $D(p\Vert q)\ne D(q\Vert p)$. Solution: $$\begin{array}{rl}H(p)& =\frac{1}{2}\log 2+\frac{1}{4}\log 4+\frac{1}{4}\log 4=1.5\mathrm{bits}\\ H(q)& =3\times \frac{1}{3}\log 3=1.58496\mathrm{bits}\\ D(p\Vert q)& =\frac{1}{2}\log \frac{3}{2}+\frac{1}{4}\log \frac{3}{4}+\frac{1}{4}\log \frac{3}{4}=\log 3-1.5=0.08496\mathrm{bits}\\ D(q\Vert p)& =\frac{1}{3}\log \frac{2}{3}+\frac{1}{3}\log \frac{4}{3}+\frac{1}{3}\log \frac{4}{3}=-\log 3+\frac{5}{3}=0.0817\mathrm{bits}\end{array}$$ It is clear that $D(p\Vert q)\ne D(q\Vert p)$.

Conditional Eelative Entropy

We define a conditional version of the relative entropy.

Definition: For joint probability mass functions $p(x,y)$ and $q(x,y)$, the conditional relative entropy $D(p(y\mid x)\Vert q(y\mid x))$ is the average of the relative entropies between the conditional probability mass functions $p(y\mid x)$ and $q(y\mid x)$ averaged over the probability mass function $p(x)$. More precisely, $$\begin{array}{rl}D(p(y\mid x)\Vert q(y\mid x))& =\sum _{x}p(x)\sum _{y}p(y\mid x)\log \frac{p(y\mid x)}{q(y\mid x)}\\ & =E_{p(x,y)}\log \frac{p(Y\mid X)}{q(Y\mid X)}.\end{array}$$

The notation for conditional relative entropy is not explicit since it omits mention of the distribution $p(x)$ of the conditioning random variable. However, it is normally understood from the context.

The relative entropy between two joint distributions on a pair of random variables can be expanded as the sum of a relative entropy and a conditional relative entropy.

For miltivariance Gaussian distributions

Suppose $p=\mathcal{N}({\mu }_1,{\mathrm{\Sigma }}_1)$ and $q=\mathcal{N}({\mu }_2,{\mathrm{\Sigma }}_2)$. Both are $n$=dimensoin multivariate Gaussian distributions.

Their relative entropy (or KL divergence) is: $$\mathrm{KL}(p\Vert q)=\frac{1}{2}[\log \frac{\left|{\mathrm{\Sigma }}_2\right|}{\left|{\mathrm{\Sigma }}_1\right|}-n+\mathrm{tr}\left\{{\mathrm{\Sigma }}_2^{-1}{\mathrm{\Sigma }}_1\right\}+{({\mu }_2-{\mu }_1)}^T{\mathrm{\Sigma }}_2^{-1}({\mu }_2-{\mu }_1)]$$