Information Theory for Machine Learning

Claude Shannon introduced information theory in 1948 to measure how much information a message carries and how efficiently it can be stored or communicated. In machine learning, the same ideas help us describe uncertainty, measure relationships between variables, and build 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 a classification tree partitions labeled data. At a node containing sample set $T$, the tree considers candidate rules $a$, such as $x_j \leq \tau$ for a numerical feature or membership in a category. Each rule sends samples into child subsets $T_v$. A node is pure when nearly all of its samples share one class; its entropy is then close to zero.

For class proportions $p_c$ in node $T$, node entropy is $$H(T)=-\sum_c p_c\log_2 p_c.$$ The uncertainty remaining after candidate split $a$ is the size-weighted average of the child entropies: $$H(T\mid a)=\sum_v\frac{|T_v|}{|T|}H(T_v).$$ Weighting matters because a tiny pure child should not outweigh a large, still-mixed child.

Information Gain is the entropy removed by the split: $$\operatorname{IG}(T,a)=H(T)-H(T\mid a).$$ The training algorithm evaluates the available features and thresholds and greedily selects the candidate with the largest gain. This is a locally best choice at the current node; it does not guarantee the globally smallest or most accurate possible tree.

The same search repeats recursively inside each child. Growth stops when a node is pure, no candidate improves the criterion, or a rule such as max_depth, min_samples_split, min_samples_leaf, or a minimum impurity decrease is reached. An unrestricted tree can memorize noise. Pre-pruning limits growth, while post-pruning removes weak branches after construction, usually with validation data or a complexity penalty. Unit 13 places these mechanics in the broader supervised-learning workflow.