Imagine a CBSE Class 10 mathematics teacher accidentally merges the marks of two sections into one spreadsheet. Section A wrote a harder question paper, Section B wrote an easier one, and both papers were checked out of 100 by the same examiner. By the time the marks reach you, the "which paper" column has been deleted by mistake — you only have a single column of forty numbers. Some students clearly scored like they wrote the hard paper, some clearly scored like they wrote the easy paper, and a few sit stubbornly in between. Can you recover, from the marks alone, both which paper each student wrote and what the average and spread of each paper's marks actually were?
This looks impossible at first because it is circular. If you already knew which students wrote which paper, computing each paper's average mark would be one line of arithmetic. If you already knew each paper's average and spread, deciding which paper a given mark "sounds like" would be easy too. But you are asked to find both at once, and each piece depends on the other. This chapter is about the algorithm built exactly for this situation: the Expectation–Maximization algorithm, or EM. It does not solve the circularity by magic — it solves it by walking around the circle deliberately, updating one half at a time, until both halves stop changing.
The chicken-and-egg problem, without any formulas yet
Before any notation, look at the shape of the problem in the simplest form it can take. Suppose you are handed two coins, coin A and coin B, taken from a locked drawer. You are told the two coins have different, unknown biases — one lands heads more often than the other — but you are not told which coin is which, and you are not even told, for any given set of ten tosses, whether coin A or coin B produced it. All you have is five separate batches of ten tosses each, and the head-counts for each batch. You are asked to estimate both coins' biases from this alone.
Here is the trick that makes it tractable. Start with a wild guess for the two biases — say coin A is fairly heads-heavy and coin B is close to fair. Using that guess, you can now ask, for each batch of ten tosses: "if these guessed biases were correct, how likely is it that this particular batch came from coin A rather than coin B?" A batch with nine heads out of ten looks far more consistent with your heads-heavy guess for A, so you lean towards crediting it mostly to A. A batch with four heads looks more like B. This step does not give you a hard yes/no answer for each batch — it gives you a degree of belief, a probability, for each batch. Once every batch has this probability attached, you can go back and recompute the two coins' biases, but now each batch's ten tosses count towards both coins, weighted by how much you believe that batch came from each one. Recompute the biases, and your degree-of-belief probabilities shift again, slightly. Repeat. The two halves of the problem — "which coin, probably" and "what bias, probably" — sharpen each other round after round until neither one moves any further. That alternation is the entire idea of EM. Everything below is this same alternation made precise and pushed onto real numbers, first for the coins and then for the CBSE marks that opened this chapter.
Formalizing the problem: latent variables and mixture models
To write this precisely, statisticians introduce a latent variable, usually called Z. "Latent" just means hidden or unobserved — in the coin problem, Z tells you which coin produced a given batch, and you never get to see its value directly. In the marks problem, Z tells you which question paper a given student wrote. What you do observe is the outcome that depends on Z: the head-count, or the mark.
A dataset generated this way is called a mixture model: it is really two (or more) separate probability distributions blended together, and every data point secretly belongs to exactly one of them, but the label has been stripped off before you see the data. If you knew the labels, this would collapse into ordinary statistics — split the data by label, compute a mean and spread for each group, done. If you knew the two distributions' parameters exactly, you could compute, for any point, how likely it is under each distribution and lean towards whichever is more likely — also a solved problem. EM exists precisely for the case where you are handed neither, and must bootstrap both from a starting guess.
EM alternates between two named steps, over and over, until the numbers stop changing:
- E-step (Expectation): freeze the current parameter guesses, and for every data point, compute the probability that it belongs to each hidden group. This probability is called that point's responsibility towards each group. It is a number between 0 and 1, computed with Bayes' theorem, and unlike a simple classifier, it is almost never a clean 0 or 1 — it is a genuine probability, and every point contributes fractionally to every group.
- M-step (Maximization): freeze the responsibilities you just computed, and re-estimate every parameter as a responsibility-weighted average over all the data, exactly the way you would compute an ordinary average, except each point's contribution is scaled by how responsible that group is for it.
Two full worked examples follow: the coins first, because the arithmetic is the simplest possible case (yes/no outcomes, no continuous curves involved), and then the CBSE marks, which is the continuous version and closes the loop on the opening scenario.
Worked Example 1: Two coins, five batches
Five batches of ten tosses each produced these head-counts: 5, 9, 8, 4, 7. You do not know which coin produced which batch. Start with an initial guess: coin A's bias θA = 0.6 (a guess that A leans towards heads), coin B's bias θB = 0.5 (a guess that B is close to fair). Assume each batch was equally likely to have come from either coin, so the prior probability of A or B for any batch is 0.5 each.
The E-step needs the probability of seeing a given head-count under each coin's guessed bias. Ten tosses with h heads and bias θ has probability given by the binomial formula:
P(h heads out of 10 | theta) = C(10, h) * theta^h * (1 - theta)^(10 - h)where C(10, h) is "10 choose h", the number of ways to arrange h heads among 10 tosses. Bayes' theorem then converts this into the responsibility — the probability that coin A produced a batch, given its head-count:
r(A | h) = P(h | theta_A) / [ P(h | theta_A) + P(h | theta_B) ]Working this out for all five batches with the initial guesses θA = 0.6, θB = 0.5:
heads=5: P(A)=0.449 P(B)=0.551
heads=9: P(A)=0.805 P(B)=0.195
heads=8: P(A)=0.733 P(B)=0.267
heads=4: P(A)=0.352 P(B)=0.648
heads=7: P(A)=0.647 P(B)=0.353Notice batch "heads=9" leans strongly towards A (0.805) — nine heads out of ten is much more consistent with a heads-heavy coin. Batch "heads=4" leans towards B for the opposite reason. No batch is assigned with total certainty, because with only ten tosses, the evidence is never conclusive; every batch keeps a nonzero probability on both coins.
The M-step now re-estimates each coin's bias, using each batch's responsibility as a weight. A batch with responsibility r towards A contributes r·h "expected heads from A" and r·(10−h) "expected tails from A" — a fractional share of its tosses, proportional to how responsible A is believed to be for it:
expected heads from A = sum over batches of r(A|h) * h
expected tails from A = sum over batches of r(A|h) * (10 - h)
new theta_A = (expected heads from A) / (expected heads from A + expected tails from A)Carrying out this sum across all five batches gives expected heads-from-A ≈ 21.297 and expected tails-from-A ≈ 8.572, so:
new theta_A = 21.297 / (21.297 + 8.572) = 0.713
new theta_B = 11.703 / (11.703 + 8.428) = 0.581Both biases moved: A's guess climbed from 0.6 towards 0.713 because it just absorbed a heavier weighted share of the high-head-count batches; B's guess climbed from 0.5 to 0.581 for the symmetric reason. This is one full round: E-step, then M-step. Feed the new θA = 0.713 and θB = 0.581 straight back into another E-step, and the responsibilities sharpen a little further, which sharpens the next M-step's averages a little further. Repeating this alternation until the numbers stop moving settles the estimates at θA ≈ 0.797 and θB ≈ 0.520 — a genuinely heads-heavy coin and a genuinely near-fair coin, recovered from head-counts alone, without ever being told which batch came from which coin.
The general E-step and M-step, and a common misconception
The coin example generalizes directly to any mixture of K hidden groups. Write πk for the overall proportion of group k in the data (its "mixing weight"), and let group k's data-generating rule have parameters θk (for a coin, θk is just a bias; for the marks example below, θk will be a mean and a spread). For any data point xi, the E-step responsibility of group k is Bayes' theorem applied directly:
r(i, k) = [ pi_k * P(x_i | theta_k) ] / [ sum over all groups j of pi_j * P(x_i | theta_j) ]The numerator is "how likely is this point under group k, weighted by how common group k is overall"; the denominator normalizes across every group so that a point's responsibilities always sum to exactly 1 across all groups. The M-step then re-estimates every parameter as a responsibility-weighted average, with the responsibilities acting purely as weights:
N_k = sum over i of r(i, k) (soft/expected count of group k)
pi_k (new) = N_k / (total number of points)
theta_k(new) = weighted average of x_i, weights r(i, k) / N_kHere is the misconception worth naming directly, because it is the single most common way students misread this algorithm: EM does not assign each point to one group the way k-means clustering does. In k-means, every point is handed entirely to its single nearest cluster centre, a hard 0-or-1 decision, and the centres are then recomputed as plain averages of the points fully owned by each cluster. EM's E-step never makes that hard decision. A point's responsibility is a genuine probability distribution across all groups — a point can be, say, 73% responsible to group 1 and 27% responsible to group 2 at the same time, and the M-step uses both fractions when it updates both groups' parameters. This is why EM is described as performing soft clustering while k-means performs hard clustering. You will see exactly how dramatic this soft split can get in Worked Example 2 below, where one data point ends up split almost exactly down the middle.
One more property worth stating precisely, because it is frequently tested in exactly this phrased form: each round of E-step followed by M-step is guaranteed to never decrease the overall likelihood of the observed data under the current parameters — the fit can only improve or stay flat, never get worse. This is why the alternation is guaranteed to settle down rather than oscillate forever. What it does not guarantee is that the point it settles at is the best possible fit overall. The likelihood surface EM is climbing usually has several separate peaks, and EM only promises to climb to the top of whichever peak it started on — a local optimum, not necessarily the global optimum. Two different starting guesses for θA and θB can therefore converge to two different final answers. In practice this is handled by re-running EM from several different random starting guesses and keeping the run that reaches the highest final likelihood.
Worked Example 2: the two-paper marks, as a Gaussian mixture
Return to the opening scenario. Unlike coin tosses, marks out of 100 are not a yes/no outcome — they are continuous, and a natural continuous distribution for "marks scattered around some average" is the Gaussian (normal) distribution, with a mean μ and a spread σ. A mixture of two Gaussians — one for the harder paper's marks, one for the easier paper's marks — is called a Gaussian Mixture Model (GMM), and it is the continuous-data version of exactly the same EM alternation used above.
To hand-trace the arithmetic exactly (a real class of forty would need a spreadsheet, not a pencil), take a small illustrative sample of eleven marks pulled from the merged sheet: 32, 38, 41, 45, 48, 60, 74, 78, 82, 85, 88. To keep the hand computation tractable, assume — as a simplifying assumption, not a law of nature — that both papers' marks have the same spread σ, so the M-step only has to re-estimate two means, two mixing weights, and one shared σ rather than two separate spreads. A full GMM would let each cluster keep its own σk, updated by the same weighted-variance idea shown below, applied separately to each group.
Start with initial guesses μlow = 40, μhigh = 80, shared σ = 10, and equal mixing weights πlow = πhigh = 0.5. The Gaussian density function needed for the E-step is:
N(x; mu, sigma) = 1 / (sigma * sqrt(2*pi)) * exp( -(x - mu)^2 / (2*sigma^2) )Plugging every mark into this formula for both clusters and applying the same Bayes' rule normalization as before gives the E-step responsibilities:
x= 32: r(low)=1.000 r(high)=0.000
x= 38: r(low)=1.000 r(high)=0.000
x= 41: r(low)=0.999 r(high)=0.001
x= 45: r(low)=0.998 r(high)=0.002
x= 48: r(low)=0.992 r(high)=0.008
x= 60: r(low)=0.500 r(high)=0.500
x= 74: r(low)=0.004 r(high)=0.996
x= 78: r(low)=0.001 r(high)=0.999
x= 82: r(low)=0.000 r(high)=1.000
x= 85: r(low)=0.000 r(high)=1.000
x= 88: r(low)=0.000 r(high)=1.000Every mark from 32 through 48 is essentially decisive for the low cluster, and every mark from 74 through 88 is essentially decisive for the high cluster, because each of those marks sits many multiples of σ away from the "wrong" cluster's mean, which drives its density under the wrong Gaussian to nearly zero. The one genuinely undecided case is x = 60: it sits exactly 20 marks from μlow = 40 and exactly 20 marks from μhigh = 80, and with both clusters sharing the same σ, that symmetric distance produces an exact 50.0% / 50.0% split — the clearest possible illustration that a responsibility is a genuine probability, not a forced choice. The diagram below plots all eleven marks against the two guessed Gaussian curves; each point's fill colour is a literal blend of blue (low) and orange (high) mixed in the exact proportion of its two responsibilities above, so x = 60 renders as a genuine muddy blend of both colours rather than a clean version of either one.
Now the M-step. For each cluster, the soft/expected count Nk is just the sum of that cluster's responsibilities down the column above:
N_low = 1.000+1.000+0.999+0.998+0.992+0.500+0.004+0.001+0.000+0.000+0.000 = 5.493
N_high = 11 - N_low = 5.507The new means are responsibility-weighted averages — each mark contributes to each cluster's mean in exact proportion to that cluster's responsibility for it, then the sum is divided by that cluster's own soft count, not by 11:
new mu_low = (1.000*32 + 1.000*38 + 0.999*41 + 0.998*45 + 0.992*48 + 0.500*60 + ... ) / 5.493 = 42.564
new mu_high = ( ... ) / 5.507 = 79.391
new pi_low = 5.493 / 11 = 0.499
new pi_high = 5.507 / 11 = 0.501The shared spread is re-estimated the same way ordinary variance is computed, except every squared deviation is weighted by its point's responsibility before averaging, and a point contributes its deviation to both clusters' sums, scaled by its two different responsibilities:
new sigma^2 = (1/11) * sum over i of [ r(low,i)*(x_i - new_mu_low)^2 + r(high,i)*(x_i - new_mu_high)^2 ]
new sigma = 7.806That is one full round. Feeding these updated parameters back into another E-step, then another M-step, and repeating for roughly two dozen further rounds, the numbers stop moving at μlow ≈ 43.49, μhigh ≈ 80.63, shared σ ≈ 7.50, πlow ≈ 0.529, πhigh ≈ 0.471. Something worth noticing at convergence: recompute x = 60's responsibility under these final, sharper parameters, and it comes out to 0.814 towards the low cluster — no longer an even split, because μlow has since moved closer to it. The 50/50 tie was a genuine feature of the crude initial guess, not a permanent property of that mark; responsibilities sharpen as the parameters they depend on sharpen.
Why this matters beyond marks and coins
EM itself will not appear by name on a CBSE board paper, but the machinery you just hand-traced is not a toy. Bayes' theorem for turning a likelihood into a responsibility, and a weighted average for turning responsibilities back into parameters, is exactly the algebra that IIT-JEE and BITSAT probability questions drill in isolation — tracing the two worked examples above by hand is real practice for that machinery, not a detour from it. You will meet this same E-step/M-step alternation again, formalized a little further, in the very first machine-learning course you take after school: it is the standard way to fit Gaussian mixture models for clustering, and a close relative of it is used to train the hidden-state models behind speech recognition. If your school offers the CBSE Artificial Intelligence elective, the "grouping data without labels" idea you saw in Worked Example 2 is the same territory that subject introduces conceptually — EM is the precise machine running underneath, once you are ready for the calculus of it.
Active recall
Q1. In Worked Example 1, why does a batch with responsibility 0.805 towards coin A contribute 0.805×9 = 7.245 "expected heads" to A's re-estimate, instead of contributing its full 9 heads to whichever coin has the higher responsibility?
A1. Because the E-step never makes a hard yes/no decision about which coin produced a batch — it computes a genuine probability. A responsibility of 0.805 towards A means the batch also carries 0.195 probability towards B, and the M-step must respect both possibilities simultaneously rather than discarding the smaller one. Splitting the batch's heads and tails fractionally, in exact proportion to the two responsibilities, is precisely how "soft clustering" differs from k-means-style hard assignment.
Q2. A data point has responsibility 0.98 towards cluster 1 and 0.02 towards cluster 2. A second point has responsibility 0.50 towards each. How does each point's influence on the new cluster-1 mean differ?
A2. The new mean for cluster 1 is a sum of (responsibility × value) divided by the soft count N1. The first point contributes 0.98×(its value) — almost its entire value — to that sum, and only 0.02×(its value) to cluster 2's sum. The second point contributes exactly half its value to each cluster's sum. Both points still count towards N1 and N2 in the denominators, again weighted by these same responsibilities.
Q3. EM guarantees the data's likelihood never decreases from one round to the next. Why doesn't this guarantee that two different runs of EM, started from two different initial guesses, will always converge to the same final parameters?
A3. The likelihood surface EM is climbing typically has several separate peaks (local optima), not one single global peak. The non-decreasing guarantee only promises that each round moves you up whichever peak's slope you are currently standing on — it says nothing about which peak you started closest to. Two different starting guesses can sit on the slopes of two different peaks and climb to two different final answers, neither of which is necessarily the tallest peak overall. This is why practical EM implementations restart from several random initial guesses and keep the run with the highest final likelihood.
Q4. Using the converged Worked-Example-2 parameters (μlow≈43.49, μhigh≈80.63, shared σ≈7.50, πlow≈0.529, πhigh≈0.471), a new mark of 62 turns out to have responsibility 0.539 towards the low cluster and 0.461 towards the high cluster — almost an even split again. Why, roughly, does this happen even though 62 is closer in raw distance to neither mean by a huge margin?
A4. 62 sits about 18.5 marks above μlow and about 18.6 marks below μhigh — almost exactly equidistant between the two converged means in units of the shared σ. Responsibility depends on relative closeness measured against the spread of each Gaussian, not on which side of some fixed cutoff the point falls; a point sitting at nearly equal standardized distance from both cluster centres will always land close to a 50/50 split, regardless of where exactly the two means happen to be.
Q5. Why does the M-step divide by the soft count Nk (the sum of a cluster's responsibilities) instead of dividing by the total number of data points, when computing a new cluster mean?
A5. A responsibility-weighted average must divide by the total weight actually used in the sum, exactly like any weighted average does — the "weight" here is the sum of responsibilities feeding that particular mean, which is Nk, not the count of every data point in the whole dataset. Dividing by the full dataset size instead would systematically shrink every cluster's mean towards zero, because it would treat points with near-zero responsibility to that cluster as if they still counted fully in the denominator.
Summary
- EM solves problems where data comes from a mixture of hidden groups, the group label (the latent variable Z) is never observed, and estimating the groups' parameters and estimating each point's group membership are circularly dependent on each other.
- The E-step freezes the current parameter guesses and uses Bayes' theorem to compute each point's responsibility — a genuine probability, not a hard label — towards every hidden group.
- The M-step freezes those responsibilities and re-estimates every parameter as a responsibility-weighted average: means, mixing weights, and spreads all update this way, dividing by each group's soft count Nk, not by the total dataset size.
- Worked Example 1 traced this on two coins with unknown, different biases, recovering θA≈0.797 and θB≈0.520 from head-counts alone. Worked Example 2 traced the continuous version — a Gaussian Mixture Model — on exam marks, recovering two clusters' means, mixing weights, and a shared spread, and showing a genuinely ambiguous point (x=60) split exactly 50/50 by the initial guess, then resolved to 0.814 once the parameters sharpened.
- EM is guaranteed to never decrease the data's likelihood from one round to the next, so it always settles down — but only at a local optimum, not necessarily the best possible fit, which is why different starting guesses can converge to different final answers.
- EM performs soft clustering (fractional, probabilistic group membership); k-means performs hard clustering (each point owned entirely by one cluster). Confusing the two is the most common misreading of this algorithm.