Maximum Likelihood with Complete Data

Everything so far has taken a probability model as given: a network with its tables filled in, a Gaussian with its mean and variance. Someone had to supply those numbers. This lesson is about where they come from when every variable in the model is observed - the case that turns out to be almost embarrassingly easy, and whose ease is worth understanding before the next lesson takes it away.

The likelihood of a data set

Fix a model with parameters $\theta$. The likelihood of a data set $\mathbf{d} = d_1, \ldots, d_N$ is the probability the model assigns to exactly those observations. If the examples are independent given the parameters, that probability is a product:

$$P(\mathbf{d} \mid h_\theta) = \prod_{j=1}^{N} P(d_j \mid h_\theta).$$

The maximum-likelihood estimate is the $\theta$ that makes this largest. Note what has been assumed away: no prior over $\theta$ appears, so every parameter value is treated as equally plausible before the data arrives. That is a deliberate choice, and the next lesson is about what it costs.

Three steps

A candy manufacturer sells bags with an unknown proportion $\theta$ of cherry candies, the rest lime. You unwrap 25 and find 18 cherry. What is $\theta$?

Step one, write the likelihood. With $c = 18$ cherries and $\ell = 7$ limes,

$$P(\mathbf{d} \mid h_\theta) = \theta^{c} \, (1 - \theta)^{\ell} = \theta^{18} (1 - \theta)^{7}.$$

Step two, take logs and differentiate. The logarithm turns the product into a sum, which is what makes the derivative tractable:

$$L(\mathbf{d} \mid h_\theta) = c \log \theta + \ell \log(1 - \theta), \qquad \frac{dL}{d\theta} = \frac{c}{\theta} - \frac{\ell}{1 - \theta}.$$

Step three, set it to zero. That gives $c(1-\theta) = \ell\theta$, so

$$\theta = \frac{c}{c + \ell} = \frac{c}{N} = \frac{18}{25} = 0.72 .$$

The maximum-likelihood hypothesis says the proportion of cherries in the bag equals the proportion observed. A grid search over two million values of $\theta$ agrees to six decimal places, and the log likelihood there is $-14.823833$, against $-14.847959$ at $\theta = 0.70$ and $-14.849407$ at $\theta = 0.74$.

It is fair to feel cheated. Considerable machinery has produced the answer any sensible person would have written down immediately. The point is not the answer; it is that the same three steps keep working when no sensible answer suggests itself.

Why taking the logarithm is safe

Two justifications, and both matter. Mathematically, $\log$ is strictly increasing, so it does not move the location of a maximum - only its height. Computationally, a product of thousands of probabilities underflows to zero in floating point while a sum of thousands of logarithms does not. Real implementations work in log space for the second reason long after the first has been forgotten.

Many parameters at once

Now suppose the candies also have a wrapper, red or green, chosen with a probability that depends on the flavour. The model has three parameters: $\theta$ for the flavour, $\theta_1 = P(\text{red} \mid \text{cherry})$, and $\theta_2 = P(\text{red} \mid \text{lime})$. Our 25 candies break down as 12 cherry-red, 6 cherry-green, 2 lime-red, 5 lime-green.

The likelihood is a product over four kinds of candy, and its logarithm is

$$L = 12 \log(\theta\theta_1) + 6 \log(\theta(1 - \theta_1)) + 2 \log((1 - \theta)\theta_2) + 5 \log((1 - \theta)(1 - \theta_2)).$$

Expand the logarithms of the products and something useful happens: every term mentioning $\theta_1$ mentions nothing else. The three partial derivatives are therefore independent equations, and each one is the one-parameter problem solved again:

$$\theta = \frac{18}{25} = 0.72, \qquad \theta_1 = \frac{12}{18} = 0.666667, \qquad \theta_2 = \frac{2}{7} = 0.285714 .$$

Running Nelder–Mead on the full three-parameter likelihood lands within $1.4 \times 10^{-8}$ of those values, at a log likelihood of $-30.468975$.

This decoupling is the reason learning a Bayesian network from complete data is cheap. Each conditional probability table is fitted by counting within its own conditioning case, independently of every other table, with no search and no iteration. It is worth naming the condition that makes it true: the data must be complete, every variable observed in every example. Break that and the terms stop separating, which is precisely the difficulty the third lesson confronts.

The separation is easier to believe once it is on screen as three numbers. The figure below shows the log likelihood split into its three terms, one per parameter. Push theta1 to either extreme and the flavour term does not shift by a digit, which is why the theta that maximises the total cannot move either.

The second preset is the failure at the end of this lesson, and it breaks in two ways rather than one. After a single cherry candy the flavour estimate is 1, so lime is impossible. But theta2 is worse off than that: its term is zero for every value, so an unobserved conditioning case leaves a whole row of the table undetermined rather than badly determined. Starting every count at one repairs both, which is where the next lesson begins.

The continuous case

The recipe does not care whether the variable is discrete. For $N$ observations from a Gaussian with unknown mean $\mu$ and standard deviation $\sigma$,

$$L = N\left(-\log\sqrt{2\pi} - \log\sigma\right) - \sum_{j=1}^{N} \frac{(x_j - \mu)^2}{2\sigma^2},$$

and setting the two partial derivatives to zero gives

$$\mu = \frac{\sum_j x_j}{N}, \qquad \sigma = \sqrt{\frac{\sum_j (x_j - \mu)^2}{N}} .$$

The sample mean and - note the denominator - the root mean squared deviation about it. On ten measurements summing to 51.0 with squared deviations summing to 3.98, that is $\mu = 5.1$ and $\sigma = 0.630872$, where dividing by $N - 1$ instead would have given $0.664998$. The two differ by the factor $\sqrt{N/(N-1)} = 1.054093$.

Which is right? Both, for different questions. Dividing by $N$ genuinely maximises the likelihood; dividing by $N-1$ genuinely gives an unbiased estimator of the population variance. Maximum likelihood was never asked to be unbiased, and it isn't. Being clear about which criterion is in force saves a great deal of confusion.

There is a bonus in this derivation. Fit a linear Gaussian model - $y$ normal about $\theta_1 x + \theta_2$ with fixed variance - and the only part of the log likelihood that depends on the parameters is $-\sum_j (y_j - \theta_1 x_j - \theta_2)^2$. Maximising it is minimising the sum of squared errors. Least squares is not a convenient loss chosen by tradition; it is maximum likelihood under Gaussian noise.

The failure that is coming

Unwrap one candy, find it cherry, and the recipe reports $\theta = 1/1 = 1$: the bag is entirely cherry, and a lime candy is impossible. Not unlikely - impossible, with probability exactly zero, a claim no amount of subsequent evidence can be multiplied back out of.

This is not an artefact of small samples in general; it is what maximum likelihood does with any event it has not yet seen. It reads "not observed" as "cannot happen". The standard field repair is to initialise every count at one instead of zero, which sounds like a hack and turns out, in the next lesson, to be a prior in disguise.

Before the quiz

Three steps: write the likelihood, differentiate the log, set it to zero. With complete data the parameters separate, so fitting a whole network is a set of independent counting problems. The Gaussian case gives the sample mean and a standard deviation divided by $N$, and it explains why least squares is the right loss for Gaussian noise. And the whole apparatus assigns probability zero to whatever it has not yet seen.