Kullback–Leibler Divergence

The Kullback-Leibler (KL) Divergence (also called relative entropy), denoted $D_{\mathrm{KL}}(P\parallel Q)$, is a type of statistical distance, that is, a measure of how one probability distribution $P$ is different from a second, reference probability distribution $Q$. Mathematically, it is defined as

$$D_{\mathrm{KL}}(P\parallel Q)=\sum _{x\in \chi }P(x)\log \left(\frac{P(x)}{Q(x)}\right)$$

To intuitively understand the concept, imagine that we have to biased coins, where coin $A$ has probability $p_1$ for heads and $p_2$ for tails, coin $B$ has probability $q_1$ for heads and $q_2$ for tails. Now we want to know how similar these two coins are.

A straight-forward way to do this is to determine how easy one may confuse these two coins. On the other hand, this means to calculate the likelihood of the coins:

$$\mathrm{likelihood}=\frac{P(\mathrm{Observations}\mid \mathrm{coin}A)}{P(\mathrm{Observations}\mid \mathrm{coin}B)}$$

Suppose in a sequence of observations, we observed heads for $N_H$ times and tails for $N_T$ times, then the likelihood function would be

$$\text{likelihood}=\frac{p_1^{N_H}{p}_2^{N_T}}{q_1^{N_H}{q}_2^{N_T}}$$

Normalize the sample size by raising it to the power of $1$ and then take the log of the expression

$$\begin{array}{rl}\log {\left(\frac{p_1^{N_H}{p}_2^{N_T}}{q_1^{N_H}{q}_2^{N_T}}\right)}^{1/N}& =\frac{N_H}{N}\log p_1+\frac{N_T}{N}\log p_2-\frac{N_H}{N}\log q_1-\frac{N_T}{N}\log q_2\end{array}$$

Assume the observations are generalized by coin $A$, then $\frac{N_H}{N}\to p_1$ and $\frac{N_T}{N}\to p_2$ when $N\to \infty$, so we get

$$p_1\log \frac{p_1}{q_1}+p_2\log \frac{p_2}{q_2}$$

This is exactly the KL-divergence of the two coins' distributions. The closer to $0$ the divergence is, the more similar these two distributions are.