The EM Algorithm
Chapter Seventy-One
Syllabus topic Module 2, "EM Algorithm"
Pages 420 to 429 of 591
In one line
Guess the parameters, use them to work out how probable each hidden value is, count with those probabilities as weights, and repeat until nothing changes.
In the wording a student can write in an examination: the expectation maximisation algorithm, or EM, finds maximum likelihood estimates when some variables are hidden. It alternates an E step, which computes the posterior distribution over the hidden variables given the current parameters, and an M step, which re-estimates the parameters by the ordinary complete-data method using those posteriors as fractional counts.
Why it exists
Hidden Variables left a circle:
the parameters <- need the hidden assignments
the assignments <- need the parameters
EM is the observation that a circle can be walked round. Neither side is known, so start anywhere on one side and go round, and the remarkable fact, proved below by running it, is that every lap improves the fit.
The two steps
Both steps in the form to reproduce in an answer.
E step. For each observation and each value of the hidden variable, compute the posterior probability of that value given the observation and the current parameters. This is Bayes rule:
responsibility of component A for an observation
= w P(observation given A) / ( w P(observation given A) + (1-w) * P(observation given B) )
It is not a guess at the hidden value. It is a distribution over it, and the whole method depends on keeping the distribution rather than choosing from it. The posteriors are called the responsibilities.
M step. Do exactly the counting of Learning With Complete Data, except that each observation contributes to every component, weighted by that component's responsibility:
p for A = (sum of responsibility heads) / (sum of responsibility flips)
w = the average responsibility
Fractional counts. That is the one idea to carry away. An observation is not assigned to a component; it is divided between them.
The run
# Expectation maximisation on the two-coin mixture of the previous chapter: the
# responsibilities of the first E step in full, the whole iteration, the proof
# that the log likelihood never falls, and the two ways it goes wrong.
import math
def lcg(seed):
x = seed
while True:
x = (1664525 * x + 1013904223) % (2 ** 32)
yield x / 2 ** 32
gen = lcg(20260930)
rnd = lambda: next(gen) # noqa: E731
P_A, P_B, MIX = 0.80, 0.30, 0.5 # the truth, which EM never sees
FLIPS, RUNS = 10, 12
records = []
for _ in range(RUNS):
coin = "A" if rnd() < MIX else "B"
p = P_A if coin == "A" else P_B
heads = sum(1 for _ in range(FLIPS) if rnd() < p)
records.append((coin, heads))
OBSERVED = [h for _, h in records] # all EM is given
def p_heads(p, h):
return p ** h * (1 - p) ** (FLIPS - h)
def loglik(pa, pb, w):
return sum(math.log(w * p_heads(pa, h) + (1 - w) * p_heads(pb, h))
for h in OBSERVED)
def e_step(pa, pb, w):
"""RESPONSIBILITIES: for each experiment, the posterior probability that
coin A produced it. This is Bayes rule, with the current parameters."""
out = []
for h in OBSERVED:
a = w * p_heads(pa, h)
b = (1 - w) * p_heads(pb, h)
out.append(a / (a + b))
return out
def m_step(resp):
"""The counting of the complete-data chapter, with FRACTIONAL counts."""
heads_a = sum(r * h for r, h in zip(resp, OBSERVED))
flips_a = sum(r * FLIPS for r in resp)
heads_b = sum((1 - r) * h for r, h in zip(resp, OBSERVED))
flips_b = sum((1 - r) * FLIPS for r in resp)
return heads_a / flips_a, heads_b / flips_b, sum(resp) / len(resp)
print("EM is given ONLY the head counts: %s" % " ".join("%d" % h for h in OBSERVED))
print("the coin used in each experiment is hidden. EM never sees it.")
print()
print("THE IDEA. if the coins were known the answer would be a count; if the")
print("parameters were known the coins could be inferred by Bayes rule. so:")
print(" E step: with the current parameters, compute for each experiment the")
print(" PROBABILITY that each coin produced it. that is not a guess at")
print(" the hidden value; it is a distribution over it.")
print(" M step: do the counting of the complete-data case, but weight each")
print(" experiment by those probabilities. FRACTIONAL COUNTS.")
print("repeat. the log likelihood cannot fall, which is proved below by running.")
print()
pa, pb, w = 0.60, 0.50, 0.5
print("START at p_A = %.2f, p_B = %.2f, w = %.2f, chosen deliberately UNEQUAL."
% (pa, pb, w))
print()
print("THE FIRST E STEP IN FULL. responsibility of coin A for each experiment:")
resp = e_step(pa, pb, w)
print(" heads | P(heads | A) | P(heads | B) | responsibility of A")
for h, r in zip(OBSERVED, resp):
print(" %5d | %13.10f | %13.10f | %18.4f"
% (h, p_heads(pa, h), p_heads(pb, h), r))
print()
middling = min(resp, key=lambda r: abs(r - 0.5))
print(" nine heads is far more likely under the coin currently believed to be")
print(" the heavier one, so it is assigned to A with high probability; two")
print(" heads goes the other way. NOTHING IS ROUNDED: the experiment at %.4f"
% middling)
print(" counts %.2f towards coin A and %.2f towards coin B, both at once."
% (middling, 1 - middling))
print()
print("THE FIRST M STEP. the fractional counts:")
heads_a = sum(r * h for r, h in zip(resp, OBSERVED))
flips_a = sum(r * FLIPS for r in resp)
print(" coin A: %.4f heads out of %.4f flips -> p_A = %.4f"
% (heads_a, flips_a, heads_a / flips_a))
heads_b = sum((1 - r) * h for r, h in zip(resp, OBSERVED))
flips_b = sum((1 - r) * FLIPS for r in resp)
print(" coin B: %.4f heads out of %.4f flips -> p_B = %.4f"
% (heads_b, flips_b, heads_b / flips_b))
print(" w = the average responsibility = %.4f" % (sum(resp) / len(resp)))
print()
print("THE WHOLE ITERATION.")
print(" iter | p_A | p_B | w | log likelihood | change")
print(" %4d | %6.4f | %6.4f | %6.4f | %14.6f |" % (0, pa, pb, w, loglik(pa, pb, w)))
prev = loglik(pa, pb, w)
for it in range(1, 21):
pa, pb, w = m_step(e_step(pa, pb, w))
ll = loglik(pa, pb, w)
print(" %4d | %6.4f | %6.4f | %6.4f | %14.6f | %+.6f"
% (it, pa, pb, w, ll, ll - prev))
prev_at_19, prev = prev, ll
print()
print(" the CHANGE column is POSITIVE at every round until it reaches zero.")
print(" that is the theorem: each round of EM increases the log likelihood or")
print(" leaves it unchanged, so the iteration converges. it says nothing about")
print(" converging to the BEST maximum, only to a stationary point.")
print(" the last row's %+.6f is floating-point rounding at a fixed point that"
% (ll - prev_at_19))
print(" has already been reached; the two values differ by %.2e, which is the"
% abs(ll - prev_at_19))
print(" last few bits of a double and not a decrease.")
print()
print(" the grid search of the previous chapter found %.4f as the best value"
% -69.1228)
print(" on a grid of 1/100, holding the mixing weight at 0.5. EM reached %.4f"
% loglik(pa, pb, w))
print(" in %d rounds without any search, and it fits the weight too, which is"
% 20)
print(" where most of the difference between the two numbers comes from.")
print(" true parameters were %.2f and %.2f with w = %.2f; EM recovered %.4f"
% (P_A, P_B, MIX, pa))
print(" and %.4f with w = %.4f from twelve experiments." % (pb, w))
print()
print("FAILURE ONE: A SYMMETRIC START. set both coins to the same value.")
pa, pb, w = 0.50, 0.50, 0.5
print(" iter | p_A | p_B | w | log likelihood")
for it in range(0, 6):
print(" %4d | %6.4f | %6.4f | %6.4f | %14.6f" % (it, pa, pb, w, loglik(pa, pb, w)))
pa, pb, w = m_step(e_step(pa, pb, w))
print(" it never moves. with the coins equal every responsibility is exactly")
print(" 0.5, so both fractional counts are the same and the M step returns the")
print(" pooled estimate for both coins, for ever. EM IS STUCK AT A SADDLE.")
print()
print("FAILURE TWO: THE LABELS COME OUT THE OTHER WAY. start with B the heavier.")
pa, pb, w = 0.50, 0.60, 0.5
for _ in range(60):
pa, pb, w = m_step(e_step(pa, pb, w))
print(" converged to p_A = %.4f, p_B = %.4f, w = %.4f" % (pa, pb, w))
print(" log likelihood %.6f, which is the SAME as before." % loglik(pa, pb, w))
print(" the two coins have simply exchanged names. nothing is wrong with the")
print(" fit; the names of mixture components are not recoverable from data.")
print()
print("WHAT DIFFERENT STARTS CONVERGE TO, run out to 200 rounds each:")
print(" start p_A, p_B | final p_A | final p_B | final w | log likelihood")
for start in ((0.60, 0.50), (0.50, 0.60), (0.99, 0.01), (0.01, 0.99),
(0.70, 0.65), (0.50, 0.50)):
pa, pb, w = start[0], start[1], 0.5
for _ in range(200):
pa, pb, w = m_step(e_step(pa, pb, w))
print(" %6.2f, %6.2f | %9.4f | %9.4f | %7.4f | %14.6f"
% (start[0], start[1], pa, pb, w, loglik(pa, pb, w)))
print(" every unequal start reaches the same log likelihood, at one of the two")
print(" relabellings. the equal start reaches a worse value and stays there.")
print(" in practice EM is run from several random starts and the best kept.")The EM Algorithm
EM is given ONLY the head counts: 9 8 9 9 9 4 8 3 7 6 1 2
the coin used in each experiment is hidden. EM never sees it.
THE IDEA. if the coins were known the answer would be a count; if the
parameters were known the coins could be inferred by Bayes rule. so:
E step: with the current parameters, compute for each experiment the
PROBABILITY that each coin produced it. that is not a guess at
the hidden value; it is a distribution over it.
M step: do the counting of the complete-data case, but weight each
experiment by those probabilities. FRACTIONAL COUNTS.
repeat. the log likelihood cannot fall, which is proved below by running.
START at p_A = 0.60, p_B = 0.50, w = 0.50, chosen deliberately UNEQUAL.
THE FIRST E STEP IN FULL. responsibility of coin A for each experiment:
heads | P(heads | A) | P(heads | B) | responsibility of A
9 | 0.0040310784 | 0.0009765625 | 0.8050
8 | 0.0026873856 | 0.0009765625 | 0.7335
9 | 0.0040310784 | 0.0009765625 | 0.8050
9 | 0.0040310784 | 0.0009765625 | 0.8050
9 | 0.0040310784 | 0.0009765625 | 0.8050
4 | 0.0005308416 | 0.0009765625 | 0.3522
8 | 0.0026873856 | 0.0009765625 | 0.7335
3 | 0.0003538944 | 0.0009765625 | 0.2660
7 | 0.0017915904 | 0.0009765625 | 0.6472
6 | 0.0011943936 | 0.0009765625 | 0.5502
1 | 0.0001572864 | 0.0009765625 | 0.1387
2 | 0.0002359296 | 0.0009765625 | 0.1946
nine heads is far more likely under the coin currently believed to be
the heavier one, so it is assigned to A with high probability; two
heads goes the other way. NOTHING IS ROUNDED: the experiment at 0.5502
counts 0.55 towards coin A and 0.45 towards coin B, both at once.
THE FIRST M STEP. the fractional counts:
coin A: 51.2810 heads out of 68.3571 flips -> p_A = 0.7502
coin B: 23.7190 heads out of 51.6429 flips -> p_B = 0.4593
w = the average responsibility = 0.5696
THE WHOLE ITERATION.
iter | p_A | p_B | w | log likelihood | change
0 | 0.6000 | 0.5000 | 0.5000 | -79.362332 |
1 | 0.7502 | 0.4593 | 0.5696 | -72.405673 | +6.956659
2 | 0.8212 | 0.3260 | 0.6038 | -68.901852 | +3.503821
3 | 0.8215 | 0.2836 | 0.6347 | -68.617504 | +0.284349
4 | 0.8166 | 0.2687 | 0.6503 | -68.567150 | +0.050353
5 | 0.8144 | 0.2630 | 0.6565 | -68.559498 | +0.007652
6 | 0.8136 | 0.2610 | 0.6587 | -68.558535 | +0.000963
7 | 0.8133 | 0.2603 | 0.6594 | -68.558422 | +0.000113
8 | 0.8132 | 0.2601 | 0.6597 | -68.558409 | +0.000013
9 | 0.8132 | 0.2600 | 0.6598 | -68.558408 | +0.000001
10 | 0.8132 | 0.2600 | 0.6598 | -68.558408 | +0.000000
11 | 0.8132 | 0.2600 | 0.6598 | -68.558408 | +0.000000
12 | 0.8132 | 0.2600 | 0.6598 | -68.558408 | +0.000000
13 | 0.8132 | 0.2600 | 0.6598 | -68.558408 | +0.000000
14 | 0.8132 | 0.2600 | 0.6598 | -68.558408 | +0.000000
15 | 0.8132 | 0.2600 | 0.6598 | -68.558408 | +0.000000
16 | 0.8132 | 0.2600 | 0.6598 | -68.558408 | +0.000000
17 | 0.8132 | 0.2600 | 0.6598 | -68.558408 | +0.000000
18 | 0.8132 | 0.2600 | 0.6598 | -68.558408 | +0.000000
19 | 0.8132 | 0.2600 | 0.6598 | -68.558408 | +0.000000
20 | 0.8132 | 0.2600 | 0.6598 | -68.558408 | -0.000000
the CHANGE column is POSITIVE at every round until it reaches zero.
that is the theorem: each round of EM increases the log likelihood or
leaves it unchanged, so the iteration converges. it says nothing about
converging to the BEST maximum, only to a stationary point.
the last row's -0.000000 is floating-point rounding at a fixed point that
has already been reached; the two values differ by 1.42e-14, which is the
last few bits of a double and not a decrease.
the grid search of the previous chapter found -69.1228 as the best value
on a grid of 1/100, holding the mixing weight at 0.5. EM reached -68.5584
in 20 rounds without any search, and it fits the weight too, which is
where most of the difference between the two numbers comes from.
true parameters were 0.80 and 0.30 with w = 0.50; EM recovered 0.8132
and 0.2600 with w = 0.6598 from twelve experiments.
FAILURE ONE: A SYMMETRIC START. set both coins to the same value.
iter | p_A | p_B | w | log likelihood
0 | 0.5000 | 0.5000 | 0.5000 | -83.177662
1 | 0.6250 | 0.6250 | 0.5000 | -79.387589
2 | 0.6250 | 0.6250 | 0.5000 | -79.387589
3 | 0.6250 | 0.6250 | 0.5000 | -79.387589
4 | 0.6250 | 0.6250 | 0.5000 | -79.387589
5 | 0.6250 | 0.6250 | 0.5000 | -79.387589
it never moves. with the coins equal every responsibility is exactly
0.5, so both fractional counts are the same and the M step returns the
pooled estimate for both coins, for ever. EM IS STUCK AT A SADDLE.
FAILURE TWO: THE LABELS COME OUT THE OTHER WAY. start with B the heavier.
converged to p_A = 0.2600, p_B = 0.8132, w = 0.3402
log likelihood -68.558408, which is the SAME as before.
the two coins have simply exchanged names. nothing is wrong with the
fit; the names of mixture components are not recoverable from data.
WHAT DIFFERENT STARTS CONVERGE TO, run out to 200 rounds each:
start p_A, p_B | final p_A | final p_B | final w | log likelihood
0.60, 0.50 | 0.8132 | 0.2600 | 0.6598 | -68.558408
0.50, 0.60 | 0.2600 | 0.8132 | 0.3402 | -68.558408
0.99, 0.01 | 0.8132 | 0.2600 | 0.6598 | -68.558408
0.01, 0.99 | 0.2600 | 0.8132 | 0.3402 | -68.558408
0.70, 0.65 | 0.8132 | 0.2600 | 0.6598 | -68.558408
0.50, 0.50 | 0.6250 | 0.6250 | 0.5000 | -79.387589
every unequal start reaches the same log likelihood, at one of the two
relabellings. the equal start reaches a worse value and stays there.
in practice EM is run from several random starts and the best kept.The EM Algorithm
The first E step, read
Twelve experiments, with the parameters at the deliberately poor start p_A = 0.60, p_B = 0.50.
The EM Algorithm
| Heads | Responsibility of A |
|---|---|
| 9 | 0.8050 |
| 8 | 0.7335 |
| 7 | 0.6472 |
| 6 | 0.5502 |
| 4 | 0.3522 |
| 3 | 0.2660 |
| 2 | 0.1946 |
| 1 | 0.1387 |
The EM Algorithm
The ordering is the point: the more heads, the more the heavier coin is held responsible, and the numbers in between are genuinely in between. The six-head experiment sits at 0.5502 and contributes 0.55 of itself to coin A and 0.45 to coin B, at the same time. Nothing is rounded to a label, and rounding it would be a different and worse algorithm.
The EM Algorithm
The first M step, read
| Fractional count | Estimate | |
|---|---|---|
| coin A | 51.2810 heads out of 68.3571 flips | p_A = 0.7502 |
| coin B | 23.7190 heads out of 51.6429 flips | p_B = 0.4593 |
| weight | average responsibility | w = 0.5696 |
The EM Algorithm
68.3571 flips. No such number of flips was performed. The fractional counts are what the complete-data counting becomes when membership is a probability, and they are the reason the M step is as easy as counting: the M step of EM is the previous chapter's formula with weights.
And notice that one round has already moved p_A from 0.60 to 0.7502 and p_B from 0.50 to 0.4593. The coins are separating on their own, from a start that barely distinguished them.
The monotonicity, which is the theorem
Read the change column:
| Round | Log likelihood | Change |
|---|---|---|
| 0 | -79.362332 | |
| 1 | -72.405673 | +6.956659 |
| 2 | -68.901852 | +3.503821 |
| 3 | -68.617504 | +0.284349 |
| 5 | -68.559498 | +0.007652 |
| 9 | -68.558408 | +0.000001 |
Every change is positive. That is the theorem, and it is the reason EM is used: each round increases the log likelihood or leaves it unchanged, so the sequence of likelihoods is increasing and bounded, and therefore converges.
The argument in one sentence, for a paper that asks why: the E step builds a lower bound on the log likelihood that touches it at the current parameters, and the M step maximises that bound, so the new likelihood is at least the bound's value, which is at least the old likelihood. The inequality behind it is Jensen's.
The theorem promises no more than that. It says the likelihood does not fall. It does not say EM reaches the largest maximum, nor that it converges quickly, nor that the answer is unique.
And the convergence has a characteristic shape: +6.96, then +3.50, then +0.28, then +0.05. Almost all the progress is in the first two or three rounds and the rest is polish. In practice EM is stopped when the change falls below a threshold, not after a fixed number of rounds.
The last row prints -0.000000, a difference of 1.42e-14. That is floating-point rounding at a fixed point already reached, the last few bits of a double, and not a decrease. It is left in the output because an implementation that tests change > 0 to decide whether to continue will behave oddly at convergence, and a student who has never seen it will misread it as a bug in the theorem.
What it recovered
| True | EM, from 12 experiments | |
|---|---|---|
p_A | 0.80 | 0.8132 |
p_B | 0.30 | 0.2600 |
w | 0.50 | 0.6598 |
Close on the coins, poor on the weight, from twelve experiments in which coin A happened to be chosen eight times. EM is maximum likelihood, so it inherits everything from Maximum Likelihood Estimation: it is not unbiased, it is unreliable on small samples, and it will fit the sample in preference to the truth.
The EM Algorithm
Failure one: the symmetric start
Set both coins to the same value and EM never moves.
| Round | p_A | p_B | Log likelihood |
|---|---|---|---|
| 0 | 0.5000 | 0.5000 | -83.177662 |
| 1 | 0.6250 | 0.6250 | -79.387589 |
| 2 to 5 | 0.6250 | 0.6250 | -79.387589 |
The mechanism is exact and worth stating: with the two components identical, every responsibility is exactly 0.5, so both fractional counts are the same, so the M step returns the same pooled estimate for both. The state reproduces itself for ever. Hidden Variables predicted this from the shape of the surface: on the diagonal there is no slope in the direction that would separate the components, and EM is sitting on a saddle.
Note that the likelihood did rise once, from -83.18 to -79.39, so the theorem is not violated. It converged, to the single-coin answer 0.6250, which is the pooled estimate the previous chapter measured as ten log units worse than the truth.
Failure two: the labels come out the other way
Started with B as the heavier coin, EM converges to p_A = 0.2600, p_B = 0.8132, w = 0.3402, at a log likelihood of -68.558408, identical to the first run. The coins have exchanged names.
Nothing is wrong with the fit. This is the label switching of the previous chapter: the names of mixture components are not recoverable from data, and any program that compares two EM runs parameter by parameter will report a difference that does not exist.
What different starts reach
| Start | Final p_A | Final p_B | Log likelihood |
|---|---|---|---|
| 0.60, 0.50 | 0.8132 | 0.2600 | -68.558408 |
| 0.50, 0.60 | 0.2600 | 0.8132 | -68.558408 |
| 0.99, 0.01 | 0.8132 | 0.2600 | -68.558408 |
| 0.70, 0.65 | 0.8132 | 0.2600 | -68.558408 |
| 0.50, 0.50 | 0.6250 | 0.6250 | -79.387589 |
Every unequal start reaches the same likelihood, at one of the two relabellings. The equal start reaches a worse value and stays there. Hence the standard practice, which a paper may ask for: run EM from several random starting points and keep the fit with the highest likelihood.
Where EM appears
The same two steps, under other names, and being able to place them is worth marks.
| Application | The hidden variable | The name there |
|---|---|---|
| Mixture of Gaussians | which component produced a point | soft clustering |
Clustering and k-means | which cluster a point belongs to | hard EM: the responsibility is forced to 0 or 1 |
Hidden Markov Models | the state at each time step | Baum-Welch, using forward-backward as its E step |
| Filling in missing values | the missing entries | imputation by EM |
The EM Algorithm
k-means is EM with the E step rounded. That one sentence connects two chapters of this module and is the cleanest way to remember either.
Distinctions
| E step | M step | |
|---|---|---|
| Computes | the posterior over the hidden variable | the parameters |
| Uses | Bayes rule | weighted counting |
| Holds fixed | the parameters | the responsibilities |
| EM | Gradient ascent on the likelihood | |
|---|---|---|
| Step size | none to choose | must be chosen |
| Guarantees the likelihood rises | yes, every round | only for a small enough step |
| Parameters stay valid probabilities | yes, automatically | must be constrained |
| Converges to the global maximum | no | no |
| Soft assignment, EM | Hard assignment, k-means | |
|---|---|---|
| A point belongs to | every component, with a weight | exactly one |
| Counts are | fractional | whole |
| A point at 0.5502 | splits 0.55 and 0.45 | goes entirely to one |
What it does not mean
The E step does not guess the hidden value. It computes a distribution over it, and keeping the distribution is the method.
The M step is not a new estimator. It is the complete-data count with fractional weights.
EM does not find the global maximum. It converges to a stationary point, which may be a worse maximum or even a saddle.
A converged EM run is not a unique answer. Its mirror image with the labels exchanged fits identically.
A symmetric start does not converge slowly. It cannot move at all.
A tiny negative change is not a violation of the theorem. At the fixed point here it is 1.42e-14, which is floating-point rounding.
EM is not an alternative to maximum likelihood. It is a way of computing it, and it inherits all of maximum likelihood's weaknesses.
Quick revision
- EM finds maximum likelihood estimates with hidden variables, by alternating two steps until the likelihood stops changing.
- E step: by Bayes rule, the posterior probability of each hidden value given the observation and the current parameters. These are the responsibilities, a distribution, not a choice.
- M step: the complete-data count, with each observation weighted by its responsibilities. Fractional counts: measured here as
51.2810heads out of68.3571flips. - The log likelihood never falls. Measured:
+6.956659,+3.503821,+0.284349,+0.050353,+0.007652. The E step builds a lower bound touching the likelihood; the M step maximises it; Jensen's inequality is behind it. - Almost all the gain is in the first two or three rounds, so stop on the size of the change, not a fixed count.
- Recovered
0.8132and0.2600against a true 0.80 and 0.30, withw = 0.6598against 0.50, from twelve experiments. - A symmetric start is stuck: equal components give every responsibility exactly 0.5, so the M step returns the pooled value
0.6250for both, for ever. A saddle. - Label switching: the mirror fit scores identically,
-68.558408either way. Components are not identifiable by name. - Practice: several random restarts, keep the highest likelihood.
- EM is behind Gaussian mixtures, Baum-Welch for HMMs, and imputation, and k-means is EM with the responsibilities forced to 0 or 1.
The EM Algorithm
Test yourself
1. State the two steps of EM. The E step computes, for each observation, the posterior distribution over the hidden variable given the observation and the current parameters, by Bayes rule. The M step re-estimates the parameters by the ordinary complete-data method, counting each observation towards every value of the hidden variable in proportion to that posterior.
2. What is a responsibility, and why must it not be rounded? The posterior probability that a particular component produced a particular observation. Rounding it to the most likely component throws away the information that the observation is ambiguous, which is precisely what lets the components separate gradually; keeping the distribution is what makes the method work, and the rounded version is a different algorithm, k-means.
3. What is meant by a fractional count? The M step's denominators and numerators are sums of weights rather than whole observations, so a coin can be credited with 51.2810 heads out of 68.3571 flips even though no such number of flips took place. Each observation contributes part of itself to every component.
4. State the convergence property of EM and the property it does not have. Each round leaves the log likelihood the same or increases it, so the sequence is increasing and bounded and therefore converges. It does not follow that the limit is the global maximum: EM converges to a stationary point, which may be a poorer local maximum or a saddle.
5. Sketch why the likelihood cannot fall. The E step constructs a function of the parameters that lies below the log likelihood everywhere and touches it at the current parameters, by Jensen's inequality. The M step moves to the maximum of that lower bound, so the bound's value does not fall, and the log likelihood at the new parameters is at least the bound's value there.
6. EM is started with both components identical. What happens, and why? It never separates them. With identical components every responsibility is exactly one half, so both weighted counts are identical and the M step returns the same pooled estimate for both components, reproducing the state for ever. The likelihood surface is symmetric about that line and has no slope in the separating direction, so the point is a saddle.
7. Two EM runs on the same data return different parameters and the same log likelihood. Explain. They have found the same fit with the components' names exchanged. The likelihood is invariant under permuting the components, so each optimum has a mirror image, and mixture parameters are identifiable only up to relabelling. Comparing runs parameter by parameter will report a difference that is not there; comparing likelihoods will not.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.