Machine Learning - Information Theory & Entropy

Information theory provides the mathematical foundation for evaluating uncertainty, loss functions, and probabilistic distance in machine learning.

Shannon Entropy

For a discrete random variable XX with alphabet X\mathcal{X} and probability mass function P(X=x)=p(x)P(X = x) = p(x):

H(X)=−∑x∈Xp(x)log⁡2p(x)=E[log⁡21p(x)]H(X) = - \sum_{x \in \mathcal{X}} p(x) \log_2 p(x) = \mathbb{E}\left[\log_2 \frac{1}{p(x)}\right]
  • Units: If the logarithm base is 22, entropy is measured in bits (or shannons). If using natural log ln⁡\ln, it is measured in nats.
  • Intuition: Quantifies the average amount of "surprise" or uncertainty in XX.
    • When p(x)=1p(x) = 1 for some outcome and 00 for all others, H(X)=0H(X) = 0 (complete certainty).
    • For a discrete variable with NN states, entropy is maximized when outcomes are equiprobable (p(x)=1Np(x) = \frac{1}{N}), yielding H(X)=log⁡2NH(X) = \log_2 N.

Binary Entropy Function

For a binary variable with parameter p∈[0,1]p \in [0, 1]:

Hb(p)=−plog⁡2p−(1−p)log⁡2(1−p)H_b(p) = - p \log_2 p - (1 - p) \log_2 (1 - p)

The maximum occurs at p=0.5p = 0.5 with Hb(0.5)=1.0 bitH_b(0.5) = 1.0\text{ bit}. As p→0p \to 0 or p→1p \to 1, Hb(p)→0H_b(p) \to 0.

Maximum Entropy Principle

The Principle of Maximum Entropy states that the probability distribution that best represents the current state of knowledge is the one with the largest entropy, subject to known constraints:

  1. Discrete with No Constraints: The Uniform Distribution maximizes entropy over a finite state space.
  2. Continuous on (−∞,∞)(-\infty, \infty) with Fixed Mean μ\mu and Variance σ2\sigma^2: The Gaussian (Normal) Distribution N(μ,σ2)\mathcal{N}(\mu, \sigma^2) is the unique distribution that maximizes differential entropy: h(X)=−∫−∞∞p(x)ln⁡p(x) dx=12ln⁡(2πeσ2)h(X) = -\int_{-\infty}^\infty p(x) \ln p(x) \, dx = \frac{1}{2} \ln(2\pi e \sigma^2)
  3. Continuous on [0,∞)[0, \infty) with Fixed Mean μ=1λ\mu = \frac{1}{\lambda}: The Exponential Distribution Exp(λ)\text{Exp}(\lambda) maximizes differential entropy.

Cross-Entropy & Kullback-Leibler (KL) Divergence

Cross-Entropy

Cross-entropy measures the average number of bits needed to encode data drawn from a true distribution PP using an estimated model distribution QQ:

H(P,Q)=−∑x∈XP(x)log⁡Q(x)=Ex∼P[−log⁡Q(x)]H(P, Q) = - \sum_{x \in \mathcal{X}} P(x) \log Q(x) = \mathbb{E}_{x \sim P}[-\log Q(x)]

In machine learning classification, minimizing cross-entropy loss is mathematically equivalent to maximizing the log-likelihood of the training data.

Relative Entropy (Kullback-Leibler Divergence)

The KL Divergence DKL(P∥Q)D_{\text{KL}}(P \parallel Q) quantifies the statistical divergence or information loss when approximating true distribution PP with model QQ:

DKL(P∥Q)=∑x∈XP(x)log⁡P(x)Q(x)=H(P,Q)−H(P)D_{\text{KL}}(P \parallel Q) = \sum_{x \in \mathcal{X}} P(x) \log \frac{P(x)}{Q(x)} = H(P, Q) - H(P)

Mathematical Properties

  1. Non-negativity (Gibbs' Inequality): DKL(P∥Q)≥0with equality if and only if P(x)=Q(x) for all xD_{\text{KL}}(P \parallel Q) \ge 0 \quad \text{with equality if and only if } P(x) = Q(x) \text{ for all } x
  2. Asymmetry: DKL(P∥Q)≠DKL(Q∥P)D_{\text{KL}}(P \parallel Q) \neq D_{\text{KL}}(Q \parallel P) Because it is asymmetric and violates the triangle inequality, KL divergence is a directed divergence rather than a formal distance metric.
  3. Relation to Optimization: Because the true distribution entropy H(P)H(P) is constant with respect to model parameters w\mathbf{w}, minimizing cross-entropy H(P,Qw)H(P, Q_{\mathbf{w}}) is strictly equivalent to minimizing DKL(P∥Qw)D_{\text{KL}}(P \parallel Q_{\mathbf{w}}).

Perplexity

In language modeling and sequence prediction, Perplexity (PPL) measures how well a probability model predicts an observed sample sequence:

PPL(P)=2H(P)=exp⁡(−1N∑i=1Nln⁡P(xi∣x1,…,xi−1))\text{PPL}(P) = 2^{H(P)} = \exp\left(-\frac{1}{N} \sum_{i=1}^N \ln P(x_i \mid x_1, \dots, x_{i-1})\right)
  • Perplexity can be interpreted as the effective branching factor of the model: a perplexity of KK means the model is as uncertain as choosing uniformly among KK possible tokens at each step.
  • Lower perplexity indicates superior predictive confidence.