Appendix A: Kullback-Leibler (KL) divergence

The KL-divergence between two distributions $P$ and $Q$ is defined as

$$KL(P\vert\vert Q)\stackrel{\triangle}{=}\sum_i P_i log \frac{P_i}{Q_i} =-\sum_i P_i log Q_i-(-\sum_i P_i log P_i)=H(P,Q)-H(P)$$

where $H(P)$ is the entropy of distribution $P$, $H(P,Q)$ is the cross-entropy of distributions $P$ and $Q$, and their difference, also called relative entropy, represents the divergence or difference between the two distributions. According Gibbs' inequality, $H(P,Q)\ge H(P)$, with the equality holds $H(P,Q)=H(P)$ if and only if $Q=P$. Therefore $KL(P\vert\vert Q) \ge 0$.