24 Relative Entropy (Kullback-Leibler Divergence)

KL quantifies the distance between two probability distributions: Let $P$ and $Q$ be two probability distributions of a discrete random variable $X$:

$$D_{KL}(P\parallel Q)=\sum _{x\in {\mathcal{R}}_X}P(x)\log \left(\frac{P(x)}{Q(x)}\right)=\mathbb{E}\left[\log \left(\frac{P(X)}{Q(X)}\right)\right]$$

By convention :

• $0\log \frac{0}{Q}=0$
• $P\log \frac{P}{0}=\infty$ Properties:
• $D_{KL}(P\parallel Q)\ge 0$
• $D_{KL}(P\parallel Q)=0\text{if}P(x)=Q(x)$
• $\text{Not symmetric:}{D}_{KL}(P\parallel Q)\ne D_{KL}(Q\parallel P)$

Kullback-Leibler Divergence : Examples

For a binary random variable $X$ with range $R_X=\{0,1\}$, assume two distributions $P$ and $Q$ are defined as :

$$\begin{array}{rl}P(0)& =1-r,P(1)=r\\ Q(0)& =1-s,Q(1)=s\end{array}$$

KL Divergences :

$$\begin{array}{rl}{D}_{KL}(P\parallel Q)& =(1-r)\log \left(\frac{1-r}{1-s}\right)+r\log \left(\frac{r}{s}\right)\\ D_{KL}(Q\parallel P)& =(1-s)\log \left(\frac{1-s}{1-r}\right)+s\log \left(\frac{s}{r}\right)\end{array}$$