Hidden Markov Models
Chapter Seventy-Two
Syllabus topic Module 2, "Hidden Markov Models"
Pages 430 to 438 of 591
In one line
A hidden Markov model is a chain of hidden states, each depending only on the one before it, with one visible observation emitted from each state.
Everything so far in this module has treated the training rows as independent. The Statistical Learning Framework said so explicitly. A hidden Markov model is the first model in the syllabus for data that arrives in order, where each row depends on the one before it.
The example used throughout
The hidden state is whether a student revised that evening. The observation is whether they answered the next morning's one-question quiz correctly. The state is never recorded; the quiz mark always is.
Two properties make it a good example and they are both realistic. Study habits are sticky, so tomorrow resembles today, which is what the transition matrix will say. And a quiz is noisy evidence: a student who revised can still get it wrong, and a student who did not can still guess right.
The three parts
A paper asking "define a hidden Markov model" wants these three and the two assumptions below.
| Written | ||
|---|---|---|
| 1 | The initial distribution | the probability of each state on the first step |
| 2 | The transition matrix | P(next state given current state) |
| 3 | The emission matrix | P(observation given state) |
And the count of numbers, which is the argument for the model:
N states, M observations: (N - 1) + N(N - 1) + N(M - 1)
Note what is not there: any number that depends on the length of the sequence, and any number indexed by a history. A model that let each day depend on all previous days would need a table indexed by every possible past, which is why the assumptions below are not a simplification of convenience but the thing that makes the model finite.
The two assumptions
Both must be stated, and the second is the one students forget.
1. The Markov assumption. The next state depends only on the current state, not on any earlier one. This is what "Markov" means, and it is what the word first-order refers to.
2. Output independence. The observation on a step depends only on that step's state, not on earlier states or earlier observations.
The model, sampled and checked
# A hidden Markov model, built and checked: the three parts, the Markov property
# verified by counting, and the cost of answering the evaluation question by
# brute force. The hidden state is whether a student revised that evening; the
# observation is whether the next morning's one-question quiz was answered.
from itertools import product
import math
def lcg(seed):
x = seed
while True:
x = (1664525 * x + 1013904223) % (2 ** 32)
yield x / 2 ** 32
gen = lcg(555035)
rnd = lambda: next(gen) # noqa: E731
STATES = ["revised", "did not"]
OBS = ["correct", "wrong"]
# 1. the initial distribution
INIT = [0.5, 0.5]
# 2. the transition matrix: habits are STICKY, so 0.9 to stay
TRANS = [[0.9, 0.1],
[0.1, 0.9]]
# 3. the emission matrix: P(observation | state)
EMIT = [[0.9, 0.1], # revised -> correct 0.9
[0.2, 0.8]] # did not -> correct 0.2
print("THE THREE PARTS OF A HIDDEN MARKOV MODEL")
print(" states (HIDDEN) : %s" % ", ".join(STATES))
print(" observations (SEEN) : %s" % ", ".join(OBS))
print()
print(" 1. the initial distribution over states")
for i, s in enumerate(STATES):
print(" P(day 1 = %-8s) = %.2f" % (s, INIT[i]))
print(" 2. the transition matrix, P(tomorrow | today)")
print(" today \\ tomorrow revised did not")
for i, s in enumerate(STATES):
print(" %-18s %s" % (s, " ".join("%9.2f" % v for v in TRANS[i])))
print(" 3. the emission matrix, P(observation | state)")
print(" state \\ observed correct wrong")
for i, s in enumerate(STATES):
print(" %-18s %s" % (s, " ".join("%9.2f" % v for v in EMIT[i])))
print()
print(" the numbers needed: %d for the initial state, %d for the transitions,"
% (len(STATES) - 1, len(STATES) * (len(STATES) - 1)))
print(" %d for the emissions. a model over %d states and %d observations needs"
% (len(STATES) * (len(OBS) - 1), len(STATES), len(OBS)))
print(" N-1 + N(N-1) + N(M-1) numbers, and NOT one per possible history.")
print()
print("THE TWO ASSUMPTIONS, which are what the word 'Markov' is doing here.")
print(" 1. the MARKOV assumption: tomorrow's state depends only on today's,")
print(" not on any earlier day.")
print(" 2. the OUTPUT INDEPENDENCE assumption: what is observed on a day")
print(" depends only on that day's state.")
print()
def step(state):
return 0 if rnd() < TRANS[state][0] else 1
def emit(state):
return 0 if rnd() < EMIT[state][0] else 1
print("A SAMPLED FORTNIGHT. the first row is the truth and is NOT available to")
print("any algorithm; the second row is the whole of the data.")
s = 0 if rnd() < INIT[0] else 1
states, obs = [], []
for day in range(14):
if day:
s = step(s)
states.append(s)
obs.append(emit(s))
print(" day : %s" % " ".join("%2d" % (d + 1) for d in range(14)))
print(" state : %s" % " ".join(" %s" % ("R" if v == 0 else "N") for v in states))
print(" observed : %s" % " ".join(" %s" % ("C" if v == 0 else "W") for v in obs))
print(" R = revised, N = did not, C = correct, W = wrong")
print()
print("THE MARKOV ASSUMPTION, CHECKED BY COUNTING. draw 400000 days and ask")
print("whether YESTERDAY adds anything once TODAY is known.")
long_states = []
s = 0 if rnd() < INIT[0] else 1
for _ in range(400000):
long_states.append(s)
s = step(s)
def frac(cond):
hits = [long_states[i + 1] for i in range(1, len(long_states) - 1) if cond(i)]
return (sum(1 for v in hits if v == 0) / len(hits), len(hits))
p, n = frac(lambda i: long_states[i] == 0)
print(" P(tomorrow revised | today revised) = %.4f (%d cases)" % (p, n))
p, n = frac(lambda i: long_states[i] == 0 and long_states[i - 1] == 0)
print(" P(tomorrow revised | today revised, yesterday revised) = %.4f (%d cases)" % (p, n))
p, n = frac(lambda i: long_states[i] == 0 and long_states[i - 1] == 1)
print(" P(tomorrow revised | today revised, yesterday did not) = %.4f (%d cases)" % (p, n))
print(" all three are the model's 0.90. knowing yesterday changes NOTHING once")
print(" today is known, which is the assumption stated as a measurement.")
print()
print("THE STATIONARY DISTRIBUTION, by repeated multiplication.")
d = [1.0, 0.0]
MILESTONES = (1, 2, 5, 10, 50, 200)
for day in range(1, max(MILESTONES) + 1):
d = [sum(d[i] * TRANS[i][j] for i in range(2)) for j in range(2)]
if day in MILESTONES:
print(" after %3d day%s from a certain start: %.6f revised, %.6f did not"
% (day, " " if day == 1 else "s", d[0], d[1]))
print(" it settles at 0.5 / 0.5, which for this matrix is the long-run share")
print(" of revising days whatever the first day was.")
print()
print("THE THREE QUESTIONS AN HMM IS ASKED")
print(" 1. EVALUATION: how probable is this observation sequence? (forward)")
print(" 2. DECODING: which state sequence most likely produced it? (Viterbi)")
print(" 3. LEARNING: what are the three matrices, given only observations?")
print(" (Baum-Welch, which is EM with forward-backward inside)")
print()
SEQ = [0, 0, 0, 1] # correct, correct, correct, wrong
print("EVALUATION BY BRUTE FORCE, on %s:" % ", ".join(OBS[o] for o in SEQ))
print(" every possible state path is enumerated and its probability added.")
def path_prob(path, seq):
p = INIT[path[0]] * EMIT[path[0]][seq[0]]
for t in range(1, len(seq)):
p *= TRANS[path[t - 1]][path[t]] * EMIT[path[t]][seq[t]]
return p
total, best = 0.0, None
print(" path | probability")
for path in product((0, 1), repeat=len(SEQ)):
p = path_prob(path, SEQ)
total += p
if best is None or p > best[0]:
best = (p, path)
print(" %-5s | %.8f" % ("".join("R" if v == 0 else "N" for v in path), p))
print(" %-5s | %.8f <- the total, P(observations)" % ("SUM", total))
print()
print(" the most likely single path is %s at %.8f, which is only %.1f per cent"
% ("".join("R" if v == 0 else "N" for v in best[1]), best[0],
100 * best[0] / total))
print(" of the total. THE MOST LIKELY PATH IS NOT THE ANSWER TO 'how probable")
print(" is this sequence'. the two questions have different answers and need")
print(" different algorithms.")
print()
print("AND THE COST. enumerating paths is N**T for N states and T days:")
for t in (4, 10, 20, 40, 100):
print(" T = %3d : %d paths" % (t, 2 ** t))
print(" at %d days a modern machine would not finish. the next chapter does" % 100)
print(" the same sum in T * N**2 arithmetic operations, which at T = 100 is")
print(" %d, by never enumerating a path at all." % (100 * 4))Hidden Markov Models
THE THREE PARTS OF A HIDDEN MARKOV MODEL
states (HIDDEN) : revised, did not
observations (SEEN) : correct, wrong
1. the initial distribution over states
P(day 1 = revised ) = 0.50
P(day 1 = did not ) = 0.50
2. the transition matrix, P(tomorrow | today)
today \ tomorrow revised did not
revised 0.90 0.10
did not 0.10 0.90
3. the emission matrix, P(observation | state)
state \ observed correct wrong
revised 0.90 0.10
did not 0.20 0.80
the numbers needed: 1 for the initial state, 2 for the transitions,
2 for the emissions. a model over 2 states and 2 observations needs
N-1 + N(N-1) + N(M-1) numbers, and NOT one per possible history.
THE TWO ASSUMPTIONS, which are what the word 'Markov' is doing here.
1. the MARKOV assumption: tomorrow's state depends only on today's,
not on any earlier day.
2. the OUTPUT INDEPENDENCE assumption: what is observed on a day
depends only on that day's state.
A SAMPLED FORTNIGHT. the first row is the truth and is NOT available to
any algorithm; the second row is the whole of the data.
day : 1 2 3 4 5 6 7 8 9 10 11 12 13 14
state : R R R N N N N N N R N R R R
observed : C C C W W W W W C W W C C C
R = revised, N = did not, C = correct, W = wrong
THE MARKOV ASSUMPTION, CHECKED BY COUNTING. draw 400000 days and ask
whether YESTERDAY adds anything once TODAY is known.
P(tomorrow revised | today revised) = 0.8999 (200461 cases)
P(tomorrow revised | today revised, yesterday revised) = 0.8997 (180389 cases)
P(tomorrow revised | today revised, yesterday did not) = 0.9018 (20072 cases)
all three are the model's 0.90. knowing yesterday changes NOTHING once
today is known, which is the assumption stated as a measurement.
THE STATIONARY DISTRIBUTION, by repeated multiplication.
after 1 day from a certain start: 0.900000 revised, 0.100000 did not
after 2 days from a certain start: 0.820000 revised, 0.180000 did not
after 5 days from a certain start: 0.663840 revised, 0.336160 did not
after 10 days from a certain start: 0.553687 revised, 0.446313 did not
after 50 days from a certain start: 0.500007 revised, 0.499993 did not
after 200 days from a certain start: 0.500000 revised, 0.500000 did not
it settles at 0.5 / 0.5, which for this matrix is the long-run share
of revising days whatever the first day was.
THE THREE QUESTIONS AN HMM IS ASKED
1. EVALUATION: how probable is this observation sequence? (forward)
2. DECODING: which state sequence most likely produced it? (Viterbi)
3. LEARNING: what are the three matrices, given only observations?
(Baum-Welch, which is EM with forward-backward inside)
EVALUATION BY BRUTE FORCE, on correct, correct, correct, wrong:
every possible state path is enumerated and its probability added.
path | probability
RRRR | 0.02657205
RRRN | 0.02361960
RRNR | 0.00007290
RRNN | 0.00524880
RNRR | 0.00007290
RNRN | 0.00006480
RNNR | 0.00001620
RNNN | 0.00116640
NRRR | 0.00065610
NRRN | 0.00058320
NRNR | 0.00000180
NRNN | 0.00012960
NNRR | 0.00014580
NNRN | 0.00012960
NNNR | 0.00003240
NNNN | 0.00233280
SUM | 0.06084495 <- the total, P(observations)
the most likely single path is RRRR at 0.02657205, which is only 43.7 per cent
of the total. THE MOST LIKELY PATH IS NOT THE ANSWER TO 'how probable
is this sequence'. the two questions have different answers and need
different algorithms.
AND THE COST. enumerating paths is N**T for N states and T days:
T = 4 : 16 paths
T = 10 : 1024 paths
T = 20 : 1048576 paths
T = 40 : 1099511627776 paths
T = 100 : 1267650600228229401496703205376 paths
at 100 days a modern machine would not finish. the next chapter does
the same sum in T * N**2 arithmetic operations, which at T = 100 is
400, by never enumerating a path at all.Hidden Markov Models
The sampled fortnight
Read the two rows against each other.
Hidden Markov Models
state : R R R N N N N N N R N R R R
observed : C C C W W W W W C W W C C C
Hidden Markov Models
Days 9 and 10 are the whole difficulty of the subject in two columns. On day 9 the student did not revise and answered correctly, which the emission matrix allows one time in five. On day 10 the student did revise and answered wrongly, which it allows one time in ten. The observation is evidence, not the state. Any algorithm reading only the second row will be wrong about those two days, and no better algorithm exists, because the information is not in the data.
Hidden Markov Models
Note also the runs. The states come in blocks, because a sticky transition matrix produces blocks, and that is exactly the structure an algorithm can exploit: a single odd observation surrounded by a run is more likely to be emission noise than a one-day change of habit.
The Markov assumption, counted
The assumption is usually stated and then believed. Here it is measured, over 400,000 days:
| Estimate | Cases | |
|---|---|---|
| next revised, given today revised | 0.8999 | 200,461 |
| next revised, given today revised and yesterday revised | 0.8997 | 180,389 |
| next revised, given today revised and yesterday did not | 0.9018 | 20,072 |
All three are the model's 0.90. Conditioning on yesterday changes nothing once today is known, which is the Markov property as an arithmetic fact rather than an assertion. It holds here because the data was generated by such a model; on real data it is an assumption about the world and can be checked in exactly this way, by seeing whether the extra conditioning moves the number.
The stationary distribution
Start certain that day one was a revising day, and push the distribution forward:
| After | Revised | Did not |
|---|---|---|
| 1 day | 0.900000 | 0.100000 |
| 2 days | 0.820000 | 0.180000 |
| 5 days | 0.663840 | 0.336160 |
| 10 days | 0.553687 | 0.446313 |
| 50 days | 0.500007 | 0.499993 |
| 200 days | 0.500000 | 0.500000 |
The certainty decays, and after fifty days the first day is forgotten. The limit is the stationary distribution: the long-run share of revising days, whatever the chain started from. How fast it decays is set by the transition matrix. This one is sticky, so the memory of day one survives about ten days; a matrix nearer 0.5 forgets it in two.
The three questions
Every use of an HMM is one of these three, and naming them with their algorithms is the cleanest answer to "what can an HMM do".
| Question | Algorithm | Chapter | |
|---|---|---|---|
| Evaluation | how probable is this observation sequence | forward | The Forward Algorithm and Viterbi |
| Decoding | which state sequence most likely produced it | Viterbi | The Forward Algorithm and Viterbi |
| Learning | what are the three matrices, from observations alone | Baum-Welch | The EM Algorithm |
Baum-Welch is EM. The hidden variable is the state at each step, the E step computes the posterior over states by forward and backward passes, and the M step re-estimates the three matrices with fractional counts. So everything The EM Algorithm said applies unchanged: the likelihood never falls, the answer depends on the start, and several restarts are kept.
Evaluation by brute force, and the number that matters
On the four-day sequence correct, correct, correct, wrong, all sixteen paths are enumerated and their probabilities added, giving P(observations) = 0.06084495.
Now the number to remember. The most likely single path is RRRR at 0.02657205, which is 43.7 per cent of the total.
Hidden Markov Models
So "how probable is this sequence" and "which path was it" are different questions with different answers. The probability of the sequence is a sum over paths; the best path is one term of that sum, here holding well under half of it. A student who reports the best path's probability as the sequence's probability is out by a factor of more than two on a four-day sequence, and by far more on a long one.
The cost, and why the next chapter exists
| Days | Paths |
|---|---|
| 4 | 16 |
| 10 | 1024 |
| 20 | 1,048,576 |
| 40 | 1,099,511,627,776 |
| 100 | 1,267,650,600,228,229,401,496,703,205,376 |
Enumeration costs NT. It is exact and it is unusable: at a hundred days no machine will finish. The Forward Algorithm and Viterbi computes the same sum in T * N2 operations, which at a hundred days is 400, by never enumerating a path at all.
Where HMMs are used
Worth naming, because a paper may ask for applications.
| Field | Hidden state | Observation |
|---|---|---|
| Speech recognition | the phoneme being spoken | a slice of the sound signal |
| Part-of-speech tagging | the word's grammatical class | the word |
| Gene finding | coding or non-coding region | the base at that position |
| Handwriting recognition | the letter being written | a stroke segment |
Speech was the application that made the model famous, and Rabiner's 1989 tutorial is the standard reference. Modern speech systems use neural networks, and an honest answer says so: the HMM is the classical treatment and the reason the problem was tractable at all for two decades.
Its place among the models of this book
An HMM is a Bayesian network unrolled in time: one node per state, one per observation, the same two matrices repeated at every step. That is why it needs no new theory: Inference in a Bayesian Network already covers what its questions are, and the next chapter's algorithms are that inference specialised to a chain, where the structure makes it cheap.
Distinctions
| A Markov chain | A hidden Markov model | |
|---|---|---|
| The state is | observed | hidden |
| Parts | initial, transition | initial, transition, emission |
| Question | what will the state be | what was the state |
| The Markov assumption | Output independence | |
|---|---|---|
| Restricts | the state sequence | the observations |
| Says | the next state depends only on the current one | an observation depends only on its own state |
| Evaluation | Decoding | |
|---|---|---|
| Asks | how probable is the sequence | which path produced it |
| Combines paths by | summing | maximising |
| Answer here | 0.06084495 | RRRR, at 0.02657205 |
| Algorithm | forward | Viterbi |
What it does not mean
The observation is not the state. Day 9 was a non-revising day answered correctly; day 10 a revising day answered wrongly.
Hidden Markov Models
The Markov assumption is not about the observations. That is output independence, a separate assumption.
The number of parameters does not grow with the length of the sequence. That is the point of the assumptions.
The stationary distribution is not the initial distribution. It is the limit the chain forgets its way into, here after about fifty days.
The best path's probability is not the sequence's probability. It is 43.7 per cent of it here.
Brute force is not merely slow. At 100 days it is 2**100 paths, which is not slow but impossible.
An HMM is not a new kind of model. It is a Bayesian network repeated in time.
Quick revision
- Three parts: the initial distribution, the transition matrix
P(next given current), the emission matrixP(observation given state). Numbers needed:(N-1) + N(N-1) + N(M-1), independent of sequence length. - Two assumptions: the Markov assumption, on the states, and output independence, on the observations.
- Measured over 400,000 days:
0.8999,0.8997,0.9018. Yesterday adds nothing once today is known. - The sampled fortnight contains a non-revising day answered correctly and a revising day answered wrongly: the observation is evidence, not the state.
- The stationary distribution is reached by repeated multiplication:
0.900000,0.820000,0.663840,0.553687,0.500007,0.500000. The start is forgotten. - Three questions: evaluation (forward), decoding (Viterbi), learning (Baum-Welch, which is EM with forward and backward passes as its E step).
P(observations) = 0.06084495by brute force; the best pathRRRRis0.02657205, only 43.7 per cent of it. Summing and maximising are different questions.- Cost of enumeration is
NT: 16 paths at 4 days, over1030at 100. The forward algorithm does the same sum inT * N2, which is 400** at 100 days. - Applications: speech recognition (Rabiner, 1989), part-of-speech tagging, gene finding, handwriting. An HMM is a Bayesian network unrolled in time.
Test yourself
1. Define a hidden Markov model and state how many numbers it needs. A chain of hidden states with one observation emitted at each step, specified by an initial distribution over states, a transition matrix giving the probability of the next state given the current one, and an emission matrix giving the probability of each observation given the state. With N states and M observations it needs (N-1) + N(N-1) + N(M-1) numbers, whatever the length of the sequence.
2. State the two independence assumptions and say what each restricts. The Markov assumption restricts the states: the next state depends only on the current state and not on any earlier one. Output independence restricts the observations: what is observed at a step depends only on that step's state, not on earlier states or observations.
Hidden Markov Models
3. How would you check the Markov assumption on real data? Estimate the probability of the next state conditioned on the current state alone, then estimate it again conditioned on the current state and the one before, and compare. If the extra conditioning moves the number, the assumption fails. On the measurement in this chapter the three estimates were 0.8999, 0.8997 and 0.9018, all the model's 0.90.
4. Distinguish a Markov chain from a hidden Markov model. In a Markov chain the state itself is observed, and the model is the initial distribution and the transition matrix. In a hidden Markov model the state is never observed and a third component, the emission matrix, relates each state to what is seen.
5. Name the three questions asked of an HMM with the algorithm for each. Evaluation, how probable a given observation sequence is, answered by the forward algorithm. Decoding, which state sequence most likely produced it, answered by Viterbi. Learning, what the three matrices are given observations alone, answered by Baum-Welch, which is EM with forward and backward passes as its E step.
6. Why is the probability of the most likely path not the probability of the observation sequence? The probability of the sequence is the sum of the probabilities of every path that could have produced it; the best path contributes one term of that sum. On the four-day sequence here the sum is 0.06084495 and the best path is 0.02657205, which is 43.7 per cent of it, so reporting the one for the other is wrong by more than a factor of two.
7. Why can the evaluation question not be answered by enumeration in practice? Enumeration costs NT paths for N states and T steps: 16 at four days, about a million at twenty, and over a thousand million million million million million at a hundred. The forward algorithm computes the identical sum in T * N2 operations, 400 at a hundred days, by combining paths as it goes instead of listing them.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.