← All notes · ML revision (DA5400)
Introduction to Estimation
Until now, PCA and K-means worked directly on the data, with no story about where it came from. This lecture adds that story: assume some random process generated the data, admit that part of the process is unknown, and use the data to estimate the unknown part.
Source: L19 on YouTube (≈20 min). Sections marked Going further go beyond what the video covers.
1 · The shift: from methods to models
Everything in the unsupervised part of the course so far was deterministic. You run PCA or Lloyd's algorithm on the points, and they hand back directions or clusters. Nowhere did we say how the points came to exist.
Estimation changes the starting point. We hypothesise that the data was produced by a probabilistic mechanism. We know its shape, but some of its details are unknown. Those unknown details are what we try to recover. We're still in unsupervised learning (there are no labels), but now probability is part of the picture. The same ideas will later carry over to supervised learning too.
2 · The black box with a button
The lecture's running example: a sealed box with a button on top. Inside is a coin that may be biased. Its chance of heads is some number $p$ that could be 0.5, 0.7, 0.9 or anything else. Each press flips the coin once. You never see the coin; you only see the outcome, written as 1 for heads and 0 for tails.
The box below has a secret $p$ picked at random when the page loaded. Press the button and watch the observations pile up.
The line is the fraction of 1s so far. Early on it jumps around. As n grows it settles down, close to the hidden p once you reveal it.
3 · What estimation is, precisely
① Observe
You're given data $x_1, \dots, x_n$. Here, a list of 0s and 1s.
② Assume a model
You assume a probabilistic mechanism that generated it. Here, a coin with $P(x=1)=p$ and $P(x=0)=1-p$. This is an assumption. The real world may not work this way.
③ Estimate
Use the data to make a guess $\hat p$ (read "p-hat") for the unknown parameter $p$.
The lecturer stresses the word assume repeatedly. The model is a story we tell to explain the data. Whether it's a good story is a separate question, to be tackled later. Everything that follows is "correct" only relative to the assumed model.
In symbols, this coin model is the Bernoulli distribution:
$$P(x;\,p)=p^{x}(1-p)^{1-x},\qquad x\in\{0,1\},\quad p\in[0,1].$$Plug in $x=1$ to get $p$, and $x=0$ to get $1-p$. One formula covers both cases, which will be handy once we start multiplying probabilities together.
4 · Making a guess, then "playing God"
The lecture uses these 12 observations:
There are 9 ones and 3 zeros. The guess almost everyone makes is the fraction of heads:
$$\hat p=\frac{\text{number of 1s}}{n}=\frac{9}{12}=\frac34 .$$Once you have $\hat p$, you can build your own box with a coin of bias $3/4$ and generate as much new data as you want. The lecturer calls this "playing God". The data's only job was to tell you about the mechanism. Once you think you know the mechanism, the data has done its job.
Your box: a coin with p̂ = 3/4
Each press of the button below generates a fresh batch of 12 tosses from your estimated box.
Notice that batches from a $3/4$ coin often contain 8, 10 or 11 heads rather than exactly 9. That's the first hint of the next idea: $\hat p$ is a guess, not the truth. Once probability is involved, you can never be 100% sure you've found the true $p$.
5 · Almost every p could have produced this data
Could a coin with $p = 2/3$ have produced 9 heads in 12 tosses? Yes, easily. What about $p = 0.0001$? Also yes. It would take an astonishingly unlucky day, but the probability isn't zero. The only values ruled out with certainty are the two extremes:
- $p = 0$ means the coin never lands heads. But we saw heads, so this is impossible.
- $p = 1$ means the coin always lands heads. But we saw tails, so this is impossible too.
Every $p$ strictly between 0 and 1 remains a contender. Drag the slider to see how probable our exact 12 observations are under each candidate.
Curve: $P(\text{data}\mid p)=p^{9}(1-p)^{3}$. That's the product of the 12 individual probabilities, one factor of $p$ for each 1 and one factor of $(1-p)$ for each 0. Multiplying them is allowed because of the independence assumption in section 6.
6 · The hidden assumptions: i.i.d.
Why did "fraction of heads" feel so natural? Because we silently assumed two things about the observations. Together they're called i.i.d., short for independent and identically distributed.
Independent
Knowing one toss tells you nothing about another:
$$P(x_i = a \mid x_j = b) = P(x_i = a)\quad\text{for all } i\ne j .$$Hearing that toss 3 was heads doesn't change your uncertainty about toss 4. This holds for any set of other tosses, not just one.
Identically distributed
Every toss follows the same law:
$$P(x_i = 1) = P(x_j = 1) = p\quad\text{for all } i, j .$$It's the same coin, in the same box, every time. Swapping to a different coin between presses could keep tosses independent, but they would no longer be identically distributed.
To see what each assumption buys you, compare three boxes. Each produces 60 tosses whose long-run fraction of heads is 0.5. Only the first is i.i.d.
A. i.i.d. (one fair coin)
B. Independent but not identical (the coin is swapped halfway)
C. Identical but not independent (a "sticky" coin)
- Box B uses a 0.2 coin for the first 30 tosses and a 0.8 coin for the rest. A single "$\hat p$" averages two different coins and describes neither.
- Box C repeats its previous outcome 85% of the time and otherwise tosses a fair coin. Each toss on its own has the same 50/50 law, but the tosses come in long runs. With dependent tosses, 60 of them carry much less information than 60 independent ones, so the fraction of heads wanders much more from one batch of 60 to the next.
7 · The question the lecture ends on
Under the i.i.d. assumption, every $p\in(0,1)$ could still have produced the 12 observations. So why prefer $3/4$ over $2/3$ or $0.0001$? "Use the fraction of heads" is intuitive, but so far it isn't principled.
8 · Going further: estimation in ℝᵈ
8.1 The general setup
A parametric model is a family of distributions indexed by a parameter vector:
$$\{\,p(x;\theta)\;:\;\theta\in\Theta\subseteq\mathbb R^{k}\,\},\qquad x\in\mathbb R^{d}.$$For the coin, $d = 1$, $k = 1$ and $\theta = p \in [0, 1]$. An estimator is any function of the data, $\hat\theta = T(x_1,\dots,x_n)$. "Fraction of heads" is one estimator; "always say 0.5" is another, worse one.
8.2 What i.i.d. gives you: the joint probability factorises
Independence turns the joint probability of all $n$ observations into a product. Identical distribution makes every factor the same function $p(\cdot\,;\theta)$:
$$p(x_1,\dots,x_n;\theta)\;\overset{\text{indep.}}{=}\;\prod_{i=1}^{n}p_i(x_i;\theta)\;\overset{\text{identical}}{=}\;\prod_{i=1}^{n}p(x_i;\theta).$$For the coin, with $h=\sum_i x_i$ heads:
$$P(x_1,\dots,x_n;p)=\prod_{i=1}^{n}p^{x_i}(1-p)^{1-x_i}=p^{\,h}(1-p)^{\,n-h}.$$That is exactly the curve from section 5, with $h = 9$ and $n = 12$. Notice that it depends on the data only through $h$. The count of heads is all you need; the order doesn't matter.
8.3 Preview: the principled answer (maximum likelihood)
Treat the joint probability as a function of $\theta$ with the data held fixed. This is the likelihood $L(\theta)$. Choose the $\theta$ that maximises it. Since the logarithm is increasing, maximise the sum $\ell(\theta)=\log L(\theta)$ instead of the product:
$$\ell(p)=h\log p+(n-h)\log(1-p),\qquad \frac{d\ell}{dp}=\frac{h}{p}-\frac{n-h}{1-p}=0\;\Longrightarrow\;\boxed{\hat p=\frac{h}{n}} .$$The second derivative, $-h/p^2-(n-h)/(1-p)^2$, is negative, so this is a maximum. The "intuitive" fraction of heads turns out to be the maximum-likelihood estimate. With $h=9$ and $n=12$, it's $3/4$, the peak of the curve in section 5.
8.4 The same idea in d dimensions: the Gaussian
Let $x_i\in\mathbb R^d$ be i.i.d. from a multivariate Gaussian with unknown mean $\mu\in\mathbb R^d$ and covariance $\Sigma\in\mathbb R^{d\times d}$ (symmetric and positive definite):
$$p(x;\mu,\Sigma)=\frac{1}{(2\pi)^{d/2}|\Sigma|^{1/2}}\exp\!\Big(-\tfrac12(x-\mu)^{\top}\Sigma^{-1}(x-\mu)\Big).$$The log-likelihood of $n$ points is
$$\ell(\mu,\Sigma)=-\frac{nd}{2}\log 2\pi-\frac n2\log|\Sigma|-\frac12\sum_{i=1}^{n}(x_i-\mu)^{\top}\Sigma^{-1}(x_i-\mu).$$Mean. Use $\nabla_v\,(v^{\top}Av)=2Av$ for symmetric $A$. Then
$$\nabla_\mu\ell=\Sigma^{-1}\sum_{i=1}^{n}(x_i-\mu)=0\;\Longrightarrow\;\hat\mu=\frac1n\sum_{i=1}^{n}x_i .$$Covariance. Write $\Lambda=\Sigma^{-1}$, so $-\tfrac n2\log|\Sigma| = \tfrac n2\log|\Lambda|$, and $\sum_i(x_i-\mu)^{\top}\Lambda(x_i-\mu)=\operatorname{tr}(\Lambda S)$ with $S=\sum_i(x_i-\hat\mu)(x_i-\hat\mu)^{\top}$. Using $\partial\log|\Lambda|/\partial\Lambda=\Lambda^{-1}$ and $\partial\operatorname{tr}(\Lambda S)/\partial\Lambda=S$:
$$\frac n2\Lambda^{-1}-\frac12 S=0\;\Longrightarrow\;\hat\Sigma=\frac1n\sum_{i=1}^{n}(x_i-\hat\mu)(x_i-\hat\mu)^{\top}.$$- $\hat\mu$ is the plain average. That's Fact 1 from L15: the mean minimises the sum of squared distances. Here it appears again as the most likely centre of a Gaussian.
- $\hat\Sigma$ is the covariance matrix whose eigenvectors PCA uses. PCA's principal directions are the axes of the fitted Gaussian's ellipse.
- In L18, K-means turned out to be maximum likelihood for spherical Gaussians with shared variance. Estimation is the framework that ties all three methods together.
Watch a 2-D Gaussian get estimated
A hidden Gaussian (dashed ellipse) produces the points. The solid ellipse is the fit from $\hat\mu$ and $\hat\Sigma$ so far. Both are 2-standard-deviation ellipses, containing about 86% of the probability. Add points and watch the estimate lock on.
8.5 Compression, counted in ℝᵈ
The lecture's "the parameter is a compressed representation" becomes concrete once you count numbers. $n$ points in $\mathbb R^d$ are $nd$ numbers. A model replaces them with $k$ parameters:
| Model | Parameters θ | Count k | d = 10 |
|---|---|---|---|
| Coin (Bernoulli) | $p$ | 1 | – |
| Die with m faces (categorical) | $p_1..p_m$, summing to 1 | $m-1$ | – |
| Gaussian, spherical $\sigma^2 I$ | $\mu,\ \sigma^2$ | $d+1$ | 11 |
| Gaussian, diagonal | $\mu,\ \sigma_1^2..\sigma_d^2$ | $2d$ | 20 |
| Gaussian, full covariance | $\mu,\ \Sigma$ (symmetric) | $d+\tfrac{d(d+1)}{2}$ | 65 |
| Mixture of K full Gaussians | $K$ means, $K$ covariances, $K-1$ weights | $K\big(d+\tfrac{d(d+1)}2\big)+K-1$ | K = 3: 197 |
A full covariance grows like $d^2$, so in high dimensions the "compressed" model can need a lot of data. This is the same parameter counting that powers BIC in L18.
8.6 An estimator is itself random
Run the same experiment again and you get different data, so a different $\hat p$. The estimator has its own distribution, called its sampling distribution. For the fraction of heads, the mean and standard deviation of $\hat p$ are
$$\mathbb E[\hat p]=p\quad(\text{unbiased}),\qquad \operatorname{sd}(\hat p)=\sqrt{\frac{p(1-p)}{n}} .$$So the uncertainty shrinks like $1/\sqrt n$: four times the data halves the error. In $d$ dimensions the same holds coordinate by coordinate: $\operatorname{Cov}(\hat\mu)=\Sigma/n$.
Key takeaways
- Estimation adds a story. Assume a probabilistic mechanism generated the data. Part of it, the parameter, is unknown.
- The goal: use the data to estimate the unknown parameter. The parameter acts as a compressed summary of the data.
- Everything is relative to the assumed model, which may or may not match reality.
- An estimate is a guess. For 9 heads in 12, every $p\in(0,1)$ could have produced the data; only $p = 0$ and $p = 1$ are ruled out.
- i.i.d. is the usual hidden assumption: independent tosses, all from the same coin.
- Open question: how do we choose between guesses in a principled way? (Preview: maximum likelihood gives $\hat p = h/n$ and, in ℝᵈ, the sample mean and covariance.)
Self-check
1. Why is p = 0.0001 still a possible explanation for 9 heads in 12 tosses, but p = 0 is not?
Under $p=0.0001$ the data has probability $p^{9}(1-p)^{3}\approx10^{-36}$. That's tiny, but not zero. Under $p=0$ any sequence containing a head has probability exactly 0, so it's impossible.
2. A box swaps between two coins at random before each press. Are the tosses independent? Identically distributed?
Both, as long as each press picks its coin afresh with the same probabilities. Every toss then follows the same overall law, and no toss affects another, so the box behaves like one coin whose bias is the weighted average of the two. Identical distribution breaks if the swap follows a schedule (as in Box B). Independence breaks if the choice depends on earlier outcomes.
3. Write the probability of the sequence 1, 1, 0, 1 under the Bernoulli model, assuming i.i.d.
$p\cdot p\cdot(1-p)\cdot p=p^{3}(1-p)$. Only the counts (3 ones, 1 zero) matter, not the order.
4. How many tosses does it take for the standard deviation of p̂ to drop below 0.01 when p ≈ 0.5?
$\sqrt{0.25/n}<0.01\Rightarrow n>2500$.
5. For 3-D data, how many numbers does a full-covariance Gaussian need, and why is that "compression" for n = 1,000 points?
$d+d(d+1)/2=3+6=9$ parameters, compared with $nd=3000$ raw numbers.
6. Where does PCA's covariance matrix come from in this lecture's framework?
It's the maximum-likelihood estimate $\hat\Sigma$ of the covariance of a Gaussian model fitted to the data (section 8.4).
For the exact wording of the lecture, open the video on YouTube and use "Show transcript".