A dealer swaps a fair die for a loaded one and back, out of sight. You see only the rolls. A hidden Markov model works out which die was in play on each roll, gives the odds behind every call, and can learn the dealer's habits from the rolls alone. Counting sixes comes within a few rolls in a hundred on an easy deal, and falls further behind as the dealer gets stickier or the die less loaded.
Learn to score a sequence, to decode the hidden states behind it, and to learn the model from the sequence alone. Each algorithm comes with a hand calculation you can check.
Pick a decoder and read the two bands: the truth, then the guess, with every wrong roll marked. Then make the dealer switch more often and watch every decoder struggle. Then we build the whole machine, piece by piece, from a two-state chain to a model learned from rolls.
You need fractions and the idea of a probability. We build the rest from zero.
A toy built in this page. The dice follow the dishonest casino of Durbin, Eddy, Krogh and Mitchison (1998): the fair die shows each face one time in six, the loaded die shows a six half the time. The two sliders set the true dealer. Every decoder here is given that true model. Chapter 7 learns it from the rolls alone.
Chapter 0
Watch a stream of rolls, try to spot the loaded die by counting sixes, and see exactly where counting breaks
You sit at a dice table in a casino that cheats. The dealer has two dice in one hand. One is fair: each face comes up one time in six. One is loaded: it shows a six half the time, and each other face one time in ten.
The dealer swaps dice now and then, with a sleight of hand you cannot see. You see one thing only: the rolls. A long line of numbers from 1 to 6. Your job is to say, for every roll, which die made it.
Here is the first idea anyone has. Sixes are the giveaway. The loaded die makes three times as many of them. So slide a window along the rolls, count the sixes inside it, and call "loaded" when the count is high.
Try it. The device below plays 80 rolls from the real cheating dealer. Slide the window and the threshold, and watch the calls against the truth.
Top: the 80 rolls, with each six in yellow. Middle: the count of sixes in the window around each roll. Bottom: the truth band, then the calls, with every wrong call in red. Move the window size and the threshold.
Computed in this page. The dealer keeps the fair die with probability 0.95 on each roll and the loaded die with probability 0.90, as in Durbin et al. A roll near the ends uses the part of the window that exists.
Two things go wrong, and they pull in opposite directions. A small window reacts fast but it is noisy. Three sixes in five rolls happens often with a fair die, so the counter raises false alarms. A big window is calm but slow. It misses short loaded stretches and it calls the switch many rolls late.
Here are the numbers behind that. In 10 fair rolls, the chance of 4 or more sixes is about 7 in 100. In 10 loaded rolls it is about 83 in 100. So a window of 10 with a threshold of 4 is a decent test for a block of rolls that all came from one die. The trouble is that the window does not know where the dealer switched. It straddles the switch and blurs it.
There is a deeper problem. The counter treats every window on its own. It throws away something you know: the dealer is lazy. Once a die is in play, it tends to stay in play for a while. A six after a run of sixes is weak evidence of a new switch. A six after twenty quiet rolls is a different matter. The counter cannot tell these apart.
Here is the counter in code, so there is no mystery about what the device does. It is a one-line idea with two tuning knobs that somebody has to set by hand.
import numpy as np def count_sixes(x, win=10, thr=4): """x holds faces 1..6. Returns 1 (loaded) or 0 (fair) for every roll.""" six = (np.asarray(x) == 6).astype(int) calls = np.zeros(len(x), dtype=int) for t in range(len(x)): lo = max(0, t - (win - 1) // 2) # a window centred on roll t hi = min(len(x), lo + win) calls[t] = 1 if six[lo:hi].sum() >= thr else 0 return calls
Be fair to the counter. On this casino, with the window and threshold tuned by hand, it calls about 80 rolls in 100 right. The best HMM decoder calls about 84. That gap is real but modest. What the HMM adds is bigger than four points: a probability for every call, a score for the whole sequence, one coherent story of swaps, and a way to learn the dealer's habits with no hand tuning at all. Keep that list in mind. It is what the rest of the lesson builds.
So we want a method that does two things at once. It should weigh each roll as evidence, like the counter does. And it should carry a belief forward from roll to roll, so that the dealer's laziness counts too. That method is the hidden Markov model, or HMM. The name says what it is. A Markov chain runs hidden from view, and a model of what each state shows lets you reason back from the rolls to the chain.
Everything in this lesson is built on the dice. By the end you can compute, by hand and in code, the chance of a sequence of rolls, the odds that any given roll came from the loaded die, the single most likely story of swaps, and the dice themselves from rolls alone. The same four tools run speech recognisers, gene finders and the step counter in your phone.
Chapter 1
Write down how the dealer switches as two numbers, run the rule, and read off how long each die stays in play
Forget the rolls for a moment. Watch only the dealer's hand, as if you could. At each roll the hand holds one of two dice. Call that the state: F for the fair die, L for the loaded die. The state changes over time, so we index it by the roll number t: z1, z2, z3 and so on.
The dealer's habit is simple. If the fair die is in play, the dealer keeps it with probability 0.95 and switches with probability 0.05. If the loaded die is in play, the dealer keeps it with probability 0.90 and switches with probability 0.10. Those four numbers are the whole rule.
Notice what the rule does not depend on. It does not care how long the current die has been in play. It does not care what happened ten rolls ago. The next state depends on the current state only. This is the Markov property: the present state carries everything the past can tell you about the future.
A sequence of states that follows such a rule is a Markov chain. We write the rule as a table, the transition matrix A. Row i is the state you are in. Column j is the state you go to.
| From \ To | F (fair) | L (loaded) |
|---|---|---|
| F (fair) | 0.95 | 0.05 |
| L (loaded) | 0.10 | 0.90 |
One more number starts the chain. Before the first roll, which die does the dealer pick up? Call that the start distribution π. We will use π = (0.5, 0.5): no idea at first, either die equally likely.
Rules are easier to feel than to read. The device below runs the chain for 200 rolls. Each tick of the band is one roll, blue for fair and warm for loaded. Below it, the lengths of the runs are collected into a histogram. Change the two switch probabilities and watch the runs stretch or shatter.
Top: 200 rolls of hidden state. Bottom: how long each fair run lasted (bars) against the curve the rule predicts. Drag a switch probability, or run the chain again.
Computed in this page. The histogram pools the fair runs from 50 chains of 200 rolls so the shape is visible. The curve is the geometric distribution with the slider's switch probability.
You can read this off the rule by hand. Suppose the fair die is in play. Each roll, it stays with probability 0.95. The run goes on until the first switch. The number of rolls until a switch, when each roll switches with probability p, follows a geometric distribution, and its average is 1 / p.
Fair: 1 / 0.05 = 20 rolls. Loaded: 1 / 0.10 = 10 rolls.
Why 1 / p? Picture many fair runs. On each roll, a fraction p of the surviving runs end. So the runs end at an average rate of p per roll, and one run lasts about 1 / p rolls. The exact proof sums p(1 − p)k−1 · k over all k, and that sum is 1 / p.
The spread matters as much as the average. The chance that the fair die survives 20 more rolls is 0.9520. Work it out: 0.952 = 0.9025, 0.954 = 0.8145, 0.955 = 0.7738, 0.9510 = 0.5987, 0.9520 = 0.3585. So about 36% of fair runs outlast their own average. Short runs are common and a few long runs are very long. Look at the histogram again: it has a tall head and a long tail.
Run the chain for a long time. What fraction of rolls use the loaded die? Not half. The fair die is stickier, so the chain spends more time there. The long-run fractions are the stationary distribution. Call them (sF, sL). In steady state, the flow out of F must equal the flow into F:
sF · 0.05 = sL · 0.10 so sF = 2 sL and with sF + sL = 1: sF = 2/3, sL = 1/3.
Check it against the run lengths. Fair runs average 20 rolls, loaded runs average 10, and they alternate. So out of every 30 rolls, 20 are fair. Two thirds. The two views agree, as they must.
The matrix A answers "where next?". Multiply it by itself and it answers "where in two rolls?". Each entry of A2 adds up the two-step routes. From F to L in two steps you can go F to F to L, or F to L to L. By hand:
(A2)FL = 0.95 × 0.05 + 0.05 × 0.90 = 0.0475 + 0.045 = 0.0925
(A2)FF = 0.95 × 0.95 + 0.05 × 0.10 = 0.9025 + 0.005 = 0.9075
(A2)LF = 0.10 × 0.95 + 0.90 × 0.10 = 0.095 + 0.09 = 0.185 (A2)LL = 0.10 × 0.05 + 0.90 × 0.90 = 0.005 + 0.81 = 0.815
Each row still adds to 1, and the off-diagonal entries have almost doubled. Keep multiplying. A10 has rows (0.73, 0.27) and (0.54, 0.46). A50 has both rows at (0.667, 0.333). After enough steps it no longer matters where you started: every row becomes the stationary distribution. That is the long-run split, reached from either die.
A2 = A @ A # two-step transitions print(A2) # [[0.9075 0.0925] [0.185 0.815]] print(np.linalg.matrix_power(A, 50)) # both rows -> [0.667 0.333] # the stationary split directly: the left eigenvector of A with eigenvalue 1 w, v = np.linalg.eig(A.T) s = v[:, np.isclose(w, 1)].real.ravel(); s /= s.sum() print(s) # [0.667 0.333]
This matters for the forward algorithm later. "Move the mass along the transitions" is exactly a multiplication by A. The forward pass is the chain's own arithmetic, with one extra factor per roll for the evidence.
Here is the chain in code. It is four lines. Notice that the state carries everything: the loop never looks back further than one step.
import numpy as np A = np.array([[0.95, 0.05], # row F: stay fair, switch to loaded [0.10, 0.90]]) # row L: switch to fair, stay loaded pi = np.array([0.5, 0.5]) def sample_chain(T, rng): z = np.empty(T, dtype=int) z[0] = rng.choice(2, p=pi) # 0 = F, 1 = L for t in range(1, T): z[t] = rng.choice(2, p=A[z[t-1]]) # the next state depends on z[t-1] only return z z = sample_chain(100000, np.random.default_rng(0)) print(z.mean()) # about 0.333: a third of rolls are loaded
You now have the hidden part of the model. There is one problem: you never see z. You see rolls. The next chapter connects each state to what it shows.
Chapter 2
Give each die its face probabilities, assemble the whole model, and compute the chance of one complete story by hand
Each state shows something. The fair die shows each face with probability 1/6. The loaded die shows a six with probability 1/2 and each other face with probability 1/10. Check that the loaded row adds up: five faces at 0.1 make 0.5, plus 0.5 for the six, equals 1.
The thing a state shows is called an emission or an observation. We write the roll at time t as xt. The table of emission probabilities is the emission matrix B. Row i is the state, column k is the face.
| Die | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| F (fair) | 1/6 | 1/6 | 1/6 | 1/6 | 1/6 | 1/6 |
| L (loaded) | 0.1 | 0.1 | 0.1 | 0.1 | 0.1 | 0.5 |
Now the model is complete. A hidden Markov model is three tables: the start distribution π, the transition matrix A, and the emission matrix B. People write the whole bundle as λ = (π, A, B). The model makes a sequence in two layers. The chain picks a state. The state rolls a face. The chain picks the next state. And so on.
Three rolls are on the table. Choose which die made each one (the buttons). The chain of boxes shows every factor in the story's probability, and the bars compare all 8 possible stories. Change the rolls with the top selector.
Computed in this page with the Durbin model and a start distribution of one half each.
Pick a story: a full path of states, together with the rolls. Say the dealer used the loaded die for all three rolls, and the rolls were 6, 6, 2. What is the chance of exactly that? Walk the two layers in order and multiply as you go.
P(LLL, 6 6 2) = 0.5 × 0.5 × 0.9 × 0.5 × 0.9 × 0.1 = 0.010125
Compare the all-fair story on the same rolls. Start 0.5, six 1/6, stay 0.95, six 1/6, stay 0.95, two 1/6. The product is 0.5 × 0.95 × 0.95 / 216 = 0.45125 / 216 = 0.002089. The loaded story is about five times as likely. Two sixes in three rolls lean loaded, and the dealer's laziness makes a stay cheap.
The general rule is the same walk written once. A path z1 … zT with rolls x1 … xT has probability:
This product is the heart of everything that follows. Every algorithm in this lesson is a clever way to add up, or to search over, products of this shape. Keep it in view.
There is a quick way to feel how much one roll says. Divide the two emission probabilities. A six is 0.5 under L and 1/6 under F: the ratio is 3. A non-six is 0.1 under L and 1/6 under F: the ratio is 0.6. So each six multiplies the odds for loaded by 3, and each other face multiplies them by 0.6.
Two non-sixes multiply the odds by 0.36. One six multiplies them by 3. Together: 3 × 0.36 = 1.08. So one six in three rolls is almost no evidence at all. Two sixes in three rolls: 9 × 0.6 = 5.4 to 1. That is the "five times" we found above, before the transitions were counted.
Each roll multiplies the odds for loaded by 3 (a six) or by 0.6 (anything else). The ladder shows the running odds on a log scale, so each roll is one step up or one step down. Toggle the dealer's laziness to see the step that evidence alone cannot take.
Computed in this page. Without laziness, the odds are the product of the emission ratios from an even start. With laziness, each step first pulls the odds toward the dealer's habit (the forward recursion of Chapter 3), then multiplies by the ratio.
Watch the ladder with the laziness switched off. It wanders wherever the last few rolls push it, and a short burst of sixes sends it high even when the dealer never switched. Switch the laziness on and the ladder gets heavy: the transitions pull the odds back toward "stay where you were" before each roll adds its push. That pull is the whole difference between the counter and the HMM.
Before the algorithms, be exact about what flows through them. For N states and K faces:
| Object | Shape | Holds | Casino |
|---|---|---|---|
| π | (N,) | start probabilities, sum 1 | (0.5, 0.5) |
| A | (N, N) | transition probabilities, each row sums to 1 | 2 × 2, four numbers |
| B | (N, K) | emission probabilities, each row sums to 1 | 2 × 6, twelve numbers |
| x | (T,) integers | the rolls, 0-based face indices in code | one line of T numbers |
| z | (T,) integers | the hidden states, never observed | what every decoder tries to recover |
| α, β, γ, δ | (T, N) | one number per roll per state, the working tables of Chapters 3 to 5 | T × 2 each |
Sixteen numbers define the casino. Everything the lesson computes is a (T, 2) table derived from those sixteen numbers and the rolls. If you can write down π, A and B, you have an HMM, and every algorithm below runs unchanged.
Generating rolls is the model read forwards, one layer at a time. It is also how every device on this page makes its data.
def sample_hmm(T, rng): z = np.empty(T, dtype=int); x = np.empty(T, dtype=int) z[0] = rng.choice(2, p=pi) x[0] = rng.choice(6, p=B[z[0]]) + 1 # the state rolls a face for t in range(1, T): z[t] = rng.choice(2, p=A[z[t-1]]) # the chain picks the next state x[t] = rng.choice(6, p=B[z[t]]) + 1 # that state rolls return z, x # you keep z only to score your decoders
Rabiner's 1989 tutorial organised the whole subject around three problems. We follow it, because every later chapter answers one of them.
Chapter 3
Given the model and the rolls, how likely are the rolls? P(x | λ). Needed to compare models and to learn one.
Chapters 4 and 5
Given the model and the rolls, which dice? Either per roll (forward-backward) or the best whole path (Viterbi).
Chapter 7
Given only the rolls, what are π, A and B? Baum-Welch, which runs problem 2 inside a loop.
Here is the model as data, and the joint probability as a function. Compare the function with the walk above. It is the same six multiplications, written for any length.
B = np.array([[1/6]*6, # row F: every face 1/6 [0.1]*5 + [0.5]]) # row L: a six half the time def joint(z, x): """P(path z and rolls x). z holds 0/1 states, x holds faces 1..6.""" p = pi[z[0]] * B[z[0], x[0]-1] for t in range(1, len(x)): p *= A[z[t-1], z[t]] * B[z[t], x[t]-1] return p print(joint([1,1,1], [6,6,2])) # 0.010125 print(joint([0,0,0], [6,6,2])) # 0.002089
Chapter 3
Add up the probability of every possible story without listing them, by carrying one small table from roll to roll
Question one. How likely are the rolls 6, 6, 2 under our model, with no idea which dice were used? The honest answer adds up every story. There are 2 states and 3 rolls, so 23 = 8 stories. We can list them all, and the device in Chapter 2 already did. Here they are:
| Path | Probability | Path | Probability |
|---|---|---|---|
| FFF | 0.002089 | LFF | 0.000660 |
| FFL | 0.000066 | LFL | 0.000021 |
| FLF | 0.000035 | LLF | 0.001875 |
| FLL | 0.000188 | LLL | 0.010125 |
P(6 6 2) = sum of all eight = 0.015058
Now think about 100 rolls. There are 2100 stories, about 1030. The age of the universe in nanoseconds is about 1026. Listing is out. Yet the answer takes a few hundred multiplications. The trick is to share work between stories that agree on their past.
Look at the eight stories again. Four of them end in L at roll 3. They differ in what came before, but from roll 3 onward they behave the same. So add them up before moving on, and carry one number per state instead of one per story.
Define the forward variable αt(i): the total probability of all stories that produce the first t rolls and end in state i at time t.
At the first roll there is nothing to sum. α1(i) is the start probability of i times the chance that i shows the first roll. After that, each step does the same three things: take the mass in each previous state, move it along the transitions, and multiply by the emission of the new roll.
At the end, the rolls are explained by stories in state F or in state L, so add the two last values. That sum is P(x), the answer to question one.
It is worth seeing the algebra once, because the same four lines justify every algorithm in this lesson. Start from the definition and peel off the last roll.
Step 4 is the one that does the work, and it is where the model's two assumptions pay off. Without them the middle and last factors would depend on the whole past, and no small table could hold it.
Each column is one roll; the two circles are the states. Press Step to compute the next column. Arrow thickness shows how much mass each path carries. The number in a circle is the forward value. Lengthen the sequence to see the count of stories explode while the work stays flat.
Computed in this page. The sequence starts 6, 6, 2 and continues with fixed rolls so the first three columns match the hand calculation below.
Rolls 6, 6, 2. Start with the first roll, a six.
α1(F) = 0.5 × 1/6 = 0.08333 α1(L) = 0.5 × 0.5 = 0.25
Second roll, another six. For F: gather the mass that moves into F, then charge the six.
α2(F) = (0.08333 × 0.95 + 0.25 × 0.10) × 1/6 = (0.07917 + 0.025) × 1/6 = 0.10417 / 6 = 0.01736
α2(L) = (0.08333 × 0.05 + 0.25 × 0.90) × 0.5 = (0.004167 + 0.225) × 0.5 = 0.22917 × 0.5 = 0.11458
Third roll, a two. Same moves, different emission.
α3(F) = (0.01736 × 0.95 + 0.11458 × 0.10) × 1/6 = (0.01649 + 0.01146) / 6 = 0.02795 / 6 = 0.004659
α3(L) = (0.01736 × 0.05 + 0.11458 × 0.90) × 0.1 = (0.000868 + 0.10313) × 0.1 = 0.10399 × 0.1 = 0.010399
P(6 6 2) = 0.004659 + 0.010399 = 0.015058
The same number as the sum of eight stories. We did 3 time steps, each with 2 states, each gathering from 2 states: 12 multiplications plus a few additions. For T rolls and N states the forward algorithm costs about N2 T operations. For 100 rolls and 2 states that is 400 operations instead of 1030 stories.
Read the values as you go, because they already tell a story. After the first six, the mass splits 0.083 to 0.25, three to one for loaded. After the second six it is 0.017 to 0.115, nearly seven to one. After the two, it is 0.0047 to 0.0104, closer to two to one. The two pulled the odds back toward fair. The forward values are the odds so far, scaled by how surprising the rolls were.
def forward(x): """Return alpha, shape (T, N). x holds faces 1..6.""" T, N = len(x), len(pi) alpha = np.zeros((T, N)) alpha[0] = pi * B[:, x[0]-1] # start, then charge roll 1 for t in range(1, T): for j in range(N): arrive = sum(alpha[t-1, i] * A[i, j] for i in range(N)) # mass moving into j alpha[t, j] = arrive * B[j, x[t]-1] # then charge roll t return alpha a = forward([6, 6, 2]) print(a[-1].sum()) # 0.015058 # the inner loops are a vector-matrix product: alpha[t] = (alpha[t-1] @ A) * B[:, x_t] def forward_fast(x): alpha = [pi * B[:, x[0]-1]] for k in x[1:]: alpha.append((alpha[-1] @ A) * B[:, k-1]) return np.array(alpha)
The one-line form is worth staring at. alpha @ A moves the mass along every transition at once. Multiplying by B[:, k] charges the roll. That is the entire forward algorithm: move, then charge, T times.
You can now score any sequence. But the forward values only use the rolls before each moment. To judge roll 17 you would also like to use rolls 18 to 100. The next chapter runs the same idea backwards and combines the two.
Chapter 4
Run the same recursion from the end, multiply the two, and get the odds that each roll came from the loaded die, using every roll you saw
Suppose roll 17 is a six and rolls 18 to 30 are all sixes too. At the moment of roll 17, you did not know that. In hindsight, roll 17 almost certainly came from the loaded die. The forward values cannot see this: they stop at the present. We want the posterior probability of each state given all the rolls, past and future.
Split the rolls at time t. The forward value already covers the rolls up to t and the state at t. Define a partner that covers the rolls after t, given the state at t. That is the backward variable.
At the last roll there is no future, so βT(i) = 1 for both states. Then step backwards. From state i at time t, you move to some state j, j shows the next roll, and then the rest of the future follows from j.
Rolls 6, 6, 2 again. Start at the end: β3(F) = β3(L) = 1. Step back to t = 2. The next roll is a two.
β2(F) = 0.95 × 1/6 × 1 + 0.05 × 0.1 × 1 = 0.15833 + 0.005 = 0.16333
β2(L) = 0.10 × 1/6 × 1 + 0.90 × 0.1 × 1 = 0.01667 + 0.09 = 0.10667
Step back to t = 1. The next roll is a six, and the future after that is the β2 values.
β1(F) = 0.95 × 1/6 × 0.16333 + 0.05 × 0.5 × 0.10667 = 0.02586 + 0.00267 = 0.02853
β1(L) = 0.10 × 1/6 × 0.16333 + 0.90 × 0.5 × 0.10667 = 0.00272 + 0.04800 = 0.05072
Check: the full probability of the rolls should come out at any time step. At t = 1: α1(F) β1(F) + α1(L) β1(L) = 0.08333 × 0.02853 + 0.25 × 0.05072 = 0.002378 + 0.012680 = 0.015058. The same P(x) as the forward pass. That equality is a good test for your code.
Now the posterior. The stories that pass through state i at time t are exactly the ones counted by αt(i) in the past and βt(i) in the future, and the Markov property lets us multiply the two halves. Divide by P(x) to turn the joint into a conditional.
Here is why multiplying is allowed. P(x, zt = i) = P(x1, …, xt, zt = i) · P(xt+1, …, xT | x1, …, xt, zt = i) by the chain rule. Given zt, the future rolls do not care about the past rolls: the state is the only bridge between them. So the second factor drops its dependence on the past rolls and becomes βt(i). Then Bayes: P(zt = i | x) = P(x, zt = i) / P(x).
γ1(L) = 0.25 × 0.05072 / 0.015058 = 0.01268 / 0.015058 = 0.842
γ2(L) = 0.11458 × 0.10667 / 0.015058 = 0.01222 / 0.015058 = 0.812
γ3(L) = 0.010399 × 1 / 0.015058 = 0.691
Compare these with the forward-only odds from Chapter 3. After roll 1 alone, the chance of loaded was 0.75. In hindsight it is 0.842: the second six raised it. After roll 2 alone it was 0.868. In hindsight it is 0.812: the two that followed lowered it. Hindsight uses the future, and the future changes the call.
This is the hero's third decoder. Filtering is the forward-only estimate, the best you can do live. Smoothing is the full posterior, the best you can do once the sequence is complete. Play with both below.
The purple curve is the probability of the loaded die at each roll. The truth band sits below it, and the calls under that, with every wrong call in red. Switch between live odds (forward only) and hindsight (forward and backward).
Computed in this page with the Durbin model, which also generated the rolls. A call is "loaded" when the probability passes one half.
Watch the live curve at a switch from fair to loaded. It climbs over several rolls, because each six only triples the odds and a non-six pulls them back. The hindsight curve jumps almost at the switch, because it can see the run of sixes that follows. Hindsight is sharper at every boundary.
A live system cannot wait for the whole sequence. But it can often wait a few steps. Fixed-lag smoothing reports the state at roll t once roll t + d has arrived, using the backward pass over just those d rolls. With d = 5 you get most of the sharpness of full hindsight at a delay of five rolls. Speech recognisers and step counters run this way: a short delay buys a much better call. Try reading the live curve in the device five rolls behind the right edge and you will see why.
If you call "loaded" wherever γt(L) is above one half, you have posterior decoding. It picks the best state at each roll on its own. It makes the most correct calls per roll you can make with this model, which is why it wins the accuracy count in the hero.
Now the honest comparison promised in Chapter 0. Over long deals from the Durbin casino, posterior decoding calls about 82 rolls in 100 right. The tuned counter calls about 80. Four points is what hindsight buys per roll here, because the counter's centred window is itself a crude smoother. What the counter cannot give you is the curve above: a calibrated probability on every roll. When the curve says 0.55, about 55 of 100 such rolls are loaded. A downstream system can act on that number. A hard call throws it away.
It has one odd habit. The sequence of per-roll best states need not be a possible story. Each call is the winner of its own vote, and the votes do not coordinate. In a model where some transitions are forbidden, posterior decoding can output a path that uses them. The next chapter fixes that with a different question.
def backward(x): T, N = len(x), len(pi) beta = np.ones((T, N)) # no future after the last roll for t in range(T-2, -1, -1): beta[t] = A @ (B[:, x[t+1]-1] * beta[t+1]) # move, charge the next roll, then the rest return beta def posterior(x): alpha, beta = forward(x), backward(x) px = alpha[-1].sum() return alpha * beta / px # gamma, shape (T, N); each row sums to 1 g = posterior([6, 6, 2]) print(g[:, 1]) # [0.842 0.812 0.691]
Chapter 5
Swap the sum for a max, remember where each max came from, and walk back along the pointers to the most likely path
Posterior decoding answers "which die at roll t?" for each t on its own. A detective asks a different question: "what is the one story that best explains everything?" That is the single path z1 … zT with the largest joint probability P(z, x). Out of 2T stories we want the top one.
The forward algorithm found the sum over all stories by carrying N numbers per step. The same trick finds the max. The reason is that the best story ending in state j at time t must begin with the best story ending in whatever state it came from. A suboptimal prefix could always be swapped for a better one without touching the rest.
Define δt(i): the probability of the best story that produces the first t rolls and ends in state i.
One more table. For each δt+1(j), write down which i won the max. Call it the back-pointer ψt+1(j). At the end, take the state with the largest δT, then follow the pointers back to roll 1. The path you walk is the answer.
Same trellis as Chapter 3, but each circle keeps only its best arrival and an arrow back to it. Step to the end, then press Trace back to light the winning path. Compare the circle values with the forward values: they are smaller, because a max is never larger than a sum.
Computed in this page on the same fixed rolls as Chapter 3, so the first three columns match the hand calculation.
Rolls 6, 6, 2. The first column is the same as before, since there is nothing to maximise over yet.
δ1(F) = 0.5 × 1/6 = 0.08333 δ1(L) = 0.5 × 0.5 = 0.25
Second roll, a six. For F, compare the two arrivals and keep the larger.
into F: 0.08333 × 0.95 = 0.07917 (from F) vs 0.25 × 0.10 = 0.025 (from L)
δ2(F) = 0.07917 × 1/6 = 0.01319, ψ2(F) = F
into L: 0.08333 × 0.05 = 0.00417 (from F) vs 0.25 × 0.90 = 0.225 (from L)
δ2(L) = 0.225 × 0.5 = 0.1125, ψ2(L) = L
Third roll, a two.
into F: 0.01319 × 0.95 = 0.01253 (from F) vs 0.1125 × 0.10 = 0.01125 (from L)
δ3(F) = 0.01253 × 1/6 = 0.002089, ψ3(F) = F
into L: 0.01319 × 0.05 = 0.00066 (from F) vs 0.1125 × 0.90 = 0.10125 (from L)
δ3(L) = 0.10125 × 0.1 = 0.010125, ψ3(L) = L
Now trace back. The larger final value is δ3(L) = 0.010125, so z3 = L. Its pointer says L, so z2 = L. That pointer says L, so z1 = L. The best story is LLL, with probability 0.010125. Check it against the table of eight stories in Chapter 3: it is the top row, and 0.002089 is exactly the FFF story, which is the best story ending in F.
Look at how close the third step was. Into F, the two arrivals were 0.01253 and 0.01125. A slightly stickier loaded die would have flipped the pointer, and the best path ending in F would have been LLF. Viterbi makes hard choices at every step, and the choices can hinge on small margins. Keep that in mind when you compare it with the soft posterior.
Two decoders, two questions. Posterior decoding picks the best state at each roll. Viterbi picks the best whole path. Usually they agree on most rolls. But they measure different things, and the device below counts where they differ.
Three bands: the truth, the Viterbi path, and the posterior calls, with wrong calls in red. The marks between the two decoder bands show where they disagree. Make the dealer jumpier and watch the disagreements move.
Computed in this page. Both decoders use the true model, including the switch rate you set.
Here is the rule of thumb. If you will be scored per roll, use posterior decoding: it maximises the expected number of correct calls. If you need one coherent story, use Viterbi: its path always obeys the transition rules, and it is what a speech recogniser returns as the recognised words. The posterior path can hop between states in ways no single story would.
def viterbi(x): T, N = len(x), len(pi) delta = np.zeros((T, N)); psi = np.zeros((T, N), dtype=int) delta[0] = pi * B[:, x[0]-1] for t in range(1, T): for j in range(N): cand = delta[t-1] * A[:, j] # every arrival into j psi[t, j] = np.argmax(cand) # remember the winner delta[t, j] = cand.max() * B[j, x[t]-1] # keep only the best, then charge the roll path = [int(np.argmax(delta[-1]))] for t in range(T-1, 0, -1): path.append(psi[t, path[-1]]) # walk the pointers back return path[::-1], delta[-1].max() print(viterbi([6, 6, 2])) # ([1, 1, 1], 0.010125)
Set forward and viterbi side by side. The only differences are sum against max, and the pointer table. Everything else, including the cost of N2 T, is shared. Mathematicians say the two live in different semirings: one adds and multiplies, the other maximises and multiplies. The algorithm is the same shape in both.
| Step | Forward | Viterbi |
|---|---|---|
| Start | α1(i) = πi Bi(x1) | δ1(i) = πi Bi(x1) |
| Combine arrivals | ∑i αt(i) Aij | maxi δt(i) Aij, and store the argmax |
| Charge the roll | × Bj(xt+1) | × Bj(xt+1) |
| Finish | P(x) = ∑i αT(i) | P(z*, x) = maxi δT(i), then trace back |
| Answers | how likely are the rolls; live odds | the single most likely path |
| Safe in long sequences | scaling, or log-sum-exp | plain logs: max and add |
Two practical notes. Ties are rare with real numbers but possible with rounded ones; break them by a fixed rule, such as the lower state index, so the output is reproducible. And if you need the top few paths rather than the top one, keep the best k arrivals per state instead of one. That is beam search with an exact beam, and speech recognisers prune it to stay fast.
Chapter 6
See a few hundred rolls drive every probability to zero in a computer, then fix it two ways and check that both give the same answer
Run the forward algorithm on 1,000 rolls and print P(x). You get exactly 0. Not small. Zero. Every roll multiplies the running values by a number between 0.05 and 0.5, and after a few hundred rolls the product falls below the smallest number a computer can hold. This is underflow, and it breaks every algorithm in this lesson in the same way.
Put a number on it. The fair die's emission is 1/6 per roll. After T rolls the product is (1/6)T. A double-precision number cannot go below about 10−308. Solve (1/6)T = 10−308: T = 308 / log10 6 = 308 / 0.778 = 396. Around 400 rolls, the fair-only story is already zero. With the transitions in the product it happens sooner.
Left: the raw forward total P(x) as the sequence grows, on a linear scale. It is invisible almost at once. Right: the same quantity as a log, which falls in a straight line and never reaches the floor. The red line is the smallest positive double. Drag the length.
Computed in this page on a fixed deal from the Durbin model. The raw curve is computed in plain floating point so you see the true underflow.
A logarithm turns products into sums. log(0.5 × 0.5 × 0.9) = log 0.5 + log 0.5 + log 0.9. Sums do not underflow: a log probability of −5,000 is a perfectly ordinary number. So store log α instead of α, log δ instead of δ, and add where you used to multiply.
Viterbi is the easy case, because a max is a max in either scale. Here is step two of the hand calculation redone in natural logs. You need ln 0.5 = −0.693, ln(1/6) = −1.792, ln 0.95 = −0.051, ln 0.90 = −0.105, ln 0.10 = −2.303, ln 0.05 = −2.996.
log δ1(F) = −0.693 − 1.792 = −2.485 log δ1(L) = −0.693 − 0.693 = −1.386
into L: −2.485 − 2.996 = −5.481 vs −1.386 − 0.105 = −1.491. log δ2(L) = −1.491 − 0.693 = −2.184
Check: e−2.184 = 0.1126, which is the 0.1125 from Chapter 5 up to rounding. The pointers are the same because the order of the candidates is the same.
The forward algorithm is harder, because it adds probabilities, and you cannot add logs directly. The tool is log-sum-exp. To compute log(ea + eb) safely, pull out the larger exponent m, then add what is left.
Try it on the final step of Chapter 3. The two last forward values were 0.004659 and 0.010399, so a = ln 0.004659 = −5.369 and b = ln 0.010399 = −4.566. Then m = −4.566, a − m = −0.803, e−0.803 = 0.448, and log(1 + 0.448) = 0.370. The result is −4.566 + 0.370 = −4.196, and e−4.196 = 0.01506. Correct, and it would have worked just as well with a = −5,369 and b = −4,566.
There is a second way, and it is the one most forward-backward code uses. After each step, divide the column of α values by their sum, and remember the sum. The scaled values are then exactly the filtered probabilities from Chapter 3, so they stay between 0 and 1 forever. The product of all the column sums you divided out is P(x). Store the logs of the sums and add them.
By hand on 6, 6, 2. Column 1 is (0.08333, 0.25), sum c1 = 0.33333, scaled to (0.25, 0.75). Move and charge the second six from the scaled column: F gets (0.25 × 0.95 + 0.75 × 0.10) / 6 = 0.3125 / 6 = 0.05208; L gets (0.25 × 0.05 + 0.75 × 0.90) × 0.5 = 0.6875 × 0.5 = 0.34375. Sum c2 = 0.39583, scaled to (0.1316, 0.8684). Third roll: F gets (0.1316 × 0.95 + 0.8684 × 0.10) / 6 = 0.21184 / 6 = 0.03531; L gets (0.1316 × 0.05 + 0.8684 × 0.9) × 0.1 = 0.78816 × 0.1 = 0.07882. Sum c3 = 0.11413.
P(x) = c1 c2 c3 = 0.33333 × 0.39583 × 0.11413 = 0.015058
The same answer a third way. And the scaled columns, (0.25, 0.75), (0.132, 0.868), (0.309, 0.691), are the live odds from Chapter 3. Scaling does two jobs at once: it keeps the numbers alive and it hands you the filtered posterior for free. The backward pass uses the same ct, and the product αβ then gives γ directly, with no division by P(x).
Check the backward half of that claim by hand. Divide each backward step by the scale of the roll it charges. From β3 = (1, 1): the scaled β2 is (0.16333, 0.10667) / c3 = (0.16333, 0.10667) / 0.11413 = (1.431, 0.935). Then the scaled β1 uses the scaled β2 and divides by c2: for L, (0.10 × 1/6 × 1.431 + 0.90 × 0.5 × 0.935) / 0.39583 = (0.02385 + 0.42075) / 0.39583 = 1.123. Now multiply with the scaled forward value at t = 1: 0.75 × 1.123 = 0.842. That is γ1(L) from Chapter 4, with no P(x) in sight.
from scipy.special import logsumexp def forward_log(x): logA, logB, logpi = np.log(A), np.log(B), np.log(pi) la = logpi + logB[:, x[0]-1] for k in x[1:]: # la[:, None] + logA has entry (i, j) = log alpha_i + log A_ij; sum over i in log space la = logsumexp(la[:, None] + logA, axis=0) + logB[:, k-1] return logsumexp(la) # log P(x) def forward_scaled(x): a = pi * B[:, x[0]-1] logpx = 0.0 for k in x[1:]: c = a.sum(); logpx += np.log(c); a = a / c # rescale, remember the scale a = (a @ A) * B[:, k-1] return logpx + np.log(a.sum()) x = rng.choice(6, size=1000) + 1 print(forward(x)[-1].sum()) # 0.0 (underflow) print(forward_log(x)) # about -1790 print(forward_scaled(x)) # the same number, to 10 decimal places
Chapter 7
Start from a guessed model, count what the guess believes happened, re-estimate from the counts, and repeat until the likelihood stops climbing
So far the casino handed us its model. Real casinos do not. You get rolls, and only rolls. The question is now: from x alone, what are π, A and B? This is problem three, and it is the one that makes HMMs useful, because the hidden structure of speech or DNA is not written down anywhere either.
Start with what you would do if you could see the dice. Count. AFL is the number of times the dealer went from fair to loaded, divided by the number of times the dealer held the fair die. BL(6) is the number of sixes rolled with the loaded die, divided by the number of loaded rolls. Counting is the maximum-likelihood estimate when the states are visible.
You cannot see the dice. But given a guessed model you can compute, for every roll, the probability that it was loaded. That is γt(L) from Chapter 4. So instead of counting, you count expected events. Roll 17 contributes 0.84 of a loaded roll and 0.16 of a fair roll. Add those fractions up and you have soft counts.
For the emissions and the start, γ is enough. For the transitions, you need the probability of a pair of states at consecutive rolls, given the whole sequence. Call it ξt(i, j). The forward value covers the past up to i, the backward value covers the future from j, and the transition and emission in between join them.
By hand, for the first transition of 6, 6, 2, with the forward and backward values we already have. P(x) = 0.015058.
ξ1(L, L) = 0.25 × 0.90 × 0.5 × 0.10667 / 0.015058 = 0.012 / 0.015058 = 0.797
ξ1(F, F) = 0.08333 × 0.95 × 1/6 × 0.16333 / 0.015058 = 0.002155 / 0.015058 = 0.143
ξ1(F, L) = 0.08333 × 0.05 × 0.5 × 0.10667 / 0.015058 = 0.000222 / 0.015058 = 0.015
ξ1(L, F) = 0.25 × 0.10 × 1/6 × 0.16333 / 0.015058 = 0.000681 / 0.015058 = 0.045
They add up to 1.000, as they must. The second transition uses α2, the emission of the two, and β3 = 1:
ξ2(L, L) = 0.11458 × 0.90 × 0.1 × 1 / 0.015058 = 0.010313 / 0.015058 = 0.685
ξ2(F, F) = 0.01736 × 0.95 × 1/6 × 1 / 0.015058 = 0.002749 / 0.015058 = 0.183
ξ2(L, F) = 0.11458 × 0.10 × 1/6 / 0.015058 = 0.001910 / 0.015058 = 0.127 ξ2(F, L) = 0.01736 × 0.05 × 0.1 / 0.015058 = 0.006
Also check that summing ξt(i, j) over j gives back γt(i): 0.143 + 0.015 = 0.158 = γ1(F), and 0.183 + 0.006 = 0.188 = γ2(F). Good. The pair posteriors are consistent with the single posteriors, as they must be, since they describe the same stories.
Now count as if the fractions were real events. Expected transitions out of F: 0.143 + 0.015 + 0.183 + 0.006 = 0.346. Of those, 0.143 + 0.183 = 0.326 stayed in F. So the new estimate of AFF is 0.326 / 0.346 = 0.941, and AFL = 0.059. Out of L: 0.045 + 0.797 + 0.127 + 0.685 = 1.654, of which 1.482 stayed. New ALL = 1.482 / 1.654 = 0.896, ALF = 0.104.
The emissions from three rolls show a trap. Visits to L: 0.842 + 0.812 + 0.691 = 2.344. Sixes happened at rolls 1 and 2, so BL(6) ← (0.842 + 0.812) / 2.344 = 0.705. A two at roll 3: BL(2) ← 0.691 / 2.344 = 0.295. And every other face: 0. The new model now says the loaded die cannot show a one. One zero in B kills every future sequence that contains a one from that state, and the zero can never recover, because a zero probability yields zero expected counts.
The fix is a pseudocount: add a small constant, say 0.5, to every soft count before dividing. It is a prior that says "I have seen every face a little." With three rolls the prior dominates. With three thousand it is a rounding error.
Left: the soft counts γ for each roll, as two stacked bars. Right: the loaded die's emission row after each M step. Step EM from the Durbin model with the pseudocount off, and watch four faces die. Then switch it on and step again.
Computed in this page on the rolls 6, 6, 2 only. With so little data the estimates swing wildly; that is the point of the device, not a bug.
Watch the first step without the pseudocount: the faces 1, 3, 4 and 5 go to exactly zero for both dice, because no roll showed them. Every later step keeps them at zero, because a zero emission gives zero posterior to any story that would have produced them. With the pseudocount, each face keeps a small floor and the estimates stay usable, if still shaped by three rolls.
Put the two halves together and you have Baum-Welch, which is the expectation-maximisation algorithm, or EM, applied to an HMM.
Baum proved in 1970 that the likelihood never goes down between iterations. Each pass finds a model under which the rolls are at least as probable as before. That is a guarantee of progress, not of arrival: the loop climbs to a local peak, and which peak depends on the start.
Here is why it climbs, in words. The M step maximises the expected log probability of the full story, where the expectation is taken with the old model's posteriors. That expected value is a lower bound on the true log likelihood, and the two touch at the old model. Raising the bound therefore raises the likelihood, or at least does not lower it. Each M step is easy because the bound is a sum of separate counting problems: one for π, one for each row of A, one for each row of B.
Starting points matter in practice. Three habits help. Give the two states different emission rows at the start, or they stay identical forever, since nothing breaks the symmetry. Start the transitions sticky, near 0.9 on the diagonal, because most real regimes persist. Run several random starts and keep the best log likelihood, which is what the devices on this page do.
Left: the current estimate of A (two stay probabilities) and B (the chance of a six from each die) as bars, with the true values as dashed lines. Right: log likelihood per roll against the iteration. Start from a random model, then step or run.
Computed in this page with scaled forward-backward and a pseudocount of 0.5 per face and per transition. The states are relabelled so that the die with the higher chance of a six is called loaded.
Three things to notice as you run it. First, the log likelihood climbs fast and then flattens. Most of the gain comes in the first ten steps. Second, with 300 rolls the estimates land near the truth but not on it; with 3,000 they land closer. Rare events, like the 0.05 switch, need many rolls to pin down. Third, press New random start a few times. Some starts climb to a worse peak, or reach the right one slowly.
Three practical details complete the recipe. When to stop: stop when the log likelihood per roll improves by less than about 10−4 between steps, or after a fixed cap such as 100 steps. Many sequences: if you have 50 recordings instead of one long one, run the E step on each, add the soft counts across all of them, and do one M step on the totals; π then gets a real estimate, since each sequence has a first state. A cheaper cousin: Viterbi training replaces the soft counts with hard counts along the Viterbi path. It is faster and often good enough for initialisation, but it is not EM: it can lower the likelihood, and it is more prone to collapsing a state.
There is also label switching. Nothing in the rolls says which state is "fair". A model with the two states swapped has exactly the same likelihood. The device relabels by the chance of a six, so the bars are comparable. Your code must do the same, or compare models by likelihood only.
def baum_welch_step(x, pi, A, B, pseudo=0.5): alpha, beta = forward(x), backward(x) # use the scaled versions in practice px = alpha[-1].sum() gamma = alpha * beta / px # (T, N) xi = (alpha[:-1, :, None] * A[None] # (T-1, N, N): alpha_t(i) A_ij ... * (B[:, np.array(x[1:])-1].T * beta[1:])[:, None, :]) / px # ... B_j(x_t+1) beta_t+1(j) pi_new = gamma[0] A_new = (xi.sum(0) + pseudo); A_new /= A_new.sum(1, keepdims=True) B_new = np.full_like(B, pseudo) for t, k in enumerate(x): B_new[:, k-1] += gamma[t] # soft count of face k in each state B_new /= B_new.sum(1, keepdims=True) return pi_new, A_new, B_new, np.log(px) for it in range(40): pi, A, B, ll = baum_welch_step(x, pi, A, B) print(it, ll / len(x)) # climbs, then flattens near -1.8
Chapter 8
Deal a long run, learn the dealer from the rolls, decode with the learned model, and then break it on purpose
Everything is now on one bench. The dealer below is yours to set: how often the hand switches, and how loaded the loaded die is. Deal a few hundred rolls. Decode them three ways with the true model, as in the hero. Then press Train, and the page runs Baum-Welch from random starts on those same rolls, with no knowledge of the truth. Switch the decoders over to the learned model and see what you lost.
Top: the rolls (sixes in yellow), the truth band, the chosen decoder's calls with wrong calls in red, and the probability of the loaded die when a decoder has one. Bottom: the accuracy of all three decoders under the model in use. Set the dealer, deal, train, and compare.
Computed in this page. Training runs Baum-Welch for 60 steps from each of 4 random starts, keeps the start with the highest log likelihood, and relabels the state with more sixes as loaded. Nothing about the truth enters training except the rolls themselves.
Each of these breaks one assumption. Watch what each decoder does, and then ask which chapter explains it.
What to expect, from many runs of this exact lab. Your numbers will differ by a few points from deal to deal.
| Dealer | Count the sixes | Viterbi | Forward-backward |
|---|---|---|---|
| switch 0.05 / 0.10, six 0.5 (Durbin) | 80% | 79% | 82% |
| switch 0.03, six 0.5 (sticky) | 83% | 85% | 88% |
| switch 0.20, six 0.5 (jumpy) | 65% | 67% | 70% |
| switch 0.05 / 0.10, six 0.3 (barely loaded) | 67% | 67% | 71% |
Read the table across. Forward-backward leads in every row, by three to five points. Viterbi and the counter trade places, because both make hard calls and the counter's centred window is a smoother of sorts. Read it down. Every decoder loses ten to fifteen points when the dealer gets jumpy or the die gets honest, and no decoder can win those points back. The data sets the ceiling; the model decides how close you get.
The lab as a script. This is the shape of every HMM project: deal or collect, train, decode, score, and keep the truth out of training.
rng = np.random.default_rng(0) z_true, x = sample_hmm(400, rng) # z_true is for scoring only best = None for restart in range(4): # several random starts pi_, A_, B_ = random_model(rng) for it in range(60): pi_, A_, B_, ll = em_step(x - 1, pi_, A_, B_) if best is None or ll > best[0]: best = (ll, pi_, A_, B_) ll, pi_, A_, B_ = best if B_[0, 5] > B_[1, 5]: # relabel: more sixes = loaded pi_, A_, B_ = pi_[::-1], A_[::-1, ::-1], B_[::-1] gamma, _, _ = forward_backward(x - 1, pi_, A_, B_) z_post = (gamma[:, 1] > 0.5).astype(int) z_vit, _ = viterbi(x - 1, pi_, A_, B_) for name, z_hat in [("count", count_sixes(x)), ("viterbi", z_vit), ("posterior", z_post)]: print(name, (z_hat == z_true).mean()) # the only place z_true appears
One more experiment runs in your head. The hero and the lab both score decoders by rolls called correctly. If instead you were paid per correct story, all-or-nothing, Viterbi would be the right choice, and you would see it win on short deals. The score you choose decides the decoder.
Chapter 9
Collect the equations on one page, place the HMM next to its relatives, and be honest about what it cannot do
A hidden Markov model is a chain you cannot see plus a window onto each state. Three tables define it. Four algorithms serve it: forward for scoring and live odds, backward for hindsight, Viterbi for the best story, and Baum-Welch for learning. Each of the first three costs N2 T, and the fourth runs the first two in a loop. Everything else is bookkeeping: logs or scaling against underflow, pseudocounts against zeros, restarts against local peaks.
Rolls 6, 6, 2 under the Durbin casino with a start of one half each. Every number below was computed by hand in this lesson, and your code should reproduce each one.
| Quantity | t = 1 (six) | t = 2 (six) | t = 3 (two) |
|---|---|---|---|
| αt(F), αt(L) | 0.08333, 0.25 | 0.01736, 0.11458 | 0.004659, 0.010399 |
| live P(L | rolls so far) | 0.750 | 0.868 | 0.691 |
| βt(F), βt(L) | 0.02853, 0.05072 | 0.16333, 0.10667 | 1, 1 |
| γt(L), hindsight | 0.842 | 0.812 | 0.691 |
| δt(F), δt(L) | 0.08333, 0.25 | 0.01319, 0.1125 | 0.002089, 0.010125 |
| scale ct | 0.33333 | 0.39583 | 0.11413 |
P(6 6 2) = 0.015058 best path LLL with 0.010125 one EM step: AFF 0.941, ALL 0.896
Here is a complete, numerically safe HMM in one block: scaled forward-backward for posteriors and log likelihood, Viterbi in log space, and one EM step. It is the Python version of what every device on this page runs.
import numpy as np def forward_backward(x, pi, A, B): """Scaled. Returns gamma (T,N), xi (T-1,N,N), log P(x). x holds 0-based symbols.""" T, N = len(x), len(pi) a = np.zeros((T, N)); c = np.zeros(T) a[0] = pi * B[:, x[0]]; c[0] = a[0].sum(); a[0] /= c[0] for t in range(1, T): a[t] = (a[t-1] @ A) * B[:, x[t]]; c[t] = a[t].sum(); a[t] /= c[t] b = np.ones((T, N)) for t in range(T-2, -1, -1): b[t] = (A @ (B[:, x[t+1]] * b[t+1])) / c[t+1] gamma = a * b # rows already sum to 1 xi = a[:-1, :, None] * A[None] * (B[:, x[1:]].T * b[1:] / c[1:, None])[:, None, :] return gamma, xi, np.log(c).sum() def viterbi(x, pi, A, B): lA, lB = np.log(A), np.log(B) T, N = len(x), len(pi) d = np.zeros((T, N)); back = np.zeros((T, N), dtype=int) d[0] = np.log(pi) + lB[:, x[0]] for t in range(1, T): s = d[t-1][:, None] + lA # (N,N): from i (rows) to j (cols) back[t] = s.argmax(0); d[t] = s.max(0) + lB[:, x[t]] z = np.zeros(T, dtype=int); z[-1] = d[-1].argmax() for t in range(T-1, 0, -1): z[t-1] = back[t, z[t]] return z, d[-1].max() def em_step(x, pi, A, B, pseudo=0.5): gamma, xi, ll = forward_backward(x, pi, A, B) A2 = xi.sum(0) + pseudo; A2 /= A2.sum(1, keepdims=True) B2 = np.full_like(B, pseudo); np.add.at(B2.T, x, gamma); B2 /= B2.sum(1, keepdims=True) return gamma[0], A2, B2, ll
Every HMM algorithm is an instance of inference on a chain, and the chain shows up with different costumes across the field.
| Model | Hidden state | What you see | Inference | Where it shines |
|---|---|---|---|---|
| HMM | one of N labels | a symbol or a vector per step | exact: forward-backward, Viterbi | segmentation, alignment, discrete regimes |
| Kalman filter | a real vector with a Gaussian belief | a linear function of it plus noise | exact: predict and update in closed form | tracking, navigation, smooth motion |
| Particle filter | anything | anything with a likelihood | approximate: weighted samples | nonlinear, multimodal beliefs, robot localisation |
| Linear-chain CRF | one of N labels | rich features of the whole input | the same forward-backward and Viterbi | labelling when you only need P(z | x) |
| RNN / Transformer | a learned vector | tokens | none needed: the state is computed, not inferred | long context, rich dependencies, lots of data |
The Bayes filter is the parent of the first three rows. The HMM is the Bayes filter with a finite state, the Kalman filter is the Bayes filter with a Gaussian state, and the particle filter is the Bayes filter with samples. If you learned one, you have the skeleton of the others.
Speech recognition ran on HMMs for thirty years. Each phoneme was a few states, the emissions were Gaussian mixtures over audio features, and Viterbi over a huge composed chain returned the words. The DNN-HMM hybrid replaced the Gaussians with a neural network but kept the chain and the Viterbi. In biology, the same machinery finds genes and CpG islands in DNA, and profile HMMs align protein families. The continuous-time HMM lets the chain switch at irregular times, which clinical records need.
Nothing above needed the observations to be faces of a die. The emission table Bi(k) only ever appeared as "how likely was this observation under state i". Replace the table with a density and every algorithm runs unchanged. Give each state a Gaussian with its own mean and spread, and Bi(xt) becomes the Gaussian density of the reading xt under state i.
That is how an HMM reads a sensor. A phone's step counter sees acceleration; walking and standing are the states. A heart monitor sees voltage; the parts of a heartbeat are the states. Early speech recognisers saw 39 numbers of audio features per 10 ms frame; each phoneme was three states in a row, and each state's emission was a mixture of Gaussians. The device below is the smallest version: one noisy reading per step, two states with different means.
The dots are readings: mean 0 in the low regime, mean 1 in the high regime, with the noise you set. The truth band is below. The purple curve is the HMM's posterior for the high regime; the grey ticks show the threshold rule, which calls high whenever a reading is above one half. Raise the noise.
Computed in this page. The regime stays with probability 0.97 per step; the HMM is given the true means, spread and stickiness. Emissions are Gaussian densities in place of the table B.
Now the gap is not four points. At a spread of 1.0 the threshold rule is near a coin flip, because a single reading barely separates the two means, while the HMM pools dozens of readings through the chain and still finds the regimes. The dice were a hard case for the HMM to shine in, because a six already says a lot on its own. A sensor is the normal case: each reading says little, and the chain does the work.
Learning works the same way too. The M step for a Gaussian emission is a weighted mean and a weighted variance, with γt(i) as the weights. The soft counts of Chapter 7 become soft averages. That is the whole change from a discrete HMM to a continuous one.
The casino's chain can go anywhere from anywhere. Real models often forbid some moves by setting entries of A to zero, and a zero stays zero through every M step. The shape you choose is a statement about the world.
the casino
Every state reaches every other. Regimes that come and go in any order: dice, market moods, activity types.
speech, gestures
States in a fixed order, each with a self-loop. A phoneme as begin, middle, end. Time can stall but never run backwards.
protein families
Match, insert and delete states for each position of a template. Aligns a new sequence to a family while allowing gaps.
A left-to-right model with three states per phoneme and forty phonemes is a chain of 120 states, and a word is a path through it. Viterbi over that chain, with a language model deciding the word-to-word transitions, was the recognised sentence for three decades. The arithmetic was exactly Chapter 5's, at scale.
The casino told us N = 2. A real problem does not. Two tools help. First, held-out log likelihood: fit with N = 2, 3, 4 on one part of the data and score another part; the gain flattens near the right N. Second, meaning: look at the learned emission rows and the decoded runs, and ask whether each state names something real. A state that only mops up outliers, or two states with nearly identical rows, is a sign to go back down.
Be honest about the limits, because they decide when to reach for something else.
| Name | Formula | Reads as |
|---|---|---|
| Joint | P(z, x) = πz1 Bz1(x1) ∏t Azt−1 zt Bzt(xt) | one story: start, show, move, show, move, show |
| Forward | αt+1(j) = Bj(xt+1) ∑i αt(i) Aij | move the mass, then charge the roll |
| Backward | βt(i) = ∑j Aij Bj(xt+1) βt+1(j) | the future from here, given this state |
| Posterior | γt(i) = αt(i) βt(i) / P(x) | past times future, normalised |
| Viterbi | δt+1(j) = Bj(xt+1) maxi δt(i) Aij | forward with max, plus pointers |
| Pair posterior | ξt(i, j) = αt(i) Aij Bj(xt+1) βt+1(j) / P(x) | soft count of one transition |
| M step | Aij ← ∑ξt(i, j) / ∑γt(i); Bi(k) ← ∑xt=k γt(i) / ∑γt(i) | count as if the fractions were events |
| Scaling | log P(x) = ∑t log ct | add the log surprise of each roll |
Open Teach and explain the trellis on the whiteboard, forward values first, then the max version. Flip through the Sparks deck when you need the one-card version of each idea. Then go back to the casino, set the dealer to switch on 1 roll in 4, and see how little any decoder can do when the dealer leaves no trace.