The Expectation-Maximization Algorithm

A Puzzle With Missing Labels

You have two coins, A and B, pulled from a drawer. They are not fair — coin A tends to land heads more often than coin B — but you don't know either coin's true bias. A friend runs an experiment: five times, they pick one of the two coins at random, flip it 10 times, and write down how many heads came up. You get five numbers: 5, 9, 8, 4, 7 heads out of 10 flips each. There's a catch. Your friend forgot to record which coin was used in each of the five rounds. You have the outcomes but not the labels.

This is not a toy problem invented for a textbook. It is the exact shape of dozens of real situations: a phone's speech recognizer hears an accent but doesn't know which speaker-cluster produced it; a hospital lab has patient test results but doesn't know which of two disease subtypes each patient has; a telecom analyst sees call-drop rates across towers but doesn't know which tower had a hardware fault versus which had bad weather. In every case, some variable that would make the problem easy — which coin, which speaker, which subtype — is hidden. Statisticians call it a latent variable.

If you knew the coin used in each round, this would be a one-line calculation: for coin A's rounds, add up all the heads, divide by all the flips, and that ratio is your best estimate of coin A's bias. Simple counting. The entire difficulty of this chapter exists because that one piece of information — the label — is missing. The Expectation-Maximization algorithm, EM for short, is the method for making progress anyway: it estimates the hidden labels and the coin biases together, each guess improving the other, until both settle down.

Why You Can't Just Average the Data

A natural first instinct: ignore the missing labels and just average everything. Total heads across all five rounds: 5+9+8+4+7 = 33, out of 50 flips, giving 0.66. But that single number throws away the fact that two different coins produced this data — it estimates one blended bias, not coin A's bias and coin B's bias separately. It answers a different, less useful question.

A second instinct: guess the labels first (say, by eyeballing which rounds look "high" and which look "low"), then compute separate averages. This can work by luck, but it is not a method — it doesn't tell you what to do when the split isn't obvious, and it gives no way to check whether your guessed labels were any good. EM replaces the eyeball guess with a principled one: instead of assigning each round to either coin A or coin B, it assigns each round a probability of having come from coin A. Round 2 (9 heads out of 10) is probably coin A. Round 4 (4 heads out of 10) is probably coin B. But "probably" needs a number, and that number needs a rule to compute it. That rule is what we build next.

Building the Tool You Need: Comparing Two Hypotheses by Counting

Formal conditional probability and Bayes' theorem are topics you will meet properly in Class 12. You don't need the full machinery yet — only one idea from it, which we can build from scratch using nothing but counting.

Suppose coin A has bias θ_A (probability of heads) and coin B has bias θ_B. If coin A produced 5 heads and 5 tails in 10 flips, in one specific order (say HHHHHTTTTT), the chance of that exact sequence is θ_A × θ_A × θ_A × θ_A × θ_A × (1−θ_A) × (1−θ_A) × (1−θ_A) × (1−θ_A) × (1−θ_A), which is θ_A⁵(1−θ_A)⁵, since each flip is independent and you just multiply the individual chances. The actual order of the 10 flips wasn't recorded, only the count of heads — but here is the key shortcut: however many different orders give exactly 5 heads out of 10, that count of orderings is the same number regardless of whether the coin is A or B. So when we compare "how likely is this data under coin A" against "how likely under coin B", that shared ordering-count multiplies both sides equally and cancels out of the comparison. We can safely compare using just θ^heads(1−θ)^tails and get the correct ratio, even without knowing the ordering-count formula.

Now the actual question we want answered: "Given that this round produced 5 heads out of 10, what is the probability it was coin A?" This is exactly the kind of question Class 12 will formalize as Bayes' theorem, but the logic is simple enough to build right now with a counting argument. Imagine repeating this whole experiment 10,000 times. Before any flips happen, half the time (5,000 trials) you'd have picked coin A, half the time (5,000 trials) coin B — that's your starting belief, 50-50. Of the 5,000 coin-A trials, a fraction θ_A⁵(1−θ_A)⁵ would show exactly 5 heads out of 10; of the 5,000 coin-B trials, a fraction θ_B⁵(1−θ_B)⁵ would show 5 heads. Among all the trials (from either coin) that ended up showing 5 heads out of 10, the fraction that came from coin A is:

P(coin A | 5 heads out of 10)
   =            (chance of A) x (chance of 5 heads, given A)
       -----------------------------------------------------------------
       (chance of A)x(chance of 5 heads|A) + (chance of B)x(chance of 5 heads|B)

If your prior belief about which coin was picked is 50-50, the "chance of A" and "chance of B" terms are equal and cancel, leaving just the ratio of θ_A⁵(1−θ_A)⁵ to the sum of both. This is precisely the E-step formula EM uses. It is Bayes' theorem, derived here from a frequency-counting argument rather than quoted as a memorized formula — when you reach it formally in Class 12, you will recognize this exact structure.

The E-Step: Computing Responsibilities for All Five Rounds

Start with a guess. We don't know θ_A and θ_B, so pick reasonable starting values: θ_A = 0.6, θ_B = 0.5. (EM never requires a correct starting guess, only a starting point — we'll see how much it corrects itself in one step.)

For each of the five rounds, compute θ_A^heads(1−θ_A)^tails and θ_B^heads(1−θ_B)^tails, then normalize to get the "responsibility" — the probability that round came from coin A.

Round 1 (5 heads, 5 tails): Under A: 0.6⁵×0.4⁵ = 0.07776 × 0.01024 = 0.0007963. Under B: 0.5¹⁰ = 0.0009766. Responsibility of A = 0.0007963 / (0.0007963 + 0.0009766) = 0.449.

Round 2 (9 heads, 1 tail): Under A: 0.6⁹×0.4¹ = 0.010078 × 0.4 = 0.0040311. Under B: 0.5¹⁰ = 0.0009766. Responsibility of A = 0.0040311 / 0.0050077 = 0.805.

Round 3 (8 heads, 2 tails): Under A: 0.6⁸×0.4² = 0.0167962 × 0.16 = 0.0026874. Under B: 0.0009766. Responsibility of A = 0.0026874 / 0.0036640 = 0.733.

Round 4 (4 heads, 6 tails): Under A: 0.6⁴×0.4⁶ = 0.1296 × 0.004096 = 0.0005308. Under B: 0.0009766. Responsibility of A = 0.0005308 / 0.0015074 = 0.352.

Round 5 (7 heads, 3 tails): Under A: 0.6⁷×0.4³ = 0.0279936 × 0.064 = 0.0017916. Under B: 0.0009766. Responsibility of A = 0.0017916 / 0.0027682 = 0.647.

Notice what these numbers say: round 2 (9 heads) is 80.5% likely to be coin A — reasonable, since A's guessed bias (0.6) is higher. Round 4 (4 heads) is only 35.2% likely to be A. No round gets assigned with total certainty, because with only 10 flips per round, either coin could plausibly have produced any of these counts. EM keeps that uncertainty alive instead of forcing a hard, possibly-wrong decision — this soft assignment is the "Expectation" in Expectation-Maximization: we compute the expected contribution of each round to each coin, rather than committing to one label.

The M-Step: Turning Responsibilities Into New Estimates

Now pretend each round contributes to both coins, weighted by its responsibility. Round 2's 9 heads count as 0.805 × 9 = 7.245 "phantom heads" for coin A and 0.195 × 9 = 1.755 for coin B. Summing this weighted count across all five rounds and dividing gives the new bias estimate — the "Maximization" step, because this weighted average is exactly the value of θ_A that makes the weighted data most probable (we prove why in the section on Jensen's inequality below).

Total weighted heads for A = 2.245+7.245+5.864+1.408+4.529 = 21.291. Total weighted tails for A = 2.245+0.805+1.466+2.112+1.941 = 8.569. New estimate: θ_A = 21.291 / (21.291+8.569) = 21.291/29.860 = 0.713.

The same table with responsibility-of-B (1 minus each row above) gives weighted heads for B = 11.709 and weighted tails for B = 8.431, so θ_B = 11.709/20.140 = 0.581.

Compare to the starting guess: θ_A moved from 0.6 to 0.713, θ_B moved from 0.5 to 0.581. Both shifted in a sensible direction — apart, since the soft-assignment step had already started separating "probably A" rounds (high head-counts) from "probably B" rounds (low head-counts). Feed these new values back into the E-step, recompute responsibilities, run the M-step again, and the estimates keep refining. After enough rounds, θ_A and θ_B stop changing — EM has converged.

Coding It: A Working coin_em() Function

Here is the entire algorithm in Python, general enough to run any number of iterations:

def coin_likelihood(heads, tails, theta):
    return (theta ** heads) * ((1 - theta) ** tails)

def coin_em(rounds, theta_A=0.6, theta_B=0.5, iterations=1):
    for _ in range(iterations):
        heads_A = tails_A = 0.0
        heads_B = tails_B = 0.0
        # E-step: compute responsibility for every round
        for heads, tails in rounds:
            like_A = coin_likelihood(heads, tails, theta_A)
            like_B = coin_likelihood(heads, tails, theta_B)
            resp_A = like_A / (like_A + like_B)
            resp_B = 1 - resp_A
            heads_A += resp_A * heads
            tails_A += resp_A * tails
            heads_B += resp_B * heads
            tails_B += resp_B * tails
        # M-step: recompute theta from weighted counts
        theta_A = heads_A / (heads_A + tails_A)
        theta_B = heads_B / (heads_B + tails_B)
    return theta_A, theta_B

data = [(5, 5), (9, 1), (8, 2), (4, 6), (7, 3)]
print(coin_em(data, iterations=1))   # (0.713, 0.581)

Trace round 2 — (heads=9, tails=1) — through the first iteration by hand to confirm the code matches the arithmetic above. coin_likelihood(9, 1, 0.6) returns 0.6⁹ × 0.4¹ = 0.0100777 × 0.4 = 0.0040311. coin_likelihood(9, 1, 0.5) returns 0.5⁹ × 0.5¹ = 0.5¹⁰ = 0.0009766. So resp_A = 0.0040311 / (0.0040311 + 0.0009766) = 0.8050, matching round 2's hand-computed 0.805 exactly. heads_A accumulates 0.805 × 9 = 7.245 and tails_A accumulates 0.805 × 1 = 0.805 from this round, which is exactly the row you see in the M-step table. Running the same accumulation over all five rounds and dividing at the end reproduces θ_A = 0.713 and θ_B = 0.581.

The General EM Algorithm

Strip away the coins and state the pattern abstractly, because this same two-step loop solves problems far beyond coin flips. You have observed data X (the head-counts), a hidden variable Z (which coin), and parameters θ you want to estimate (the two biases).

• E-step (Expectation): using the current parameter guess θ^(t), compute the probability distribution over the hidden variable Z for every data point — in our example, the five responsibility values.
• M-step (Maximization): using those probabilities as weights, find the parameter values θ^(t+1) that maximize the expected log-likelihood of the (now weighted) complete data — in our example, the two weighted averages.
• Repeat until θ stops changing meaningfully (convergence).

Every application — coins, mixtures of measurements, hidden Markov models used in speech recognition, missing survey responses — is this same loop with X, Z, and θ swapped for the problem at hand.

Why EM Never Gets Worse: The Jensen's Inequality Proof

A reasonable worry: since the E-step is a soft guess about the hidden labels, could the M-step, built on a wrong guess, make the parameter estimate worse? EM has a guarantee against this: the observed-data log-likelihood never decreases from one iteration to the next. Here is why, built from one fact about the logarithm function you already know from calculus — log is concave, meaning its graph bends like the underside of a dome, always curving below any straight line joining two points on it.

For a concave function f, and any weights that add to 1, f applied to a weighted average is at least the weighted average of f applied to each point individually — this is Jensen's inequality. Picture two points on the dome-shaped log curve: the straight chord connecting them lies below the curve (because the curve bends away from the chord, upward), so the curve's height at the midpoint is at least as high as the chord's height there. That's the whole inequality, generalized from two points to any weighted mix.

Write the log-likelihood of the observed data as a sum over the hidden variable's possible values z, weighted by any distribution q(z) we choose to introduce (it must sum to 1 over z, but is otherwise free):

log P(X|theta) = log [ sum over z of  q(z) x P(X,z|theta)/q(z) ]
              >= sum over z of  q(z) x log[ P(X,z|theta)/q(z) ]     (Jensen, log is concave)

Call the right-hand side the lower bound, B(q, θ). This inequality holds for any choice of q — it's a floor that sits at or below the true log-likelihood everywhere. Crucially, the gap between the true log-likelihood and the bound closes completely — equality — exactly when q(z) is chosen to equal the true posterior P(z|X, θ), because then P(X,z|θ)/q(z) becomes a constant (equal to P(X|θ)) for every z, and Jensen's inequality is only tight when the quantity being averaged doesn't vary.

This is precisely what the two EM steps do. The E-step sets q(z) = P(z|X, θ^(t)) — the responsibilities we computed — which makes the bound touch the true log-likelihood exactly at θ = θ^(t). The M-step then picks θ^(t+1) to maximize the bound B(q, θ) with q held fixed at that E-step value — and since the bound at θ^(t) equals the true log-likelihood at θ^(t), and the M-step can only push the bound up or leave it unchanged, we get:

log P(X|theta^(t+1)) >= B(q, theta^(t+1))   [bound is always <= true log-likelihood]
                     >= B(q, theta^(t))    [M-step maximizes the bound]
                      = log P(X|theta^(t)) [E-step made the bound tight here]

Chaining these three facts together: the true log-likelihood at the new parameters is at least as large as the true log-likelihood at the old parameters. Every EM iteration is guaranteed not to make things worse. It says nothing about reaching the best possible estimate — only that it never backslides, which is exactly the property that made it safe to run the coin example for as many iterations as needed.

From Coins to Curves: Gaussian Mixture Models

Suppose a school records the Class 10 pre-board mathematics marks (out of 100) for 200 students across the district, and plots a histogram. Instead of one neat bell curve centered around a single average, the histogram shows two humps — a cluster around 54 marks and a second, smaller cluster around 81 marks. A plausible explanation: two overlapping subpopulations sit inside this one dataset — say, students who had access to a structured test-series and revision batch, and students who didn't — each subpopulation roughly bell-shaped (Normal / Gaussian) around its own mean, but nobody recorded which student belonged to which group. This is the coin problem again, except the outcome per student isn't "heads or tails" but a continuous mark, and the underlying distribution per hidden group isn't a binomial but a Gaussian (Normal) curve.

A Gaussian Mixture Model (GMM) formalizes this: assume the data is generated by K hidden Gaussian components, each with its own mean μ_k, variance σ_k², and mixing weight π_k (the overall proportion of data belonging to component k, with all π_k summing to 1). For our marks example, K = 2. EM estimates μ₁, σ₁², μ₂, σ₂², π₁, π₂ — six unknowns — using exactly the same two-step loop: E-step computes, for every student, the probability their mark came from component 1 versus component 2 (using the Gaussian probability density in place of the binomial formula); M-step recomputes each component's mean, variance, and weight as a responsibility-weighted average over all students, exactly as the coin M-step computed a responsibility-weighted average over rounds.

Enrichment: Deriving the GMM Update Rules

The coin M-step was a weighted average you could compute with only arithmetic. The GMM M-step update formulas can be derived the same way conceptually, but writing out the derivation rigorously needs two tools — partial derivatives and Lagrange multipliers — that lie outside the CBSE syllabus at any grade (Class 12 calculus covers only single-variable functions). Treat this section as genuine enrichment, not exam material: the result is worth knowing, and the intuition is buildable from scratch, but you will not be tested on this derivation in a Board exam.

Partial derivatives, intuitively. Ordinary calculus asks: for a function of one variable, how fast does output change as input changes? A partial derivative asks the same question for a function of several variables, but answers it one variable at a time, holding every other variable frozen. Picture standing on a hillside whose elevation depends on two coordinates — how far east you've walked, and how far north. If you take one step north while staying at the same east-west position, the elevation changes at some rate — that rate is the partial derivative with respect to "north." Take a different step, purely east this time, and you get a different rate — the partial derivative with respect to "east." At the summit (a maximum), both of these rates are zero simultaneously — no direction you step, north or east, increases your elevation. That is the multivariable version of "set the derivative to zero to find a maximum," applied one direction at a time.

Lagrange multipliers, intuitively, with a solvable example first. Suppose you must maximize the product xy, but x and y are constrained to add up to 10 (think: a rectangular field with a fixed total of x+y=10 units of fencing available for two adjacent sides). You can solve this with only Class 12 single-variable calculus: substitute y = 10−x, so the area becomes A(x) = x(10−x) = 10x−x². Differentiating, dA/dx = 10−2x, which is zero at x = 5, giving y = 5 and maximum area 25. Substitution works here because the constraint was simple enough to solve for one variable directly.

A Lagrange multiplier is a technique for when substitution gets messy (many variables, harder constraints) — instead of eliminating a variable, you introduce one new variable, λ, and combine the objective and the constraint into a single expression: xy − λ(x+y−10). Take partial derivatives with respect to x, y, and λ, and set all three to zero. Solving this system reproduces x = y = 5 — the same answer as substitution, just reached without eliminating a variable by hand. The multiplier λ has a meaning: it measures how much the best-possible value would improve if the constraint's budget (the 10, here) were relaxed by one unit — sometimes called its "shadow price."

In the GMM M-step, the mixing weights π₁, π₂, …, π_K are exactly this kind of constrained optimization: you want the values of π_k that make the (weighted) data most probable, but they're constrained to sum to 1 — you can't just maximize each π_k independently, or they would all rush to 1. A Lagrange multiplier enforces that constraint while optimizing. Carrying out the full calculation (which we won't reproduce symbol-by-symbol here, since it needs the multivariable machinery just described) leads to a strikingly simple, intuitive result: the new π_k is just the average responsibility for component k across all data points — the same "weighted average" pattern as everything else in this chapter. Similarly, μ_k updates to the responsibility-weighted average of the data values, and σ_k² updates to the responsibility-weighted average squared-distance from that mean. Every M-step in this chapter, from coin bias to Gaussian mean to mixing weight, resolves to the same underlying idea: a weighted average, where the weights are the responsibilities computed in the E-step.

Two Common Misconceptions

Misconception 1: "EM always finds the best possible parameter values." False. The Jensen's-inequality proof guarantees the log-likelihood never decreases — it does not guarantee EM reaches the single best (global maximum) solution. The log-likelihood surface for a mixture model typically has several local maxima — points where every nearby direction is worse, but a genuinely better solution exists further away. EM climbs uphill and stops the moment it reaches any peak, local or global, because at a local peak the bound-maximizing M-step can no longer improve anything. This is why real implementations run EM from several different random starting guesses and keep the run that reaches the highest log-likelihood.

Misconception 2: "k-means and EM/GMM are unrelated clustering methods." Also false — k-means is a special, simplified case of EM applied to a GMM. Constrain every Gaussian component to have the same, perfectly round (spherical) variance, and instead of the E-step computing a soft responsibility spread across all components, force it to assign each point entirely to whichever component's mean it is closest to (probability 1 for the nearest, 0 for all others) — that hard, winner-take-all assignment, followed by an M-step that simply averages each group's points for the new mean, is exactly k-means. K-means is sometimes called "hard EM": same two-step skeleton, with the E-step's soft probability replaced by an all-or-nothing decision.

EM in Your Exams

Be precise about where this topic sits. It is not part of the IIT-JEE (Main or Advanced) or BITSAT syllabus — both test only physics, chemistry, and mathematics, with no statistics-and-machine-learning component. Where EM does appear directly is GATE's Data Science and Artificial Intelligence paper, which explicitly lists Expectation-Maximization and Gaussian Mixture Models as examinable topics — this chapter's worked derivation is at the right depth for that. For CBSE Boards, this chapter is not itself board syllabus, but the underlying tools you practiced along the way are: writing and comparing binomial-style probability expressions, reasoning about conditional probability via counting (a preview of Class 12's Bayes' theorem), and using concavity to reason about a function's behavior (Class 12 calculus) are all genuinely examinable skills, exercised here in a research-grade setting rather than a textbook one. If you pursue computer science or statistics research later — an Olympiad in informatics, an undergraduate ML course, or GATE preparation — EM is one of the algorithms you will meet again and again, and this derivation from first principles will still be the correct one.

Summary

EM solves parameter-estimation problems where a variable that would make the estimation trivial — which coin, which subpopulation — is hidden. It alternates two steps: the E-step computes, for every data point, a soft probability distribution over the hidden variable given the current parameter guess (built here from a counting argument that is the same logic Class 12 will formalize as Bayes' theorem); the M-step recomputes the parameters as a responsibility-weighted average, maximizing the expected likelihood given those soft assignments. Worked by hand on five rounds of coin flips, one E-step and M-step moved θ_A from a guessed 0.6 to a data-informed 0.713, and θ_B from 0.5 to 0.581 — both computed via the exact same accumulation the coin_em() function performs. A Jensen's-inequality argument, resting only on the concavity of the log function, proves the observed-data log-likelihood never decreases across iterations — though it can and does stall at a local rather than global maximum, which is why multiple random restarts matter in practice. The same loop, unchanged in structure, estimates the means, variances, and mixing weights of a Gaussian Mixture Model — the mixing-weight update in particular needs multivariable partial derivatives and a Lagrange multiplier, tools that sit beyond the CBSE syllabus at any grade, included here as enrichment because the result they produce is the same weighted-average pattern that governs every other step in this chapter.

Practice: Active Recall

1. In the coin example, round 4 had 4 heads out of 10 flips, yet its E-step responsibility for coin A was 0.352 rather than exactly matching its raw head-fraction of 0.4. Explain, using the E-step formula, why these two numbers are not the same thing and shouldn't be expected to match.
2. If a sixth round of 10 flips came up with exactly 6 heads, would its responsibility for coin A (using the original θ_A=0.6, θ_B=0.5 guess) be closer to 0.5, closer to 0.805 (round 2's value), or closer to 0.352 (round 4's value)? Justify without recomputing the full decimal — reasoning about where 6 heads sits relative to the other rounds is enough.
3. Re-run one more full E-step and M-step by hand using θ_A=0.713 and θ_B=0.581 (the outputs of iteration 1) as the new starting guess, for just round 1 (5 heads, 5 tails). Has round 1's responsibility for A moved closer to or further from 0.5 compared to iteration 1? What does that tell you about how confidently EM can separate a perfectly balanced round (5-5)?
4. Explain in your own words why the log-likelihood bound B(q, θ) touches the true log-likelihood exactly when q(z) is set to the true posterior P(z|X, θ) — what does Jensen's inequality's "equality" condition require, and why does that specific choice of q satisfy it?
5. A classmate says: "Since EM's log-likelihood never decreases, running it for 1000 iterations must give the true best-fit coin biases." Identify the flawed assumption in this claim and describe a concrete way to guard against it in practice.