Information Theory for Machine Learning

Information theory, pioneered by Claude Shannon in 1948, is the mathematical study of quantifying, storing, and communicating data. In machine learning, it provides the fundamental tools to measure statistical uncertainty, quantify structural correlations, and design robust loss functions.

• Shannon Entropy ($H(X)$): Measures the average amount of uncertainty or 'surprise' in a random variable $X$. If an outcome is highly certain, its entropy is low; if it is completely random, its entropy is maximized. The formula for a discrete variable is:

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

Biased Coin Trace: Let's calculate and compare the entropy of a fair coin vs. a heavily biased coin:

- *Fair Coin:* $P(H) = 0.5, P(T) = 0.5$. The entropy is: $$H(X) = -(0.5 \log_2 0.5 + 0.5 \log_2 0.5) = -(0.5(-1) + 0.5(-1)) = 1.0 \text{ bit}$$ This represents maximum uncertainty—we have no prior bias about the toss.

- *Biased Coin:* $P(H) = 0.8, P(T) = 0.2$. The entropy is: $$H(X) = -(0.8 \log_2 0.8 + 0.8 \log_2 0.8) \approx -(0.8(-0.32) + 0.2(-2.32)) \approx 0.256 + 0.464 = 0.72 \text{ bits}$$ Because the coin is heavily biased, we are less 'surprised' by the outcomes on average, reducing our statistical entropy from $1.0$ down to $0.72$ bits!

• Joint Entropy ($H(X, Y)$): Measures the combined total uncertainty in a pair of random variables $X$ and $Y$ simultaneously: $$H(X, Y) = -\sum_{x} \sum_{y} P(x, y) \log_2 P(x, y)$$

• Conditional Entropy ($H(Y | X)$): Measures the remaining uncertainty of variable $Y$ given that we already know the exact value of variable $X$: $$H(Y | X) = -\sum_{x} \sum_{y} P(x, y) \log_2 P(y | x)$$

In machine learning, models output predicted probability distributions ($Q$) trying to approximate the true target distribution ($P$). We need to measure how much these two distributions differ.

• Kullback-Leibler (KL) Divergence ($D_{\text{KL}}(P \parallel Q)$): Measures the extra information/bits required to represent data using distribution $Q$ instead of the true distribution $P$. It acts as an asymmetric distance measure ($D_{\text{KL}}(P \parallel Q) \neq D_{\text{KL}}(Q \parallel P)$): $$D_{\text{KL}}(P \parallel Q) = \sum_{x \in \mathcal{X}} P(x) \log \frac{P(x)}{Q(x)}$$

• Cross-Entropy ($H(P, Q)$): Measures the average bits needed to encode symbols from true distribution $P$ using code model $Q$. It is mathematically equal to the sum of the true distribution's entropy and the KL divergence: $$H(P, Q) = H(P) + D_{\text{KL}}(P \parallel Q) = -\sum_{x \in \mathcal{X}} P(x) \log Q(x)$$

Cross-Entropy Loss Calculation: Suppose we have a binary classification task. The true label of an image is $P = [1.0, 0.0]$ (it is $100\%$ a cat). Our neural network outputs a prediction $Q = [0.8, 0.2]$ (the model is $80\%$ confident it is a cat). Let's calculate the Cross-Entropy Loss (using natural logarithms): $$H(P, Q) = -\left( 1.0 \ln(0.8) + 0.0 \ln(0.2) \right) = -1.0 \times (-0.223) + 0 = 0.223 \text{ nats}$$ If our model was less confident (e.g. $Q = [0.5, 0.5]$), the loss would rise to $-\ln(0.5) = 0.693$ nats. In deep classification networks, minimizing the cross-entropy loss function is mathematically equivalent to minimizing the KL divergence, forcing our predictions $Q$ to match true targets $P$!

Information theory also guides how classical algorithms build models, such as Decision Trees.

When a Decision Tree decides which feature column to split on, it chooses the feature that decreases dataset entropy the most. This reduction in entropy is called Information Gain (IG). High Information Gain means the resulting child split partitions are highly homogeneous (pure) compared to the unsplit parent dataset: $$\text{IG}(T, a) = H(T) - H(T | a)$$