12.1 Self-Information, Entropy, and Coding: How Uncertainty Becomes Bits

Two log messages of the same length can be very different surprises if one appears daily and the other once a year. Information theory measures uncertainty through a probability model. This lesson uses finite discrete outcome sets; discrete entropy cannot simply be applied to a continuous density.

Learning Objectives

• Distinguish the self-information of a single outcome from the entropy of a random variable;
• Explain the relationship between entropy and the average length of lossless compression;
• Understand joint entropy, conditional entropy, and mutual information;
• Differentiate between cross-entropy, KL divergence, and their roles in model training.

1. The More Unexpected the Outcome, the Higher the Self-Information

For an outcome $x$ with probability $p(x)$, self-information is defined as:

$$I(x)=-{\log }_{2}p(x).$$

When using base 2, the unit is bits. This definition satisfies three intuitive properties:

The formula initially assumes p(x)>0. An outcome with probability zero cannot occur under the model; its extended self-information is positive infinity. Observing it calls the model’s zero-probability assertion into question.

• An event that is certain ($p=1$) has zero self-information;
• The rarer an event, the higher its self-information;
• When independent events occur together, their probabilities multiply and their self-informations add.

For example, if an alert appears with a daily probability of $1/1024$, observing it yields 10 bits of self-information. This measures the degree of surprise under a probability model, not actual business loss. A high-probability failure might still be costly, and a low-probability log entry might carry no business value.

2. Entropy is Average Self-Information

The entropy of a discrete random variable $X$ is given by:

$$H(X)=-\sum _{x}p(x){\log }_{2}p(x)=\mathbb{E}[I(X)].$$

We define $0\log 0=0$. Entropy quantifies the average uncertainty before the value of $X$ is revealed.

For a fair coin with two equally likely outcomes:

$$H(X)=-2\times \frac{1}{2}{\log }_2\frac{1}{2}=1\text{ bit}.$$

If the probability of heads is 0.9, the entropy is approximately 0.469 bit. The outcome becomes more predictable, and the average uncertainty decreases. However, do not interpret a "50% chance of rain" forecast as carrying more information, always clarify the random variable, prior distribution, and the actual observed result.

For a fixed set of $n\ge 1$ possible outcomes, $0\le H(X)\le {\log }_{2}n$, with equality at the upper bound for the uniform distribution. Changing the outcome set changes the bound and the question. Check variables, distributions, and units before interpreting entropy comparisons.

3. Why Entropy Is Related to Compression

For a finite alphabet with at least two positive-probability symbols, a binary uniquely decodable code has average length $L\ge H(X)$. Huffman coding constructs an optimal binary prefix code with $H(X)\le L<H(X)+1$. Lengths are per symbol. A one-symbol source may use an empty codeword if message length is supplied externally.

For four symbols with probabilities 1/2, 1/4, 1/8, 1/8, use codewords 0, 10, 110, 111. None is a prefix of another. This Python 3 check verifies that the average length equals entropy:

import math

probabilities = [0.5, 0.25, 0.125, 0.125]
codes = ["0", "10", "110", "111"]
entropy = -math.fsum(p * math.log2(p) for p in probabilities)
average_length = math.fsum(p * len(c) for p, c in zip(probabilities, codes))
assert all(not b.startswith(a) for a in codes for b in codes if a != b)
print(entropy, average_length)  # 1.75 1.75

This does not mean that any file can be compressed down to exactly $H(X)$ bits:

• Entropy depends on the source probability model;
• A single finite file incurs overhead from the code table and container;
• Failure to exploit correlations between symbols misses potential compression structures;
• Already compressed or nearly random data may actually grow larger when compressed.

Arithmetic and range coding can more precisely approximate the code lengths dictated by the probability model. The core strength of a compression system often isn't the mathematical formula of the encoder, but rather its ability to accurately predict the distribution of the next symbol.

For $N$ IID symbols, block entropy is $NH(X)$. With dependence, use joint entropy or an entropy rate instead of multiplying blindly. Nor can a lossless compressor shorten every $n$-bit input: there are $2^n$ such inputs but only $2^n-1$ binary strings shorter than $n$, so an injective mapping is impossible.

4. Conditional Entropy and Mutual Information

The joint entropy $H(X,Y)$ captures the uncertainty associated with observing both variables $X$ and $Y$ simultaneously. The conditional entropy:

$$H(Y\mid X)=H(X,Y)-H(X)$$

measures the average remaining uncertainty in $Y$ after knowing the value of $X$.

Mutual information is defined as:

$$I(X;Y)=H(Y)-H(Y\mid X)=H(X)+H(Y)-H(X,Y).$$

Mutual information is nonnegative and is zero exactly when the variables are independent. It detects more than linear dependence: if $X$ is uniform on $-1,0,1$ and $Y=X^2$, their covariance is zero but $X$ determines $Y$, giving $I(X;Y)=H(Y)\approx 0.9183$ bits. Conditional entropy averages over values of $X$; its nonincrease on average does not mean every individual observation reduces uncertainty.

Mutual information does not inherently indicate causality. High mutual information can still arise when both $X$ and $Y$ are influenced by a third, shared factor. Estimating mutual information from finite samples is also subject to biases introduced by binning, density estimation, and discretization effects.

5. Cross-Entropy and KL Divergence

Given a true distribution $P$ and a model distribution $Q$, the cross-entropy is defined as:

$$H(P,Q)=-\sum _{x}P(x)\log Q(x).$$

The KL divergence is:

$$D_{\mathrm{KL}}(P\parallel Q)=\sum _{x}P(x)\log \frac{P(x)}{Q(x)}.$$

Under well-defined conditions and with the same logarithmic base, the following identity holds:

$$H(P,Q)=H(P)+D_{\mathrm{KL}}(P\parallel Q).$$

For fixed $P$, minimizing cross-entropy is equivalent to minimizing $D_{\mathrm{KL}}(P\parallel Q)$. Training data estimate an unknown generating distribution; they do not define the true distribution itself. KL is nonnegative and vanishes exactly when $P=Q$, but is generally asymmetric and fails the triangle inequality, so it is not a distance metric.

This binary example checks the decomposition and asymmetry directly. Its helpers assume the supplied distributions are normalized, have matching lengths, and that Q is positive wherever P is positive; they do not implement general distribution validation:

import math

P = [0.75, 0.25]
Q = [0.5, 0.5]
def entropy_bits(probabilities):
    return -math.fsum(p * math.log2(p) for p in probabilities if p > 0)

def kl_bits(p, q):
    return math.fsum(a * math.log2(a / b) for a, b in zip(p, q) if a > 0)

h = entropy_bits(P)
cross = -math.fsum(p * math.log2(q) for p, q in zip(P, Q))
print(f"{h:.6f} {cross:.6f} {kl_bits(P, Q):.6f} {kl_bits(Q, P):.6f}")
# 0.811278 1.000000 0.188722 0.207519
assert math.isclose(cross, h + kl_bits(P, Q))

If there exists an outcome where $P(x)>0$ but $Q(x)=0$, both cross-entropy and forward KL divergence will diverge. This explains why classification implementations directly work with logits and use stable log_softmax computations, rather than first computing probabilities that might round to zero before taking the logarithm.

6. A Binary Classification Loss

For true labels $y\in \{0,1\}$ and predicted probability of the positive class $q$, the binary cross-entropy loss is:

$$L=-[y\log q+(1-y)\log (1-q)].$$

import math

def binary_cross_entropy_from_probability(y: int, q: float) -> float:
    if y not in (0, 1):
        raise ValueError("y must be 0 or 1")
    if not 0.0 < q < 1.0:
        raise ValueError("q must lie strictly between 0 and 1")
    return -(y * math.log(q) + (1 - y) * math.log1p(-q))

print(f"{binary_cross_entropy_from_probability(1, 0.9):.6f}")  # 0.105361
print(f"{binary_cross_entropy_from_probability(1, 0.1):.6f}")  # 2.302585

The code uses the natural logarithm, so the units are nats; switching to base 2 yields bits. In machine learning, the choice of logarithmic base typically only affects the numerical scale and gradient magnitude by a constant factor, this does not change the optimal solution, but alters the loss value and gradient size.

The probability interface deliberately rejects endpoints. Mathematically, assigning probability 1 to the correct class gives zero loss, while assigning it probability zero gives positive infinity. For a finite logit z, continue with this equivalent formula to avoid first forming a probability that saturates to 0 or 1:

def binary_cross_entropy_from_logit(y: int, z: float) -> float:
    if y not in (0, 1) or not math.isfinite(z):
        raise ValueError("require a binary label and a finite logit")
    return max(z, 0.0) - y * z + math.log1p(math.exp(-abs(z)))

print(binary_cross_entropy_from_logit(1, 1000.0))  # 0.0: tiny positive loss underflows
print(binary_cross_entropy_from_logit(0, 1000.0))  # 1000.0

Changing logarithm base scales this loss by a positive constant. If an unscaled regularization term is also present, the total objective’s relative weights change. Underflow remains possible: the displayed zero at positive-class logit 1,000 is not an exactly zero mathematical loss.

Common Misconceptions

• Entropy is just "disorder": This is an intuitive analogy, but in practice, entropy requires a specific random variable and its probability distribution to be defined.
• Low-entropy data is always valuable: Entropy measures uncertainty, not business value or truthfulness.
• Cross-entropy equals error rate: It penalizes confidence in predicted probabilities, and is not equivalent to a 0/1 classification error rate.
• KL divergence is symmetric: Swapping $P$ and $Q$ typically yields a different result.

Exercise

1. Compute the entropy of a fair four-sided die and provide the most natural fixed-length encoding.
2. Compare the entropies of coins with probabilities of heads equal to 0.5, 0.9, and 0.99.
3. Construct two probability distributions to verify that $D_{KL}(P\parallel Q)\ne D_{KL}(Q\parallel P)$.
4. Explain why a compressor cannot guarantee that every input file will become shorter.

Summary

Information entropy measures the uncertainty of a random event, while conditional entropy and mutual information quantify the shared uncertainty between variables. Cross-entropy and Kullback-Leibler (KL) divergence convert the deviation of a probabilistic model into an optimization objective, though both rely on well-defined distributions and numerical implementations.

The next lesson shifts focus from "how many bits are needed to represent a message" to "how finite bits can approximate real numbers."

• MIT Information Theory: Entropy and Divergence
• MIT Information Theory: Huffman Codes