7 concepts20 worked examples32 exercises5 exam-level7 figures
What are you here for?
10 Clustering: K-means, mixtures of Gaussians and the EM algorithm
Start with this
One question before you read anything. Getting it wrong is the point: it shows you what this section is for.
§10.6 — a bag exactly halfway between two machines
Machine 1 fills $60$ of every $100$ bags, with weights $\mathcal N(500,\,2^2)$ in grams; machine 2 fills the other $40$, with weights $\mathcal N(510,\,2^2)$. A bag weighing exactly $505$ g comes off the belt.
Find(a) What is the probability that machine 1 filled this bag?
Edge check: with equal shares $0.5$ and $0.5$ the same computation gives $0.5$, the symmetric answer most people expect here.
Near the middle between two components the prior shares decide; this section calls the result a .
Two machines fill coffee bags onto one belt, and nobody records which machine filled which bag. The weights crowd around $500$ g and around $510$ g, so the average weight, $504$ g, turns up seven times less often than $500$ g. A $506$ g bag comes past: which machine filled it, and how sure can you be?
By the end you can run and EM by hand, and you will have the number for the $506$ g bag: out of $100$ such bags, about $89$ come from machine 2.
In 60 seconds
K-means splits unlabeled points into $K$ groups by alternating nearest-prototype assignments with cluster means; a mixture of Gaussians does the same softly, and EM fits it by alternating responsibilities with weighted means, covariances and shares.
refitting every component with the responsibilities held fixed; $\Sigma_j$ uses the new $\mu_j$
Compressed image
$$24K+n\lceil\log_2K\rceil\ \text{ bits, against }24n$$
an $n$-pixel RGB image stored as $K$ colors plus one label per pixel
Three most common mistakes
Dropping $\pi_j$ from the responsibility. It is $\pi_j\mathcal N(x_i\mid\mu_j,\Sigma_j)$ over the sum, not $\mathcal N$ alone: halfway between two equal-variance components the answer is the prior share, not $0.5$.
Dividing by $n$ instead of $N_j$ in the M step. $\mu_j=\sum_i\gamma(z_{ij})x_i/N_j$ with $N_j=\sum_i\gamma(z_{ij})$, and only the share uses $n$: $\pi_j=N_j/n$.
Trusting one run. K-means and EM both stop at a local optimum that depends on the start; run from several starts and keep the smallest $J$ or the largest $l$.
Two course documents give different weights:
Chapter 1 slides, undergraduate line: midterm 25, final 25, four quizzes 20, two-phase project 30.
STARS syllabus page printed on 21 September 2026: midterm 30, final 30, problem sets and quizzes 20, project 20. It is the later document; confirm which split applies.
The STARS weekly list has this topic as its eighth item; the lecture slides number it chapter 10.
How much time do you have?
10 minutes
The two algorithms in the form exams ask for: the K-means steps, the responsibility and the EM updates.
The 60-second card · K-means · Responsibilities · EM for a Gaussian mixture · Formula card
45 minutes
Every block once with its first worked example, then one EM iteration from fully worked to bare.
The 60-second card · K-means · K-medoids · Compressing an image with K-means · EM on two coins · A mixture of Gaussians · Responsibilities · EM for a Gaussian mixture · Scaffolding comes off · Formula card
full read
Adds the derivations, the look-alike pairs and mixed practice where you pick the method yourself.
The opening pages · Recall first · K-means · K-medoids · Compressing an image with K-means · EM on two coins · A mixture of Gaussians · Responsibilities · EM for a Gaussian mixture · Look-alike pairs · Method boxes · Scaffolding comes off · Full exam-style question · Practice set · Check yourself
By the end of this section
Run K-means by hand: assign each point to its nearest prototype, move each prototype to its cluster mean, track $J$, and recognize a start that ends in a .
Apply K-medoids with the Manhattan or the , choosing each prototype among the cluster's own points.
Compute the size of an image compressed by K-means and compare it with the original.
Estimate two coin biases with EM when the coin behind each run is hidden, and compare with the estimate from known coins.
Write a Gaussian mixture as a model, evaluate its density and its moments, and count its parameters.
Compute responsibilities, and explain why they can disagree with the nearest mean.
Perform one EM iteration for a Gaussian mixture, derive its M step, and check that the log-likelihood went up.
Syllabus coverage
covered
Clustering — covered
K-means
indicator variables, the $J$, the E and M steps and why each is exact, convergence to a local minimum
K-medoids with a general dissimilarity
and compression
The lecturer's chapter title. Spread over three blocks, in the lecture's order.
covered
Probabilistic clustering — covered
: the responsibility of each component for each point, as the posterior of a hidden label, and how it differs from the of K-means.
The contrast with K-means comes back in the first look-alike pair.
covered
mixture of Gaussians — covered
The multivariate Gaussian
the mixture density and its
the latent one-hot variable with $p(z)$ and $p(x\mid z)$
the log-likelihood of a sample
the number of parameters
covered
expectation maximization — covered
EM on two coins with hidden labels, complete against ; EM for a Gaussian mixture: the E and M steps, where the M step comes from, the log-likelihood as a stopping rule, starting from K-means, restarts.
The lecture introduces EM on the two-coin experiment before the mixture, and so does this section.
off syllabus
Why the log-likelihood never decreases under EM — off syllabus
The monotonicity of EM, used here to check every worked iteration.
Further reading: stated without proof. The proof uses Jensen's inequality and is not on the slides.
off syllabus
Singular solutions of the mixture likelihood — off syllabus
A component that shrinks onto one data point sends $l$ to infinity.
Further reading, not on the slides. It explains why software keeps each variance above a small floor.
off syllabus
Choosing K with a held-out log-likelihood — off syllabus
Validation log-likelihood against training log-likelihood as $K$ grows.
Further reading: it joins this section with the cross-validation section and is used in one interleaved practice question only.
Recall first
Bayes' rule and total probability
For events $A_1,\dots,A_K$ that split the sample space: $P(A_j\mid B)=\dfrac{P(B\mid A_j)P(A_j)}{\sum_{k=1}^KP(B\mid A_k)P(A_k)}$; the denominator is $P(B)$ by the law of total probability.
Coin posteriors and responsibilities are exactly this formula.
Maximum likelihood estimates
For i.i.d. data $\hat\theta=\arg\max_\theta\sum_i\log p(x_i\mid\theta)$. For binomial runs this is heads over flips; for a Gaussian, $\hat\mu=\frac1n\sum_ix_i$ and $\hat\sigma^2=\frac1n\sum_i(x_i-\hat\mu)^2$.
Every M step is one of these, with weights.
Binomial probabilities
$\Pr(x=k)=\binom{F}{k}\theta^k(1-\theta)^{F-k}$ for $k$ heads in $F$ flips with heads probability $\theta$.
Each coin run is one binomial draw.
The multivariate Gaussian
$$\mathcal N(x\mid\mu,\Sigma)=\dfrac{1}{(2\pi)^{p/2}\lvert\Sigma\rvert^{1/2}}\exp\!\big(-\tfrac12(x-\mu)^T\Sigma^{-1}(x-\mu)\big)$$ with $\mu=E[X]$ and $\Sigma=E[(X-\mu)(X-\mu)^T]$. For $\Sigma=\sigma^2I$ it is a product of $p$ one-dimensional densities.
Each mixture component is one.
The mean minimizes squared distance
$\sum_i\lVert x_i-c\rVert^2=\sum_i\lVert x_i-\bar x\rVert^2+n\lVert\bar x-c\rVert^2$, so $c=\bar x$ is the unique minimizer.
This is the M step of K-means.
Law of total expectation
$E[X]=\sum_jP(j)\,E[X\mid j]$, and the same for $E[X^2]$.
It gives the mean and variance of a mixture.
To maximize $f(\pi)$ subject to $g(\pi)=0$, set $\nabla\big(f+\lambda g\big)=0$ and solve together with the constraint.
The shares $\pi_j$ must add up to $1$.
Two-way posteriors as a logistic function
$\dfrac{a}{a+b}=\dfrac{1}{1+e^{-d}}$ with $d=\log(a/b)$.
With two components, a responsibility comes from one log-odds.
Try it yourself first (2 questions)
1§10.1 — one number to stand for four readings
Four readings on a line are $0$, $1$, $2$ and $9$. We want one number $c$ that stands for all four, in the sense that $\sum_i(x_i-c)^2$ is as small as possible.
Find(a) Which $c$ is best?
Given
readings $0,\ 1,\ 2,\ 9$
criterion: $\sum_i(x_i-c)^2$ as small as possible
Hint 1/4
Treat the sum as a function of $c$ and look for its lowest point instead of trying values.
Hint 2/4
A smooth function is lowest where its derivative is $0$: $\frac{d}{dc}\sum_i(x_i-c)^2=-2\sum_i(x_i-c)$.
Odds check: prior odds $1:1$ times the likelihood ratio $0.81/0.25=3.24$ gives $3.24:1$, and $3.24/4.24=0.764$.
EM's E step computes exactly this for every run of flips, with the current guesses in place of the known $0.9$ and $0.5$.
Notation
symbol
reads as
means
watch out
$\{x_i\}_{i=1}^n,\ \ x_i=(x_{i1},\dots,x_{ip})$
the data
$n$ unlabeled points in $\mathbb R^p$
There are no labels $y_i$.
$K$
K
the number of clusters or components
Chosen before the run; neither K-means nor EM estimates it.
$r_{ik}$
r i k
$1$ if point $i$ is in cluster $k$, else $0$
Exactly one $1$ per point: $\sum_kr_{ik}=1$.
$k_i^*$
k i star
the cluster the E step gives point $i$: the index of its nearest prototype
With a tie, the conventions below decide.
$\mu_k$
mu k
the prototype of cluster $k$, or the mean of component $k$
In K-medoids it must be one of the data points.
$J,\ \ \tilde J$
J, J tilde
the distortion: total squared distance (K-means), total dissimilarity (K-medoids)
$J$ adds squared distances, not distances.
$N_k\ \ \text{(K-medoids)}$
N k
the set of points in cluster $k$
In EM, $N_j$ is a number, not a set.
$V(x_i,\mu_k)$
V of x i and mu k
a dissimilarity, such as the Manhattan or the cosine dissimilarity
The cosine dissimilarity is $1-\cos$, not $\cos$.
$\theta_A,\ \theta_B,\ z_i,\ F$
theta A, theta B, z i, F
heads probabilities of coins A and B, the coin of run $i$, flips per run
$z_i$ is hidden in the EM version.
$\mathcal N(x\mid\mu,\Sigma)$
normal density of x given mu and Sigma
the Gaussian density
In one dimension $\Sigma=\sigma^2$, a variance.
$\mathcal N_j(x)$
N j of x
short for $\mathcal N(x\mid\mu_j,\Sigma_j)$
Used in the mistake boxes to keep formulas short.
$\pi_j$
pi j
the mixing coefficient: the share of component $j$
Not $3.14\ldots$; the $\pi_j$ add up to $1$.
$z=(z_1,\dots,z_K)$
z
the hidden one-hot label of a point
$z_j=1$ means component $j$ produced the point.
$\gamma(z_{ij})$
gamma of z i j
the responsibility $p(z_{ij}=1\mid x_i)$
One number per point and component; each point's add up to $1$.
$N_j\ \ \text{(EM)}$
N j
the of component $j$, $\sum_i\gamma(z_{ij})$
Usually not a whole number; $\sum_jN_j=n$.
$l(\pi,\mu,\Sigma)$
l of pi, mu, Sigma
the log-likelihood $\sum_i\log p(x_i)$
Natural log of a sum, per point.
$\theta^{(s)}$
theta at step s
a parameter after $s$ EM iterations
$s=0$ is the start.
Conventions used here
Squared Euclidean distance.
$\lVert x-\mu\rVert^2=\sum_{j=1}^p(x_j-\mu_j)^2$. K-means assigns and scores with it; the square root is never taken.
The nearest prototype is the same with or without the root, and squares add up to J.
Ties in the E step.
A point moves only to a strictly nearer prototype. In the first E step, where no point has a cluster yet, a tie goes to the smaller index $k$.
With this rule J drops strictly whenever a point moves, which is what makes the run stop.
Empty clusters.
If an E step leaves a cluster with no points, its prototype stays where it was. None of the examples here runs into this.
The mean of no points is undefined; some implementations re-seed the prototype instead.
When to stop.
K-means stops when an E step changes no assignment. EM stops when $l$ changes by less than a tolerance, or after a fixed number of iterations.
K-means reaches an exact fixed point; EM usually only approaches one.
Natural logarithm.
$\log$ always means $\ln$, base $e$, in every log-likelihood and log-odds here.
Another base would only rescale l; every derivative on this page assumes base e.
Variances, not standard deviations.
$\mathcal N(\mu,v)$ always has the variance second, so $\mathcal N(x\mid\mu_j,\sigma_j^2)$ is read with $\sigma_j^2$, and a question that gives a standard deviation $\sigma$ means the variance $\sigma^2$. The M step divides the weighted squares by $N_j$.
That is the maximum likelihood estimate the updates come from; mixing the two gets a variance wrong by a square.
Coin priors.
In the coin examples each coin is picked with probability $1/2$, and this prior is not estimated.
Only the two heads probabilities are unknown, as in the lecture's setup.
Four decimals.
Numbers are shown to four decimals and computed from unrounded values, so recomputing from the rounded ones can move the last digit.
Responsibilities close to 0 or 1 need the digits.
10.1K-means: nearest prototype, then cluster mean, until nothing moves
Groups unlabeled points by alternating two easy steps: each point joins its nearest prototype, each prototype moves to its group's mean.
Regression and classification learned from labeled pairs $(x_i,y_i)$; here there are only points $\{x_i\}_{i=1}^n$, and the groups themselves are the unknown.
Solvable with what we have
Given two relay positions, send each sensor to the nearer one by comparing squared distances.
Given a group of points, find the single point with the smallest total squared distance to them: their mean.
Not solvable yet
Choose the groups and the relay positions at the same time.
Tell whether a grouping is the best one without scoring every possible split.
Six sensors sit at $x_1=(1,1)$, $x_2=(2,1)$, $x_3=(1,2)$, $x_4=(5,4)$, $x_5=(6,5)$, $x_6=(5,6)$ (km). A radio link costs energy in proportion to its squared length.
Put the two relays on $x_1$ and $x_2$.
Send every sensor to the nearer relay: $x_3$ joins relay 1; $x_4,x_5,x_6$ join relay 2.
Total cost: $J=0+1+0+18+32+34=85$.
Why it fails
Each easy step was used once and never repeated. Relay 2 sits on $x_2$, far from the three sensors it mostly serves. Moving each relay to its group's mean, regrouping and repeating brings $J$ down to $4$.
MethodK-means
Conditions
data $\{x_i\}_{i=1}^n$ with $x_i\in\mathbb R^p$; the number of clusters $K$ is fixed in advance
hard assignment: $r_{ik}\in\{0,1\}$ and $\sum_{k=1}^Kr_{ik}=1$ for every $i$
a start: $K$ initial prototypes $\mu_1,\dots,\mu_K$
$J$ adds up each point's squared distance to the prototype of its own cluster. The E step holds the prototypes and sends every point to the nearest one; the M step holds the groups and moves every prototype to the mean of its group. Repeat until an E step changes nothing.
Why each step is exact, and why the run stops
E step. With the prototypes fixed, $J$ is a sum of one term per point, $\sum_kr_{ik}\lVert x_i-\mu_k\rVert^2$, and each term is smallest when its single $1$ sits at the nearest prototype.
M step. With the groups fixed, $J$ is quadratic in $\mu_k$, and $\nabla_{\mu_k}J=-2\sum_ir_{ik}(x_i-\mu_k)=0$ gives the mean of cluster $k$. The denominator $\sum_ir_{ik}$ counts its points. $K$ clusters, $K$ means: hence the name.
It stops. Neither step can raise $J$. An E step that moves a point lowers $J$ strictly, because a point only moves to a strictly nearer prototype, so no assignment can come back. There are at most $K^n$ assignments, so the run ends.
Where it stops. At an assignment that neither step can improve: a local minimum that depends on the start. The lecture notes point out that minimizing $J$ exactly is NP-hard, which is why we settle for this.
The distortion after every half-step of the sensor run in the first worked example. $\textcolor{#8250df}{J}$ falls from $85$ to $4$ and stays there once an E step moves no sensor. Circles mark E steps, squares M steps.
Looks like this, but is not
Pick $K$ by running K-means for $K=1,2,3,\dots$ and keeping the $K$ with the smallest $J$.
$J$ can only fall as $K$ grows. For the six sensors the best $J$ is $48.17$ at $K=1$, $4$ at $K=2$, $2.33$ at $K=3$ and $0$ at $K=6$, where every sensor is its own prototype. The smallest $J$ always picks the largest $K$.
sensor
to μ₁
to μ₂
cluster
$x_1=(1,1)$
$0.25$
$21.25$
1
$x_2=(2,1)$
$1.25$
$15.25$
1 (was 2)
$x_3=(1,2)$
$0.25$
$16.25$
1
$x_4=(5,4)$
$22.25$
$0.25$
2
$x_5=(6,5)$
$37.25$
$3.25$
2
$x_6=(5,6)$
$36.25$
$4.25$
2
Only $x_2$ changes cluster at this step: $1.25<15.25$, so it leaves relay 2 for relay 1.
K-means on six sensors, starting from relays on sensors 1 and 2
Run K-means with $K=2$ on the six sensors, starting from $\mu_1=x_1$ and $\mu_2=x_2$, until an E step changes no assignment. Report the clusters, the prototypes and $J$ after every half-step.
FindThe final clusters and prototypes, and $J$ after each E and M step.
Independent check of the final $J$: in a cluster of $m$ points, the squared distances to the mean add up to the sum of all pairwise squared distances divided by $m$. The pairs give $1+1+2=4$ and $2+4+2=8$, so $J=\tfrac43+\tfrac83=4$. Scoring all $31$ two-group splits by computer gives no $J$ below $4$.
Two full iterations and one more E step: $18$ squared distances in all.
This closes the opening attempt: the same two easy steps, repeated until nothing moved, took $J$ from $85$ to $4$.
Four points on a rectangle: a start that traps K-means
The points are $(0,0)$, $(0,2)$, $(6,0)$ and $(6,2)$. Run K-means with $K=2$ from start A, $\mu_1=(3,-1)$ and $\mu_2=(3,3)$, and from start B, $\mu_1=(-1,1)$ and $\mu_2=(7,1)$. Compare the final values of $J$.
Both end states are fixed points. In state A each point is $9$ from its own mean and $13$ from the other, so no E step can move it, although state B has a $J$ nine times smaller.
K-means always stops, but where it stops depends on the start: run it from several starts and keep the smallest $J$.
Checkpoint
§10.1 — one K-means iteration on a line
Five readings on a line are clustered with $K=2$. The run starts from the prototypes $\mu_1=2$ and $\mu_2=3$.
Find(a) After one E step and one M step, what are $\mu_1$ and $\mu_2$?
Given
readings: $0,\ 2,\ 3,\ 9,\ 11$
start: $\mu_1=2$, $\mu_2=3$
Hint 1/4
First decide which prototype each reading is nearer to; only then average.
Hint 2/4
E step: $r_{ik}=1$ for the nearer prototype. M step: $\mu_k$ is the mean of the readings in cluster $k$.
Hint 3/4
Readings $0,2,3,9,11$ against $\mu_1=2$, $\mu_2=3$: the distances of $0$ are $2$ and $3$, of $3$ are $1$ and $0$, of $9$ are $7$ and $6$.
Hint 4/4
The clusters are $\{0,2\}$ and $\{3,9,11\}$, so $\mu_1=1$ and $\mu_2=23/3\approx7.67$.
Show solution
On a line the squared distance is just $(x-\mu)^2$, so the E step is a comparison of absolute differences.
E step
$$0:\ 4\text{ vs }9;\quad 2:\ 0\text{ vs }1;\quad 3:\ 1\text{ vs }0$$
$0$ and $2$ join $\mu_1$, and $3$ sits on $\mu_2$.
$$9:\ 49\text{ vs }36;\quad 11:\ 81\text{ vs }64$$
$J$ check: with the new clusters, $J=4+0+0+36+64=104$ around the old prototypes and $J=2+34.67=36.67$ around the new means, so the M step lowered it, as it must.
Run the E step for every point before touching any prototype.
⚠ Adding distances instead of squared distances
the nearest prototype is the same either way, so the square is easy to drop when adding up
right$$\begin{aligned}&\text{assign every }x_i,\\ &\text{then move every }\mu_k\end{aligned}$$
Step through the run of the first worked example. Each sensor takes the color of its cluster, diamonds mark the relays, and the dashed line holds the points equally far from both relays: the E step switches there. Each frame prints $\textcolor{#8250df}{J}$.
At the edges
start both relays in one corner
Relay 2 first serves four sensors, three of them far away, so $J=85$ after the first E step.
E step 3 no change
The assignment repeats E step 2, so $J$ stays at $4$ and the run stops.
10.2K-medoids: any dissimilarity, and prototypes that are data points
Swaps the squared distance for any dissimilarity $V$ and makes each prototype one of its cluster's own points.
The mean is the right prototype only for squared Euclidean distance; other ways of measuring difference need another M step.
MethodK-medoids clustering
Conditions
a dissimilarity $V(x_i,\mu_k)\ge0$ chosen for the data
The E step is the K-means E step with $V$ in place of the squared distance. The M step cannot average, so it tries every member of the cluster as the prototype and keeps the one whose total dissimilarity to the members is smallest.
One cluster with an . The $\textcolor{#8250df}{\text{mean}}$ $(3,3)$ lands where no member is; the $\textcolor{#1f6feb}{\text{medoid}}$ under is the member $(2,2)$, whose total distance to the others is $18$.
Looks like this, but is not
K-medoids with $V(x,\mu)=\lVert x-\mu\rVert^2$ is just K-means.
The M step still has to pick a member. For the cluster $\{0,1,5\}$ on a line, K-means puts the prototype at the mean $2$, with total $14$; K-medoids must choose among $0$, $1$ and $5$, and picks $1$, with total $17$.
The medoid of a cluster with an outlier, under Manhattan distance
A cluster holds $(1,1)$, $(2,1)$, $(1,2)$, $(2,2)$ and $(9,9)$. Find its under the Manhattan distance and compare it with the mean. Then move the outlier to $(90,90)$ and repeat.
FindThe medoid and the mean, before and after the outlier moves.
Direct recount after the move: $(2,2)$ has total $2+1+1+176=180$ and $(2,1)$ has $1+2+1+(88+89)=181$, so $(2,2)$ still wins.
A far outlier adds almost the same amount to every candidate's total, so it barely changes which member wins; the mean has no such protection.
Cosine dissimilarity: a short text joins the long article it resembles
Word counts for the words (goal, match, vote) describe a two-line text $x=(1,1,0)$. The prototypes are a long sports article $\mu_1=(30,40,0)$ and a short politics note $\mu_2=(0,1,2)$. Assign $x$ by squared Euclidean distance and by cosine dissimilarity.
Scale check: $V(10x,\mu_1)=V(x,\mu_1)$ because the factor $10$ cancels in the ratio, so a text ten times longer with the same word proportions lands in the same cluster.
Use the cosine when only the proportions of the features matter, as for word counts; use a distance when the size of the vector itself carries meaning.
Checkpoint
§10.2 — the K-medoids M step on a line
After an E step, one K-medoids cluster holds the readings $1,2,6,7,20$, and its prototype until now was $2$. The dissimilarity is $V(x,m)=\lvert x-m\rvert$.
Find(a) Which prototype does the M step choose?
Given
cluster members: $1,\ 2,\ 6,\ 7,\ 20$
current prototype: $2$
$V(x,m)=\lvert x-m\rvert$
Hint 1/4
The new prototype has to be one of the five readings; look for the one that is closest to all the others at once.
Each of the $K$ prototype colors costs $24$ bits, once. Each pixel then stores only which of the $K$ colors it got, and a fixed-length code for $K$ labels needs $\lceil\log_2K\rceil$ bits. When $n$ is much larger than $K$ the ratio is close to $24/\lceil\log_2K\rceil$.
Bits per pixel for a $64{,}000$-pixel image as $K$ grows: the $\textcolor{#8250df}{\text{staircase }\lceil\log_2K\rceil}$ plus a palette share too small to see. Going from $8$ to $9$ colors adds a whole bit to every pixel.
Looks like this, but is not
Three colors need $\log_23\approx1.58$ bits per pixel.
A fixed-length label per pixel uses whole bits: the labels $00,01,10$ need $\lceil\log_23\rceil=2$ bits, the same as for $K=4$, and the code $11$ goes unused. Codes that pack several pixels together get nearer to $1.58$; the scheme here does not.
Bits for a 320 by 200 image with 8 and with 9 colors
An RGB image of $320\times200$ pixels is compressed by K-means. Compare its size with $K=8$ and with $K=9$ against the original.
FindBoth compressed sizes and both compression ratios.
Given
$320\times200$ pixels, $8$ bits per channel, three channels
$K=8$ or $K=9$
Solution
We plug into the size formula; the only step that needs thought is the ceiling.
For large $n$ the ratio should be close to $24/\lceil\log_2K\rceil$: $24/3=8$ and $24/4=6$, and the exact ratios sit just below, because of the palette.
Choose $K$ as a power of two when you can: $K=9$ pays for $16$ labels and uses nine.
The squared error of the compressed pixels is J
Four pixels $(200,40,40)$, $(220,60,40)$, $(20,40,200)$ and $(40,40,220)$ are compressed with $K=2$; K-means groups the first two and the last two. Find the prototypes, the total squared color error of the compressed copy, and the bits against the original.
FindThe two prototype colors, the total squared error, and both bit counts.
With only four pixels the palette is most of the cost.
Answer $$\boxed{\begin{aligned}&\mu_1=(210,50,40)\\ &\mu_2=(30,40,210)\\ &J=800;\ \ 52\text{ bits vs }96\end{aligned}}$$
Check
Pairwise check: pixels 1 and 2 differ by $(20,20,0)$, squared length $800$, and a pair adds half of that to $J$; pixels 3 and 4 add another $400$, so $J=800$. Per channel that is about $8.2$ levels out of $256$.
K-means suits compression because it minimizes exactly what the compressed image loses: the squared error of the replaced pixels.
Checkpoint
§10.3 — the size of a compressed image
An RGB image of $400\times300$ pixels, $8$ bits per channel, is compressed by K-means with $K=16$ and stored as the palette plus a fixed-length label per pixel.
Find(a) How many bits does the compressed image take?
Given
$400\times300$ pixels, $24$ bits per pixel in the original
$K=16$
Hint 1/4
Split the storage into two parts: the colors, stored once, and the labels, one per pixel.
Hint 2/4
$24K+n\lceil\log_2K\rceil$ bits.
Hint 3/4
Here $n=400\cdot300=120{,}000$, $K=16$ and $\log_216=4$.
E step: with the current guesses, compute for each run the probability that coin A was used. M step: credit coin A with that share of the run's heads and flips, coin B with the rest, and divide heads by flips for each coin. With known coins every share is $0$ or $1$ and this is the ordinary estimate.
Where the two steps come from
E step. Bayes' rule gives $$\Pr(z_i=A\mid x_i)=\dfrac{\frac12\Pr(x_i\mid\theta_A)}{\frac12\Pr(x_i\mid\theta_A)+\frac12\Pr(x_i\mid\theta_B)}.$$ The factor $\binom{F}{x_i}$ sits in both binomial probabilities, so it cancels along with the $\tfrac12$.
M step. Weight each run's complete-data log-likelihood by its posterior and add: $\sum_i\gamma_{iA}\big[x_i\log\theta_A+(F-x_i)\log(1-\theta_A)\big]$, plus the same with $1-\gamma_{iA}$ for coin B. The lecture notes call this the expected likelihood.
Setting its derivative in $\theta_A$ to zero gives $\sum_i\gamma_{iA}x_i/\theta_A=\sum_i\gamma_{iA}(F-x_i)/(1-\theta_A)$, whose solution is the weighted fraction of heads in the box.
The E step of the worked example, run by run. Each bar is split into the posterior of $\textcolor{#1f6feb}{\text{coin A}}$ and of $\textcolor{#d1690a}{\text{coin B}}$. Lopsided runs go almost entirely to one coin; the run with $4$ heads is split about one third to two thirds.
Looks like this, but is not
Skip the probabilities: give each run to the more likely coin and count, as K-means would.
That is a different algorithm. Here it jumps to $\theta_A=0.75$, $\theta_B=0.35$ and never moves, while EM keeps the run with $4$ heads split and ends at $0.7333$ and $0.3709$. The log-likelihood of the heads counts is $-8.0400$ at EM's answer and $-8.0649$ at the hard one.
run
heads
ratio a/b
γ for A
A: heads, tails
B: heads, tails
1
$8$
$11.3906$
$0.9193$
$7.3544,\ 1.8386$
$0.6456,\ 0.1614$
2
$3$
$0.1975$
$0.1649$
$0.4948,\ 1.1546$
$2.5052,\ 5.8454$
3
$7$
$5.0625$
$0.8351$
$5.8454,\ 2.5052$
$1.1546,\ 0.4948$
4
$4$
$0.4444$
$0.3077$
$1.2308,\ 1.8462$
$2.7692,\ 4.1538$
total
$22$
$14.9253,\ 7.3445$
$7.0747,\ 10.6555$
Coin A is credited with $14.9253$ heads out of $22.2699$ flips and coin B with $7.0747$ out of $17.7301$: those two fractions are the M step.
Two coins with known labels: the complete-data estimate
Four runs of $10$ flips each: coin A gave $8$ and $7$ heads, coin B gave $3$ and $4$. Estimate $\theta_A$ and $\theta_B$ by maximum likelihood.
Find$\hat\theta_A$ and $\hat\theta_B$.
Given
coin A: $8$ and $7$ heads; coin B: $3$ and $4$ heads
$F=10$ flips per run
Solution
With the coins known, the log-likelihood splits into one part per coin, and each part is maximized on its own.
Each estimate is its coin's fraction of heads, $15/20$ and $7/20$, the binomial estimate from the section on maximum likelihood.
With labels there is nothing to iterate: we count coin by coin.
One EM iteration for two coins whose labels were lost
The same four runs, with $8,3,7,4$ heads out of $10$, but nobody recorded the coins. Each run used A or B with probability $1/2$. Start from $\theta_A^{(0)}=0.6$, $\theta_B^{(0)}=0.4$ and do one EM iteration.
FindThe posteriors $\gamma_{iA}$ and the new estimates $\theta_A^{(1)},\theta_B^{(1)}$.
Given
heads $x_i$: $8,\ 3,\ 7,\ 4$ out of $F=10$
$\Pr(z_i=A)=\Pr(z_i=B)=1/2$
$\theta_A^{(0)}=0.6$, $\theta_B^{(0)}=0.4$
Solution
Because $\theta_A^{(0)}=1-\theta_B^{(0)}$, the likelihood ratio collapses to a power of $1.5$, so each posterior takes one line.
The log-likelihood of the heads counts, $\sum_i\log\big[\tfrac12\Pr(x_i\mid\theta_A)+\tfrac12\Pr(x_i\mid\theta_B)\big]$, rises from $-8.5300$ at the start to $-8.1784$.
Continuing, EM settles within $10$ iterations at $\theta_A=0.7333$, $\theta_B=0.3709$, with $l=-8.0400$.
Each EM iteration is the known-coin estimate with fractional counts; the posteriors decide the fractions.
Checkpoint
§10.4 — the E step for one run of flips
Coin A lands heads with probability $0.8$ and coin B with probability $0.5$; a run picks one of them with probability $1/2$ each. One run of $10$ flips shows $6$ heads.
Find(a) What is $\Pr(z=A\mid 6\text{ heads})$?
Given
$\theta_A=0.8$, $\theta_B=0.5$
$\Pr(z=A)=\Pr(z=B)=1/2$
$6$ heads in $F=10$ flips
Hint 1/4
Compare how well each coin explains six heads and four tails, then weigh by the equal priors.
Hint 2/4
$\gamma_A=\dfrac{a}{a+b}$ with $a=\theta_A^x(1-\theta_A)^{F-x}$ and $b=\theta_B^x(1-\theta_B)^{F-x}$.
Hint 3/4
Here $x=6$, $F=10$: $a/b=(0.8/0.5)^6\,(0.2/0.5)^4$.
Hint 4/4
$a/b=0.4295$, so $\gamma_A=0.4295/1.4295=0.30$.
Show solution
The likelihood ratio is the fastest route: every common factor cancels in it.
To draw one point, pick component $j$ with probability $\pi_j$, then draw $x$ from that Gaussian. Summing out the hidden choice gives the mixture density. Each term of the log-likelihood is $\log\sum_j\pi_j\mathcal N(x_i\mid\mu_j,\Sigma_j)$, a sum inside a logarithm, which is why no formula maximizes it in one step.
Why p(x) is a density, and where it comes from
$p(x)\ge0$, and $\int p(x)\,dx=\sum_j\pi_j\int\mathcal N(x\mid\mu_j,\Sigma_j)\,dx=\sum_j\pi_j=1$.
By the law of total probability over the $K$ possible values of $z$, $p(x)=\sum_zp(z)\,p(x\mid z)$; the $z$ with $z_j=1$ contributes $\pi_j\,\mathcal N(x\mid\mu_j,\Sigma_j)$.
Written with exponents, $p(x\mid z)=\prod_j\mathcal N(x\mid\mu_j,\Sigma_j)^{z_j}$: only the factor with $z_j=1$ is not raised to the power $0$.
The bag-weight mixture of the opening: $\textcolor{#1f6feb}{0.6\,\mathcal N(x\mid500,4)}$ and $\textcolor{#d1690a}{0.4\,\mathcal N(x\mid510,4)}$ add up to $\textcolor{#8250df}{p(x)}$. At the average weight $504$ the density is $0.017$, seven times lower than at $500$.
Looks like this, but is not
The mixture of $\mathcal N(500,4)$ and $\mathcal N(510,4)$ with weights $0.6$ and $0.4$ is the distribution of $0.6X_1+0.4X_2$, for independent $X_1\sim\mathcal N(500,4)$ and $X_2\sim\mathcal N(510,4)$.
A weighted sum of independent Gaussians is again one Gaussian, here $\mathcal N(504,\ 2.08)$, with a single hump at $504$. The mixture does not add the two variables; it picks one of them, which is how it gets two humps.
weight x (g)
mixture p(x)
one Gaussian N(x | 504, 28)
$496$
$0.0162$
$0.0240$
$500$
$0.1197$
$0.0567$
$504$
$0.0171$
$0.0754$
$506$
$0.0121$
$0.0702$
$510$
$0.0798$
$0.0396$
$514$
$0.0108$
$0.0126$
The single Gaussian gives $0.0754$ at $504$, over four times the mixture's $0.0171$, and less than half the mixture's value at $500$.
Mean and variance of the bag-weight mixture
Bags come from machine 1 with probability $0.6$, weights $\mathcal N(500,4)$, and from machine 2 with probability $0.4$, weights $\mathcal N(510,4)$, in grams. Find the mean and the variance of a random bag's weight, and the single Gaussian with the same two numbers.
Find$E[X]$, $\operatorname{Var}X$, and the matching single Gaussian.
Given
$\pi_1=0.6$, $\mu_1=500$, $\sigma_1^2=4$
$\pi_2=0.4$, $\mu_2=510$, $\sigma_2^2=4$
Solution
Condition on the hidden machine: each conditional moment is known, and the law of total expectation combines them.
Matching the mean and variance gives $\mathcal N(504,28)$, one wide hump centered in the valley between the machines; the mixture keeps the two humps.
How many numbers a Gaussian mixture needs
Count the free parameters of a mixture of $K$ Gaussians in $p$ dimensions with full covariance matrices. Evaluate the count for $K=3$, $p=2$ and for $K=3$, $p=10$.
FindThe number of free parameters, in general and in the two cases.
Given$K$ components, each with $\pi_j$, $\mu_j\in\mathbb R^p$ and a $p\times p$ covariance $\Sigma_j$
Solution
Count per component, then subtract one for the constraint on the weights.
Weights
$$K-1$$
The $K$ weights add to $1$, so the last one follows from the others.
Means
$$Kp$$
Each component has its own mean, a free vector of $p$ numbers.
Covariances
$$K\,\tfrac{p(p+1)}{2}$$
A covariance matrix is symmetric, so only the diagonal and one triangle are free.
Totals
$$K=3,\ p=2:\ \ 2+6+9=17$$
Weights, means and covariances are chosen independently, so their counts add: $K-1=2$, $Kp=6$, $K\cdot3=9$.
$$K=3,\ p=10:\ \ 2+30+165=197$$
The covariances take most of the count as $p$ grows.
Answer $$\boxed{(K-1)+Kp+K\,\tfrac{p(p+1)}{2}}$$
Check
Edge check $K=1$, $p=2$: $0+2+3=5$, one mean and one $2\times2$ covariance with three free entries, as for a single Gaussian.
In high dimensions the covariances dominate the count; with diagonal covariances the last term drops to $Kp$.
Checkpoint
§10.5 — a mixture density at one point
A mixture of two one-dimensional Gaussians has $p(x)=0.25\,\mathcal N(x\mid0,1)+0.75\,\mathcal N(x\mid2,1)$. We need its value at $x=0$.
The share of component $j$ times its density at $x$, divided by the same product summed over all components. $\pi_j$ is the probability of component $j$ before seeing $x$, and $\gamma(z_j)$ is the probability after seeing it. The $K$ responsibilities of a point add up to $1$.
Bayes' rule, and what it does to the likelihood equations
Bayes' rule: $p(z_j=1\mid x)=p(z_j=1)\,p(x\mid z_j=1)/p(x)$, with $p(z_j=1)=\pi_j$, $p(x\mid z_j=1)=\mathcal N(x\mid\mu_j,\Sigma_j)$ and $p(x)$ the mixture.
Differentiating $l$ in $\mu_j$ produces the responsibilities by themselves: $\nabla_{\mu_j}l=\sum_i\gamma(z_{ij})\,\Sigma_j^{-1}(x_i-\mu_j)$.
Setting it to zero gives $\mu_j=\sum_i\gamma(z_{ij})x_i\big/\sum_i\gamma(z_{ij})$, a weighted mean. But the weights depend on $\mu_j$, so this is an equation, not a formula; the next block turns it into an iteration.
Responsibilities for the two machines. $\textcolor{#1f6feb}{\gamma_1}$ and $\textcolor{#d1690a}{\gamma_2}$ cross at $505.16$ g, a little past the $\textcolor{#8250df}{\text{K-means cut at }505}$, because machine 1 fills more bags. A $506$ g bag gets $\gamma_2=0.89$.
Looks like this, but is not
$\gamma(z_{i1})=0.7$ says component 1 produced $7$ out of every $10$ points of the data.
That is $\pi_1$, one number for the whole data. $\gamma(z_{i1})$ belongs to one point: among many points with this same value, about $7$ in $10$ came from component 1. Averaging $\gamma(z_{i1})$ over all points estimates $\pi_1$.
Which machine filled the 506 g bag?
Machine 1 fills $60$ of every $100$ bags, with weights $\mathcal N(500,4)$; machine 2 fills the other $40$, with weights $\mathcal N(510,4)$, in grams. Find the responsibilities of both machines for a $506$ g bag and for a $505$ g bag.
Log-odds route: $\log\frac{\gamma_2}{\gamma_1}=\log\frac{0.4}{0.6}+\frac{36-16}{8}=-0.405+2.5=2.095$, and $1/(1+e^{-2.095})=0.890$.
This answers the opening question: out of $100$ bags that weigh $506$ g, about $89$ come from machine 2. Near the middle, where the densities are close, the shares decide.
Two equally distant means, unequal responsibilities
Two components in the plane have $\pi_1=\pi_2=0.5$, $\mu_1=(0,0)$ with $\Sigma_1=I$, and $\mu_2=(4,0)$ with $\Sigma_2=4I$. Find the responsibilities for $x=(2,1)$, which is $\sqrt5$ from both means.
We evaluate each density from the multivariate formula, because the determinant $\lvert\Sigma_j\rvert$ differs between the two components and does not cancel.
Log-ratio route: $\log\frac{\mathcal N_2}{\mathcal N_1}=-\frac58+\frac52-\log4=0.4887$, and $1/(1+e^{-0.4887})=0.620$.
At equal distance the wider component wins: a spread-out Gaussian explains a far point better than a tight one does.
Checkpoint
§10.6 — one responsibility in one dimension
A two-component mixture on a line has $\pi_1=\pi_2=0.5$, means $\mu_1=0$ and $\mu_2=2$, and variances $\sigma_1^2=\sigma_2^2=1$. A point sits at $x=1.5$.
Find(a) What is the responsibility $\gamma(z_2)$ of component 2 for this point?
wrong$$\gamma(z_j)=1\ \text{for the nearest }\mu_j$$
right$$\gamma(z_j)\ \text{also depends on }\pi_j\text{ and }\Sigma_j$$
10.7EM for a Gaussian mixture: responsibilities, then weighted means, covariances and shares
Alternates responsibilities with refitting each Gaussian to the points weighted by them; the log-likelihood never goes down.
The likelihood equations said $\mu_j$ is the $\gamma$-weighted mean, but $\gamma$ depends on $\mu_j$. EM breaks the circle the way K-means did: fix one, solve for the other.
MethodThe EM algorithm for a mixture of Gaussians
Conditions
data $\{x_i\}_{i=1}^n$ and a number of components $K$
a start for every $\pi_j,\mu_j,\Sigma_j$, for example from a K-means run
E step: hold the parameters and compute every point's responsibilities. M step: hold the responsibilities and refit each component as if its data were the points weighted by $\gamma$: a weighted mean, a weighted covariance around the new mean, and a share equal to its effective number of points $N_j$ over $n$. Repeat until $l$ stops changing.
Where the M step comes from
Means. With the $\gamma(z_{ij})$ held fixed, $\nabla_{\mu_j}l=\sum_i\gamma(z_{ij})\,\Sigma_j^{-1}(x_i-\mu_j)=0$ gives $\mu_j^{\text{new}}$. The covariance follows the same way, around the new mean.
Shares. Maximize $l+\lambda\big(\sum_k\pi_k-1\big)$. The derivative in $\pi_j$ is $\sum_i\mathcal N(x_i\mid\mu_j,\Sigma_j)/p(x_i)+\lambda=0$; multiplying by $\pi_j$ turns it into $N_j+\lambda\pi_j=0$.
Summing over $j$ gives $n+\lambda=0$, so $\lambda=-n$ and $\pi_j^{\text{new}}=N_j/n$.
Never downhill. An EM iteration cannot lower $l$. This is a general property of EM whose proof uses Jensen's inequality (further reading); every worked iteration here checks it with numbers.
EM on the ten numbers $0, \allowbreak 1, \allowbreak 1, \allowbreak 2, \allowbreak 6, \allowbreak 7, \allowbreak 12, \allowbreak 13, \allowbreak 13, \allowbreak 14$ from two starts. Both log-likelihoods rise at every iteration; $\textcolor{#8250df}{\text{the start at }\mu=(4,13)}$ ends at $-25.43$, the start at $\mu=(1,10)$ at $-26.36$, a lower local maximum.
Looks like this, but is not
The larger the log-likelihood, the better the mixture, so EM should push $l$ as high as it can go.
Put $\mu_2$ on one data point and shrink $\sigma_2$: that point's density grows without limit, so $l\to\infty$ while component 2 describes a single number. These are further reading; in practice one restarts EM or keeps every variance above a small floor.
One full EM iteration on five points
Fit $K=2$ Gaussians to the numbers $1,3,4,8,9$, starting from $\pi=(0.5,0.5)$, $\mu=(2,8)$ and $\sigma^2=(4,4)$. Carry out one E step and one M step, and compare the log-likelihood before and after.
Find$\gamma(z_{i1})$ for every point, then $N_j$, $\pi_j$, $\mu_j$, $\sigma_j^2$, and $l$ before and after.
Two independent checks: $N_1+N_2=5=n$, and $\pi_1\mu_1+\pi_2\mu_2=0.5562(2.6017)+0.4438(8.0060)=5.0$, the plain mean of the data, which every M step must reproduce.
Five log-odds, then two counts, two means and two variances: about $30$ multiplications.
One iteration moved the means from $(2,8)$ to $(2.60,\ 8.01)$ and cut both variances; the next iteration repeats the same five lines from the new values.
The covariance update in two dimensions
In an M step, component $j$ has responsibilities $1$, $0.5$ and $0.5$ for the points $(0,0)$, $(2,0)$ and $(2,2)$, and $0$ for every other point. Find $N_j$, $\mu_j$ and $\Sigma_j$.
Find$N_j$, $\mu_j^{\text{new}}$ and $\Sigma_j^{\text{new}}$.
Trace check: the trace of $\Sigma_j$ must equal the weighted mean squared distance to $\mu_j$, $\tfrac12\big[1(1.25)+0.5(1.25)+0.5(3.25)\big]=1.75$, and $1+0.75=1.75$. The determinant $0.75-0.25=0.5>0$, so $\Sigma_j$ is a valid covariance.
In several dimensions the M step is the same weighted average, applied to outer products.
Checkpoint
§10.7 — the M step from given responsibilities
An E step on the four numbers $0,2,4,10$ has given component 1 the responsibilities $1,\ 0.8,\ 0.4,\ 0$, in that order.
Find(a) What is $\mu_1^{\text{new}}$?
Given
data $x=(0,\ 2,\ 4,\ 10)$
$\gamma(z_{i1})=(1,\ 0.8,\ 0.4,\ 0)$
Hint 1/4
The new mean is an average in which each point counts as much as its responsibility.
Hint 2/4
$\mu_1^{\text{new}}=\sum_i\gamma(z_{i1})x_i\big/N_1$ with $N_1=\sum_i\gamma(z_{i1})$.
Hint 3/4
Here $x=(0,2,4,10)$ and $\gamma(z_{i1})=(1,0.8,0.4,0)$, so the weighted sum is $0+1.6+1.6+0$.
Hint 4/4
$N_1=2.2$ and $\mu_1^{\text{new}}=3.2/2.2=1.45$.
Show solution
The column sum $N_1$ is needed by both formulas, so it comes first.
Effective count
$$N_1=1+0.8+0.4+0=2.2$$
Each responsibility is the fraction of a point that component 1 owns, so their sum is its effective number of points.
Range check: $\mu_1$ is a weighted average of $0,2,4$ with most weight on $0$ and $2$, so it must lie between $0$ and $4$ and nearer the low end; $1.45$ does.
A column sum first, then everything divides by it; only $\pi_j$ divides by $n$.
Step through EM on thirteen bag weights, from a poor start with both components near the middle. The curves are $\textcolor{#1f6feb}{\pi_1\mathcal N(x\mid\mu_1,\sigma_1^2)}$ and $\textcolor{#d1690a}{\pi_2\mathcal N(x\mid\mu_2,\sigma_2^2)}$, and each bar splits one bag between the machines. By iteration $18$ the means are $500.0$ and $510.0$ and the shares $8/13$ and $5/13$.
At the edges
iteration 0 l = −40.82
Both components are wide and overlap, so every bag is split between them.
iteration 18 l = −35.57
Each bag belongs almost entirely to one machine, and the shares are the counts $8$ and $5$ over $13$.
Running K-means by hand
A question gives points, $K$ and starting prototypes, and asks for the clusters, the prototypes or $J$ after some steps.
Table
One row per point, one column per prototype, holding squared distances.
Assign
Mark the smallest entry in each row; a point moves only to a strictly nearer prototype.
Average
Replace each prototype by the mean of its marked points, dividing by the cluster size.
Score
Add each point's squared distance to its own prototype: that is $J$.
Stop
Repeat until an E step marks the same entries as the one before.
Where it goes wrong
An empty cluster: keep its prototype where it was, and say so.
Distances instead of squared distances in $J$.
Moving a prototype before every point is assigned.
EM for hidden coins by hand
Runs of flips with an unknown coin each time; the question gives starting biases and asks for one or more EM iterations.
Ratio
For each run, $a_i/b_i=(\theta_A/\theta_B)^{x_i}\big((1-\theta_A)/(1-\theta_B)\big)^{F-x_i}$.
Posterior
$\gamma_{iA}=\dfrac{a_i/b_i}{1+a_i/b_i}$, and coin B gets $1-\gamma_{iA}$.
Credit
Coin A gets $\gamma_{iA}x_i$ heads and $\gamma_{iA}F$ flips from run $i$; coin B gets the rest.
Divide
Each coin's new $\theta$ is its credited heads over its credited flips.
Check
The credited heads add up to the total heads, and the log-likelihood went up.
Where it goes wrong
Unequal priors: multiply $a_i/b_i$ by $\Pr(A)/\Pr(B)$ before step 2.
Dividing coin A's heads by all the flips instead of its credited flips.
One EM iteration for a Gaussian mixture by hand
A question gives data, $K$ and starting $\pi$, $\mu$, $\sigma^2$, and asks for the responsibilities or the next parameters.
Products
For each point and component, $\pi_j\mathcal N(x_i\mid\mu_j,\sigma_j^2)$; with two components use the log-odds.
Normalize
Divide each row by its sum: a point's responsibilities add up to $1$.
Count
Column sums give $N_j$; check that they add up to $n$.
Refit
$\mu_j$ as the weighted mean, then $\sigma_j^2$ around the new $\mu_j$, both over $N_j$; $\pi_j=N_j/n$.
Check
$\sum_j\pi_j\mu_j$ equals the plain mean of the data, and $l$ did not go down.
Where it goes wrong
Leaving $\pi_j$ out of the products.
Normalizing down a column instead of across a row.
Using the old mean inside the variance.
K-means places a 505.1 g bag with machine 2
K-means has settled on the prototypes $500$ g and $510$ g. A bag weighs $505.1$ g. Which cluster does the E step give it?
FindThe cluster of the bag.
Given
prototypes $\mu_1=500$, $\mu_2=510$
bag $x=505.1$ g
Solution
K-means compares squared distances and nothing else.
The two machines are equally likely at $505.16$ g, and $505.1$ lies just below it, on machine 1's side.
Near the cut the shares tip a balance that the distances leave almost even.
K-means asks only which prototype is nearer, so the $505.1$ g bag goes to machine 2; EM also weighs how common each machine is, and machine 1 comes out slightly more likely.
How to tell them apart
If a question gives shares and variances or covariances, it wants responsibilities; if it gives only prototypes, it wants the nearest one.
The new share of machine 1 after an E step
An E step on four bags of $499$, $502$, $507$ and $511$ g gave machine 1 the responsibilities $1.0000$, $0.9996$, $0.0100$ and $0.0000$. What share of the bags does the M step give machine 1?
Find$\pi_1^{\text{new}}$.
Given$\gamma(z_{i1})=1.0000,\ \allowbreak 0.9996,\ \allowbreak 0.0100,\ \allowbreak 0.0000$ for four bags
Solution
A share is the average responsibility over all points, so we add the column and divide by $n$.
The bag is $3$ g from machine 1's mean and $7$ g from machine 2's.
Responsibility
$$\gamma_1=\frac{1}{1+e^{-5.405}}=0.9955$$
Almost certainly machine 1.
Answer $$\boxed{\gamma_1=0.9955}$$
Check
Direct densities: $0.6\,\mathcal N(503\mid500,4)=0.03886$ and $0.4\,\mathcal N(503\mid510,4)=0.00017$, and $0.03886/0.03903=0.9955$.
A responsibility describes one bag, and it can be close to $1$ while the share is only $0.6$.
$\pi_1$ answers what share of all bags machine 1 fills; $\gamma(z_{i1})$ answers how likely it is that this one bag came from machine 1.
How to tell them apart
One number for the whole data set is a share $\pi_j$; one number per point is a responsibility. The M step links them: the new share is the average responsibility.
Scaffolding comes off
The common skeleton
E step: for each point and component compute $\pi_j\mathcal N(x_i\mid\mu_j,\sigma_j^2)$, then divide each point's row by its sum to get $\gamma(z_{ij})$.
Counts: $N_j=\sum_i\gamma(z_{ij})$, which must add up to $n$.
Means: $\mu_j=\sum_i\gamma(z_{ij})x_i/N_j$.
Variances: $\sigma_j^2=\sum_i\gamma(z_{ij})(x_i-\mu_j)^2/N_j$, around the new means.
Shares: $\pi_j=N_j/n$; then check that $l$ went up.
1 · fully worked
One EM iteration on five numbers with unequal starting variances
Fit $K=2$ Gaussians to $1,2,4,7,8$, starting from $\pi=(0.5,0.5)$, $\mu=(1,5)$ and $\sigma^2=(1,4)$. Carry out one EM iteration.
FindThe responsibilities, then $N_j$, $\mu_j$, $\sigma_j^2$, $\pi_j$ and the change in $l$.
Mean check: $0.35(1.4929)+0.65(5.9655)=4.4$, the plain mean of $1,2,4,7,8$.
A narrow component gives up far points quickly; here component 1 kept only $1$ and most of $2$.
2 · you write the reasoning
Easier: the responsibilities are given, so only the M step is left. The data are $0,1,5,6$, and component 1 has $\gamma(z_{i1})=1,\ \allowbreak 0.8,\ \allowbreak 0.2,\ \allowbreak 0$. For each line, write why it is allowed.
The same around $5.1$: data and responsibilities are mirror images, so the variance agrees.
$$\pi_1=\pi_2=\frac{2}{4}=0.5$$
reasoning
Shares are counts over $n$; equal counts give equal shares.
3 · find the buried error
Harder, and the solution below hides two errors. Fit $K=2$ Gaussians to $2,3,5,9$ from $\pi=(0.7,\ 0.3)$, $\mu=(3,\ 8)$ and $\sigma^2=(1,\ 4)$, and carry out one EM iteration.
One EM iteration is five lines: responsibilities, counts, means, variances, shares. Start with the point that sits between the two means.
Hint 2/4
$$\gamma(z_{i1})=\dfrac{\pi_1\mathcal N(x_i\mid\mu_1,\sigma_1^2)}{\sum_k\pi_k\mathcal N(x_i\mid\mu_k,\sigma_k^2)}$$ then $N_j=\sum_i\gamma(z_{ij})$, $\mu_j=\sum_i\gamma(z_{ij})x_i/N_j$, $\sigma_j^2=\sum_i\gamma(z_{ij})(x_i-\mu_j)^2/N_j$, $\pi_j=N_j/n$.
Hint 3/4
Data $0,2,3,7$ with $\pi=(0.5,0.5)$, $\mu=(1,7)$, $\sigma^2=(1,4)$. At $x=3$ the two products are $0.5\,\mathcal N(3\mid1,1)=0.0270$ and $0.5\,\mathcal N(3\mid7,4)=0.0135$.
Mean check: $0.6575(1.4944)+0.3425(5.8901)=3.0$, the plain mean of $0,2,3,7$; and $l$ rose from $-9.6986$ to $-8.7503$.
When one point sits between the components, its split decides most of the update, so compute it first.
Full exam-style question
From K-means to EM on six readings, and a reading in betweenexam format
Six sensor readings are $1,2,3,7,8,12$.
(a) Run K-means with $K=2$ from $\mu_1=1$, $\mu_2=12$ until it stops, and give $J$.
(b) Start a two-component Gaussian mixture from the result: shares from the cluster sizes, means from the prototypes, variances from the clusters.
(c) A new reading $x=5$ arrives. Which cluster does K-means give it, and what are the mixture's responsibilities?
(d) Explain the difference in one sentence.
Find(a) the clusters and $J$; (b) $\pi$, $\mu$, $\sigma^2$; (c) the K-means cluster and the responsibilities of $x=5$; (d) the reason they differ.
Given
readings $1,\ 2,\ 3,\ 7,\ 8,\ 12$
K-means start $\mu_1=1$, $\mu_2=12$
new reading $x=5$
Solution
K-means first, because its clusters are the cheapest good start for EM; the responsibilities then come from the log-densities, because the two variances differ.
(c) through the densities: $\mathcal N(5\mid2,\tfrac23)=0.000572$ and $\mathcal N(5\mid9,\tfrac{14}3)=0.0333$, and $0.0333/(0.0333+0.000572)=0.983$. One EM iteration from this start moves the means only to $1.9947$ and $8.9601$.
Two E steps and one M step of K-means, then two log-densities.
K-means is a cheap way to start EM, but its hard cut and EM's responsibilities disagree wherever the clusters have different spreads.
Practice
A · concept 4 questions
1§10.1 — does K-means always find the best split?
A classmate says that every iteration of K-means lowers $J$ until it reaches the smallest $J$ over all ways of splitting the data into $K$ groups.
Find(a) Is the claim true or false?
Given
K-means with a fixed $K$ and a given start
$J=\sum_i\sum_kr_{ik}\lVert x_i-\mu_k\rVert^2$
Hint 1/4
Split the claim in two, whether $J$ goes down and whether it ends at the best split, and check each part on its own.
Hint 2/4
Each step minimizes $J$ over its own unknowns, so $J$ cannot rise; a stopping point is only a state that neither step can improve.
Hint 3/4
Test case: the corners $(0,0), \allowbreak (0,2), \allowbreak (6,0), \allowbreak (6,2)$ with the start $\mu_1=(3,-1)$, $\mu_2=(3,3)$.
Hint 4/4
That run stops at $J=36$ while the left-right split has $J=4$, so the claim is false.
Show solution
One counterexample settles a claim about every run, so we look for a start that stalls.
From $(3,-1)$ and $(3,3)$ the run splits top from bottom and stops: each corner is $9$ from its mean and $13$ from the other.
Answer $$\boxed{\text{False}}$$
Check
The left-right split is also a fixed point, and a better one; K-means can end at either, depending on where it starts.
Restart K-means from several starts and keep the run with the smallest $J$.
2§10.5 — can a mixture density exceed 1?
A classmate claims that a Gaussian mixture density $p(x)=\sum_j\pi_j\mathcal N(x\mid\mu_j,\sigma_j^2)$ can be larger than $1$ at some $x$, even though its mixing coefficients add up to $1$.
Find(a) Is the claim true or false?
Given
$\pi_j\ge0$, $\sum_j\pi_j=1$
test case: $p(x)=0.5\,\mathcal N(x\mid0,\ 0.01)+0.5\,\mathcal N(x\mid3,\ 1)$
Hint 1/4
A density is not a probability; ask what limits its height and what limits its area.
Hint 2/4
$\mathcal N(\mu\mid\mu,\sigma^2)=1/\sqrt{2\pi\sigma^2}$, which grows without limit as $\sigma^2\to0$.
Hint 3/4
In the test case $\sigma_1^2=0.01$, so $\mathcal N(0\mid0,0.01)=1/\sqrt{0.0628}=3.99$, with weight $0.5$.
Hint 4/4
$p(0)\approx0.5(3.99)+0.5(0.004)=2.0>1$, so the claim is true.
Show solution
One evaluation at the narrow component's peak decides the claim.
Street distances add the horizontal and the vertical blocks; first decide which medoid each kiosk is closer to.
Hint 2/4
E: nearest medoid by $V$. M: in each cluster, the member with the smallest total $V$ to the members.
Hint 3/4
The first three kiosks are $0$, $1$ and $2$ blocks from $(0,0)$; $(5,5)$ and $(6,3)$ are $4$ and $5$ from $(7,7)$.
Hint 4/4
Cluster 2's totals are $7$ for $(5,5)$, $8$ for $(6,3)$ and $9$ for $(7,7)$, so the medoids become $(0,0)$ and $(5,5)$; nothing changes after that, and $\tilde J=10$.
Show solution
Each cluster has three members, so the M step is three sums per cluster.
E step
$$\begin{aligned}&(5,5):\ 10\text{ vs }4\\ &(6,3):\ 9\text{ vs }5\end{aligned}$$
Distances to $(0,0)$ and $(7,7)$; the near three kiosks stay with $(0,0)$.
The palette adds only $768$ bits, so the ratio sits just under $24/5=4.8$.
Same label length as K = 5
$$\lceil\log_2K\rceil=3\iff5\le K\le8$$
Three bits name up to $8$ colors.
Answer $$\boxed{\begin{aligned}K=5&:\ 196{,}728\ (\times8.00)\\ K=32&:\ 328{,}448\ (\times4.79)\\ &K=6,7,8\text{ as }K=5\end{aligned}}$$
Check
The ratios sit just below $24/3$ and $24/5$, by the palette's share.
Between powers of two, extra colors are free in label bits and cost only $24$ bits each.
5§10.4 — three runs with lost coin labels
Three runs of $10$ flips were made, each with coin A or coin B picked with probability $1/2$, and the coins were not recorded. The heads counts were $9$, $2$ and $6$.
Find
(a) Compute the posteriors $\gamma_{iA}$.
(b) Compute $\theta_A^{(1)}$ and $\theta_B^{(1)}$.
Given
heads: $9,\ 2,\ 6$ out of $10$
start: $\theta_A^{(0)}=0.7$, $\theta_B^{(0)}=0.4$
each coin picked with probability $1/2$
Hint 1/4
Start from how much better one coin explains each run than the other; the binomial coefficient will cancel.
Hint 2/4
$a_i/b_i=(\theta_A/\theta_B)^{x_i}\big((1-\theta_A)/(1-\theta_B)\big)^{10-x_i}$ and $\gamma_{iA}=\frac{a_i/b_i}{1+a_i/b_i}$; then heads over flips for each coin.
Hint 3/4
With $\theta_A=0.7$ and $\theta_B=0.4$ the two factors are $1.75$ and $0.5$; the heads are $9,2,6$.
Hint 4/4
$\gamma_{iA}=(0.9872,\ 0.0118,\ 0.6422)$, so $\theta_A^{(1)}=0.7776$ and $\theta_B^{(1)}=0.3119$.
Show solution
The ratio $a_i/b_i=1.75^{x_i}0.5^{10-x_i}$ gives each posterior in one line.
E step
$$\frac{a_i}{b_i}=76.968,\ \ 0.01196,\ \ 1.7952$$
The binomial coefficient and the prior $1/2$ are the same for both coins, so they cancel in the ratio, leaving $1.75^{x}\,0.5^{10-x}$ for $x=9,2,6$.
$$\gamma_{iA}=0.9872,\ \ 0.0118,\ \ 0.6422$$
A run's two posteriors add to $1$, so with $r=a_i/b_i$ we get $\gamma_{iA}=r/(1+r)$ without evaluating any binomial probability.
Credit
$$H_A=9(0.9872)+2(0.0118)+6(0.6422)=12.7617$$
Coin A made each run with probability $\gamma_{iA}$, so it is credited with that fraction of the run's heads.
$$F_A=10(0.9872+0.0118+0.6422)=16.4124$$
The same fraction of each run's $10$ flips, so heads and flips are credited on the same footing.
A symmetric $3\times3$ matrix has $6$ free entries; a diagonal one has $3$.
Answer $$\boxed{39\ \text{and}\ 27}$$
Check
Edge check with $p=1$: both versions give $3+4+4=11$, as they must, since a $1\times1$ covariance is diagonal.
Diagonal covariances save $K\,p(p-1)/2$ numbers, the off-diagonal ones.
7§10.6 — responsibilities with unequal spreads
Two components in the plane: component 1 has $\pi_1=0.3$, $\mu_1=(0,0)$, $\Sigma_1=\operatorname{diag}(1,4)$; component 2 has $\pi_2=0.7$, $\mu_2=(3,0)$, $\Sigma_2=I$. A point is observed at $x=(1,2)$.
Evaluate each Gaussian at the point first; the shares enter only at the end.
Hint 2/4
In two dimensions $$\mathcal N(x\mid\mu,\Sigma)=\frac{1}{2\pi\lvert\Sigma\rvert^{1/2}}\exp\big(-\tfrac12(x-\mu)^T\Sigma^{-1}(x-\mu)\big)$$ then $\gamma(z_1)=\pi_1\mathcal N_1/(\pi_1\mathcal N_1+\pi_2\mathcal N_2)$.
Hint 3/4
$x-\mu_1=(1,2)$ with $\Sigma_1^{-1}=\operatorname{diag}(1,\tfrac14)$; $x-\mu_2=(-2,2)$ with $\Sigma_2^{-1}=I$; $\pi=(0.3,0.7)$.
Hint 4/4
$\mathcal N_1=e^{-1}/(4\pi)=0.0293$ and $\mathcal N_2=e^{-4}/(2\pi)=0.0029$, so $\gamma(z_1)=0.81$.
Show solution
Diagonal covariances make each quadratic form a sum of two scaled squares.
Bayes' rule weighs each density by its share; component 1's density is ten times larger, which outweighs a share less than half as big.
Answer $$\boxed{\gamma(z_1)=0.8115}$$
Check
Log-odds route: $\log\frac{0.3}{0.7}+(-1-\log(4\pi))-(-4-\log(2\pi))=-0.847+3-0.693=1.460$, and $1/(1+e^{-1.460})=0.8115$.
Stretching halves a component's peak here ($\lvert\Sigma_1\rvert^{1/2}=2$) but pays back in the exponent: with $\Sigma_1=I$ the same point would give $\gamma(z_1)=0.66$, with the stretch $0.81$.
8§10.7 — an M step from a table of responsibilities
An E step on five numbers has produced the responsibilities of component 1 below; component 2 has the rest of each point.
Find
(a) Compute $N_1$, $N_2$, $\pi_1$ and $\pi_2$.
(b) Compute $\mu_1$, $\mu_2$, $\sigma_1^2$ and $\sigma_2^2$.
$N_1$ is the column sum $1+0.9+0.6+0.1+0$; $N_2=5-N_1$ because each point's two responsibilities add to $1$, and a share is a count over all $n=5$ points.
The maximizing mean does not depend on the variance, so $\sigma_1^2$ is fitted around the new $\mu_1=3.6923$, each squared deviation with its point's weight.
The same rule for component 2 around $9.3333$; its weights $0, \allowbreak 0.1, \allowbreak 0.4, \allowbreak 0.9, \allowbreak 1$ are one minus component 1's.
$0.52(3.6923)+0.48(9.3333)=6.4$, the plain mean of $2,4,5,10,11$.
A point with a small responsibility can still dominate a variance: $10$, with weight only $0.1$, adds $3.98$ to the weighted sum, about $1.5$ of $\sigma_1^2=3.06$, because it is far from $\mu_1$.
C · exam level 5 questions
1§10.7 — the new mean after one EM iteration
A two-component mixture is fitted to the numbers $2,5,6,9$. The current parameters are $\pi=(0.5,0.5)$, $\mu=(2,6)$ and $\sigma^2=(4,4)$.
Find(a) After one EM iteration, what is $\mu_1^{\text{new}}$?
Responsibilities first, then a weighted mean; with equal shares and variances each responsibility comes from one log-odds.
Hint 2/4
$\log\frac{\gamma(z_{i1})}{\gamma(z_{i2})}=\frac{(x_i-\mu_2)^2-(x_i-\mu_1)^2}{2\sigma^2}$, then $\mu_1^{\text{new}}=\sum_i\gamma(z_{i1})x_i/\sum_i\gamma(z_{i1})$.
Hint 3/4
With $\mu=(2,6)$ and $\sigma^2=4$ the log-odds is $((x-6)^2-(x-2)^2)/8=4-x$, for $x=2,5,6,9$.
Hint 4/4
$\gamma(z_{i1})=0.8808,\ \allowbreak 0.2689,\ \allowbreak 0.1192,\ \allowbreak 0.0067$, so $\mu_1^{\text{new}}=3.8816/1.2756=3.04$.
Show solution
The log-odds is linear in $x$ here, which avoids four density evaluations per component.
$$(0,0):\ 4\text{ to }\mu_1,\ \ 8\text{ to }\mu_2$$
Nothing moves, so the run stops at $16$.
Answer $$\boxed{J=16}$$
Check
The top-bottom split, with means $(1,0)$ and $(1,4)$, has $J=4\times1=4$, so $16$ is a local minimum four times the best.
On an elongated shape, prototypes that start on the long sides split it the wrong way.
3§10.7 — the Lagrange multiplier for the shares
To maximize $l(\pi,\mu,\Sigma)$ over the shares, the derivation adds $\lambda\big(\sum_k\pi_k-1\big)$ and sets the derivative in each $\pi_j$ to zero. For every $j$ this gives $\sum_i\mathcal N(x_i\mid\mu_j,\Sigma_j)/p(x_i)+\lambda=0$, where the data have $n$ points and the mixture $K$ components.
Find(a) What is $\lambda$?
Given
$\sum_{i=1}^n\mathcal N(x_i\mid\mu_j,\Sigma_j)/p(x_i)+\lambda=0$ for $j=1,\dots,K$
The $K$ equations share one unknown; combine them so that the constraint $\sum_j\pi_j=1$ appears.
Hint 2/4
Multiply equation $j$ by $\pi_j$: since $\pi_j\mathcal N(x_i\mid\mu_j,\Sigma_j)/p(x_i)=\gamma(z_{ij})$, it becomes $\sum_i\gamma(z_{ij})+\lambda\pi_j=0$.
Hint 3/4
Sum over $j=1,\dots,K$: each point's responsibilities add to $1$, and $\sum_j\pi_j=1$.
Hint 4/4
$n+\lambda=0$, so $\lambda=-n$ and $\pi_j=N_j/n$.
Show solution
Multiplying by $\pi_j$ turns each condition into responsibilities, which sum neatly.
$\pi_j\mathcal N(x_i\mid\mu_j,\Sigma_j)/p(x_i)$ is the responsibility.
Sum over j
$$\sum_jN_j+\lambda\sum_j\pi_j=n+\lambda=0$$
Every point's responsibilities add to $1$.
$$\lambda=-n\ \Rightarrow\ \pi_j=N_j/n$$
Substituting $\lambda=-n$ into $N_j+\lambda\pi_j=0$ isolates $\pi_j$, and it satisfies the constraint by construction.
Answer $$\boxed{\lambda=-n}$$
Check
The resulting shares add up to $\sum_jN_j/n=1$, so the constraint holds, as it must.
Whenever a constraint says weights add to one, summing the multiplied conditions finds $\lambda$.
4§10.4 — the first EM update of a coin bias
Two runs of $10$ flips were made, each with a hidden coin, A or B with probability $1/2$. They showed $7$ and $2$ heads. EM starts from $\theta_A^{(0)}=0.6$ and $\theta_B^{(0)}=0.4$.
The E step first: how likely is coin A for each run? Only then count.
Hint 2/4
$\gamma_{iA}=\frac{a_i/b_i}{1+a_i/b_i}$ with $a_i/b_i=1.5^{2x_i-10}$ for these guesses; $\theta_A^{(1)}=\sum_i\gamma_{iA}x_i\big/\big(10\sum_i\gamma_{iA}\big)$.
Hint 3/4
Heads $7$ and $2$: the ratios are $1.5^4=5.0625$ and $1.5^{-6}=0.0878$.
Hint 4/4
$\gamma_A=(0.8351,\ 0.0807)$, so $\theta_A^{(1)}=6.0068/9.1576=0.656$.
Show solution
With $\theta_A=1-\theta_B$ the ratio is a power of $1.5$.
With $\theta_A=1-\theta_B$ each head multiplies the ratio by $1.5$ and each tail divides it by $1.5$, so $7$ heads and $3$ tails give $1.5^{4}$, and $2$ and $8$ give $1.5^{-6}$.
Each run gives A the fraction $\gamma_{iA}$ of its heads and of its flips, and the M step treats these as if they were observed counts.
Answer $$\boxed{\theta_A^{(1)}=0.656}$$
Check
Coin B gets $2.9932$ heads out of $10.8424$ flips, $0.276$, and the heads add up: $6.0068+2.9932=9$.
Coin A ends below $0.7$ because EM still credits it with $8\%$ of the $2$-head run; the $7$-head run alone gives exactly $0.7$, whatever its share.
5§10.3 — the largest palette that fits a budget
A $500\times400$ RGB image, $8$ bits per channel, must be stored in at most $600{,}000$ bits as a K-means palette plus a fixed-length label per pixel.
Find(a) What is the largest $K$ that fits?
Given
$500\times400$ pixels
budget: $600{,}000$ bits
size $=24K+n\lceil\log_2K\rceil$
Hint 1/4
The label length jumps just after powers of two, so check the values of $K$ on either side of each jump.
Hint 2/4
The condition is $24K+n\lceil\log_2K\rceil\le600{,}000$.
Hint 3/4
$n=200{,}000$; labels of $3$ bits alone already take $600{,}000$ bits.
Hint 4/4
Only $2$-bit labels fit, so $K\le4$, and $K=4$ takes $400{,}096$ bits.
Show solution
The label bits jump in steps, so we test the step edges.
Three-bit labels
$$K=5:\ 120+600{,}000=600{,}120>600{,}000$$
Five colors need $3$-bit labels, which alone fill the $600{,}000$ budget; the palette's $120$ bits push it over.
Two-bit labels
$$K=4:\ 96+400{,}000=400{,}096\le600{,}000$$
Four colors still fit in $2$-bit labels, and every $K$ from $5$ to $8$ costs more than $K=5$ did.
Answer $$\boxed{K=4}$$
Check
Every $K$ from $5$ to $8$ also needs $3$ bits per label and is over budget; $K=4$ is the edge.
Budgets on compressed size are decided by the label length first and the palette second.
D · interleaved 4 questions
1§10.5 — six readings and two models
Six readings are $1,2,3,7,8,9$. Model A is one Gaussian fitted by maximum likelihood. Model B is the mixture $0.5\,\mathcal N(x\mid2,\tfrac23)+0.5\,\mathcal N(x\mid8,\tfrac23)$.
Find
(a) Fit model A: give $\hat\mu$ and $\hat\sigma^2$.
(b) Compare the two densities at $x=5$ and at $x=2$.
(c) Compare the log-likelihoods of the six readings under the two models.
Given
readings $1,\ 2,\ 3,\ 7,\ 8,\ 9$
model B: $p(x)=0.5\,\mathcal N(x\mid2,\tfrac23)+0.5\,\mathcal N(x\mid8,\tfrac23)$
Hint 1/4
Fit A with the usual estimates, then evaluate both models where the readings are and where they are not.
Hint 2/4
Gaussian MLE: $\hat\mu=\bar x$, $\hat\sigma^2=\frac1n\sum_i(x_i-\bar x)^2$; a log-likelihood is $\sum_i\log p(x_i)$.
Hint 3/4
Readings $1,2,3,7,8,9$: $\bar x=5$ and $\sum_i(x_i-5)^2=58$; model B has means $2$ and $8$ and variance $2/3$.
Hint 4/4
$\hat\sigma^2=9.667$; at $5$, A gives $0.128$ and B $0.0006$; at $2$, A gives $0.081$ and B $0.244$; $l_A=-15.32<l_B=-11.46$.
Show solution
The single Gaussian has closed-form estimates; model B only needs evaluating.
Ratio check at $x=5$: $0.1283/0.00057\approx220$, so A believes the gap between the groups is the most likely place for a reading, which the data contradict.
Maximum likelihood fits the model it is given; if that model has one hump, it cannot see two groups.
2§10.6 — a resistor from one of two suppliers
A lab buys $80$ of every $100$ resistors from supplier 1, whose values follow $\mathcal N(100,\ 1)$ in ohms, and the rest from supplier 2, whose values follow $\mathcal N(103,\ 4)$. A resistor from the drawer measures $102$ ohms.
Find(a) What is the probability that the resistor came from supplier 2?
Bayes' rule: each density is weighted by its prior share, and the denominator is the total probability of $102$.
Answer $$\boxed{0.449}$$
Check
Odds check: prior odds $0.2/0.8=0.25$ times the density ratio $0.1760/0.0540=3.26$ gives $0.815$, and $0.815/1.815=0.449$.
This is a responsibility under another name: a mixture of two suppliers.
3§10.7 — five fitted mixtures and one table
Mixtures with $K=1,\dots,5$ components were fitted by EM to $120$ training readings, keeping the best of $20$ starts for each $K$. Each fit was then scored by its log-likelihood on the training readings and on $60$ held-out readings.
Find
(a) Which $K$ would the training log-likelihood choose, and why is that no help?
(b) Which $K$ do the held-out readings support?
(c) What do the tiny variances at $K=4$ and $K=5$ tell you?
Given
training $l$ for $K=1,\dots,5$: $-326.8,\ \allowbreak -313.7,\ \allowbreak -306.1,\ \allowbreak -301.7,\ \allowbreak -297.1$
the fits with $K=4$ and $K=5$ contain components with variances $0.05$ and $0.02$
Hint 1/4
Ask which of the two columns can get worse when the model gets more flexible.
Hint 2/4
A mixture with more components contains every smaller one, so its best training $l$ cannot be lower; a held-out log-likelihood measures fit to new data, as in cross-validation.
Training picks $K=5$ by construction; the held-out column peaks at $K=3$; the tiny variances are components wrapped around a few training readings.
Show solution
The training column cannot decide, so we look for the peak of the held-out column.
Training column
$$-326.8<-313.7<-306.1<-301.7<-297.1$$
It rises at every $K$, so it always points to the largest.
Held-out column
$$-159.2<-155.4<-153.4>-157.2>-162.3$$
It peaks at $K=3$.
The tiny variances
$$\sigma^2=0.05,\ 0.02$$
Such narrow components sit on a few training readings; new readings rarely land exactly there, which lowers the held-out $l$.
Answer $$\boxed{K=3}$$
Check
The readings were simulated from a mixture with three components, so $K=3$ is the right answer here.
Choose $K$ on data the fit has not seen; the training log-likelihood always asks for more components.
4§10.7 — a gradient step against an EM step
A two-component mixture is fitted to $1,3,4,8,9$ with the current parameters $\pi=(0.5,0.5)$, $\mu=(2,8)$ and $\sigma^2=(4,4)$. The responsibilities of component 1 at these parameters are $0.9975,\ \allowbreak 0.9526,\ \allowbreak 0.8176,\ \allowbreak 0.0110,\ \allowbreak 0.0025$.
Find
(a) Compute $\partial l/\partial\mu_1$ at the current parameters.
(b) Take one gradient ascent step with $\eta=0.5$.
(c) Show that the EM update of $\mu_1$ is a gradient step, and find its step size.
Differentiate the log-likelihood in $\mu_1$, look for the responsibilities in the result, then compare it with the EM formula.
Hint 2/4
In one dimension $\dfrac{\partial l}{\partial\mu_1}=\sum_i\gamma(z_{i1})\dfrac{x_i-\mu_1}{\sigma_1^2}$.
Hint 3/4
With $\mu_1=2$ and $\sigma_1^2=4$ the deviations are $-1,1,2,6,7$ and the weights $0.9975, \allowbreak 0.9526, \allowbreak 0.8176, \allowbreak 0.0110, \allowbreak 0.0025$; $N_1=2.7811$.
Hint 4/4
The gradient is $0.4184$; $\eta=0.5$ gives $\mu_1=2.2092$; EM is the step with $\eta=\sigma_1^2/N_1=1.4383$, which lands at $2.6017$.
Show solution
The gradient already contains the responsibilities, so the two updates can be put side by side.
$$\begin{aligned}J&=\textstyle\sum_i\sum_kr_{ik}{\lVert x_i-\mu_k\rVert}^2\\ \text{E: }r_{ik}&=1\text{ for the nearest }\mu_k\\ \text{M: }\mu_k&=\frac{\sum_ir_{ik}x_i}{\sum_ir_{ik}}\end{aligned}$$
$K$ fixed; a point moves only to a strictly nearer prototype
the mixture density, its latent variable and its log-likelihood;
the responsibility formula;
the EM updates for a Gaussian mixture, and where the share update comes from.
Then reopen the page and compare; whatever is missing is your reread list.
Run K-means by hand on a few points, keep track of $J$, and give a start that stops at a worse split?
c-kmeans
Pick the medoid of a small cluster under the Manhattan distance, and assign a vector by cosine dissimilarity?
c-kmedoids
Compute the size of a compressed image for a given $K$, with the ceiling right?
c-compression
Do one EM iteration for two hidden coins, including the credited heads and flips?
c-coins
Write a mixture's density, latent variable and log-likelihood, and count its parameters?
c-mixture
Compute a responsibility, and explain why it can disagree with the nearest mean?
c-responsibility
Do one full EM iteration for a one-dimensional mixture, derive $\pi_j=N_j/n$, and check that $l$ went up?
c-em-gmm
Glossary (26 terms)
clusteringkümeleme
Splitting unlabeled data into groups of similar points, with no labels to learn from.
clusterküme
One of the groups a clustering method finds.
K-meansK ortalamalar
A clustering method that alternates assigning each point to its nearest prototype and moving each prototype to the mean of its points, lowering the distortion $J$ at every step.
prototypeprototip
The vector $\mu_k$ that represents cluster $k$; in K-means it is the cluster's mean.
distortion measure
The K-means objective $J$: the total squared distance of the points to the prototypes of their clusters.
hard assignment
Each point belongs to exactly one cluster, coded by $r_{ik}\in\{0,1\}$.
K-medoids
A variant of K-means that uses a general dissimilarity $V$ and requires each prototype to be one of the data points.
medoid
The member of a cluster with the smallest total dissimilarity to the other members.
dissimilaritybenzemezlik ölçüsü
A nonnegative score $V(x,\mu)$ that is small for similar vectors, such as a distance.
Manhattan distanceManhattan uzaklığı
The sum of absolute coordinate differences, $\sum_j\lvert x_j-\mu_j\rvert$; far points count less than under squared distance.
cosine dissimilaritykosinüs uzaklığı
One minus the cosine of the angle between two vectors; it ignores their lengths.
outlieraykırı değer
A point far away from the rest of the data.
image segmentationgörüntü bölütleme
Splitting an image into regions of similar appearance, here by clustering pixel colors.
görüntü sıkıştırma
Storing an image in fewer bits; with K-means, as $K$ colors plus one label per pixel.
latent variablegizli değişken
A variable of the model that is never observed, such as the coin behind a run or the component behind a point.
tam veri
The observed data together with the values of the latent variables.
missing dataeksik veri
Values that were not recorded; here, the latent labels, so only the observed part is available.
mixture of GaussiansGauss karışım modeli
The density $p(x)=\sum_j\pi_j\mathcal N(x\mid\mu_j,\Sigma_j)$: pick component $j$ with probability $\pi_j$, then draw from its Gaussian.
mixing coefficientkarışım katsayısı
The weight $\pi_j$ of component $j$ in a mixture; the weights are nonnegative and add up to $1$.
responsibility
The posterior probability $\gamma(z_{ij})=p(z_{ij}=1\mid x_i)$ that component $j$ produced the point $x_i$.
soft assignment
An assignment of each point to every cluster with a probability, as the responsibilities do.
beklenti maksimizasyonu
An iterative method for maximum likelihood with latent variables: compute their posteriors (E step), then maximize the expected complete-data log-likelihood (M step).
effective number of points
$N_j=\sum_i\gamma(z_{ij})$, the number of points component $j$ accounts for; usually not a whole number.
local minimumyerel minimum
A state that no single step of the method can improve, although a better one exists elsewhere.
Lagrange multiplierLagrange çarpanı
The extra variable $\lambda$ that handles an equality constraint, here $\sum_j\pi_j=1$.
singular solution
A degenerate maximum of a mixture likelihood in which one component shrinks onto a single data point and its variance goes to zero.
What comes next
§11 · Feature selection
Here every point kept all of its features, and we asked which group it belongs to. Next the question turns to the features themselves: which of them are worth keeping at all.
Sources
textbookT. Hastie, R. Tibshirani, J. Friedman, The Elements of Statistical Learning, Springer (course textbook) The weekly line names no chapter of the book, so no section numbers are cited here.
course materialEEE 485 lecture slides and lecture notes, chapter 10: Clustering Scope, order of topics and notation (r_ik, mu_k, J, V, J tilde, N_k, theta_A, theta_B, pi_j, z, gamma(z_ij), N_j, l) follow these materials; all explanations, data, figures and exercises here are original.
course materialEEE 485 syllabus page on STARS, Fall 2026-27, printed 21 September 2026 Assessment weights, the weekly topic list and the recommended books.
textbookC. M. Bishop, Pattern Recognition and Machine Learning, Springer One of the recommended books on the syllabus; the lecture's K-means and EM illustrations come from it.
standard resultC. B. Do and S. Batzoglou, a primer on the EM algorithm, Nature Biotechnology 26(8), 2008 The article the lecture cites for its two-coin experiment; the coin data on this page are new.
standard resultBayes' rule, the binomial and Gaussian distributions, and Lagrange multipliers Standard results used in the derivations. Every number and figure on this page was computed for it.