Entropy, Cross-entropy, KL divergence and Beyond

As a reminder, entropy represents the level of uncertainty/randomness in the data or unpredictability associated with a random variable drawn from some distribution. That is, it shows how mixed or varied the data is, high entropy values means high uncertainty and very hard to predict, while low entropy means low uncertainty. Mathematically information entropy is calculated as:

$$H(X) = -\sum_{i=1}^n p_i \log_2(p_i) \tag{1}$$

where $n$ is the number of classes, and $p_i$ is the probability of class $i$.

The uniform distribution has the highest entropy since all outcomes are equally likely, in this case, the entropy is:

$$H(X) = -\sum_{i=1}^n \frac{1}{n} \log_2(\frac{1}{n}) \tag{2}$$ $$= \log_2(n)$$

Lets go through an example to solidify the concept. Let's assume we had a hypothetical country of 6 people from 2 tribes. Without any split, the entropy would be:

$$-(\frac{3}{6} \log_2(\frac{3}{6}) + \frac{3}{6} \log_2(\frac{3}{6})) = 1$$

However, with that split, the right side after the split with two people would have entropy of 0, and left side would have entropy of :

$$-(\frac{1}{4} \log_2(\frac{1}{4}) + \frac{3}{4} \log_2(\frac{3}{4})) \approx 0.811$$

The weighted entropy for both sides would be:

$$(\frac{2}{6} \times 0) + (\frac{4}{6} \times 0.811) \approx 0.541$$ $$= 1 - 0.541 \approx 0.459$$

Entropy variations

Cross-Entropy

Cross-entropy extends the idea of entropy when there exists two distributions (actual observed distribution and predicted data distribution). It is mostly useful in tracking the training loss of classification ML models. Mathematically, if the actual is ($P$) and predicted ($Q$), then each cross-entropy:

$$H_{ce}(P,Q) = -\sum_{i=1}^{n} P_i \log_2 Q_i \tag{3}$$

With our six people example in the previous section, let's assume we had a road and some ML algorithm to predict who has pass the road among the six people. Hence assuming the two probability distributions for each road:

$$\begin{array}{cc} \text{Actual probabilities } (P) & \text{Predicted probabilities } (Q) \\ \hline 0.3 & 0.1 \\ 0.2 & 0.05 \\ 0.15 & 0.15 \\ 0.15 & 0.2 \\ 0.1 & 0.25 \\ 0.1 & 0.25 \end{array}$$

The cross-entropy for the two distribution would be:

$$H_{ce}(P,Q) = -(0.3\log_2 0.1 + 0.2\log_2 0.05 + 0.15\log_2 0.15 + 0.15\log_2 0.2 + 0.1\log_2 0.25 + 0.1\log_2 0.25)$$ $$\approx 3.26$$

However if the probability distribution between the Actual and predicted were similar as:

$$\begin{array}{cc} \text{Actual probabilities } (P) & \text{Predicted probabilities } (Q) \\ \hline 0.3 & 0.28 \\ 0.2 & 0.22 \\ 0.15 & 0.14 \\ 0.15 & 0.16 \\ 0.1 & 0.11 \\ 0.1 & 0.09 \end{array}$$

The cross-entropy would be:

$$H_{ce}(P,Q) = -(0.3\log_2 0.28 + 0.2\log_2 0.22 + 0.15\log_2 0.14 + 0.15\log_2 0.16 + 0.1\log_2 0.11 + 0.1\log_2 0.09)$$ $$\approx 2.38$$

Joint Entropy

Consider selecting a number in the of range of 1 to 12 $n \in \{1, \dots, 12\}$. Let $X(n)$ be 1 if n is even, and $Y(n)$ be 1 if n is divisible by 3.

$$\begin{array}{cccccccccccc} \text{Number} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \hline X & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ Y & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \end{array}$$

Since $(X=0, Y=0)$ occurs at $n \in \{1, 5, 7, 11\}$, $(X=0, Y=1)$ occurs at $n \in \{3, 6\}$, $(X=1, Y=0)$ occurs at $n \in \{2, 4, 8, 10\}$, and $(X=1, Y=1)$ occurs at $n \in \{6, 12\}$. We can summarize the joint distribution of $X$ and $Y$ as:

$$\begin{array}{ccc} P(X, Y) & Y=0 & Y=1 \\ \hline X=0 & \frac{4}{12} & \frac{2}{12} \\ X=1 & \frac{4}{12} & \frac{2}{12} \\ \end{array}$$

And our joint entropy would be:

$$= -\left(\frac{4}{12}\log_2 \frac{4}{12} + \frac{2}{12}\log_2 \frac{2}{12} + \frac{4}{12}\log_2 \frac{4}{12} + \frac{2}{12}\log_2 \frac{2}{12}\right)$$ $$\approx 1.918$$

Joint entropy is a measure of the total uncertainty associated with a set of random variables.Therefore we can represent it a formula as used above is:

$$H(X, Y) = - \sum_{x \in \mathcal{X}} \sum_{y \in \mathcal{Y}} P(x, y) \log_2 P(x, y) \tag{4}$$

OR

$$H(X, Y) = - \sum_{x, y} P(x, y) \log_2 P(x, y) \tag{5}$$

Perplexity

This is a measure of predictability. The lowest perplexity is 1, which means the outcome is certain. Higher perplexity values indicate more uncertainty. It is calculated as:

$$Perplexity(P) = 2^{H_{ce}(P)} \tag{6}$$

Kullback-Leibler (KL) Divergence

KL divergence is an extension of cross-entropy for statistical comparison of two probability distributions. It solves the inherent uncertainity problem in cross-entropy since $H(P,P) = H(P)$. This is because cross-entropy satisfies $H(P,Q)=H(P)+D_{\mathrm{KL}}(P||Q) \quad \text{and} \quad H(P,P)=H(P)>0$ in general, it does not vanish even when $(Q=P)$. Hence KL divergence subtracts the entropy of the actual distribution from the cross-entropy resulting in:

$$D_{KL}(P,Q) = H_{ce}(P,Q) - H(P) \tag{7}$$ $$= -\left(\sum_{j=1}^{n} p_j \log_2 q_j - \sum_{j=1}^{n} p_j \log_2 p_j\right) \tag{8}$$

Mutual Information

Mutual information is very similar to KL divergence; the main difference is that while KL divergence compares how similar two distributions are, mutual information measures the dependency between two random variables by calculating the KL divergence between their joint distribution $P(X, Y)$ and the product of their marginals $P(X)P(Y)$ which is calculated as:

$$I(X; Y) = \sum_{x \in \mathcal{X}} \sum_{y \in \mathcal{Y}} p(x, y) \log \left( \frac{p(x, y)}{p(x)p(y)} \right) \tag{9}$$

With another representation as:

$$I(X; Y) = H(X,Y) - H(X/Y) - H(Y/X) \tag{10}$$ $$= H(X) + H(Y) - H(X,Y) \tag{11}$$

Reconsider the joint entropy example above with $X$ and $Y$. First the conditional distributions $P(Y/X)$ normalizing each row:

$$\begin{array}{ccc} P(Y/X) & Y=0 & Y=1 \\ \hline X=0 & \frac{4/12}{6/12} = \frac{2}{3} & \frac{2/12}{6/12} = \frac{ 1}{3} \\ X=1 & \frac{4/12}{6/12} = \frac{2}{3} & \frac{2/12}{6/12} = \frac{1}{3} \\ \end{array}$$

Then calculating the conditional entropy $H(Y/X)$:

$$= -\left(\frac{2}{3}\log_2 \frac{2}{3} + \frac{1}{3}\log_2 \frac{1}{3} + \frac{2}{3}\log_2 \frac{2}{3} + \frac{1}{3}\log_2 \frac{1}{3}\right)$$ $$\approx 0.918$$

Hence the mutual information between $X$ and $Y$ would be:

$$I(X; Y) = H(X) - H(Y/X)$$ $$= 1 - 0.918$$ $$= 0.082$$

And we can verify joint entropy with the mutual information formula as:

$$H(X,Y) = H(X) + H(Y) - I(X; Y) \tag{12}$$ $$= 1 + 1 - 0.082 = 1.918$$

Conclusion

Understanding these concepts is crucial since all the machine learning algorithms are based on the idea of minimizing some form of a loss function which is often a variation of the above concepts.