Estimation: maximum likelihood and Bayesian updating

So far the course has studied two kinds of unsupervised learning. Representation learning found good representations with PCA, for linear relationships between features (Part 3), and with kernel PCA for non-linear ones (Part 5). Clustering grouped the points with Lloyd's algorithm, K-means (Parts 6 and 7).

None of these methods assumed anything about how the data was produced. Estimation does. It assumes a probabilistic model: some random mechanism that generated the data. We are still in unsupervised learning and still have only data, but the methods move from deterministic procedures to probability. The lecture adds that the same tools will be useful for supervised learning later in the course.

The hypothesis, at a high level: 2:30

• Some probabilistic mechanism generates the data.
• Something about this mechanism is unknown to us.
• Given the data, find (estimate) what is unknown.

The lecture's picture is a black box with a button on top. Inside is a coin that need not be fair: the chance of heads is some value \(p\), perhaps 0.7 or 0.9, which we do not know. Each press of the button flips the coin and shows the outcome, written 1 for heads and 0 for tails. Four presses might give 1, 0, 1, 1. These are our observations.

Keep two sides apart. The observations are what we see. The box is a story we assume in order to explain them. It may or may not be true of the real world; for now we make the assumption and work with it, and the lecture postpones the question of how good such assumptions are. Within the story, the bias \(p\) is the unknown parameter.

The parameter is a compressed representation of the data. A thousand 0/1 values are explained by one number: if we knew \(p\), we would know the mechanism that produced them. This is the course's comprehension is compression theme from Part 2 in a new form.

Twelve presses give

The model says each observation is a random variable \(x\) with \(P(x = 1) = p\) and \(P(x = 0) = 1 - p\). What would you guess for \(p\)? The natural guess counts heads. There are 9 ones and 3 zeros out of 12, so

With an estimate in hand we can build our own box, a coin with bias 3/4, and generate as many observations as we like 10:59. The data mattered only because it told us about the mechanism. Once the parameter is fixed, we no longer need the data.

But 3/4 is a guess. As soon as probabilities enter, we can never be fully sure we have the true \(p\). Which values could have produced these twelve tosses?

So the only values we can rule out are 0 and 1 13:48. Every \(p\) strictly between them remains a contender, and still we chose 3/4. The lecture asks which assumptions went into that choice.

Write the observations as \(x_1, x_2, \dots, x_n\), each 0 or 1. Two assumptions are almost always made about data like this, usually without saying so.

Independent L19 · 16:41

Knowing one outcome does not change the probability of another:

If the third toss was heads, our uncertainty about the fourth toss is unchanged. The same holds when we condition on any set of the other observations.

Identically distributed L19 · 17:44

The same coin is flipped every time. There is one box and we press it \(n\) times. Two different coins tossed once each are still independent, because the first result says nothing about the second, but they are not identically distributed: their biases may differ.

The standard abbreviation for the pair is i.i.d. Under these assumptions, is there a principled way to call one guess better than another? Can we argue that 2/3 beats 0.0001, or that 3/4 beats every other value? The fraction of heads is intuitive, but so far nothing more. Lecture 20 supplies the principle.

Take the four observations 1, 0, 1, 1. Put every candidate value of \(p\) from 0 to 1 on a horizontal axis and ask of each one: if this were the true bias, what is the chance of seeing exactly this data? Plot that chance against \(p\). The curve is 0 at \(p = 0\) and at \(p = 1\), which we already know cannot produce this data, and it peaks at \(p = 3/4\) 2:16. That is the same as the fraction of ones.

Fisher's principle of maximum likelihood turns this into a method. Among all the parameter values that could have generated the data, bet on the one under which the observed data is most probable. The idea is old, and the lecture treats it as a review for anyone who has met it in a statistics course.

Writing it down L20 · 3:56

The likelihood function is a function of the parameter, with the data held fixed:

Here \(x_1, \dots, x_n\) are the specific observed values, so the first line is the joint probability that the first toss came out as \(x_1\), the second as \(x_2\), and so on, if the bias is \(p\). Independence splits it into a product, and identical distribution puts the same \(p\) in every factor 5:05.

The compact form \(p^{x_i}(1-p)^{1-x_i}\) covers both outcomes at once. If \(x_i = 1\) it is \(p^1(1-p)^0 = p\); if \(x_i = 0\) it is \(p^0(1-p)^1 = 1-p\). For 1, 0, 1, 1:

That is the curve described above. Explore it below.

A hat marks a guess. The maximum likelihood (ML) guess is the value of \(p\) that maximizes \(L\):

Products are awkward to differentiate and sums are easy, so maximize the logarithm instead. This is safe because \(\log\) is monotonically increasing. If \(L(\hat p) > L(p)\) for every other \(p\), then \(\log L(\hat p) > \log L(p)\) as well, so the maximizer does not move. The log turns the product into a sum:

This log-likelihood is a concave function of \(p\), so the maximum is where its derivative is zero 9:29. The lecture leaves the derivative as an exercise:

Expanding the left side gives \(\sum x_i - p\sum x_i = pn - p\sum x_i\). The \(p\sum x_i\) terms cancel, leaving \(\sum x_i = pn\).

Check it on 1, 0, 1, 1. The derivative of \(p^3(1-p) = p^3 - p^4\) is \(3p^2 - 4p^3 = p^2(3 - 4p)\), which is zero at \(p = 3/4\). For the twelve tosses of L19, \(9/12 = 3/4\) as well.

The intuitive guess now has a principle behind it: choose the \(p\) that makes the observed data most probable. It quietly relied on both assumptions 11:09, independence to split the joint probability into a product and identical distribution to use one \(p\) in every factor.

Now let each \(x_i \in \mathbb{R}\), for example the heights of 100 people. A coin box can only produce 0s and 1s, so it cannot explain this data. We need a different box, which means a different probabilistic model. The simplest choice is a Gaussian 12:50:

To keep things simple, assume the variance \(\sigma^2\) is known and only the mean \(\mu\) is unknown 13:26. With real data we would not know the variance either, but the simplification makes the method clear.

First attempt: multiply probabilities L20 · 14:27

Copying the coin recipe gives \(L(\mu, \sigma^2;\, x_1, \dots, x_n) = P(x_1, \dots, x_n;\, \mu, \sigma^2) = \prod_i P(x_i;\, \mu, \sigma^2)\) by independence. Suppose the first height measured is 162.53 cm and we try \(\mu = 150\). What is the chance that a Gaussian with mean 150 produces exactly 162.53?

For a continuous distribution, probabilities belong to intervals. \(P(a \le X \le b)\) is the area under the density curve between \(a\) and \(b\) 15:32. A single value has zero width and so zero probability. Every factor of the product is 0, for every \(\mu\), however close to the data or far from it. A function that is 0 everywhere cannot tell one \(\mu\) from another, so there is nothing to maximize.

Fisher's fix: multiply densities

Fisher's proposal was to replace the probabilities by the probability density function (PDF). For independent data the joint density factorizes just as probabilities do:

Each factor is the height of the bell curve at \(x_i\) 18:45. It is not a probability, and it need not even lie between 0 and 1. But it is nonzero, and it is larger when \(\mu\) puts \(x_i\) near the peak, so it works as a proxy for the probability. This is also why the function is called a likelihood and not a probability: it is not strictly the probability of the data 19:47.

Same drill as before: take the logarithm. It is the natural log, so it cancels the exponential:

We maximize over \(\mu\). The first term does not contain \(\mu\), so it can be dropped. Since \(\sigma^2\) is a known constant, the factor \(\frac{1}{2\sigma^2}\) does not change the maximizer either:

The lecture leaves the remaining two steps as an exercise. Setting the derivative to zero gives \(2\sum_i (x_i - \mu) = 0\), so \(\sum_i x_i = n\mu\).

The sample mean may look like an obvious guess anyway, so why the machinery? Because the sample mean is the ML answer because we assumed a Gaussian. Suppose domain knowledge suggests a different model, say a Laplace distribution, which looks like a Gaussian with a sharper peak 22:32. Maximum likelihood then gives the sample median instead of the mean. The estimator is tied to the probabilistic model you assume, and the method adapts to that model because it works with the model's own density.

Standard context, not derived in the lecture: the Laplace density is proportional to \(e^{-|x - \mu|/b}\), so its log-likelihood is \(-\frac1b\sum_i |x_i - \mu|\) plus a constant. Maximizing it means minimizing the sum of absolute distances, which the median does.

1. Maximum likelihood, for any model
2. Assume a probabilistic model for the data, with unknown parameters \(\theta\).
3. Write down its probability (discrete data) or its PDF (continuous data).
4. Under i.i.d. data, the likelihood is the product over data points: \(L(\theta;\, x_1, \dots, x_n) = \prod_{i} f(x_i;\, \theta)\).
5. Take the logarithm, turning the product into a sum.
6. Maximize over \(\theta\), often by setting the derivative to zero. The maximizer is \(\hat\theta_{\text{ML}}\).

The method is simple and, more importantly, general. Once you have a model, you have an estimator. The resulting estimators need not be intuitive in advance. Here they matched intuition (the fraction of heads, the sample mean), which is reassuring, but the method still produces estimates when we have no intuition at all. That is why it is so popular in statistics and machine learning.

A statistics course would go on to prove good properties of the ML estimator, and in some well-defined senses show that no estimator can do better 24:41. This course takes it as a good estimator that gives reasonable guesses. The lecture ends with a question 25:53: is something besides the data often available in practice, and if so, can we do better than maximum likelihood?

Back to the coin box. Coin tosses are called Bernoulli trials: \(x_i \sim \text{Bernoulli}(p)\), meaning \(P(x_i = 1) = p\) for every \(i\). The setup is the same as before.

Now add one thing. Before you have seen any data, someone walks in and says, "I believe the bias p is somewhere close to 1." That is an English sentence, yet it carries information about the coin in the box. Other statements are possible, such as: \(p\) is either small or large, but certainly not near 0.5.

The lecture calls this domain knowledge, or a hunch, perhaps built from a practitioner's experience 3:50. It is a hunch about the parameter, not about the data, and it exists before a single data point is seen.

Maximum likelihood has no way to use it. Ask the ML method for a guess before any data arrives and it can say nothing, because it depends only on data 4:25.

Goal: codify a hunch about the parameters in precise mathematical form and build it into the estimation procedure. This leads to Bayesian modelling.

The approach is to treat the unknown parameter as a random variable and encode the hunch as a probability distribution over its possible values. Values we believe more get more weight. The lecture sketches three examples 7:22:

• \(p\) is close to 1: a density on \([0, 1]\) that peaks near 0.9.
• \(p\) is small or large, not near 0.5: a U-shaped density on \([0, 1]\), high at both ends and low in the middle 8:34.
• For a Gaussian mean \(\mu\): a bump around the value we think most likely.

In general, call the parameter \(\theta\). The hunch becomes a distribution \(P(\theta)\), the prior. When \(\theta\) is continuous, like \(p\) or \(\mu\), \(P(\theta)\) is a PDF whose support is the set of values \(\theta\) can take; for \(p\) that is \([0, 1]\). Its shape records our belief before we see data. To get the chance that \(\theta\) lies in some range, integrate the density over that range.

Then the data arrives and the belief must be updated. Suppose we believed \(p \approx 0.9\), so we expected mostly heads, but 1000 tosses come out with 900 tails. The data contradicts the belief and should pull it away. If instead the data agrees with the belief, it should strengthen it and make us more confident.

The updated hunch is again a distribution, now conditioned on the data: \(P(\theta \mid \text{data})\). Moving from the prior \(P(\theta)\) to the posterior \(P(\theta \mid \text{data})\) is the Bayesian way of doing things 13:32. You have a hunch, you see data, you update the hunch.

Where Bayes comes in

Bayes' theorem from school says \(P(A \mid B) = P(B \mid A)\,P(A)/P(B)\). Take \(A\) to be the parameter \(\theta\) and \(B\) the data \(x_1, \dots, x_n\):

The first factor in the numerator is the chance of the data when the parameter is \(\theta\), which is the likelihood from Lecture 20 16:14. The denominator is called the evidence: the chance of observing the data at all. It does not depend on \(\theta\).

The lecture's sketch

Start with a prior peaking at 0.9. Observe 10 tosses, 8 zeros and 2 ones. The likelihood alone points to \(2/10 = 0.2\) and the prior to 0.9, so the posterior lands somewhere between; the lecture's freehand sketch puts its peak near 0.27, a number made up for illustration. With the flipped data, nine 1s and one 0, data and hunch agree, and the posterior rises even more sharply at 0.9 19:09. Both cases are reproduced, with an actual prior, in the interactive figure further down.

For Bernoulli data the parameter is \(\theta = p\). How do we write a prior on it mathematically? We need a continuous distribution supported only on \([0, 1]\), since \(p\) is a probability. A Gaussian will not do, because it gives positive density to every real number. A good choice is the Beta distribution 20:16, which has two positive parameters \(\alpha\) and \(\beta\):

\(Z\) is a normalizing constant that does not depend on \(p\) and makes the density integrate to 1. What matters for us is the functional form: a power of \(p\) times a power of \(1 - p\).

The two parameters make it very flexible:

• \(\alpha = 2,\ \beta = 2\): the density is \(p(1-p)/Z\), symmetric and highest at 0.5. We believe the coin is roughly fair, but spread our bets.
• \(\alpha = 2,\ \beta = 5\): small \(\alpha\) and large \(\beta\) push the mass toward 0. We believe \(p\) is closer to 0 than to 1.
• \(\alpha = 0.5,\ \beta = 0.5\): U-shaped 23:38. The coin is biased one way or the other, but \(p\) is not near 0.5. This encodes the second hunch above.

Now apply posterior \(\propto\) likelihood \(\times\) prior. The likelihood is the Bernoulli likelihood from Lecture 20 and the prior is the Beta density:

Both factors are a power of \(p\) times a power of \(1 - p\), so the exponents simply add 25:20:

We write \(\propto\) because the evidence and the normalizing constant are left out. They are not needed, as the next step shows.

This has the same functional form as the prior. Any density on \([0, 1]\) of the form \(p^{a-1}(1-p)^{b-1}\) is a Beta density, so the posterior is a Beta distribution. Only its parameters have changed, and they now depend on both the prior's \(\alpha, \beta\) and the data. We never have to compute the posterior density point by point: knowing its two parameters gives us the whole function.

This convenience comes from the pairing 27:44. Another prior on \([0, 1]\) would still give a posterior when multiplied by the Bernoulli likelihood, and it might be useful, but it need not have the same form as the prior. Standard name: a prior whose posterior stays in the same family is called a conjugate prior. The Beta is conjugate to the Bernoulli.

Maximum likelihood uses only the counts: \(\hat p_{\text{ML}} = n_H/(n_H + n_T) = n_H/n\) 29:30. The Bayesian approach gives a whole distribution over \(p\). If we must commit to a single guess, there are several sensible choices.

The posterior mean

The expected value of a Beta\((\alpha, \beta)\) distribution is \(\alpha/(\alpha+\beta)\) 30:32. The posterior is Beta\((\alpha + n_H,\ \beta + n_T)\), so its mean is

The prior as ghost data

Compare this with \(n_H/n\). The posterior mean is exactly what maximum likelihood would give if, besides the \(n\) real tosses, we had \(\alpha + \beta\) extra pseudo-observations, which the lecture calls ghost data: \(\alpha\) ghost heads and \(\beta\) ghost tails. A Beta prior acts as if someone had already done \(\alpha + \beta\) experiments. If someone tells us they did 100 experiments and saw 80 heads and 20 tails, we can encode that as the prior Beta(80, 20) 32:18. The posterior then takes these ghost samples into account along with the real ones.

Maximum a posteriori (MAP)

Maximum likelihood picks the maximizer of the likelihood. The maximum a posteriori (MAP) estimator picks the maximizer of the posterior density, its mode, written \(\hat p_{\text{MAP}}\). For the Beta posterior it differs slightly from the posterior mean. The lecture does not write the formula; the standard result is that for \(a, b > 1\) the mode of Beta\((a, b)\) is \((a-1)/(a+b-2)\), so

Because we hold an entire distribution, the choice is ours 33:58: take its mode (MAP), its mean, or even draw samples from it and average them. Until we choose, the posterior is a belief over every possible value of \(p\) that does not commit to any single one.

The lecture calls these basic statistical ideas. Next they are put to work on a specific unsupervised learning problem. K-means assumed no probabilistic model for the data. With a reasonable model, maximum likelihood gives a probabilistic counterpart of K-means clustering: the Gaussian mixture model of Part 9. The lecture raises the same question for representation learning.

Both principles come back in supervised learning: maximum likelihood in the probabilistic view of regression (Part 11), Gaussian priors and ridge regression (Part 12), and generative classifiers such as naive Bayes (Part 14).

Estimation

Assuming a probabilistic model generated the data and using the data to guess its unknown parameters.

Probabilistic model

The assumed random mechanism (the box in the lecture's picture) behind the data, such as a coin with bias \(p\) or a Gaussian \(\mathcal{N}(\mu, \sigma^2)\).

i.i.d.

Independent (one outcome does not change the probability of another) and identically distributed (the same law, such as one \(p\), for every observation).

Likelihood function

\(L(\theta;\, x_1, \dots, x_n)\): the probability (or density) of the observed data, viewed as a function of the parameter.

Maximum likelihood estimator

\(\hat\theta_{\text{ML}} = \arg\max_\theta L(\theta;\, x_1, \dots, x_n)\), Fisher's principle. For coins, the fraction of heads.

Log-likelihood

\(\log L\). It has the same maximizer as \(L\) because log is increasing, and turns products into sums.

Bernoulli trial

A 0/1 outcome with \(P(x = 1) = p\): one coin toss.

Prior

\(P(\theta)\): a distribution over the parameter that encodes a hunch before any data is seen.

Posterior

\(P(\theta \mid \text{data}) \propto P(\text{data} \mid \theta)\,P(\theta)\): the hunch updated by the data.

Evidence

\(P(x_1, \dots, x_n)\), the denominator in Bayes' theorem. It does not depend on \(\theta\).

Beta distribution

Density \(\propto p^{\alpha-1}(1-p)^{\beta-1}\) on \([0, 1]\), with \(\alpha, \beta > 0\) and mean \(\alpha/(\alpha + \beta)\).

Conjugate prior

A prior whose posterior has the same form. Beta prior with Bernoulli data gives Beta\((\alpha + n_H, \beta + n_T)\).

Ghost data

Reading a Beta\((\alpha, \beta)\) prior as \(\alpha\) imaginary heads and \(\beta\) imaginary tails added to the real tosses.

MAP estimate

Maximum a posteriori: the value of \(\theta\) where the posterior density is highest (its mode).