## Cross Entropy and KL Divergence

As we saw in an earlier post, the entropy of a discrete probability distribution is defined to be

\[H(p)=H(p_1,p_2,\ldots,p_n)=-\sum_{i}p_i \log p_i.\]

Kullback and Leibler defined a similar measure now known as *KL divergence*. This measure quantifies how similar a probability distribution \(p\) is to a candidate distribution \(q\).

\[D_{\text{KL}}(p\ | q)=\sum_i p_i \log \frac{p_i}{q_i}.\]

\(D_\text{KL}\) is non-negative and zero if and only if \( p_i = q_i \) for all \(i\). However, it is important to note that it is not in general symmetric:

\[ D_{\text{KL}}(p| q) \neq D_{\text{KL}}(q| p).\]

Jonathon Shlens explains that KL Divergence can be interpreted as measuring the likelihood that samples represented by the empirical distribution \(p\) were generated by a fixed distribution \(q\). If \(D_{\text{KL}}(p| q)=0\), we can guarantee that \(p\) is generated by \(q\). As \(D_{\text{KL}}(p| q)\rightarrow\infty\), we can say that it is increasingly unlikely that \(p\) was generated by \(q\).

Algebraically, we can rewrite the definition as

\[ \begin{array}{rl} D_{\text{KL}}(p| q) &=\sum_i p_i \log \frac{p_i}{q_i} \\ &=\sum_i \left ( - p_i \log q_i + p_i \log p_i \right)\\ &=- \sum_i p_i \log q_i + \sum_i p_i \log p_i \\ &=- \sum_i p_i \log q_i - \sum_i p_i \log \frac{1}{p_i} \\ &=- \sum_i p_i \log q_i-H(p) \\ &=\sum_i p_i \log \frac{1}{q_i}-H(p)\\ \end{array} \]

KL Divergence breaks down as something that looks similar to entropy (but combining \(p\) and \(q\)) minus the entropy of \(p\). This first term is often called *cross entropy*:

\[H(p, q)=\sum_i p_i \log \frac{1}{q_i}.\]

We could alternatively use this relationship to define cross entropy as:

\[H(p, q)=H(p) + D_\text{KL}(p| q).\]

Intuatively, the cross entropy is the uncertainty implicit in \(H(p)\) plus the likelihood that \(p\) could have be generated by \(q\). If we consider \(p\) to be a fixed distribution, \(H(p, q)\) and \(D_\text{KL}(p | q)\) differ by a constant factor for all \(q\).