Where We Are

• Last week: Bayes’ rule turned a prior and a likelihood into a posterior for an unknown.
• This week and next: maximum likelihood when part of the data is missing, the EM algorithm.
• The E-step of EM is Bayes’ rule, applied to the missing data.
• On the way: Shannon’s measure of information, which explains why EM works and returns later in Bayesian computation.

Probability and Likelihood

• The same expression \(p(X \mid \theta)\) answers two questions.
• Probability: \(\theta\) fixed, \(X\) random. A coin with \(\theta = 0.7\) gives 7 heads in 10 flips with probability \(\binom{10}{7}(0.7)^7(0.3)^3 = 0.267\).
• Likelihood: \(X\) fixed at what we observed, \(\theta\) varies: \(L(\theta; X) = p(X \mid \theta)\).
• Question: having seen 7 heads, which value do the data favor, \(\theta = 0.7\) or \(\theta = 0.3\)?

Likelihood Notation

• Probability is used for prediction and simulation; likelihood for estimation, inference, and model fitting.
• Capital \(L\) for the likelihood, script \(\ell\) for its logarithm, never a plain \(l\), which looks like 1 or I.
• Some texts write \(L(\theta \mid X)\); same meaning.

Why Logarithms

For independent data, \(L(\theta; X) = \prod_i p(x_i \mid \theta)\) and \(\ell(\theta; X) = \sum_i \log p(x_i \mid \theta)\).

• \(\log\) is increasing, so \(L\) and \(\ell\) have the same maximizer, still called the maximum likelihood estimate.

where \(x_i\): the \(i\)th observation.

Example: Normal Data

• \(x_1, \ldots, x_n \iid \Normal(\mu, \sigma^2)\): \[\ell(\mu, \sigma^2; X) = -\frac n2\log(2\pi) - \frac n2\log\sigma^2 - \frac{1}{2\sigma^2}\sum_{i=1}^n (x_i - \mu)^2\]
• Setting the two derivatives to zero: \(\hat\mu = \bar x\) and \(\hat\sigma^2 = \frac1n\sum_i (x_i - \bar x)^2\).

where \(\mu\), \(\sigma^2\): the mean and the variance; \(n\): the sample size; \(\bar x\): the sample mean.

A Likelihood Method

• As we use it, EM is a likelihood method: \(\theta\) is a fixed unknown constant, and we maximize \(\ell(\theta; X)\).
• No prior on \(\theta\), no posterior for \(\theta\).
• The only conditional distribution of an unknown in EM is that of the missing data given the observed data, by Bayes’ rule.
• Same likelihood, two uses: the Bayesian puts \(p(X \mid \theta)\) into Bayes’ rule; the frequentist maximizes it.

Where Missing Data Arise

• The common thread: incomplete information makes direct maximum likelihood hard.

Customer Segmentation

• An online retailer records, for each customer, the amount spent, the items purchased, and the visit frequency.
• Goal: customer segments for targeted marketing.
• The segment of each customer is not recorded.
• We need to estimate each segment’s characteristics, assign customers to segments, and handle the uncertainty in the assignments, all at once.
• We observe two continuous features, spending and visit frequency, for 150 simulated customers, 50 per segment; the segment labels are missing, and the data appear to cluster.

Customer Segments

The Missing-Data Problem

• Observed data \(X = (x_1, \ldots, x_n)\): what we measure.
• Latent data \(Z = (z_1, \ldots, z_n)\): what we wish we knew.
• Complete data \((X, Z)\).
• Complete-data likelihood, if we knew \(Z\): \(L_c(\theta; X, Z) = p(X, Z \mid \theta)\), often easy to maximize.
• Observed-data likelihood, what we have: \(L(\theta; X) = p(X \mid \theta) = \int p(X, Z \mid \theta)\,dZ\), usually hard.

where the integral is a sum when \(Z\) is discrete; \(\ell_c = \log L_c\) and \(\ell = \log L\).

Why Direct Maximization Fails

\[\frac{\partial}{\partial\theta}\,\ell(\theta; X) = \frac{\int \frac{\partial}{\partial\theta}\, p(X, Z \mid \theta)\,dZ}{\int p(X, Z \mid \theta)\,dZ}\]

where \(p(X, Z \mid \theta)\): the joint density of the observed and latent data; both integrals are over \(Z\).

• The integral stays in the denominator.
• Setting the gradient to zero usually gives coupled equations with no closed-form solution.
• With a high-dimensional \(Z\), even numerical integration is infeasible.
• The idea of EM: maximize a lower bound on \(\ell\) that is easier to work with, and iterate.

Convex Functions

• \(f\) is convex if \[f(\lambda x + (1 - \lambda)y) \le \lambda f(x) + (1 - \lambda) f(y) \quad \text{for all } x, y \text{ and } \lambda \in [0, 1].\]
• The chord between two points of the graph lies above the graph.
• Convex: \(x^2\), \(e^x\), \(|x|\), \(\max(0, x)\).
• Concave, the inequality reversed: \(\log x\).

where \(\lambda\): the weight on \(x\) in the average \(\lambda x + (1 - \lambda)y\).

A Convex Function and Its Chord

Jensen’s Inequality

where \(X\): a random variable with a finite mean (positive, for the \(\log\) question below).

• The function at the average is at most the average of the function, for a convex \(f\).
• It is the definition of convexity, with the weights \(\lambda\) and \(1 - \lambda\) replaced by probabilities.
• Question: \(\log\) is concave. Which is larger, \(\log\E[X]\) or \(\E[\log X]\)?

A Lower Bound on the Log-Likelihood

For any distribution \(q(Z)\) of the latent data, positive wherever \(p(X, Z \mid \theta)\) is, \[\ell(\theta; X) = \log\int \frac{p(X, Z \mid \theta)}{q(Z)}\,q(Z)\,dZ = \log\E_q\Bigl[\frac{p(X, Z \mid \theta)}{q(Z)}\Bigr] \ge \E_q\Bigl[\log\frac{p(X, Z \mid \theta)}{q(Z)}\Bigr] = \mathcal{L}(q, \theta).\]

where \(p(X, Z \mid \theta)\): the joint density of the observed and latent data; \(\E_q\): the expectation over \(Z\) distributed as \(q\).

• The inequality is Jensen’s, for the concave \(\log\).
• \(\mathcal{L}(q, \theta) = \E_q[\log p(X, Z \mid \theta)] - \E_q[\log q(Z)]\) is the evidence lower bound (ELBO).
• It holds for every \(q\).

When the Bound Is Tight

• Jensen’s inequality for the strictly concave \(\log\) is an equality only when the random variable is constant: \(p(X, Z \mid \theta)/q(Z) = c\).
• Then \(q(Z) = p(X, Z \mid \theta)/c\), and since \(q\) integrates to 1, \(c = p(X \mid \theta)\).
• So \(q(Z) = p(X, Z \mid \theta)/p(X \mid \theta) = p(Z \mid X, \theta)\), the posterior of the latent data.

• For any other \(q\), how far below \(\ell\) is the bound? Measuring that gap means measuring how far \(q\) is from the posterior: a question about information.

where \(c\): a constant, free of \(Z\); \(p(Z \mid X, \theta)\): the conditional distribution of the latent data given the observed data.

Shannon’s Question

• Claude Shannon, A Mathematical Theory of Communication (1948): how much information does a message carry, and how compactly can it be sent?
• His answer sets meaning aside: information is the reduction of uncertainty.
• A message that tells us what we already expected carries little information. A surprising one carries a lot.
• Surprise, entropy, cross-entropy, and the Kullback–Leibler divergence all measure information in this sense.

Information as Surprise

• Three requirements for the information \(I(p)\) of an event of probability \(p\):
  • Rare is informative: \(I(p)\) decreases as \(p\) increases.
  • Certain is uninformative: \(I(1) = 0\).
  • Independent information adds: \(I(p_1 p_2) = I(p_1) + I(p_2)\).
• Up to the choice of unit, the only continuous function with these properties is \[I(p) = -\log p:\] the logarithm turns the product of probabilities of independent events into a sum of information.

where \(p_1\), \(p_2\): the probabilities of two independent events, so \(p_1 p_2\) is the probability that both happen.

Bits

• With \(\log_2\) the unit is the bit, a word Shannon credits to John Tukey: \(I(p) = -\log_2 p\).
• One fair coin flip: \(-\log_2(1/2) = 1\) bit.
• One roll of a fair die: \(\log_2 6 = 2.58\) bits. One card from a shuffled deck: \(\log_2 52 = 5.70\) bits.
• Ten fair coin flips: \(-\log_2(1/1024) = 10\) bits, one per flip: information adds.
• With the natural logarithm the unit is the nat: 1 nat \(= 1/\log 2 \approx 1.44\) bits. Log-likelihoods are in nats.

The Surprise Curve

Entropy: Average Surprise

• Before we observe \(X\), the information we expect to receive is its entropy: \[H(X) = \E[-\log_2 p(X)] = -\sum_x p(x)\log_2 p(x).\]
• The entropy is the average surprise of \(X\), its uncertainty, in bits.
• A fair coin: 1 bit. A fair die: \(\log_2 6 = 2.58\) bits. A certain outcome: 0 bits.
• An outcome with \(p(x) = 0\) contributes 0, since \(p\log p \to 0\) as \(p \to 0\).

where \(p(x)\): the probability that \(X = x\).

The Entropy of a Coin

Low and High Entropy

Twenty Questions

Codes

• A code writes each outcome as a string of 0s and 1s. Here the codeword is the list of answers to the questions, yes \(= 0\) and no \(= 1\).
• No codeword begins another, a prefix code, so a stream of codewords decodes without separators.
• Short codewords for common outcomes, as in Morse code, where E is one dot and T one dash (Morse needs a pause between letters; a prefix code does not).
• Average length: \(1.75\) bits, the entropy.

Shannon’s Source Coding Theorem

• Entropy is the limit of lossless compression: it can be approached but not beaten.
• Huffman (1952) found the best prefix code for any distribution; his method is part of the compression in ZIP and PNG files.
• When every probability is a power of \(1/2\), as in our example, the best code meets the entropy exactly.

where \(H(X)\): the entropy of the outcome, in bits; prefix code: no codeword begins another.

Using the Wrong Code

• Every prefix code has \(\sum_x 2^{-l(x)} \le 1\) (Kraft’s inequality), so its lengths are \(l(x) = -\log_2 q(x)\) for some \(q\) with total at most 1: choosing a code is choosing a distribution.
• Outcomes come from \(P\), but the code was built for \(Q\): outcome \(x\) gets a codeword of length \(-\log_2 q(x)\).
• The average length is the cross-entropy \[H(P, Q) = -\sum_x p(x)\log_2 q(x) = \E_P[-\log_2 q(X)].\]
• For \(P = (1/2, 1/4, 1/8, 1/8)\): the code built for \(P\) averages 1.75 bits; the uniform code, 2 bits for every outcome, averages 2; the code built for \(Q = (1/8, 1/8, 1/4, 1/2)\) averages 2.625.

where \(l(x)\): the length of the codeword for \(x\); \(p\), \(q\): the probabilities under \(P\) and \(Q\); \(\E_P\): the expectation with \(X\) distributed as \(P\).

Extra Bits

Relative Entropy

\[\mathrm{KL}(P \,\|\, Q) = H(P, Q) - H(P) = \sum_x p(x)\log_2\frac{p(x)}{q(x)}\]

• The average number of extra bits paid for coding data from \(P\) with a code built for \(Q\).
• Zero when \(Q = P\), and never negative (Gibbs’ inequality): no prefix code averages fewer bits on data from \(P\) than the entropy \(H(P)\).
• It compares two distributions, which is what the gap in EM’s bound needs.

where \(H(P, Q)\): the cross-entropy; \(H(P)\): the entropy of \(P\); \(p\), \(q\): the probabilities under \(P\) and \(Q\).

What Shannon Changed

• Communication: every noisy channel has a capacity; below it, error-correcting codes make transmission as reliable as we like. They run phones, Wi-Fi, CDs, and deep-space probes.
• Compression: entropy is the limit of lossless compression. Entropy coding is inside ZIP and PNG, and inside the lossy JPEG and MP3 formats.
• Statistics: Kullback and Leibler (1951) brought Shannon’s measure into statistics as a divergence between distributions; Akaike (1973) built AIC on it.
• Machine learning: logistic-regression and neural-network classifiers are trained by minimizing a cross-entropy, their negative log-likelihood; variational inference minimizes a KL divergence by maximizing an ELBO.

Likelihood Is Code Length

• The negative log-likelihood \(-\ell(\theta; X) = -\sum_i \log p(x_i \mid \theta)\) is the total surprise of the data under the model. For discrete data it is their code length, in nats, under a code built for the model.
• Within a model, maximum likelihood picks the parameter value whose code compresses the data best.
• If \(P\) generates the data, then as \(n\) grows \[-\frac1n\,\ell(\theta; X) \to H(P, Q_\theta) = H(P) + \mathrm{KL}(P \,\|\, Q_\theta).\]
• \(H(P)\) does not involve \(\theta\), so maximizing likelihood minimizes \(\mathrm{KL}(P \,\|\, Q_\theta)\), the divergence of the model from \(P\).

where \(Q_\theta\): the model distribution, with density \(q_\theta(x) = p(x \mid \theta)\); \(x_1, \ldots, x_n\): independent draws from \(P\); \(H\) and \(\mathrm{KL}\) in nats here, since \(\ell\) uses the natural logarithm (for continuous data \(H(P)\) is the differential entropy); the limit is the law of large numbers.

Divergences

• We need to measure how different two distributions are: how far an approximate posterior is from the true one, how much information is lost using one distribution in place of another.
• A divergence \(D(P \,\|\, Q)\) satisfies \(D(P \,\|\, Q) \ge 0\), with \(D(P \,\|\, Q) = 0\) if and only if \(P = Q\).
• Unlike a distance, it need not be symmetric and need not satisfy the triangle inequality.

where \(p\), \(q\): the densities of \(P\) and \(Q\).

The KL Divergence

\[\mathrm{KL}(P \,\|\, Q) = \int p(x)\log\frac{p(x)}{q(x)}\,dx = \E_P\Bigl[\log\frac{p(X)}{q(X)}\Bigr]\]

where \(p\), \(q\): the densities of \(P\) and \(Q\); \(\E_P\): the expectation with \(X\) distributed as \(P\); \(\log\): the natural logarithm, so KL is in nats (divide by \(\log 2\) for bits).

• Also called the relative entropy. Direction matters: \(\mathrm{KL}(P \,\|\, Q)\) averages under \(P\).

Gibbs’ Inequality

• By Jensen for the concave \(\log\): \(\mathrm{KL}(P \,\|\, Q) = -\E_P[\log(q/p)] \ge -\log\E_P[q/p] = -\log\int_{p > 0} q \ge -\log 1 = 0\).
• In coding terms: on data from \(P\), a code built for \(Q\) costs at least \(H(P)\) bits per outcome, the cost of the code built for \(P\).
• A consequence: with \(Q\) uniform on \(K\) outcomes, \(\mathrm{KL}(P \,\|\, Q) = \log_2 K - H(P) \ge 0\) bits, so no distribution on \(K\) outcomes has entropy above \(\log_2 K\).

where \(p\), \(q\): the densities (or probabilities) of \(P\) and \(Q\); the integral runs over the values where \(p > 0\).

Two Examples

• Two normals: for \(P = \Normal(\mu_1, \sigma_1^2)\) and \(Q = \Normal(\mu_2, \sigma_2^2)\), \[\mathrm{KL}(P \,\|\, Q) = \log\frac{\sigma_2}{\sigma_1} + \frac{\sigma_1^2 + (\mu_1 - \mu_2)^2}{2\sigma_2^2} - \frac12.\]
• For the normals: write out \(\log(p/q)\), take its expectation under \(P\), and use \(\E_P[X] = \mu_1\) and \(\E_P[X^2] = \sigma_1^2 + \mu_1^2\).
• Two Bernoullis: for \(P = \Ber(a)\) and \(Q = \Ber(b)\), the binary KL divergence, common in information theory and machine learning, \[\mathrm{KL}(P \,\|\, Q) = a\log\frac{a}{b} + (1 - a)\log\frac{1 - a}{1 - b}.\]

where \(\mu_1, \mu_2\): the means; \(\sigma_1^2, \sigma_2^2\): the variances; \(a\), \(b\): the success probabilities; \(p\), \(q\): the densities of \(P\) and \(Q\).

KL Divergence Between Two Normals

KL Divergence in Statistical Inference

• Model selection: for a model \(Q_\theta\) of the true \(P\), \[\mathrm{KL}(P \,\|\, Q_\theta) = \E_P[\log p(X)] - \E_P[\log q_\theta(X)],\] so minimizing the divergence over \(\theta\) maximizes the expected log-likelihood.
• Variational inference: approximate an intractable posterior \(p(z \mid x)\) by the \(q\) in a tractable family that minimizes \(\mathrm{KL}\bigl(q \,\|\, p(\cdot \mid x)\bigr)\), the basis of variational Bayes and variational EM.

where \(p\), \(q_\theta\): the densities of \(P\) and \(Q_\theta\); \(z\), \(x\): the latent and the observed data.

Back to EM’s Bound

\[\mathcal{L}(q, \theta) = \E_q[\log p(X, Z \mid \theta)] - \E_q[\log q(Z)] = \underbrace{\E_q[\log p(X, Z \mid \theta)]}_{\text{fit}} + \underbrace{H(q)}_{\text{entropy of } q}\]

• The ELBO is the expected log joint plus the entropy of \(q\): fit rewards concentrating \(q\) where the joint density is high, entropy rewards spreading it out.
• Remember our lower bound? The gap is exactly a KL divergence: \(\ell(\theta; X) - \mathcal{L}(q, \theta) = \mathrm{KL}\bigl(q(Z) \,\|\, p(Z \mid X, \theta)\bigr)\).
• So Gibbs’ inequality is the bound: \(\ell(\theta; X) \ge \mathcal{L}(q, \theta)\), with equality exactly when \(q = p(Z \mid X, \theta)\). The posterior is the \(q\) that balances fit and entropy best.

where \(H(q) = -\E_q[\log q(Z)]\): the entropy of \(q\), in nats (for a continuous \(Z\), the differential entropy \(-\int q(z)\log q(z)\,dz\), which can be negative).

Notation

Punchlines, and What Comes Next

• With latent data the log-likelihood is the log of an integral, \(\ell(\theta; X) = \log\int p(X, Z \mid \theta)\,dZ\), and setting its gradient to zero rarely has a closed-form solution.
• Jensen’s inequality gives a lower bound for every \(q\), \(\ell(\theta; X) \ge \mathcal{L}(q, \theta)\), tight exactly when \(q\) is the posterior \(p(Z \mid X, \theta)\).
• Information is surprise, \(-\log p\). Entropy is average surprise and the limit of lossless compression.
• The KL divergence is the extra length paid for coding with the wrong distribution, and Gibbs’ inequality says it is never negative.
• In the limit, maximizing the likelihood minimizes \(\mathrm{KL}(P \,\|\, Q_\theta)\), and the gap in EM’s bound is a KL divergence.

The log of an integral is what makes these likelihoods hard. Jensen’s inequality trades it for an average of logs, at the price of a gap, and information theory says exactly what the gap is.

Maximum Entropy

• On \(K\) outcomes, the uniform distribution has the largest entropy, \(\log_2 K\): it assumes nothing beyond the list of outcomes.
• Among densities with a given variance \(\sigma^2\), the normal has the largest differential entropy, \(\frac12\log_2(2\pi e\sigma^2)\) bits.
• The maximum entropy principle (Jaynes, 1957): given what we know, as constraints, choose the distribution with the largest entropy. It adds no information we do not have.

where the differential entropy of a density \(p\) is \(-\int p(x)\log_2 p(x)\,dx\); \(\sigma^2\): the variance.

Surprise Is Energy

• Write any positive density as \(p(x) = e^{-E(x)}/\mathcal{Z}\), with \(\mathcal{Z} = \int e^{-E(x)}\,dx\). Then \(-\log p(x) = E(x) + \log\mathcal{Z}\): surprise is energy, up to a constant.
• Low energy, high probability; high energy, rare.
• In physics, \(p_T(x) = e^{-E(x)/T}/\mathcal{Z}_T\) is the Boltzmann distribution at temperature \(T\). Among all distributions with the same average energy as \(p_T\), it has the largest entropy.
• Hamiltonian Monte Carlo writes the posterior as \(\pi(\theta \mid X) \propto e^{-U(\theta)}\), with potential energy \(U(\theta) = -\log[L(\theta; X)\,\pi(\theta)]\).

where \(E(x)\): the energy of state \(x\); \(\mathcal{Z}\), \(\mathcal{Z}_T\): the normalizing constants; \(T > 0\): the temperature, in units where Boltzmann’s constant is 1; \(L(\theta; X)\): the likelihood; \(\pi(\theta)\): the prior.

Temperature