Math for Data Science · MDS-10
Measure surprise, quantify shared information, and meet the loss functions that train modern models — all built from one number: bits.
Information theory gives data scientists a single currency — the bit — for measuring uncertainty, surprise, and how much one variable tells you about another. This compact course builds from Shannon's entropy through mutual information, cross-entropy, and KL divergence, then connects them to compression and the loss functions that train classifiers and deep networks. Every idea is paired with a small NumPy experiment so you can see the math move.
Course Outline
Every lesson is self-contained: a full explanation, worked step-by-step examples (in Python), common mistakes, a try-it-yourself, and an interactive quiz. Jump to a unit:
Information theory turns the vague idea of surprise into a number. We start by quantifying how surprising a single outcome is.
Self-information (or surprisal) measures how surprised you should be to observe an outcome of probability p: I(x) = -log(p(x)). The logarithm is the right tool because information is additive for independent events — seeing two independent outcomes should add their surprises, and probabilities multiply, so -log turns a product into a sum: -log(p*q) = -log(p) + -log(q). Rare events carry many bits; certain events (p=1) carry zero. This single definition is the foundation for entropy, cross-entropy, and KL divergence, which are all just averages of -log(probability). In ML, every log-likelihood and cross-entropy loss is literally an average self-information, so understanding surprisal explains why our loss functions look the way they do.
Worked Example 1
Problem. How many bits of self-information does a fair coin landing heads carry?
Answer. 1 bit
Worked Example 2
Problem. A weather model says rain has probability 0.1. How surprising (in bits) is observing rain?
Answer. ≈ 3.32 bits
Worked Example 3
Problem. Two independent fair dice both show a 6. Show the total surprise equals the sum of the parts.
Answer. ≈ 5.17 bits, equal to the sum of the two individual surprises
Problem. A spam filter assigns probability 0.02 to a particular email being spam, and that email turns out to be spam. How many bits of self-information did that outcome carry?
Solution. Self-information is I = -log2(p) with p = 0.02. Compute -np.log2(0.02) = -(-5.6439) = 5.6439. Because spam was predicted to be quite unlikely (0.02), actually observing it is highly surprising. Answer: ≈ 5.64 bits.
The same surprise can be expressed in different units depending on the logarithm base. Here we learn to convert and to choose.
The unit of information is set by the logarithm base. Base 2 gives bits (the surprise of one fair coin flip), base e gives nats, and base 10 gives hartleys (or bans). Changing base only rescales by a constant: log_b(x) = ln(x)/ln(b), so 1 nat = 1/ln(2) ≈ 1.4427 bits, and 1 bit = ln(2) ≈ 0.6931 nats. Bits dominate compression and communication because data is binary. Nats dominate machine learning because the natural log has the cleanest derivatives — d/dx ln(x) = 1/x — which keeps gradients of cross-entropy and log-likelihood simple. Frameworks like PyTorch and TensorFlow compute losses in nats by default, so recognizing the base prevents confusion when a loss value looks 'too small' compared to a bit-based expectation.
Worked Example 1
Problem. A distribution has entropy 2.0 bits. Express it in nats.
Answer. ≈ 1.386 nats
Worked Example 2
Problem. A PyTorch model reports a cross-entropy loss of 0.6931 nats on a balanced binary task. What is that in bits, and what does it mean?
Answer. 1.0 bit; the model is at chance level
Worked Example 3
Problem. Compute -log of p = 0.25 in bits, nats, and hartleys and confirm they describe the same surprise.
Answer. 2.0 bits = 1.386 nats = 0.602 hartleys
Problem. A language model reports a per-token entropy of 3.0 nats. Convert this to bits and to base-10 hartleys.
Solution. Bits = nats / ln(2) = 3.0 / 0.6931 = 4.3281 bits (or 3.0 * log2(e) = 3.0 * 1.4427). Hartleys = nats / ln(10) = 3.0 / 2.3026 = 1.3029 hartleys. Answer: 3.0 nats ≈ 4.33 bits ≈ 1.30 hartleys.
Entropy averages self-information over all outcomes, giving one number for the uncertainty of a whole distribution.
Shannon entropy is the expected self-information: H(X) = -sum_x p(x) log p(x). It answers 'on average, how surprised will I be per draw?' and equals the minimum average number of bits needed to encode outcomes from the distribution. Each term p(x)*(-log p(x)) weights a surprise by how often it happens, so both very rare and very common outcomes contribute little, while moderately uncertain outcomes contribute most. By convention 0*log(0) = 0 because vanishing-probability outcomes add nothing. Entropy is central to ML: it sets the floor for compression, defines the irreducible part of cross-entropy loss, and appears as the impurity measure in decision trees. A high-entropy target is hard to predict; a low-entropy target is nearly deterministic.
Worked Example 1
Problem. Compute the entropy of a fair four-sided die.
Answer. 2 bits
Worked Example 2
Problem. A skewed three-class distribution is p = [0.7, 0.2, 0.1]. Find its entropy in bits.
Answer. ≈ 1.157 bits
Worked Example 3
Problem. Write a safe entropy computation for p = [0.5, 0.5, 0.0] that handles the zero-probability term.
Answer. 1 bit
Problem. A loaded coin has p(heads) = 0.9. Compute its Shannon entropy in bits and explain whether it is more or less than a fair coin.
Solution. H = -(0.9*log2(0.9) + 0.1*log2(0.1)). Compute -(0.9*-0.152 + 0.1*-3.3219) = -(-0.1368 - 0.3322) = 0.469 bits. This is far less than the fair coin's 1 bit, because the outcome is much more predictable. Answer: ≈ 0.469 bits, less than a fair coin.
Entropy obeys a few clean rules that explain when uncertainty is largest, smallest, and how it behaves under mixing.
Three properties matter most. (1) Minimum: H(X) >= 0, with equality only when one outcome has probability 1 — a certain variable has zero entropy. (2) Maximum: over n outcomes, H(X) <= log n, achieved exactly by the uniform distribution, which is maximally uncertain. (3) Concavity: H is a concave function of the probability vector, so averaging two distributions never reduces entropy — mixing increases (or holds) uncertainty. These properties justify the maximum-entropy principle (assume the least-committal distribution consistent with constraints), bound how much information a variable can carry, and underpin why uniform priors are a natural 'no-information' default in Bayesian ML. Concavity also guarantees mutual information is non-negative, a fact we rely on later.
Worked Example 1
Problem. Verify the maximum-entropy claim: which of p=[0.5,0.5] or q=[0.9,0.1] has higher entropy?
Answer. p=[0.5,0.5] is higher (1 bit vs 0.469 bits)
Worked Example 2
Problem. Confirm a degenerate distribution has minimum entropy: p = [1.0, 0.0, 0.0].
Answer. 0 bits (the minimum)
Worked Example 3
Problem. Demonstrate concavity: show the entropy of the average of a=[0.9,0.1] and b=[0.1,0.9] is at least the average of their entropies.
Answer. H(mixture)=1.0 >= 0.469 = average of entropies; concavity holds
Problem. Over 8 equally likely outcomes, what is the maximum possible entropy, and what distribution achieves it?
Solution. The maximum is log2(n) with n = 8, so log2(8) = 3 bits, achieved by the uniform distribution p = [1/8]*8. Check: -8 * (1/8) * log2(1/8) = -log2(1/8) = 3. Answer: 3 bits, achieved by the uniform distribution over the 8 outcomes.
A few distributions appear constantly. Knowing their entropy by heart builds strong intuition.
The uniform distribution over n outcomes has entropy exactly log2(n) — the maximum — because every outcome is equally surprising. The Bernoulli (single yes/no event) has the binary entropy function H_b(p) = -p log2(p) - (1-p) log2(1-p): it is 0 at p=0 or p=1, rises symmetrically, and peaks at 1 bit when p=0.5. Skewed multinomials fall below log2(n) by an amount that grows as probability concentrates. These cases anchor ML intuition: a balanced binary classifier faces 1 bit of label uncertainty, a heavily imbalanced one faces far less, and the entropy of class labels sets the irreducible portion of cross-entropy loss. Recognizing the shape of the Bernoulli curve also explains why models struggle most near p=0.5 decision boundaries.
Worked Example 1
Problem. What is the entropy of a uniform distribution over 6 outcomes (a fair die)?
Answer. ≈ 2.585 bits
Worked Example 2
Problem. Plot-free check: evaluate the binary entropy function at p = 0.5 and p = 0.2.
Answer. Hb(0.5)=1.0 bit; Hb(0.2)≈0.722 bits
Worked Example 3
Problem. Compare a balanced class distribution [0.5,0.5] with an imbalanced one [0.95,0.05] for a binary classification target.
Answer. 1.0 bit vs ≈ 0.286 bits; the imbalanced target carries much less uncertainty
Problem. A dataset's label is positive 30% of the time. How many bits of uncertainty does the label carry, and how does it compare to a balanced label?
Solution. Use the binary entropy function with p = 0.3: H_b(0.3) = -(0.3*log2(0.3) + 0.7*log2(0.7)) = -(0.3*-1.737 + 0.7*-0.515) = -(-0.521 - 0.360) = 0.881 bits. A balanced label is 1.0 bit, so a 30/70 split is somewhat easier to predict. Answer: ≈ 0.881 bits, less than the 1-bit balanced case.
Real data rarely comes as a clean distribution. We estimate entropy by counting frequencies first.
To estimate the entropy of a categorical column, count how often each value occurs, normalize the counts into a probability vector, then apply H = -sum p log p. This 'plug-in' estimator is consistent: as the sample grows, the empirical entropy converges to the true entropy. For small samples it is slightly biased downward, because unseen rare categories are missed — a hint that smoothing or bias corrections matter when categories are many and data is scarce. In practice np.unique(..., return_counts=True) gives the counts in one call. Estimating entropy from data is the everyday version of every concept in this unit: it powers feature-quality checks, decision-tree impurity, and sanity checks on how predictable a target column is before modeling.
Worked Example 1
Problem. Estimate the entropy (bits) of the array ['a','a','b','c'].
Answer. 1.5 bits
Worked Example 2
Problem. Write a reusable entropy(labels) function that handles any base and zero-safe counts.
Answer. A function returning 0.0 for constant data and 1.0 bit for a balanced binary column
Worked Example 3
Problem. From 1000 simulated draws of a 70/30 binary variable, estimate the entropy and compare to the true value 0.881 bits.
Answer. ≈ 0.879 bits, matching the true 0.881 bits within sampling noise
Problem. Given the array ['red','red','red','blue','green'], estimate its entropy in bits using NumPy.
Solution. Counts: red=3, blue=1, green=1 over 5 items, so p = [0.6, 0.2, 0.2]. Entropy = -(0.6*log2(0.6) + 0.2*log2(0.2) + 0.2*log2(0.2)) = -(0.6*-0.737 + 0.2*-2.322 + 0.2*-2.322) = -(-0.442 - 0.464 - 0.464) = 1.371 bits. In code: _,c=np.unique(x,return_counts=True); p=c/c.sum(); -np.sum(p*np.log2(p)) -> 1.371. Answer: ≈ 1.371 bits.
Write a NumPy function entropy(p, base=2) that takes a probability vector and returns its Shannon entropy, correctly handling zero-probability entries so 0*log(0) contributes 0. Use it to plot the entropy of a Bernoulli variable as p sweeps from 0 to 1, and confirm the peak is exactly 1 bit at p = 0.5. Then load a column of categorical data, estimate its distribution by counting frequencies, and report its entropy in bits.
Deliverable · A script with the reusable entropy function, the Bernoulli entropy curve, and the estimated entropy (in bits) of a real categorical column.
1. What is the Shannon entropy, in bits, of a fair coin flip?
Answer C. H = -(0.5 log2 0.5 + 0.5 log2 0.5) = -(0.5*-1 + 0.5*-1) = 1 bit; a fair binary choice carries exactly one bit.
2. For a discrete variable with n possible outcomes, entropy is maximized when the distribution is:
Answer B. Uncertainty is greatest when every outcome is equally likely; the uniform distribution achieves the maximum entropy of log n.
3. The self-information of an outcome with probability p is defined as:
Answer B. Self-information (surprisal) is -log(p): the smaller the probability, the larger the information content.
4. Switching from base-2 to base-e logarithms changes the units of entropy from bits to:
Answer A. Base-2 logs give bits; natural (base-e) logs give nats. The choice only rescales entropy by a constant factor.
5. What is the entropy of a distribution that places probability 1 on a single outcome?
Answer C. A certain outcome carries no surprise, so its entropy is 0; the convention 0*log(0) = 0 keeps the sum well defined.
I can compute the self-information of an outcome and the Shannon entropy of a distribution.
I can explain why entropy is maximized by the uniform distribution and minimized by a certain one.
I can estimate entropy from a sample of data in NumPy and interpret the result in bits.
When two variables travel together we measure the uncertainty of the pair as a whole.
Joint entropy H(X, Y) = -sum_{x,y} p(x, y) log p(x, y) is just Shannon entropy applied to the joint distribution treated as one big variable (X, Y). It measures the total uncertainty needed to pin down both values at once. Two bounds frame it: H(X, Y) >= max(H(X), H(Y)), since knowing the pair is at least as uncertain as knowing either alone; and H(X, Y) <= H(X) + H(Y), with equality exactly when X and Y are independent. That gap, H(X)+H(Y) - H(X,Y), is the mutual information we will define shortly. In ML, joint entropy underlies how we reason about pairs of features or feature-and-label relationships and is the building block for conditional entropy and information gain.
Worked Example 1
Problem. Two independent fair coins X and Y. Compute H(X, Y).
Answer. 2 bits
Worked Example 2
Problem. A joint table P(X,Y) = [[0.4, 0.1],[0.1, 0.4]]. Compute the joint entropy.
Answer. ≈ 1.722 bits
Worked Example 3
Problem. If Y is a deterministic copy of a fair coin X, what is H(X, Y)?
Answer. 1 bit
Problem. Given the joint table P(X,Y) = [[0.5, 0.25],[0.0, 0.25]], compute the joint entropy in bits.
Solution. Nonzero cells are 0.5, 0.25, 0.25. H(X,Y) = -(0.5*log2(0.5) + 0.25*log2(0.25) + 0.25*log2(0.25)) = -(0.5*-1 + 0.25*-2 + 0.25*-2) = -(-0.5 - 0.5 - 0.5) = 1.5 bits. In code: J=np.array([[0.5,0.25],[0,0.25]]); nz=J[J>0]; -np.sum(nz*np.log2(nz)) -> 1.5. Answer: 1.5 bits.
Once we observe one variable, how much uncertainty about the other is left? That is conditional entropy.
Conditional entropy H(Y|X) = sum_x p(x) H(Y|X=x) = -sum_{x,y} p(x,y) log p(y|x) is the average uncertainty remaining in Y after X is known. It is a weighted average of the entropy of Y within each value of X. Key bounds: 0 <= H(Y|X) <= H(Y). It hits 0 when X fully determines Y, and equals H(Y) when X tells you nothing about Y (independence). Conditioning never increases entropy on average — 'information can't hurt.' This is the workhorse of decision trees: a split on feature X is good precisely when H(Y|X) is small, meaning the label is nearly determined within each branch. Information gain, defined next via mutual information, is just H(Y) - H(Y|X).
Worked Example 1
Problem. Joint table P(X,Y) = [[0.5, 0.0],[0.0, 0.5]] (Y copies X). Find H(Y|X).
Answer. 0 bits
Worked Example 2
Problem. Independent fair coins, J = [[0.25,0.25],[0.25,0.25]]. Compute H(Y|X).
Answer. 1 bit
Worked Example 3
Problem. For J = [[0.4,0.1],[0.1,0.4]] compute H(Y|X) using the chain rule H(Y|X) = H(X,Y) - H(X).
Answer. ≈ 0.722 bits
Problem. For the joint table P(X,Y) = [[0.5, 0.25],[0.0, 0.25]], compute H(Y|X) in bits via the chain rule.
Solution. First H(X,Y): nonzero cells 0.5,0.25,0.25 give 1.5 bits (from the previous lesson). Marginal of X: px = [0.5+0.25, 0+0.25] = [0.75, 0.25], so H(X) = -(0.75*log2(0.75)+0.25*log2(0.25)) = -(0.75*-0.415+0.25*-2) = -(-0.311-0.5) = 0.811 bits. Then H(Y|X) = H(X,Y) - H(X) = 1.5 - 0.811 = 0.689 bits. Answer: ≈ 0.689 bits.
Joint uncertainty decomposes into a clean sum, which lets us build big entropies from small pieces.
The chain rule states H(X, Y) = H(X) + H(Y|X), and symmetrically = H(Y) + H(X|Y). In words, the total uncertainty of the pair equals the uncertainty of the first variable plus the leftover uncertainty of the second given the first. It generalizes to many variables: H(X1,...,Xn) = sum_i H(Xi | X1,...,X(i-1)). This decomposition is the algebraic engine behind mutual information and information gain, and it mirrors the way probabilistic models factorize a joint distribution into conditionals (the same logic that defines autoregressive language models, where the log-likelihood of a sequence is a sum of per-token conditional surprises). Rearranged, the chain rule gives H(Y|X) = H(X,Y) - H(X), the most convenient way to compute conditional entropy in code.
Worked Example 1
Problem. Verify the chain rule numerically for J = [[0.4,0.1],[0.1,0.4]].
Answer. 1.0 + 0.722 = 1.722 = H(X,Y)
Worked Example 2
Problem. Show both orderings agree for the same table: H(X)+H(Y|X) = H(Y)+H(X|Y).
Answer. Both orderings give 1.722 bits
Worked Example 3
Problem. Use the chain rule to compute the joint entropy of a length-3 sequence of independent fair bits.
Answer. 3 bits
Problem. You are told H(X) = 1.5 bits and H(X, Y) = 2.3 bits. What is H(Y|X)?
Solution. Rearrange the chain rule H(X,Y) = H(X) + H(Y|X) to get H(Y|X) = H(X,Y) - H(X) = 2.3 - 1.5 = 0.8 bits. Answer: 0.8 bits of uncertainty about Y remains once X is known.
Mutual information measures how many bits learning one variable tells you about another.
Mutual information I(X; Y) = H(Y) - H(Y|X) = H(X) + H(Y) - H(X, Y) is the average reduction in uncertainty about one variable from observing the other. Equivalently it is the KL divergence between the joint distribution and the product of marginals: I(X;Y) = sum p(x,y) log( p(x,y) / (p(x)p(y)) ). It is always non-negative and symmetric, I(X;Y) = I(Y;X). Zero means independence; larger values mean stronger shared information. In ML this is the principled score for feature relevance (how much a feature tells you about the label), the basis of decision-tree information gain, and a target in representation learning. Unlike correlation, it captures any dependence, including nonlinear and categorical relationships.
Worked Example 1
Problem. Compute I(X;Y) for the correlated table J = [[0.4,0.1],[0.1,0.4]].
Answer. ≈ 0.278 bits
Worked Example 2
Problem. Compute MI directly from the log-ratio formula for the same table.
Answer. ≈ 0.278 bits
Worked Example 3
Problem. What is the mutual information when Y is a deterministic copy of X (fair coin)?
Answer. 1 bit
Problem. You measure H(Y) = 2.0 bits and H(Y|X) = 0.5 bits. What is the mutual information I(X;Y), and what fraction of Y's uncertainty does X resolve?
Solution. I(X;Y) = H(Y) - H(Y|X) = 2.0 - 0.5 = 1.5 bits. The fraction of uncertainty resolved is 1.5/2.0 = 0.75, so X explains 75% of the uncertainty in Y. Answer: 1.5 bits, resolving 75% of Y's uncertainty.
MI and correlation both measure association, but MI is far more general. Knowing the difference avoids costly mistakes.
Mutual information is zero if and only if the variables are independent — a complete characterization that correlation lacks. Pearson correlation only detects linear association, so a strong nonlinear relationship (like Y = X^2 with X symmetric around zero) can have zero correlation yet large mutual information. MI also works directly on categorical variables, where correlation is undefined. The cost is that MI must be estimated from a joint distribution, which needs more data and, for continuous variables, binning or density estimation. In feature selection, ranking features by MI catches predictive signals that correlation filters miss; in diagnostics, near-zero correlation but high MI is a red flag that an important nonlinear effect exists. Treat correlation as a fast linear screen and MI as the general-purpose dependence detector.
Worked Example 1
Problem. Show that Y = X^2 has zero correlation but nonzero MI when X takes values {-1, 0, 1} uniformly.
Answer. Correlation 0, but MI ≈ 0.918 bits
Worked Example 2
Problem. Confirm an independent pair has both zero correlation and zero MI using a product table.
Answer. MI = 0 bits
Worked Example 3
Problem. Two features have correlations 0.05 and 0.0 with the target, but feature B has MI 0.4 bits while feature A has MI 0.01 bits. Which should you keep?
Answer. Keep feature B (high MI despite near-zero correlation)
Problem. A feature has Pearson correlation 0.0 with the target but its mutual information with the target is 0.6 bits. Should you keep the feature, and why?
Solution. Yes, keep it. Zero correlation only rules out a linear relationship, but the mutual information of 0.6 bits proves the feature shares real information with the target — almost certainly through a nonlinear or categorical dependence that correlation cannot see. Discarding it based on correlation would throw away a genuinely predictive feature. Answer: keep the feature; MI shows it is informative despite zero linear correlation.
In practice we estimate MI from samples by building an empirical joint table.
To estimate I(X; Y) from two columns, count co-occurrences into a contingency table, normalize to a joint probability matrix, derive the marginals by summing rows and columns, then apply I = sum p(x,y) log( p(x,y) / (p(x)p(y)) ) over nonzero cells. np.histogram2d (for binned continuous data) or a counts matrix from np.unique (for categoricals) builds the table quickly. The plug-in estimator is biased upward for MI in small samples — random noise creates apparent dependence — so estimated MI of truly independent variables is often slightly positive, not exactly zero. Remedies include more data, coarser bins, or bias corrections. This estimate is exactly what scikit-learn's mutual_info_classif computes under the hood for feature selection.
Worked Example 1
Problem. Estimate MI from paired categorical arrays x=['a','a','b','b'], y=['0','1','0','1'] (independent by construction).
Answer. 0 bits
Worked Example 2
Problem. Write a reusable mutual_information(x, y) for categorical arrays.
Answer. A reusable estimator that returns ~0.918 bits when y copies x
Worked Example 3
Problem. Demonstrate small-sample upward bias: estimate MI for two truly independent 50-sample binary columns.
Answer. ≈ 0.02 bits of spurious MI from finite-sample bias (true value 0)
Problem. From the contingency counts table [[20, 0],[0, 30]] (a perfect association between X and Y over 50 samples), estimate the mutual information in bits.
Solution. Normalize: J = [[0.4, 0.0],[0.0, 0.6]]. Marginals px = [0.4, 0.6], py = [0.4, 0.6]. Only diagonal cells are nonzero. I = 0.4*log2(0.4/(0.4*0.4)) + 0.6*log2(0.6/(0.6*0.6)) = 0.4*log2(1/0.4) + 0.6*log2(1/0.6) = 0.4*1.3219 + 0.6*0.7370 = 0.5288 + 0.4422 = 0.971 bits. This equals H(X) = H(Y) since the variables determine each other. Answer: ≈ 0.971 bits.
Given two categorical columns, build the joint probability table with NumPy by counting co-occurrences and normalizing. Compute H(X), H(Y), H(X, Y), H(Y given X), and I(X; Y) directly from your tables. Verify numerically that H(X, Y) = H(X) + H(Y given X) and that I(X; Y) = H(X) + H(Y) - H(X, Y). Then construct one independent pair and one strongly dependent pair and confirm the mutual information behaves as expected.
Deliverable · A script that prints all five quantities, confirms the chain-rule and MI identities to numerical tolerance, and reports MI for an independent vs. a dependent pair.
1. Mutual information I(X; Y) equals zero exactly when:
Answer B. Mutual information measures shared information; it is zero if and only if X and Y are independent, so neither tells you anything about the other.
2. The chain rule for entropy states that H(X, Y) equals:
Answer B. Joint uncertainty decomposes additively: H(X, Y) = H(X) + H(Y given X).
3. Conditional entropy H(Y given X) represents:
Answer C. H(Y given X) is the average remaining uncertainty in Y once X is known; if X determines Y, it is zero.
4. Which expression correctly gives mutual information?
Answer A. Mutual information is the sum of the individual entropies minus the joint entropy: I(X; Y) = H(X) + H(Y) - H(X, Y).
5. Compared with the Pearson correlation coefficient, mutual information:
Answer B. Correlation captures linear association only; mutual information detects any form of statistical dependence between the variables.
I can compute joint and conditional entropy from a joint distribution table.
I can compute mutual information and explain it as the reduction in uncertainty.
I can estimate mutual information between two columns of data in NumPy.
Cross-entropy measures the cost of using the wrong probability model to describe the true world.
Cross-entropy H(p, q) = -sum_x p(x) log q(x) is the average number of bits to encode outcomes that truly follow p when you use a code optimized for a model q. Because the optimal code length for an outcome is -log q(x), but the outcomes actually occur with frequency p(x), the expected cost is taken under p. When q matches p, cross-entropy equals the entropy H(p) — the best possible. Any mismatch makes it larger. This is exactly the structure of a supervised loss: p is the true label distribution (often one-hot), and q is the model's predicted distribution. Minimizing cross-entropy pushes the model's q toward the truth p, which is why nearly every classifier is trained on it.
Worked Example 1
Problem. True p = [0.5, 0.5], model q = [0.5, 0.5]. Compute H(p, q) and compare to H(p).
Answer. H(p,q) = 1.0 bit = H(p)
Worked Example 2
Problem. True p = [0.5, 0.5] but a wrong model q = [0.9, 0.1]. Compute the cross-entropy.
Answer. ≈ 1.737 bits
Worked Example 3
Problem. One-hot true label p = [1, 0, 0] with model prediction q = [0.7, 0.2, 0.1]. Compute the cross-entropy (this is the classification loss for one example).
Answer. ≈ 0.515 bits
Problem. A binary classifier predicts q = [0.8, 0.2] when the true one-hot label is p = [1, 0]. Compute the cross-entropy loss for this example in bits.
Solution. With a one-hot label only the true-class term contributes: H(p,q) = -1*log2(0.8) - 0*log2(0.2) = -log2(0.8) = 0.3219 bits. The model was fairly confident in the correct class, so the loss is small. Answer: ≈ 0.322 bits.
KL divergence isolates the penalty for using the wrong model, separate from the data's irreducible uncertainty.
The Kullback-Leibler divergence D_KL(p || q) = sum_x p(x) log( p(x) / q(x) ) measures the extra bits paid for encoding data from p with a code built for q. It connects directly to cross-entropy: H(p, q) = H(p) + D_KL(p || q). Since H(p) is fixed by the data, the only part a model can reduce is the KL term — so minimizing cross-entropy is exactly minimizing KL. KL is always non-negative (Gibbs' inequality) and zero only when p = q. It is the canonical 'distance-like' measure between distributions in ML, appearing in variational inference, the ELBO, knowledge distillation, and policy-optimization regularizers. Unlike a true metric, it is asymmetric, which has real modeling consequences explored later.
Worked Example 1
Problem. Compute D_KL(p || q) for p = [0.5, 0.5] and q = [0.9, 0.1].
Answer. ≈ 0.737 bits
Worked Example 2
Problem. Verify the decomposition H(p, q) = H(p) + D_KL(p || q) for the pair above.
Answer. 1.737 = 1.0 + 0.737, confirmed
Worked Example 3
Problem. Compute D_KL(p || q) when p = q = [0.3, 0.7].
Answer. 0 bits
Problem. Compute the KL divergence D_KL(p || q) in bits for p = [0.25, 0.75] and q = [0.5, 0.5].
Solution. D_KL = 0.25*log2(0.25/0.5) + 0.75*log2(0.75/0.5) = 0.25*log2(0.5) + 0.75*log2(1.5) = 0.25*(-1) + 0.75*(0.585) = -0.25 + 0.4387 = 0.1887 bits. In code: np.sum(p*np.log2(p/q)) -> 0.1887. The result is positive, as KL must be. Answer: ≈ 0.189 bits.
Two defining properties of KL — it never goes below zero, and direction matters.
Non-negativity follows from Gibbs' inequality (a consequence of the concavity of log via Jensen's inequality): -sum p log(q/p) >= -log(sum p * q/p) = -log(1) = 0, so D_KL(p || q) >= 0 with equality only when p = q everywhere. Asymmetry means D_KL(p || q) is generally not equal to D_KL(q || p), because the averaging weight (the true p) differs between the two. This breaks the triangle inequality too, so KL is a divergence, not a metric. The asymmetry is not a flaw; it encodes which distribution you trust as 'true.' In ML you almost always use D_KL(true || model) (forward KL, the cross-entropy direction), but variational inference often minimizes the reverse, with different qualitative effects covered next.
Worked Example 1
Problem. Show asymmetry: compute D_KL(p || q) and D_KL(q || p) for p = [0.5, 0.5], q = [0.9, 0.1].
Answer. 0.737 vs 0.531 bits — not equal
Worked Example 2
Problem. Confirm non-negativity on a random pair of distributions.
Answer. Always >= 0 (e.g. ≈ 0.31 bits for one random pair)
Worked Example 3
Problem. Explain via the formula why D_KL(p || q) = 0 forces p = q.
Answer. Zero KL implies p and q match on the support of p
Problem. For p = [0.7, 0.3] and q = [0.3, 0.7], compute both D_KL(p || q) and D_KL(q || p) and state whether KL is symmetric here.
Solution. Forward: D_KL(p||q) = 0.7*log2(0.7/0.3) + 0.3*log2(0.3/0.7) = 0.7*1.222 + 0.3*(-1.222) = 0.8554 - 0.3666 = 0.489 bits. Reverse: by the symmetry of these particular distributions D_KL(q||p) = 0.3*log2(0.3/0.7) + 0.7*log2(0.7/0.3) = same 0.489 bits. Here they happen to be equal because p and q are mirror images, but in general KL is NOT symmetric. Answer: both ≈ 0.489 bits in this special mirrored case; KL is asymmetric in general.
The single most common ML loss is just cross-entropy between true labels and predicted probabilities.
For a classifier, the true label is a one-hot distribution p and the model outputs a predicted distribution q (e.g. from a softmax). The per-example loss is cross-entropy H(p, q) = -sum_c p_c log q_c, which collapses to -log q_{true} because only the true class has p_c = 1. Averaged over a dataset this is the log loss / negative log-likelihood. It rewards confident correct predictions (loss -> 0 as q_true -> 1) and harshly punishes confident wrong ones (loss -> infinity as q_true -> 0). Because H(p, q) = H(p) + D_KL(p || q) and one-hot p has H(p)=0, minimizing log loss is exactly minimizing KL from predictions to truth. Frameworks compute it in nats by default; multiply by log2(e) to read it in bits.
Worked Example 1
Problem. True class index 2 of 3, prediction q = [0.1, 0.2, 0.7]. Compute the log loss in nats.
Answer. ≈ 0.357 nats
Worked Example 2
Problem. Average log loss over two examples: truths [0, 1], predictions [[0.8,0.2],[0.3,0.7]].
Answer. ≈ 0.290 nats
Worked Example 3
Problem. Show the penalty for a confidently wrong prediction: true class 0 but q = [0.01, 0.99].
Answer. ≈ 4.605 nats (vs 0.010 when confidently right)
Problem. A 4-class model predicts q = [0.1, 0.6, 0.2, 0.1] and the true class is index 1. Compute the cross-entropy loss in nats and in bits.
Solution. Only the true class contributes: loss = -ln(q_1) = -ln(0.6) = 0.5108 nats. Convert to bits: 0.5108 * log2(e) = 0.5108 * 1.4427 = 0.7370 bits (equivalently -log2(0.6)). Answer: ≈ 0.511 nats ≈ 0.737 bits.
Because KL is asymmetric, choosing which direction to minimize shapes the kind of approximation you get.
Forward KL, D_KL(p || q) with the true p as weight, is 'mean-seeking' (mass-covering): it heavily penalizes q for assigning low probability anywhere p is high, so the fitted q stretches to cover all modes of p, even averaging across them. This is the direction implied by maximum likelihood and cross-entropy training. Reverse KL, D_KL(q || p), is 'mode-seeking' (zero-forcing): it penalizes q for putting mass where p is near zero, so q tends to lock onto a single mode and ignore others. Variational inference typically minimizes reverse KL because it is tractable, which is why variational approximations of multimodal posteriors often collapse to one mode. Knowing the direction predicts whether your approximation will over-spread or over-concentrate.
Worked Example 1
Problem. For a bimodal true p = [0.5, 0.0, 0.5] and a unimodal candidate q = [0.0, 1.0, 0.0], evaluate forward KL.
Answer. Enormous (effectively infinite) forward KL — coverage is mandatory
Worked Example 2
Problem. Same distributions, evaluate reverse KL D_KL(q || p).
Answer. Reverse KL tolerates picking a single mode (finite when q sits on a true mode)
Worked Example 3
Problem. Summarize the practical consequence for fitting a unimodal q to a two-mode p.
Answer. Forward = mass-covering; reverse = mode-seeking
Problem. You fit a single Gaussian q to a true distribution p that has two well-separated peaks. If you minimize reverse KL D_KL(q || p), what behavior do you expect, and how would forward KL differ?
Solution. Minimizing reverse KL is mode-seeking: q will lock onto one of the two peaks and essentially ignore the other, because reverse KL severely penalizes putting probability mass where p is near zero (the valley between peaks). Forward KL D_KL(p || q) is mass-covering: it penalizes q for assigning low probability where p is high, so q would broaden to straddle both peaks, often placing unwanted mass in the low-density valley between them. Answer: reverse KL picks one mode; forward KL spreads to cover both.
Naive log formulas overflow or hit log(0). Stable implementations are essential for real training.
Two numerical traps dominate. First, log(0) = -inf when a predicted probability is exactly zero; clip probabilities into [eps, 1] (e.g. eps = 1e-12) or mask zero terms so they contribute nothing. Second, computing softmax then log separately can overflow on large logits; the log-sum-exp trick subtracts the max logit before exponentiating, and combined log-softmax = z - logsumexp(z) avoids the intermediate blow-up entirely. Practical cross-entropy from logits is therefore loss = -(z_true - logsumexp(z)). For KL, mask or epsilon-guard both p and q. These are the exact stabilizations inside framework ops like cross_entropy and kl_div, and reproducing them in NumPy makes the math concrete and the gradients trustworthy.
Worked Example 1
Problem. Write a stable cross_entropy(p, q) that clips q to avoid log(0).
Answer. A clip-guarded cross-entropy returning 0.0 for a perfect one-hot prediction
Worked Example 2
Problem. Implement log-softmax with the log-sum-exp trick for logits z = [1000, 1001, 1002].
Answer. log-softmax ≈ [-2.408, -1.408, -0.408], computed without overflow
Worked Example 3
Problem. Compute cross-entropy loss directly from logits z = [2.0, 1.0, 0.1] for true class 0.
Answer. ≈ 0.408 nats
Problem. Implement a stable kl_divergence(p, q) in NumPy that avoids log(0), then use it on p = [0.5, 0.5, 0.0] and q = [0.4, 0.4, 0.2].
Solution. Define: def kl_divergence(p, q, eps=1e-12): p=np.clip(p,eps,1); q=np.clip(q,eps,1); m = p>eps; return np.sum(p[m]*np.log2(p[m]/q[m])). Only the first two terms of p are nonzero, so KL = 0.5*log2(0.5/0.4) + 0.5*log2(0.5/0.4) = 0.5*0.3219 + 0.5*0.3219 = 0.3219 bits. The zero-probability third class contributes nothing because p=0 there. Answer: ≈ 0.322 bits, computed without any log(0) error.
In NumPy, implement cross_entropy(p, q) and kl_divergence(p, q) with stable handling of small probabilities. Verify the identity H(p, q) = H(p) + D_KL(p || q) on random distributions, and confirm D_KL(p || q) >= 0 with equality only when p == q. Then simulate a 3-class classifier: fix one-hot true labels, sweep a predicted probability for the correct class from 0.01 to 0.99, and plot how the cross-entropy (log) loss falls as the prediction improves.
Deliverable · A script with both functions, a numerical check of the decomposition and non-negativity, and a plot of log loss versus the predicted probability of the correct class.
1. Cross-entropy H(p, q) and entropy H(p) are related to KL divergence by:
Answer B. Cross-entropy equals the true entropy plus the KL divergence: H(p, q) = H(p) + D_KL(p || q), so minimizing it minimizes KL.
2. The KL divergence D_KL(p || q) is:
Answer A. By Gibbs' inequality KL is non-negative and equals zero only when the distributions match; it is asymmetric and not a metric.
3. Why is cross-entropy the standard loss for a probabilistic classifier?
Answer B. Because H(p, q) = H(p) + D_KL(p || q) and H(p) is fixed by the data, minimizing cross-entropy minimizes the KL gap between predictions and truth.
4. A classifier predicts probability 0.9 for the true class. The contribution to its log loss (base e) is approximately:
Answer A. Log loss for the correct class is -ln(predicted probability) = -ln(0.9) ≈ 0.105; higher confidence in the truth means smaller loss.
5. Computing cross-entropy directly can fail numerically because:
Answer B. If q assigns probability 0 to an observed outcome, log(q) is negative infinity; clipping with a small epsilon or using log-sum-exp keeps it stable.
I can compute cross-entropy and KL divergence between two distributions.
I can explain why cross-entropy is the natural loss for classification and how it relates to KL.
I can implement numerically stable cross-entropy and KL in NumPy and avoid log-of-zero errors.
Compression starts with assigning binary codewords to symbols in a way that can always be decoded back.
A code maps each symbol to a binary string (codeword). For lossless decoding we need unique decodability: any concatenation of codewords parses to exactly one symbol sequence. A prefix (instantaneous) code — where no codeword is a prefix of another — guarantees this and can be decoded on the fly, symbol by symbol, with no lookahead. Variable-length codes let frequent symbols use short codewords, the key to beating fixed-length encoding. The expected code length L = sum p(x) * len(codeword(x)) is what we minimize. This matters in ML wherever model size or description length is a cost (minimum description length, model compression, tokenizer design), and it grounds the deep link between probability and optimal code length that drives entropy-based reasoning.
Worked Example 1
Problem. Is the code {a:0, b:10, c:11} a prefix code? Decode the stream 01011.
Answer. Yes, a prefix code; 01011 decodes to 'abc'
Worked Example 2
Problem. Show {a:0, b:01, c:11} is NOT a prefix code and why that is a problem.
Answer. Not a prefix code; '0' prefixes '01', causing ambiguity
Worked Example 3
Problem. Compute the expected code length of {a:0, b:10, c:11} for p = [0.6, 0.3, 0.1].
Answer. 1.4 bits per symbol
Problem. For symbols with probabilities p = [0.5, 0.25, 0.125, 0.125] and the prefix code {0, 10, 110, 111}, compute the expected code length in bits per symbol.
Solution. Codeword lengths are [1, 2, 3, 3]. Expected length L = 0.5*1 + 0.25*2 + 0.125*3 + 0.125*3 = 0.5 + 0.5 + 0.375 + 0.375 = 1.75 bits/symbol. In code: np.sum(np.array([0.5,0.25,0.125,0.125])*np.array([1,2,3,3])) -> 1.75. Answer: 1.75 bits per symbol.
The Kraft inequality tells you exactly which sets of codeword lengths are achievable with a prefix code.
For a binary prefix code with codeword lengths l_1,...,l_n, the Kraft inequality states sum_i 2^(-l_i) <= 1. Conversely, any set of lengths satisfying it can be realized as a prefix code. Intuitively, each codeword of length l 'claims' a fraction 2^(-l) of the space of infinite binary strings, and these claims must not overlap or exceed the whole. The inequality bounds how short codewords can be: you cannot make everything short. Combined with the optimal length -log2 p(x), it leads directly to Shannon's source coding theorem. In ML and the minimum description length view, Kraft connects any probability model to a valid code, formalizing 'better model = shorter description = lower loss.'
Worked Example 1
Problem. Check Kraft for lengths [1, 2, 3, 3].
Answer. Kraft sum = 1.0 <= 1, feasible
Worked Example 2
Problem. Are lengths [1, 1, 2] possible for a binary prefix code?
Answer. No; Kraft sum 1.25 > 1
Worked Example 3
Problem. Relate Kraft to optimal lengths: verify lengths l_i = ceil(-log2 p_i) satisfy Kraft for p = [0.6, 0.3, 0.1].
Answer. Kraft sum 0.8125 <= 1, feasible
Problem. Do the codeword lengths [2, 2, 2, 2] satisfy the Kraft inequality for a binary prefix code, and what does the result tell you?
Solution. Compute sum of 2^(-l_i) = 2^(-2) + 2^(-2) + 2^(-2) + 2^(-2) = 0.25 * 4 = 1.0. Since 1.0 <= 1, the inequality holds, so a prefix code with these lengths exists — in fact it is the complete fixed-length code {00, 01, 10, 11} for 4 symbols. Equality means the code uses the entire binary space with no slack. Answer: yes, Kraft sum = 1.0; a complete fixed-length 2-bit code is feasible.
Entropy is not just an abstract average surprise — it is the hard floor on lossless compression.
Shannon's source coding theorem says the expected code length per symbol of any uniquely decodable code satisfies L >= H(X), the source entropy in bits, and that codes exist with L < H(X) + 1 (and arbitrarily close to H when coding long blocks of symbols together). So entropy is the achievable lower bound: you cannot losslessly compress below H bits per symbol on average, but you can get nearly there. The proof rests on Kraft plus Gibbs' inequality, with the gap L - H equal to a KL divergence between the true distribution and the one implied by the code lengths. This is why entropy is the natural yardstick for compression performance and why a perfect model (q = p) yields the minimal description — directly mirroring the cross-entropy story from Unit 3.
Worked Example 1
Problem. Compute the entropy floor for p = [0.5, 0.25, 0.125, 0.125].
Answer. H = 1.75 bits per symbol (the lower bound)
Worked Example 2
Problem. A code achieves L = 1.75 bits/symbol for that source. How does it compare to entropy?
Answer. Optimal: L equals H, redundancy 0
Worked Example 3
Problem. For p = [0.6, 0.3, 0.1], find the entropy and the theoretical bound on the best L.
Answer. H ≈ 1.296 bits; optimal L lies in [1.296, 2.296)
Problem. A source has entropy 2.3 bits per symbol. What can you say about the best possible average code length L for a single-symbol lossless code?
Solution. Shannon's source coding theorem bounds it as H <= L < H + 1, so 2.3 <= L < 3.3 bits per symbol. You cannot beat 2.3 bits on average (the entropy floor), and a good code such as Huffman will achieve an L strictly below 3.3, typically close to 2.3. Answer: L is at least 2.3 bits and can be made less than 3.3 bits per symbol.
Huffman coding is a simple greedy algorithm that produces the optimal prefix code for known symbol probabilities.
Huffman coding builds an optimal prefix code bottom-up. Repeatedly take the two least-probable nodes, merge them into a parent whose probability is their sum, and continue until one root remains; assigning 0/1 to the branches yields codewords. Frequent symbols end up near the root with short codewords, rare ones deeper with long ones, approximating the ideal length -log2 p(x). Huffman is provably optimal among symbol-by-symbol codes: its expected length is minimal and satisfies H <= L < H + 1. A min-heap (Python's heapq) makes it efficient. In ML pipelines Huffman-style coding shows up in model and gradient compression and in tokenizer/byte-encoding design, where matching code length to frequency saves storage and bandwidth.
Worked Example 1
Problem. Build a Huffman code for symbols with probabilities A:0.5, B:0.25, C:0.125, D:0.125.
Answer. A=0, B=10, C=110, D=111
Worked Example 2
Problem. Compute the expected length of that Huffman code and compare to entropy.
Answer. L = 1.75 bits = H (optimal)
Worked Example 3
Problem. Sketch a heapq-based Huffman builder and the lengths it gives for p = [0.6, 0.3, 0.1].
Answer. Lengths A=1,B=2,C=2; L = 1.4 bits (just above H = 1.296)
Problem. Build a Huffman code for four symbols with probabilities [0.4, 0.3, 0.2, 0.1] and give the codeword lengths.
Solution. Sort: [0.1, 0.2, 0.3, 0.4]. Merge two smallest 0.1+0.2 = 0.3 (this combined node). Pool now {0.3(merged), 0.3, 0.4}. Merge two smallest 0.3+0.3 = 0.6. Pool {0.6, 0.4}. Merge 0.6+0.4 = 1.0 root. Tracing depths: the 0.4 symbol is at depth 1 (length 1); the 0.3 symbol at depth 2 (length 2); the 0.2 and 0.1 symbols are deepest at depth 3 (lengths 3 and 3). Expected L = 0.4*1 + 0.3*2 + 0.2*3 + 0.1*3 = 0.4 + 0.6 + 0.6 + 0.3 = 1.9 bits. Answer: lengths [1, 2, 3, 3], expected length 1.9 bits/symbol.
The whole point of variable-length coding is matching code length to how often a symbol appears.
Expected code length L = sum p(x) l(x) is minimized when the high-probability symbols carry the smallest l(x). The ideal is l(x) = -log2 p(x): a symbol that occurs half the time should cost 1 bit, a quarter of the time 2 bits, and so on. Spending the same length on a rare symbol as a common one wastes bits on average, raising L above entropy. This trade-off is the operational meaning of self-information from Unit 1 — code length should equal surprisal. The same principle governs efficient model design: allocate representational capacity (and, by analogy, loss-weighting) to the events that actually happen, not uniformly. Mismatch between code lengths and true frequencies is precisely the KL-divergence redundancy.
Worked Example 1
Problem. Compare a fixed 2-bit code with a frequency-matched code for p = [0.7, 0.1, 0.1, 0.1].
Answer. Fixed 2.0 bits vs matched 1.5 bits per symbol
Worked Example 2
Problem. Show the cost of a bad assignment: give the rarest symbol the shortest code for p = [0.7, 0.2, 0.1] with lengths [3, 2, 1].
Answer. Bad assignment 2.6 bits vs sensible 1.3 bits
Worked Example 3
Problem. Compute the ideal (fractional) lengths -log2 p for p = [0.5, 0.25, 0.25] and the resulting L.
Answer. Ideal lengths [1,2,2]; L = 1.5 bits = entropy
Problem. For p = [0.8, 0.1, 0.1], compare the expected length of a fixed 2-bit code with a variable code of lengths [1, 2, 2].
Solution. Fixed-length code: each of 3 symbols would need 2 bits (ceil(log2 3) = 2), so L_fixed = 2.0 bits/symbol. Variable code [1,2,2]: L = 0.8*1 + 0.1*2 + 0.1*2 = 0.8 + 0.2 + 0.2 = 1.2 bits/symbol. Giving the dominant 0.8 symbol a 1-bit codeword saves 0.8 bits per symbol on average. Answer: fixed 2.0 bits vs variable 1.2 bits per symbol.
We close the loop by measuring how close a real code gets to the entropy bound.
To evaluate a code, compute its empirical expected length L = sum p(x) l(x) from symbol frequencies and codeword lengths, compute the source entropy H, and report the redundancy L - H (always >= 0) or the efficiency H / L (<= 1). For a corpus, the achieved compression ratio is total_encoded_bits / (n_symbols * fixed_bits_per_symbol). A code is good when L sits between H and H + 1 and the redundancy is near zero; persistent redundancy means the code lengths mismatch the true probabilities, which equals a KL divergence. This measurement workflow is the practical bridge from theory to engineering and mirrors how you would benchmark a learned compressor or a tokenizer's bits-per-character against the entropy of the data.
Worked Example 1
Problem. A Huffman code on p = [0.5, 0.25, 0.125, 0.125] has lengths [1, 2, 3, 3]. Report L, H, and redundancy.
Answer. L = 1.75, H = 1.75, redundancy 0 (perfectly efficient)
Worked Example 2
Problem. For p = [0.6, 0.3, 0.1] with Huffman lengths [1, 2, 2], measure redundancy and confirm L < H + 1.
Answer. L = 1.4, H ≈ 1.296, redundancy ≈ 0.105 bits; within [H, H+1)
Worked Example 3
Problem. Estimate the compression ratio of encoding 1000 symbols (3-symbol alphabet) with the code above versus a fixed 2-bit code.
Answer. ≈ 0.70 ratio (about 30% smaller than the fixed-length baseline)
Problem. A code achieves an expected length of 2.1 bits per symbol on a source whose entropy is 2.0 bits per symbol. Compute the redundancy and the coding efficiency, and say whether the code is near-optimal.
Solution. Redundancy = L - H = 2.1 - 2.0 = 0.1 bits per symbol (non-negative, as required). Efficiency = H / L = 2.0 / 2.1 = 0.952, i.e. about 95.2%. Since L sits just above H and well within [H, H+1), and efficiency is over 95%, the code is near-optimal — only 0.1 bit per symbol is wasted. Answer: redundancy 0.1 bits/symbol, efficiency ≈ 95.2%; yes, near-optimal.
Given a set of symbols with frequencies, build a Huffman code (you may use a heap from Python's standard library) and record each codeword's length. In NumPy, compute the expected code length as the frequency-weighted average of codeword lengths, then compute the source entropy. Show that the average code length sits between the entropy and entropy + 1 bit. Finally, verify your codeword lengths satisfy the Kraft inequality.
Deliverable · A script printing the Huffman codewords, the average code length, the source entropy, the gap between them, and a confirmation that Kraft's inequality holds.
1. Shannon's source coding theorem says the average number of bits per symbol for lossless coding cannot be less than:
Answer B. Entropy is the fundamental lower bound: no lossless code can use fewer than H bits per symbol on average.
2. In an efficient code, symbols that occur more frequently should be assigned:
Answer B. To minimize average length, frequent symbols get short codewords and rare symbols get long ones, near -log2 p bits each.
3. A prefix code is one in which:
Answer B. Prefix (instantaneous) codes guarantee unambiguous decoding because no codeword begins another, so a stream can be parsed left to right.
4. The Kraft inequality for a binary prefix code with lengths l_i requires that:
Answer A. A binary prefix code with codeword lengths l_i exists if and only if sum of 2^(-l_i) is at most 1.
5. Huffman coding builds an optimal prefix code by repeatedly:
Answer B. Huffman's greedy step combines the two lowest-probability nodes, building the tree bottom-up so frequent symbols end up nearer the root.
I can explain why entropy is the lower bound on average code length for lossless coding.
I can build a Huffman code and compute its average bits per symbol.
I can compare an achieved compression rate against the entropy of the source in NumPy.
We tie the loss from Unit 3 to the actual softmax outputs of a neural classifier.
A neural classifier produces logits z, converts them to probabilities via softmax q_c = exp(z_c)/sum_k exp(z_k), and is trained with cross-entropy against one-hot labels. The per-example loss reduces to -log q_{true}, the negative log probability assigned to the correct class. Because softmax-cross-entropy has the clean gradient dL/dz = q - p (predicted minus one-hot true), training pushes the predicted probability of the right class up and the rest down. This is the workhorse objective of essentially every modern classifier and language model (where perplexity = exp(loss)). Computing it stably means combining softmax and log into log-softmax via log-sum-exp, exactly as in Unit 3, so logits never overflow.
Worked Example 1
Problem. Logits z = [2.0, 1.0, 0.1], true class 0. Compute softmax probabilities and the loss in nats.
Answer. q ≈ [0.659, 0.242, 0.099]; loss ≈ 0.417 nats
Worked Example 2
Problem. Verify the gradient dL/dz = q - p for the example above.
Answer. grad ≈ [-0.341, 0.242, 0.099]
Worked Example 3
Problem. Convert a language-model cross-entropy of 1.5 nats/token into perplexity.
Answer. Perplexity ≈ 4.48
Problem. A 3-class classifier outputs logits z = [0.0, 1.0, 2.0] and the true class is index 2. Compute the softmax probability of the true class and the cross-entropy loss in nats.
Solution. Stable softmax: subtract max (2.0): exp([-2,-1,0]) = [0.1353, 0.3679, 1.0], sum = 1.5032. Probabilities = [0.0900, 0.2447, 0.6652]. The true class (index 2) has q = 0.6652. Loss = -ln(0.6652) = 0.4076 nats. In code: e=np.exp(z-z.max()); q=e/e.sum(); -np.log(q[2]) -> 0.4076. Answer: q_true ≈ 0.665, loss ≈ 0.408 nats.
Maximum likelihood and cross-entropy minimization are the same objective seen from two angles.
Maximum likelihood estimation (MLE) chooses parameters theta that maximize the probability of the observed data, equivalently maximizing the average log-likelihood (1/n) sum log q_theta(x_i). The empirical data distribution p_hat puts mass 1/n on each observed point, so the average negative log-likelihood is exactly the cross-entropy H(p_hat, q_theta). Since H(p_hat, q_theta) = H(p_hat) + D_KL(p_hat || q_theta) and H(p_hat) does not depend on theta, maximizing likelihood is identical to minimizing the forward KL divergence D_KL(p_hat || q_theta) from the model to the data. This unifies the course: cross-entropy loss, negative log-likelihood, and KL minimization are one objective, which is why fitting models 'pulls' q toward the empirical distribution.
Worked Example 1
Problem. Three coin flips H, H, T. Find the MLE of p = P(heads) and the corresponding log-likelihood.
Answer. p_hat = 2/3; total log-likelihood ≈ -1.910 nats
Worked Example 2
Problem. Show the average negative log-likelihood equals cross-entropy H(p_hat, q) for the data above with q = [0.5, 0.5] (heads, tails).
Answer. Cross-entropy = 1 bit/flip = avg negative log-likelihood
Worked Example 3
Problem. Confirm that the KL term, not the entropy, is what MLE drives to zero when q can match p_hat.
Answer. KL -> 0 at the MLE; remaining cross-entropy = H(p_hat) ≈ 0.918 bits
Problem. You observe 4 samples from a 2-category variable: A, A, A, B. Find the maximum-likelihood estimate of P(A), and explain its connection to minimizing KL divergence.
Solution. The MLE for a categorical is just the observed frequency: P(A) = 3/4 = 0.75, P(B) = 1/4 = 0.25. This is the empirical distribution p_hat. Maximizing the data likelihood is equivalent to minimizing the cross-entropy H(p_hat, q), and since H(p_hat, q) = H(p_hat) + D_KL(p_hat || q), the only adjustable part is the KL term. Setting q = p_hat = [0.75, 0.25] makes D_KL(p_hat || q) = 0, the global minimum. Answer: P(A) = 0.75; the MLE is exactly the model that drives the KL divergence from data to model to zero.
Decision trees pick splits by how much they reduce label uncertainty — a direct application of entropy and mutual information.
Information gain from splitting the target Y on a feature X is IG = H(Y) - H(Y|X), the parent entropy minus the weighted average entropy of the children. It is exactly the mutual information I(X; Y): the number of bits the feature reveals about the label. ID3 and C4.5 trees greedily choose the split with maximum information gain at each node, so the tree carves the data into increasingly pure (low-entropy) regions. C4.5 refines this with gain ratio (IG divided by the split's own entropy) to avoid favoring high-cardinality features. This makes information theory the literal splitting criterion of one of the most-used ML model families and a clean, computable feature-importance signal.
Worked Example 1
Problem. Parent labels: 3 positive, 3 negative. Compute H(Y).
Answer. H(Y) = 1 bit
Worked Example 2
Problem. A feature splits the 6 examples into branch L = {+,+,+} and branch R = {-,-,-}. Compute information gain.
Answer. IG = 1.0 bit (perfect split)
Worked Example 3
Problem. A weaker feature splits into L = {+,+,-} and R = {+,-,-}. Compute IG and confirm it equals the mutual information.
Answer. IG ≈ 0.082 bits, equal to the feature-label mutual information
Problem. A node has 8 samples: 4 positive, 4 negative. A feature splits them into branch L = {+,+,+,-} and branch R = {+,-,-,-}. Compute the information gain in bits.
Solution. Parent entropy H(Y) = 1.0 bit (balanced 4/4). Each branch has 4 samples in a 3:1 ratio, so branch entropy = H_b(0.25) = -(0.25*log2(0.25) + 0.75*log2(0.75)) = -(0.25*-2 + 0.75*-0.415) = -(-0.5 - 0.311) = 0.811 bits. Weighted child entropy = (4/8)*0.811 + (4/8)*0.811 = 0.811 bits. Information gain = 1.0 - 0.811 = 0.189 bits. Answer: IG ≈ 0.189 bits.
Variational inference approximates hard posteriors by minimizing a KL divergence, summarized by the ELBO.
When a true posterior p(z|x) is intractable, variational inference picks a simpler distribution q(z) and minimizes the reverse KL D_KL(q(z) || p(z|x)). Because that KL contains the unknown evidence log p(x), we instead maximize the evidence lower bound (ELBO) = E_q[log p(x, z)] - E_q[log q(z)] = E_q[log p(x|z)] - D_KL(q(z) || p(z)). The identity log p(x) = ELBO + D_KL(q || posterior) shows maximizing the ELBO simultaneously tightens the bound on the evidence and drives q toward the true posterior. The ELBO splits into a reconstruction term plus a KL regularizer pulling q toward the prior — exactly the loss of a variational autoencoder. Reverse KL here is why VI can be mode-seeking (Unit 3).
Worked Example 1
Problem. Compute the KL regularizer between an approximate posterior q = N(0.5, 1) and prior p = N(0, 1) (1-D Gaussians, same variance).
Answer. ≈ 0.125 nats
Worked Example 2
Problem. Write the ELBO decomposition and identify each VAE term.
Answer. ELBO = reconstruction - KL-to-prior
Worked Example 3
Problem. Given a reconstruction log-likelihood of -10 nats and a KL term of 2 nats, compute the ELBO and explain the effect of increasing the KL weight.
Answer. ELBO = -12 nats; higher KL weight tightens latent regularization, lowering reconstruction
Problem. In a VAE, the expected reconstruction log-likelihood is -8 nats and the KL divergence between the approximate posterior and the prior is 3 nats. Compute the ELBO, and state what happens to the latent code if you double the weight on the KL term.
Solution. ELBO = E_q[log p(x|z)] - D_KL(q || prior) = -8 - 3 = -11 nats (this is the quantity we maximize). Doubling the KL weight gives ELBO = -8 - 2*3 = -14 nats, applying stronger pressure to push the approximate posterior toward the prior. The latent code becomes more regularized and prior-like (closer to the standard normal), which improves sampling/disentanglement but typically degrades reconstruction fidelity. Answer: ELBO = -11 nats; doubling the KL weight pulls the latent code closer to the prior at the cost of reconstruction.
Mutual information ranks features by how much they tell you about the target and guides what a representation should keep.
In feature selection, we score each feature by its mutual information I(X_j; Y) with the target and keep the highest — a model-agnostic filter that, unlike correlation, captures nonlinear and categorical dependence (scikit-learn's mutual_info_classif does exactly this). Smarter variants (mRMR) maximize relevance to the target while minimizing redundancy among chosen features, both measured by MI. In representation learning, MI is the objective itself: methods like InfoNCE and contrastive learning maximize the mutual information between related views, encouraging embeddings that retain predictive information. The caution from Unit 2 carries over — MI estimates are biased in small samples and depend on binning for continuous variables, so treat rankings as guidance, not gospel.
Worked Example 1
Problem. Two features have I(X1;Y) = 0.45 bits and I(X2;Y) = 0.05 bits. Which is more informative about Y?
Answer. X1 (0.45 bits vs 0.05 bits)
Worked Example 2
Problem. X1 and X2 each have MI 0.4 bits with Y, but I(X1; X2) = 0.38 bits. Should you keep both?
Answer. Keep one; the features are largely redundant
Worked Example 3
Problem. State the representation-learning objective behind contrastive methods in MI terms.
Answer. Maximize mutual information between related views (InfoNCE bounds it)
Problem. Three candidate features have mutual information with the target of 0.6, 0.3, and 0.55 bits. Feature 1 and feature 3 also have a mutual information of 0.5 bits with each other. Using a relevance-minus-redundancy idea, which two features would you select?
Solution. By pure relevance the top two are feature 1 (0.6) and feature 3 (0.55). But features 1 and 3 share 0.5 bits of MI with each other, so they are highly redundant — keeping both adds little new information about the target. Using relevance minus redundancy (mRMR), after picking feature 1 (highest relevance 0.6), feature 3's net value is about 0.55 - 0.5 = 0.05, while feature 2's net value is its full 0.3 (it is not redundant with feature 1). So the better pair is feature 1 and feature 2. Answer: select features 1 and 2 (feature 3 is too redundant with feature 1).
The information bottleneck frames a good representation as one that keeps label-relevant bits while compressing away the rest.
The information bottleneck (IB) principle says a useful representation T of input X should maximize I(T; Y) — information about the label — while minimizing I(T; X) — information retained about the input. The objective is to minimize I(T; X) - beta * I(T; Y), trading compression against prediction, with beta tuning the balance. Applied to deep networks, IB interprets each layer as squeezing the input through a bottleneck that discards nuisance detail and preserves what predicts Y; some theories describe a 'compression phase' late in training where I(T; X) drops while accuracy holds. While the empirical details are debated, IB gives a clean information-theoretic lens on generalization (less retained input information can mean less overfitting) and unifies the course's themes: entropy, mutual information, and the compression-versus-prediction trade-off.
Worked Example 1
Problem. Write the information bottleneck objective and identify the role of beta.
Answer. L = I(T;X) - beta*I(T;Y); beta sets the compression-vs-prediction trade-off
Worked Example 2
Problem. Two representations: A has I(T;X)=5 bits, I(T;Y)=2 bits; B has I(T;X)=3 bits, I(T;Y)=2 bits. With beta=1, which is preferred?
Answer. B (lower IB objective: keeps I(T;Y)=2 but compresses X more)
Worked Example 3
Problem. Explain in IB terms why discarding input information can improve generalization.
Answer. Compressing away input-specific detail (low I(T;X)) while keeping I(T;Y) curbs overfitting
Problem. Using the information bottleneck objective minimize I(T;X) - beta*I(T;Y) with beta = 2, compare representation P (I(T;X)=6, I(T;Y)=3) with representation Q (I(T;X)=4, I(T;Y)=2.5). Which is preferred?
Solution. Compute the objective L = I(T;X) - beta*I(T;Y) for each (lower is better). For P: L_P = 6 - 2*3 = 6 - 6 = 0. For Q: L_Q = 4 - 2*2.5 = 4 - 5 = -1. Since -1 < 0, representation Q has the lower (better) objective: it compresses the input more (4 vs 6 bits) while giving up only a little label information (2.5 vs 3 bits), and with beta = 2 that trade-off pays off. Answer: representation Q is preferred (L_Q = -1 < L_P = 0).
Take a small labeled dataset with one categorical feature and a binary target. In NumPy, compute the target's entropy before any split, then the weighted average entropy of the target within each feature value (the conditional entropy). Report the information gain as the difference, and confirm it equals the mutual information between the feature and the target. Repeat for a second, less informative feature and explain which split a decision tree would prefer and why.
Deliverable · A script reporting the parent entropy, each feature's information gain, the matching mutual information, and a one-line justification of the preferred split.
1. Training a classifier with cross-entropy loss is equivalent to:
Answer B. Minimizing cross-entropy (negative log likelihood) is the same as maximizing the likelihood the model assigns to the observed labels.
2. A decision tree chooses a split that maximizes information gain, which is:
Answer B. Information gain is parent entropy minus the weighted child entropy — the mutual information between feature and target — so the tree picks the most informative split.
3. In variational inference, the KL divergence term in the ELBO serves to:
Answer B. Variational methods minimize a KL divergence so the tractable approximation stays close to the true posterior; the ELBO's KL term enforces this.
4. Maximum likelihood estimation can be viewed as minimizing the KL divergence between:
Answer B. Maximizing likelihood minimizes D_KL(data || model), pulling the model distribution toward the empirical distribution of the observed data.
5. The information bottleneck principle describes a good learned representation as one that:
Answer B. The information bottleneck seeks representations that retain information about the target while discarding nuisance detail from the input, trading compression against prediction.
I can explain how cross-entropy loss and maximum likelihood both reduce to minimizing KL divergence.
I can compute information gain for a decision-tree split and rank features by mutual information.
I can describe the role of KL divergence in variational inference and the information bottleneck.
Where this leads
Part of the open-source Crunch Academy tech-education path. Pair it with the data-science and ML tracks when you're ready.
All Math for Data Science courses Crunch Academy home