Temporal Models and Hidden Markov Models
Prerequisite Knowledge
This lecture builds on the following concepts from earlier lectures. If any feel unfamiliar, review the linked notes before proceeding.
Previously Covered in This Subject
- Conditional independence and Bayesian-network querying — covered in Lecture 13 (Bayesian Networks: D-Separation, Variable Elimination, and Approximate Inferencing)
- Marginalization over hidden variables — covered in Lecture 13 (Bayesian Networks: Variable Elimination)
14.1 Temporal Data and the Markov Assumption
Hook: Imagine you are a weather forecaster. It rained yesterday, and it rained the day before. Should you predict rain today? What if it also rained five years ago on this exact date — does that matter? The answer is obvious: recent weather matters, ancient weather does not. But how do we formalize the idea of "recent" in a principled way? That question is what the Markov assumption answers, and it is the foundation of every temporal model in AI.
Life itself is temporal — what you do today impacts tomorrow, and today you look behind at what happened yesterday. This temporal dependency is fundamental to how we reason about the world. In the modules leading up to this one, we learned about propositional logic, first-order logic, Bayesian networks, and various forms of inferencing (exact and approximate). All of those models treated the world as static snapshots. A Bayesian network captures dependencies between variables at a single point in time, but it does not account for how events unfold over days, hours, or minutes.
The moment time enters the picture, the modeling challenge changes. Consider a simple example: you track the weather every day. Day 1 is rainy, Day 2 is sunny, Day 3 is rainy, Day 4 is rainy, and so on up to Day 25. Now you want to predict whether Day 25 will be rainy. Does that prediction depend on what happened five years ago? The answer, intuitively, is no. What matters most is the recent past — did it rain yesterday, or the day before? That insight is the foundation of the Markov property.
Intuition + Analogy: Think of a board game like Snakes and Ladders. Where you land next depends only on your current square and the dice roll — it does not matter how you got to that square. If you are on square 47, the path you took (whether you climbed a snake on turn 3 or a ladder on turn 10) is irrelevant to your next move. The Markov property says the same thing about any system: if you know the present state fully, the past adds nothing. The analogy breaks down when the present state is incomplete — if your "square" in real life is just "I feel fine," that does not capture whether you were exposed to a virus three days ago. That is where higher-order Markov models (or richer state descriptions) come in.
A temporal model (a model that represents data changing over time, with each observation indexed by a time step) captures data that changes over time, where each observation is indexed by a time step. The key question becomes: how far back in time should we look to make a good prediction? Markov models provide a principled answer to that question.
Formalize: A temporal model is a sequence of random variables \(X_1, X_2, X_3, \ldots\) indexed by discrete time steps \(t = 1, 2, 3, \ldots\). Each \(X_t\) represents the state of the system at time \(t\). The Markov property constrains how much of the past we need to condition on:
\[ P(X_t \mid X_{t-1}, X_{t-2}, \ldots, X_1) = P(X_t \mid X_{t-1}) \]
This equation states that the probability of the current state \(X_t\) (at time \(t\)), given the entire history \(X_{t-1}, X_{t-2}, \ldots, X_1\), is exactly the same as the probability of \(X_t\) given only the immediately previous state \(X_{t-1}\). In other words, once you know \(X_{t-1}\), the variables \(X_{t-2}, X_{t-3}, \ldots, X_1\) carry no additional information about \(X_t\).
The notation \(t-1\) does not literally mean "one minute ago" — it means one prior event. Depending on the domain, that could be the last minute, the last hour, the last day, or the last semester exam. It is one past instance.
14.1.1 First-Order and Higher-Order Markov Models
If we consider only the single most recent past event — that is, if today is time \(t\) and we look only at time \(t-1\) — that is called a first-order Markov model. The defining assumption is:
\[ P(X_t \mid X_{t-1}, X_{t-2}, \ldots, X_1) = P(X_t \mid X_{t-1}) \]
In words: the probability of the current state depends only on the immediately previous state, not on the entire history.
Worked Example — First-Order Markov: Suppose you model a student's attendance as a first-order Markov process with two states: Present (P) and Absent (A). The assumption says:
\[ P(\text{Absent on Day 5} \mid \text{Present on Day 4}, \text{Absent on Day 3}, \text{Present on Day 2}, \text{Absent on Day 1}) = P(\text{Absent on Day 5} \mid \text{Present on Day 4}) \]
Only Day 4's attendance matters. Days 1–3 are irrelevant once Day 4 is known. This dramatically simplifies the model: instead of tracking the entire attendance history, we only need to know the most recent state.
If we also consider the state before that — \(t-1\) and \(t-2\) — that is called a second-order Markov model:
\[ P(X_t \mid X_{t-1}, X_{t-2}, \ldots, X_1) = P(X_t \mid X_{t-1}, X_{t-2}) \]
Worked Example — Second-Order Markov: Continuing the attendance example, a second-order model says:
\[ P(\text{Absent on Day 5} \mid \text{Present on Day 4}, \text{Absent on Day 3}) = P(\text{Absent on Day 5} \mid \text{Present on Day 4}, \text{Absent on Day 3}) \]
Now both Day 4 and Day 3 matter. Perhaps a student who was absent on Day 3 but present on Day 4 has a different pattern than one who was present on both days.
You can extend this to third-order, fourth-order, and so on. In general, an \(n\)-th order Markov model conditions on the \(n\) most recent states. The trade-off is clear: higher order means more information but also a more complex model with more parameters to estimate.
Scope: The first-order Markov assumption is a modeling choice, not a law of nature. It works well when the state variable is rich enough to capture all relevant history. For example, in a weather model with just "Rainy/Sunny," a first-order assumption is approximate — a long dry spell might behave differently from a single dry day. The fix is either to increase the order (second-order, third-order) or to enrich the state variables (add humidity, pressure, season). The textbook (Russell & Norvig, Chapter 14) notes that increasing the order can always be reformulated as increasing the set of state variables while keeping the order fixed — both approaches are equivalent in expressive power.
Assumption: The Markov property assumes the state space is complete — that is, the state variables contain all information needed to predict the future. If important factors are omitted from the state, the assumption is violated and predictions will be poor.
Pitfalls:
- Confusing "Markov" with "memoryless": The Markov property does not mean the system has no memory. It means the state variable you have chosen already encodes all the memory you need. If your state is too simple, you lose information.
- Using higher-order when first-order suffices: For exams, always use first-order Markov unless explicitly told otherwise. Second-order examples in the course are for understanding, not for exam problems.
- Ignoring the time-homogeneous assumption: The Markov model assumes the transition probabilities do not change over time (the process is time-homogeneous). If customer behavior shifts during a holiday season, the TPM from normal days may no longer apply.
14.1.2 Why the Markov Assumption Works
The Markov assumption does not claim that older history is irrelevant in general. It claims that given the immediate past, older history adds no additional predictive power. In many real-world domains — weather, purchasing behavior, word sequences in language — this turns out to be a remarkably good approximation. The immediate past carries the strongest signal about the present.
Student Q&A:
Q: If the Markov assumption is just an approximation, why do we use it? Why not model the full history?
A: Two reasons. First, the full history grows without bound — after 1000 days, you would need to condition on 999 past states, which is computationally infeasible. Second, in practice the immediate past really does carry most of the predictive power. The Markov assumption gives us a model that is both tractable and surprisingly accurate. If it is not accurate enough, the remedy is to enrich the state (add more variables) rather than to extend the history indefinitely.
Exam note: For this course, always use first-order Markov unless the problem explicitly says otherwise. The exam will test your ability to identify the Markov property, write the first-order assumption equation, and distinguish it from higher-order variants. Expect low-order thinking questions (Bloom's: remembering and understanding) on this topic in the quiz.
Recap + Bridge: The Markov property tells us that the current state depends only on the immediately previous state — it is the "Snakes and Ladders" principle of temporal modeling. This assumption keeps our models tractable. Next, we see how to represent a Markov model concretely using a Transition Probability Matrix (TPM) — the tool that lets us compute predictions rather than just state assumptions.
Real-World & Domain Connection: The Markov property appears everywhere in AI and computer science. In natural language processing, bigram language models (predicting the next word given only the previous word) are first-order Markov models. In speech recognition, phoneme transitions follow Markov dynamics. In finance, stock price models often assume a Markov structure — the future price depends on the current price, not the full price history. In genetics, DNA sequence models use Markov chains to identify coding regions. The Markov assumption is one of the most powerful simplifying assumptions in all of probabilistic modeling, and understanding it deeply gives you a foundation for dozens of AI applications.
14.2 Markov Models and the Transition Probability Matrix
Hook: A shop owner notices that customers who buy computers tend to come back for media accessories next time, while media buyers tend to stick with media. Can we capture this pattern in a single matrix and use it to predict future purchases? The answer is yes — and that matrix is the Transition Probability Matrix (TPM).
A Markov model is a directed graph where each node represents a state, and each edge carries a probability — the probability of transitioning from one state to another. The model can be drawn as a diagram or represented as a matrix. The two representations are interchangeable: given a diagram you can fill in the matrix, and given a matrix you can draw the diagram. Both are called a Transition Probability Matrix (TPM).
Intuition + Analogy: Think of the TPM as a "cheat sheet" for a board game. If you are on square "Computer," the cheat sheet tells you the chance of moving to square "Media" versus staying on "Computer" on your next turn. The cheat sheet does not care how you got to "Computer" — that is the Markov property at work. The TPM is the complete set of all such one-step move probabilities for every square on the board.
14.2.1 The Shop Example
Consider a shop that sells two types of products: Computer electronics (C) and Media accessories (M). A customer visits the shop repeatedly. Each visit, the customer buys one type. The Markov model has two states — C and M — with the following transition probabilities:
- If the customer bought a Computer last time, the probability of buying a Computer again is 0.4; the probability of switching to Media is 0.6.
- If the customer bought Media last time, the probability of buying Media again is 0.8; the probability of switching to Computer is 0.2.
These four values define the entire model. The TPM is a \(2 \times 2\) matrix:
Formalize: The Transition Probability Matrix for a two-state Markov model with states C (Computer) and M (Media) is:
\[ \text{TPM} = \begin{pmatrix} P(C_t \mid C_{t-1}) & P(M_t \mid C_{t-1}) \\ P(C_t \mid M_{t-1}) & P(M_t \mid M_{t-1}) \end{pmatrix} = \begin{pmatrix} 0.4 & 0.6 \\ 0.2 & 0.8 \end{pmatrix} \]
Each cell \(T_{ij}\) gives the probability of transitioning from state \(i\) (row) to state \(j\) (column). The rows represent the previous state at time \(t-1\), and the columns represent the current state at time \(t\). Each column sums to 1 because the current state must be one of the possible options.
Worked Example — Reading the TPM: The shop owner observes a regular customer. On the customer's last visit, they bought a Computer. Using the TPM, we can answer:
- "What is the probability they buy a Computer again?" → Look at row C, column C: 0.4 (40% chance).
- "What is the probability they switch to Media?" → Look at row C, column M: 0.6 (60% chance).
Now suppose the customer bought Media last time:
- "What is the probability they buy Media again?" → Row M, column M: 0.8 (80% chance — media buyers are loyal!).
- "What is the probability they switch to Computer?" → Row M, column C: 0.2 (20% chance).
Sense-check: The numbers make intuitive sense. Media buyers are more "sticky" (0.8 repeat rate) than computer buyers (0.4 repeat rate). This matches the real-world observation that accessories generate repeat purchases while big-ticket electronics are less frequent.
14.2.2 Reading the TPM
The convention for the TPM is always: the columns represent the current state (time \(t\)) and the rows represent the previous state (time \(t-1\)). Specifically, each cell answers the question: "What is the probability of the current state (column) given the previous state (row)?"
- Top-left cell: \(P(C_t \mid C_{t-1}) = 0.4\) — "What is the probability I get a Computer today, given that yesterday I also got a Computer?"
- Top-right cell: \(P(M_t \mid C_{t-1}) = 0.6\) — "What is the probability I get Media today, given that yesterday I got a Computer?"
- Bottom-left cell: \(P(C_t \mid M_{t-1}) = 0.2\) — "What is the probability I get a Computer today, given that yesterday I got Media?"
- Bottom-right cell: \(P(M_t \mid M_{t-1}) = 0.8\) — "What is the probability I get Media today, given that yesterday I also got Media?"
Each column of the TPM sums to 1, because the current state must be one of the possible options.
Student Q&A:
Q: Would it be wrong to transpose the matrix?
A: It is not mathematically wrong, but the convention is to keep the current state along the top (columns) and the previous state along the side (rows). Always write it this way for consistency and for exams. If you transpose it, the matrix multiplication formulas in later sections will give incorrect results.
The data in the TPM comes from domain experts — in this case, the shop owner who knows customer behavior patterns. If a regular customer visited last time and bought Media, the shop owner can estimate the probability that the same customer will buy Media again versus switching to Computer.
Pitfalls:
- Mixing up rows and columns: The most common mistake is reading the matrix backwards. Always remember: rows = previous state (\(t-1\)), columns = current state (\(t\)). A quick check: if a customer bought Media and is very loyal to Media, the bottom-right cell should be high (close to 1), not low.
- Forgetting that columns sum to 1: Each column must sum to 1 because the customer must buy something. If your column sums to 0.9 or 1.1, you have made an error. (Note: some textbooks use rows summing to 1 instead — follow the convention specified in your course.)
- Assuming the TPM is symmetric: The TPM is generally not symmetric. In our example, \(P(M \mid C) = 0.6\) but \(P(C \mid M) = 0.2\). The two directions of transition can have very different probabilities.
14.2.3 Second-Order Markov TPM
For a second-order Markov model, the TPM grows. Instead of considering just the one previous state, we consider the two previous states. With two possible products (C and M), the previous two-visit combinations are: CC, CM, MC, MM. Each of these can transition to C or M, giving us a \(4 \times 2\) matrix (or equivalently, 8 cells).
The rows represent the pair of states from the two previous visits \((t-2, t-1)\), and the columns represent the current state \((t)\). For example:
- Row "CM, Column C": "What is the probability I get a Computer today, given that two visits ago I got Computer and the last visit I got Media?"
- Row "MM, Column M": "What is the probability I get Media today, given that both of the last two visits I got Media?"
General Formula: For an \(n\)-th order Markov model with \(k\) possible states, the TPM has \(k^n \times k\) cells. For second order with 2 states: \(2^2 \times 2 = 8\) cells. For third order with 2 states: \(2^3 \times 2 = 16\) cells. In general, the number of cells grows exponentially with the order — this is the "curse of dimensionality" for higher-order Markov models.
Worked Example — Second-Order TPM Size: A weather model with 3 states (Sunny, Rainy, Cloudy) and second-order Markov:
- Number of two-day combinations: \(3^2 = 9\) (SS, SR, SC, RS, RR, RC, CS, CR, CC)
- Number of current states: 3
- TPM size: \(9 \times 3 = 27\) cells
Compare this to a first-order TPM for the same 3 states: only \(3 \times 3 = 9\) cells. The second-order model requires three times as many parameters — and the gap widens rapidly as the number of states increases.
Scope: Second-order Markov models are useful when the first-order assumption is too restrictive — for example, when the pattern of the last two states matters, not just the most recent one. However, the exponential growth in parameters means that second-order models require much more data to estimate reliably. For exams in this course, always use first-order Markov unless the problem explicitly states otherwise.
Recap + Bridge: The TPM is the "cheat sheet" of a Markov model — it tells you the probability of every possible one-step transition. Rows are the previous state, columns are the current state, and each column sums to 1. Now that we can represent a Markov model as a matrix, the natural next question is: how do we use this matrix to answer real questions — like predicting the next state, computing sequence probabilities, or finding the most likely pattern? That is what Section 14.3 covers.
14.3 Inferencing from Markov Models
Hook: You have the TPM — the "cheat sheet" of your Markov model. Now what? The real power of a Markov model is not in storing the matrix, but in answering questions with it. Given that a customer bought a Computer today, what will they buy tomorrow? What is the probability of the exact sequence C, M, M, C? And if you want the single most likely purchasing pattern for the next three visits, how do you find it? This section walks through four distinct query types, each building on the previous one.
Given a Markov model (diagram or TPM), we can answer several types of queries. The professor walked through four distinct query types, each building on the previous one.
Intuition + Analogy: Think of the TPM as a road map between cities. Each city is a state, and each road has a "probability sign" telling you how likely you are to take that road. The four query types are like different questions a traveler might ask: "Where will I end up tomorrow?" (prediction), "What is the chance I follow this exact route?" (sequence probability), "What if I must leave city X after staying exactly two days?" (constraint), and "What is the single best route for the next three days?" (most likely pattern).
14.3.1 Type 1: Predicting the Next State
Given the TPM and an initial state (what the customer bought today), predict what the customer will buy tomorrow.
The initial state is represented as a column vector \(I\). If today the customer bought a Computer, then:
\[ I = \begin{pmatrix} 1 \\ 0 \end{pmatrix} \]
(The probability of Computer is 1, Media is 0.)
To find the next state, multiply the TPM by the initial vector:
\[ \text{Next State} = \text{TPM} \times I \]
Formalize: The next-state prediction is a matrix–vector multiplication:
\[ \begin{pmatrix} P(C_t \mid C_{t-1}) & P(M_t \mid C_{t-1}) \\ P(C_t \mid M_{t-1}) & P(M_t \mid M_{t-1}) \end{pmatrix} \times \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} P(C_t \mid C_{t-1}) \times 1 + P(M_t \mid C_{t-1}) \times 0 \\ P(C_t \mid M_{t-1}) \times 1 + P(M_t \mid M_{t-1}) \times 0 \end{pmatrix} = \begin{pmatrix} 0.4 \\ 0.6 \end{pmatrix} \]
The result is a probability distribution over the next state: Computer with probability 0.4, Media with probability 0.6.
Worked Example — Predicting the Next State: A customer bought a Computer today. What will they buy tomorrow?
\[ \begin{pmatrix} 0.4 & 0.6 \\ 0.2 & 0.8 \end{pmatrix} \times \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 0.4 \times 1 + 0.6 \times 0 \\ 0.2 \times 1 + 0.8 \times 0 \end{pmatrix} = \begin{pmatrix} 0.4 \\ 0.6 \end{pmatrix} \]
Answer: Computer with probability 0.4, Media with probability 0.6.
Sense-check: Since \(P(M \mid C) = 0.6 > P(C \mid C) = 0.4\), a computer buyer is more likely to switch to media than to buy another computer. The result confirms this.
Worked Example — Predicting with No Initial State: If the initial state is not given, assume equal probability: Computer = 0.5, Media = 0.5. Then:
\[ \begin{pmatrix} 0.4 & 0.6 \\ 0.2 & 0.8 \end{pmatrix} \times \begin{pmatrix} 0.5 \\ 0.5 \end{pmatrix} = \begin{pmatrix} 0.4 \times 0.5 + 0.6 \times 0.5 \\ 0.2 \times 0.5 + 0.8 \times 0.5 \end{pmatrix} = \begin{pmatrix} 0.5 \\ 0.5 \end{pmatrix} \]
Answer: Computer with probability 0.5, Media with probability 0.5.
Sense-check: When we start with equal probabilities and the TPM is not strongly biased in one direction, the distribution may stay balanced or shift gradually.
You can keep multiplying by the TPM to get further future states, but note that the TPM stays fixed — it is a "stale" estimate. For one or two steps ahead this is reasonably accurate, but for longer horizons the TPM should ideally be updated.
14.3.2 Type 2: Probability of a Specific Sequence
Given that today the customer bought a Computer, what is the probability that the purchasing behavior follows the exact sequence: Computer, Media, Media, Computer?
This is a joint probability question, but we do not apply the chain rule from Bayesian networks. Instead, we use the Markov property directly. Each transition's probability comes from the TPM:
Formalize: The probability of a specific sequence \(s_1, s_2, \ldots, s_n\) under the Markov assumption is the product of the initial probability and all subsequent transition probabilities:
\[ P(s_1, s_2, \ldots, s_n) = P(s_1) \times P(s_2 \mid s_1) \times P(s_3 \mid s_2) \times \cdots \times P(s_n \mid s_{n-1}) \]
Each term \(P(s_i \mid s_{i-1})\) is read directly from the TPM. The first term \(P(s_1)\) is the probability of the initial state — if it is given, \(P(s_1) = 1\).
Worked Example — Probability of Sequence C, M, M, C: Given that today the customer bought a Computer, compute the probability of the sequence: Computer → Media → Media → Computer.
\[ P(C, M, M, C) = P(C) \times P(M \mid C) \times P(M \mid M) \times P(C \mid M) \]
Substituting from the TPM:
\[ = 1 \times 0.6 \times 0.8 \times 0.2 = \mathbf{0.096} \]
Step-by-step breakdown:
- \(P(C) = 1\): given that today the customer bought a Computer.
- \(P(M \mid C) = 0.6\): from TPM row C, column M. "Computer buyer switches to Media."
- \(P(M \mid M) = 0.8\): from TPM row M, column M. "Media buyer stays with Media."
- \(P(C \mid M) = 0.2\): from TPM row M, column C. "Media buyer switches to Computer."
Sense-check: 0.096 is a small number, which makes sense — this is the probability of one very specific four-visit sequence. There are \(2^4 = 16\) possible sequences of length 4, and their probabilities must sum to 1.
Student Q&A:
Q: Is computing a sequence probability the same as applying the chain rule from Bayesian networks?
A: No. The chain rule from Bayesian networks decomposes a joint probability into conditional probabilities using the structure of the network — each conditioning set can be different and depends on the graph structure. Here, we are simply multiplying first-order conditional transition probabilities from the TPM. Each term is \(P(\text{current state} \mid \text{previous state})\) — the Markov property, not chain rule. The TPM provides all the terms directly, and we just multiply them in order.
14.3.3 Type 3: Sequence with an "Only" Constraint
A more nuanced question: "What is the probability that a customer who purchased Media will keep coming back to purchase Media in the next two consecutive visits only?"
Pitfall — The "Only" Keyword: The word "only" is critical. It means:
- Today: Media (given, probability = 1)
- Next visit: Media
- Visit after that: Media
- The visit after that: not Media — i.e., Computer
The "only" forces the fourth day to be Computer, not Media. If the word "only" were absent, the question would simply ask for the probability of three consecutive Media purchases, and the fourth day could be either C or M. Always read problem statements very carefully — the word "only" changes the question fundamentally.
Formalize: With the "only" constraint, the sequence is Media → Media → Media → Computer:
\[ P(M, M, M, C) = P(M) \times P(M \mid M) \times P(M \mid M) \times P(C \mid M) \]
Worked Example — "Only" Constraint: Compute the probability that a customer who purchased Media will buy Media for the next two consecutive visits only.
The sequence is: Media → Media → Media → Computer.
\[ P(M, M, M, C) = P(M) \times P(M \mid M) \times P(M \mid M) \times P(C \mid M) \] \[ = 1 \times 0.8 \times 0.8 \times 0.2 = \mathbf{0.128} \]
Step-by-step:
- \(P(M) = 1\): given that today the customer bought Media.
- \(P(M \mid M) = 0.8\): Media buyer stays with Media (visit 2).
- \(P(M \mid M) = 0.8\): Media buyer stays with Media (visit 3).
- \(P(C \mid M) = 0.2\): Media buyer switches to Computer (visit 4 — forced by "only").
Sense-check: 0.128 is the probability of a specific constrained sequence. Compare this to the probability of three Media purchases without the "only" constraint: \(1 \times 0.8 \times 0.8 = 0.64\), which is much higher because it includes the possibility of a fourth Media purchase as well.
Exam Guidance: The "only" keyword is a favorite exam trick. When you see "only," it forces the next state after the constrained period to be the complement of the constrained state. For example, "Media for two visits only" means M, M, C — not M, M, M. Always check whether the problem says "only" or not, and adjust the sequence accordingly.
14.3.4 Type 4: Expected Purchase Pattern (Most Likely Sequence)
This is the most interesting type of query. Given that today the customer bought a Computer, what will the customer buy on the next three visits? The answer is not a probability number — it is a pattern (e.g., Media, Media, Media).
The approach is straightforward: at each step, look at the transition probabilities and pick the more likely outcome.
Formalize — Greedy Approach: To find the most likely sequence of length \(n\) starting from state \(s_0\):
- Start at \(s_0\).
- For each subsequent step \(i = 1, 2, \ldots, n\):
- Look at the TPM row for the current state.
- Pick the column (next state) with the highest probability.
- The resulting sequence is the most likely pattern.
This greedy approach works because we are asked for the most likely pattern, not a probability value. At each step, we independently pick the most likely next state.
Worked Example — Most Likely Pattern: Given that today the customer bought a Computer, what will they buy on the next three visits?
Starting from Computer:
- Visit 1: \(P(C \mid C) = 0.4\) vs. \(P(M \mid C) = 0.6\). Media is more likely → pick Media.
- Visit 2: From Media, \(P(M \mid M) = 0.8\) vs. \(P(C \mid M) = 0.2\). Media is more likely → pick Media.
- Visit 3: From Media again, \(P(M \mid M) = 0.8\) vs. \(P(C \mid M) = 0.2\). Media is more likely → pick Media.
Answer: The most likely pattern is Media, Media, Media.
Sense-check: No multiplication is needed. At each time step, simply compare the outgoing transition probabilities and pick the state with the higher probability. Since Media buyers are "sticky" (0.8 repeat rate), once the customer switches to Media, they are likely to stay there.
Student Q&A:
Q: Does the direction of the arrow in the Markov model diagram matter?
A: Yes. The arrows in the Markov model diagram always point from the previous state to the current state. When reading the diagram, always observe the direction: the arrow goes from \(t-1\) to \(t\). The matrix convention has \(t-1\) on the rows and \(t\) on the columns, which is the same information in tabular form. If you reverse the arrow direction, you are computing the wrong conditional probability.
Pitfalls:
- Confusing Type 2 and Type 4: Type 2 asks for the probability of a specific given sequence (you multiply). Type 4 asks for the most likely sequence (you compare and pick). Do not multiply when asked for a pattern.
- Forgetting the initial state in Type 2: The first term \(P(s_1)\) is 1 if the initial state is given. If it is not given and you assume equal probability, use 0.5 for each state (or the specified initial distribution).
- Not reading "only" carefully in Type 3: The "only" keyword forces the next state after the constrained period. Missing this changes the entire calculation.
Exam note: All four query types are examinable. Type 1 (next state) and Type 2 (sequence probability) are the most common. Type 3 ("only" constraint) is a favorite trick question. Type 4 (most likely pattern) requires no multiplication — just compare and pick. For all types, always start from the TPM and trace through the transitions carefully.
Recap + Bridge: We have seen four ways to query a Markov model: predict the next state (matrix multiplication), compute a sequence probability (product of transitions), handle the "only" constraint (force the complement state), and find the most likely pattern (greedy comparison). These queries are the building blocks for everything that follows. But so far, we have assumed we can observe the state directly — we know whether the customer bought Computer or Media. What happens when the state is hidden? That is the question that leads us to Hidden Markov Models in Section 14.4.
14.5 HMM Query Types
Hook: You have an HMM with its TPM and EPM. Now you are a detective with a toolkit. Depending on the question you ask, you use a different tool. "Where am I right now?" is filtering. "Where will I be tomorrow?" is prediction. "Where was I last week?" is smoothing. "What path did I take to get here?" is most likely explanation. Each question sounds similar, but the computational approach — and the answer — is fundamentally different.
Given an HMM with its TPM and EPM, we can ask four types of queries. Each has a different interpretation and a different computational approach.
Intuition + Analogy: The professor summarized the four queries in a single memorable line:
- Filtering = "Where am I right now?"
- Prediction = "Where will I be?"
- Smoothing = "Where was I?"
- Most likely explanation = "What path did I take?"
Think of a hiker lost in fog. Filtering asks: "Given what I see around me now, where am I most likely standing?" Prediction asks: "Given what I have seen so far, where will the trail lead next?" Smoothing asks: "Now that I have more information, can I figure out where I was an hour ago?" Most likely explanation asks: "What is the single most likely path I took from the trailhead to here?"
14.5.1 Filtering
Filtering asks: "What is the probability of the hidden state today, given all the observed evidence up to and including today?"
\[ P(X_t \mid E_1, E_2, \ldots, E_t) \]
This is also called state estimation or computing the belief state. Filtering is about the current hidden state — it answers "where am I right now?" This is what a rational agent does to keep track of the current state so that rational decisions can be made.
Worked Example — Filtering: In the weather pressure HMM, suppose the observed evidence is: Day 1 = Rainy, Day 2 = Sunny, Day 3 = Rainy, Day 4 = Rainy. Filtering asks:
"What is the probability that Day 4 is a low pressure day, given that it was rainy on Day 1, sunny on Day 2, rainy on Day 3, and rainy on Day 4?"
The answer is a probability distribution over the hidden states for Day 4: e.g., \(P(\text{Low} \mid E_1, E_2, E_3, E_4) = 0.85\) and \(P(\text{High} \mid E_1, E_2, E_3, E_4) = 0.15\).
Sense-check: Since rainy days are more likely under low pressure (from the EPM), and we have observed mostly rainy days, the posterior probability for low pressure should be high.
14.5.2 Prediction
Prediction asks: "What is the probability of a future hidden state, given all the observed evidence up to today?"
\[ P(X_{t+k} \mid E_1, E_2, \ldots, E_t) \]
Prediction extends forward in time from the current evidence. It uses only the transition model (TPM), not the sensor model (EPM), because there is no new evidence to incorporate.
Worked Example — Prediction: In the weather pressure HMM, given the evidence up to Day 4, prediction asks:
"What will the pressure be on Day 5 (\(t+1\)) or Day 6 (\(t+2\))?"
This is useful for forecasting — if you know the current belief state (from filtering), you can project it forward using the TPM.
14.5.3 Smoothing
Smoothing asks: "What is the probability of a past hidden state, given all the observed evidence up to today?"
\[ P(X_s \mid E_1, E_2, \ldots, E_t) \quad \text{where } s < t \]
Smoothing looks backward — it uses future evidence to refine our understanding of a past state. This is more powerful than filtering at time \(s\), because smoothing uses evidence from time \(s+1\) through \(t\) that was not available at time \(s\).
Worked Example — Smoothing: In the weather pressure HMM, given all observations up to Day 5, smoothing asks:
"What was the pressure on Day 3?"
At the time Day 3 occurred, you only had evidence from Days 1–3 (filtering). But now, with evidence from Days 4 and 5 as well, you can produce a better estimate of Day 3's pressure. Smoothing incorporates the backward flow of information.
The term "smoothing" comes from the fact that when tracking a moving object with noisy observations, the smoothed trajectory is literally smoother (less noisy) than the filtered trajectory.
14.5.4 Most Likely Explanation (Viterbi's Algorithm)
Most Likely Explanation asks: "Given the observed evidence sequence, what is the most likely sequence of hidden states that produced it?"
\[ \arg\max_{X_1, X_2, \ldots, X_t} P(X_1, X_2, \ldots, X_t \mid E_1, E_2, \ldots, E_t) \]
The answer is not a probability number — it is a pattern. For example, if the observed evidence is Rainy, Sunny, Rainy, Rainy, the answer might be: "Low pressure, High pressure, Low pressure, Low pressure." Or it could be a different pattern. We want the single most likely pattern.
This is solved by Viterbi's algorithm, which has immense applications in modern AI — speech recognition, natural language processing, bioinformatics, and many other fields rely on it.
Worked Example — Most Likely Explanation: In the weather pressure HMM, the observed evidence is: Rainy, Sunny, Rainy, Rainy. The most likely explanation asks:
"What sequence of pressure states (L or H) is most likely to have produced this evidence?"
The answer might be: L, H, L, L. This means Day 1 was low pressure (producing Rainy), Day 2 was high pressure (producing Sunny), and Days 3–4 were low pressure (producing Rainy each).
Important distinction: This is not the same as taking the most likely state at each individual time step (which is what filtering gives you). The most likely sequence may differ from the concatenation of most likely individual states, because the transition probabilities create dependencies between states.
Pitfall — Filtering vs. Most Likely Explanation: A common mistake is to use filtering to find the most likely state at each time step, then concatenate them to get the "most likely sequence." This is wrong. Filtering gives the marginal distribution at each time step independently. The most likely sequence considers the joint probability of the entire path, including transition costs between consecutive states. Viterbi's algorithm correctly accounts for these inter-state dependencies.
Exam note: For this course, you need to know filtering and most likely explanation (Viterbi). The professor explained all four types for completeness, but the exam focuses on these two. Remember:
- Filtering uses sum (the forward propagation algorithm sums incoming paths).
- Viterbi uses max (instead of summing, it takes the maximum over incoming paths).
The professor's words: "In some cases you add, in some cases you take the maximum. That is the only difference."
Recap + Bridge: The four HMM query types — filtering, prediction, smoothing, and most likely explanation — answer fundamentally different questions about the same model. For this course, filtering and Viterbi are the two you must master. Both are powered by the same computational engine: the forward propagation algorithm, which we cover in detail in Section 14.6. The only difference is that filtering sums incoming paths while Viterbi takes the maximum.
14.6 Forward Propagation Algorithm
Hook: You have an HMM with two matrices (TPM and EPM), and you want to compute the probability of observing a specific sequence of evidence. How do you do it? The naive approach — enumerate every possible hidden-state sequence and sum their probabilities — is exponential in the number of time steps. The forward propagation algorithm (FPA) solves this in linear time by "propagating" accumulated probabilities forward through the model. It is the computational engine that powers both filtering and Viterbi's algorithm.
The forward propagation algorithm (FPA) is the computational engine that powers filtering and, with slight variations, the other query types. Understanding FPA makes everything else straightforward.
Intuition + Analogy: Think of the FPA as a bucket brigade at a fire. Each "bucket" is a forward variable \(\alpha\) that carries accumulated probability from one time step to the next. At each step, the bucket receives contributions from all possible previous states (summed together), gets multiplied by the transition and emission probabilities, and passes the result forward. By the end, the buckets at the last time step hold the total probability of the evidence sequence. The key insight: instead of enumerating all \(2^n\) possible hidden-state sequences (exponential), the FPA reuses intermediate results to compute the answer in \(O(n)\) time (linear).
14.6.1 The Query
Given an HMM with TPM and EPM, compute the probability of observing a specific evidence sequence. For example: what is the probability that Day 1 is Sunny, Day 2 is Sunny, and Day 3 is Rainy?
\[ P(E_1 = \text{Sunny}, E_2 = \text{Sunny}, E_3 = \text{Rainy}) \]
The hidden variable each day is either Low pressure (L) or High pressure (H). We marginalize over all possible hidden-state sequences.
Formalize: The probability of an evidence sequence \(e_1, e_2, \ldots, e_T\) is obtained by summing (marginalizing) over all possible hidden-state sequences:
\[ P(e_1, e_2, \ldots, e_T) = \sum_{x_1} \sum_{x_2} \cdots \sum_{x_T} P(x_1) \prod_{t=1}^{T} P(e_t \mid x_t) \prod_{t=2}^{T} P(x_t \mid x_{t-1}) \]
For \(T\) time steps and \(S\) hidden states, there are \(S^T\) possible hidden-state sequences. The FPA computes this sum in \(O(S^2 T)\) time instead of \(O(S^T)\) by reusing intermediate results — a classic dynamic programming approach.
14.6.2 The Algorithm, Step by Step
We use the following HMM parameters (the same weather pressure example from Section 14.4):
TPM (hidden state transitions):
| L(t) | H(t) | |
|---|---|---|
| L(t-1) | 0.5 | 0.5 |
| H(t-1) | 0.2 | 0.8 |
Each column sums to 1. Reading: "If yesterday was Low pressure, there is a 50% chance of Low today and 50% chance of High."
EPM (evidence given hidden state):
| Sunny | Rainy | |
|---|---|---|
| L | 0.2 | 0.8 |
| H | 0.6 | 0.4 |
Reading: "If it is Low pressure, the probability of Sunny is 0.2 and Rainy is 0.8." Low pressure makes rain likely; High pressure makes sun likely.
Initial probabilities: \(P(L) = 0.5\), \(P(H) = 0.5\) (equal likelihood, since we have no prior information).
Step 1 — Initialize (Day 1):
We start with the first day. The evidence for Day 1 is Sunny.
First, write down the initial probabilities:
\[ P(L_1) = 0.5, \quad P(H_1) = 0.5 \]
Now incorporate the evidence. The probability of Sunny given each hidden state comes from the EPM:
\[ P(\text{Sunny} \mid L) = 0.2, \quad P(\text{Sunny} \mid H) = 0.6 \]
Compute the forward variable \(\alpha\) for each hidden state. The forward variable \(\alpha_t(s)\) represents the joint probability of the evidence sequence up to time \(t\) and being in state \(s\) at time \(t\):
\[ \alpha_1(L) = P(L_1) \times P(\text{Sunny} \mid L) = 0.5 \times 0.2 = 0.1 \] \[ \alpha_1(H) = P(H_1) \times P(\text{Sunny} \mid H) = 0.5 \times 0.6 = 0.3 \]
Where does each number come from?
- \(P(L_1) = 0.5\): initial probability (given or assumed).
- \(P(\text{Sunny} \mid L) = 0.2\): from the EPM row L, column Sunny.
- The multiplication: initial probability × emission probability. No transition involved yet because this is the first time step.
Normalization (optional for this query type): If desired, normalize by dividing each by the sum \(0.1 + 0.3 = 0.4\):
\[ \hat{\alpha}_1(L) = \frac{0.1}{0.4} = 0.25, \quad \hat{\alpha}_1(H) = \frac{0.3}{0.4} = 0.75 \]
Normalization is not required for computing the probability of the evidence sequence (the unnormalized values give the correct final answer). However, normalization is needed for filtering (where you want actual probabilities that sum to 1 at each step), so it was introduced here as a concept.
Step 2 — Propagate to Day 2:
Day 2 can be either L or H. For each possible hidden state on Day 2, there are two possible paths from Day 1 (one from L and one from H). We compute the probability along each path, then sum them.
The formula for each path is:
\[ \text{(path from state } s' \text{ to state } s\text{)} = \alpha_1(s') \times P(s \mid s') \times P(\text{evidence}_2 \mid s) \]
Three ingredients: previous forward variable (from Step 1), transition probability (from TPM), emission probability (from EPM).
Path to Day 2 = L:
- From Day 1 = L: \(\alpha_1(L) \times P(L \mid L) \times P(\text{Sunny} \mid L) = 0.1 \times 0.5 \times 0.2 = 0.01\)
- From Day 1 = H: \(\alpha_1(H) \times P(L \mid H) \times P(\text{Sunny} \mid L) = 0.3 \times 0.2 \times 0.2 = 0.012\)
Path to Day 2 = H:
- From Day 1 = L: \(\alpha_1(L) \times P(H \mid L) \times P(\text{Sunny} \mid H) = 0.1 \times 0.5 \times 0.6 = 0.03\)
- From Day 1 = H: \(\alpha_1(H) \times P(H \mid H) \times P(\text{Sunny} \mid H) = 0.3 \times 0.8 \times 0.6 = 0.144\)
Now combine the incoming paths by summing:
\[ \alpha_2(L) = 0.01 + 0.012 = 0.022 \] \[ \alpha_2(H) = 0.03 + 0.144 = 0.174 \]
Where does each number come from?
- Transition probabilities (\(P(L \mid L) = 0.5\), \(P(L \mid H) = 0.2\), \(P(H \mid L) = 0.5\), \(P(H \mid H) = 0.8\)): from the TPM.
- Emission probabilities (\(P(\text{Sunny} \mid L) = 0.2\), \(P(\text{Sunny} \mid H) = 0.6\)): from the EPM.
- Previous forward variables (\(\alpha_1(L) = 0.1\), \(\alpha_1(H) = 0.3\)): from Step 1.
- The operation: sum the incoming paths. This is what distinguishes forward propagation (for filtering) from Viterbi (which takes the max).
Step 3 — Propagate to Day 3:
Day 3's evidence is Rainy. The EPM gives: \(P(\text{Rainy} \mid L) = 0.8\), \(P(\text{Rainy} \mid H) = 0.4\).
Path to Day 3 = L:
- From Day 2 = L: \(\alpha_2(L) \times P(L \mid L) \times P(\text{Rainy} \mid L) = 0.022 \times 0.5 \times 0.8 = 0.0088\)
- From Day 2 = H: \(\alpha_2(H) \times P(L \mid H) \times P(\text{Rainy} \mid L) = 0.174 \times 0.2 \times 0.8 = 0.02784\)
Path to Day 3 = H:
- From Day 2 = L: \(\alpha_2(L) \times P(H \mid L) \times P(\text{Rainy} \mid H) = 0.022 \times 0.5 \times 0.4 = 0.0044\)
- From Day 2 = H: \(\alpha_2(H) \times P(H \mid H) \times P(\text{Rainy} \mid H) = 0.174 \times 0.8 \times 0.4 = 0.05568\)
Combining:
\[ \alpha_3(L) = 0.0088 + 0.02784 = 0.03664 \] \[ \alpha_3(H) = 0.0044 + 0.05568 = 0.06008 \]
Final answer: The probability of the evidence sequence (Sunny, Sunny, Rainy) is obtained by summing the forward variables from the last day:
\[ P(\text{Sunny}, \text{Sunny}, \text{Rainy}) = \alpha_3(L) + \alpha_3(H) = 0.03664 + 0.06008 = \mathbf{0.09672} \]
Worked Example — Complete Trace: Here is the full computation in one view:
| Day | Evidence | \(\alpha(L)\) | \(\alpha(H)\) | Sum |
|---|---|---|---|---|
| 1 | Sunny | 0.1 | 0.3 | 0.4 |
| 2 | Sunny | 0.022 | 0.174 | 0.196 |
| 3 | Rainy | 0.03664 | 0.06008 | 0.09672 |
Sense-check: The final probability 0.09672 is less than 1, which is correct — it is the probability of one specific three-day evidence sequence. The probability of Sunny on Day 1 is 0.4 (from the initial probabilities and EPM), and each subsequent step further constrains the probability, making the final number smaller.
14.6.3 Understanding the Summation
At each node (hidden state at each time step), there are exactly two incoming arrows — one from each possible previous hidden state. You independently compute the probability along each incoming path, then add them together to get that node's forward variable. The only exception is the first node, which has no incoming arrows; its value comes solely from the initial probability times the emission probability.
The key insight: at every stage, two ingredients are needed:
- TPM provides the transition probability along the edge between hidden states.
- EPM provides the emission probability for the observed evidence given the hidden state.
The forward variable from the previous stage provides the "accumulated evidence so far."
General Formula: The forward variable at time \(t\) for state \(s\) is:
\[ \alpha_t(s) = P(e_t \mid s) \times \sum_{s'} \alpha_{t-1}(s') \times P(s \mid s') \]
where:
- \(P(e_t \mid s)\) is the emission probability from the EPM.
- \(P(s \mid s')\) is the transition probability from the TPM.
- \(\alpha_{t-1}(s')\) is the forward variable from the previous time step.
- The sum \(\sum_{s'}\) runs over all possible previous hidden states.
For the first time step (\(t = 1\)):
\[ \alpha_1(s) = P(s_1) \times P(e_1 \mid s) \]
where \(P(s_1)\) is the initial probability of state \(s\).
14.6.4 Connection to Filtering and Viterbi
The forward propagation algorithm is the foundation for both filtering and Viterbi's algorithm:
The Sum-vs-Max Distinction: The professor's key insight — "In some cases you add, in some case you take the maximum. That is the only difference." — refers to the difference between filtering and Viterbi:
- Filtering uses the same forward pass but sums the incoming paths at each node. The sum represents the total probability of reaching that state given all evidence so far. Filtering also normalizes at each step to get actual probabilities.
- Viterbi's algorithm is nearly identical, but instead of summing the incoming paths, it takes the maximum. The answer is not a probability but the most likely path through the hidden states.
| Algorithm | Operation at each node | Output |
|---|---|---|
| Forward propagation (FPA) | Sum | Probability of evidence sequence |
| Filtering | Sum + normalize | Probability of current state given evidence |
| Viterbi | Max | Most likely hidden state sequence |
The computational structure is identical — only the aggregation operation differs.
Pitfalls:
- Forgetting to sum over incoming paths: At each node, you must consider both incoming paths (from each possible previous state) and add them. Missing one path gives an incorrect result.
- Using the wrong probability at each step: Each path computation uses three numbers: the previous forward variable (\(\alpha\)), the transition probability (TPM), and the emission probability (EPM). Mixing up which matrix provides which value is a common error.
- Confusing normalized and unnormalized forward variables: For computing the probability of the evidence sequence, use unnormalized values. For filtering (where you want probabilities at each step), normalize by dividing each \(\alpha\) by the sum of all \(\alpha\) values at that time step.
Exam note: The Forward Propagation Algorithm is a guaranteed exam question. You must be able to:
- Trace the computation step by step, showing where each number comes from (TPM for transitions, EPM for emissions, previous stage for accumulated probability).
- Compute the final probability by summing the forward variables at the last time step.
- Distinguish filtering (sum) from Viterbi (max).
Practice the computation with the worked example above until you can do it without looking at the solution.
Recap + Bridge: The forward propagation algorithm computes the probability of an evidence sequence by propagating accumulated probabilities forward through the HMM, using the TPM for transitions and the EPM for emissions. At each node, incoming paths are summed (for filtering) or maximized (for Viterbi). This completes our coverage of the core HMM machinery. The exam guidance and industry applications sections that follow summarize the key takeaways for exam preparation and real-world relevance.
Exam Guidance Summary
Exam note: The following guidance distills the professor's explicit exam intel for this lecture. Use it to prioritize your study time.
- Mark distribution: The quiz is 50 questions for 1 hour (approximately 1 minute per question), worth 5 marks. Best of two quizzes counts. Assignments total 25 marks. EC2 mid-semester is 30 marks. Final exam is 40 marks.
- Quiz level: Quiz questions target lower-order thinking (Bloom's taxonomy: remembering and understanding). Expect questions like "identify the TPM from a diagram" or "what does this cell in the TPM represent?" — not full problem-solving.
- Final exam: Will include higher-order thinking (creating, analyzing, critiquing). Expect problems requiring full computation of Markov model queries and HMM problems.
- Exam scope: Complete course, but approximately 90% from post-mid-semester content. Expect 3–5 marks from pre-mid-semester topics.
- First-order Markov only for exams: Always use first-order Markov unless explicitly told otherwise. Second-order examples were shown for understanding, but exam problems will be first-order.
- TPM convention: Current state along the top (columns), previous state along the side (rows). Always write it this way.
- Initial probability: If not given, assume 0.5 for each state.
- "Only" keyword: Read problem statements very carefully. The word "only" constrains the sequence — it forces a specific outcome on the next state after the "only" period.
- Expected pattern queries: No multiplication needed. At each step, compare transition probabilities and pick the higher one.
- HMM: You need two matrices — TPM and EPM. The exam will provide both.
- Forward Propagation Algorithm: Understand where each number comes from (TPM for transitions, EPM for emissions, previous stage for accumulated probability). Know how to trace the computation.
- Filtering and Viterbi: These are the two HMM query types for the course. Filtering uses sum; Viterbi uses max.
- Practice: Solve the problems in the slides. Very few students practice these — doing so gives a significant advantage.
Key Industry Applications
Real-World & Domain Connection: Markov models and HMMs are not just academic exercises — they power some of the most widely used technologies in the world. Here are the key application domains.
- Language modeling: Markov models and HMMs underpin next-word prediction, autocorrect, and Grammarly-style tools. The concept of "what was the previous word, what is the likely next word" is a direct application of transition probabilities. Modern large language models extend this idea with far richer state representations, but the Markov property remains at their conceptual core.
- Speech recognition: HMMs were the dominant approach for decades. The hidden states represent phonemes (the basic units of sound); the observed evidence is the acoustic signal (the waveform captured by a microphone). The TPM encodes how likely one phoneme is to follow another (e.g., "th" is often followed by "e" in English), and the EPM encodes how likely each phoneme is to produce a particular acoustic pattern. Viterbi's algorithm finds the most likely sequence of phonemes — which is the recognized sentence. While modern systems use deep neural networks, HMMs remain foundational to understanding how sequential inference works.
- Bioinformatics: Gene sequence analysis uses HMMs to identify coding regions in DNA. The hidden states are "gene" vs. "non-gene"; the observed evidence is the nucleotide sequence (A, T, G, C). The TPM captures the tendency of nucleotides to cluster in coding vs. non-coding regions, and the EPM captures the frequency of each nucleotide in each region. HMMs are also used for protein structure prediction and multiple sequence alignment.
- Weather prediction: The pressure/weather example from this lecture is directly applicable. Meteorological models use temporal dependencies to forecast weather patterns. The Markov assumption captures the persistence of weather states (rainy days tend to follow rainy days), and the EPM captures how pressure systems produce observable weather.
- Finance: Stock price models often assume a Markov structure — the future price depends on the current price, not the full price history. HMMs are used to detect market regimes (bull vs. bear markets) from observable price movements, where the regime is hidden and the price changes are evidence.
- Robot localization: The textbook (Russell & Norvig, Chapter 14) describes a robot using HMMs to determine its location from noisy sensor readings. The hidden state is the robot's position on a grid; the evidence is the sensor readings (which may be noisy or incomplete). The forward-backward algorithm allows the robot to integrate evidence over time and track its position accurately, even with significant sensor noise.
- Historical note: Markov processes originated from work by Andrei Markov (1856–1922) on probability and prediction. The professor recommended a 20–25 minute video on this history for those interested in the mathematical development in Russia.
ACI Lecture 14 notes · Temporal Models and Hidden Markov Models
Sections Breakdown
Temporal models, the Markov property, and first-order versus higher-order Markov models.
The Transition Probability Matrix (TPM), the shop example, and how to read rows and columns.
Four query types: next-state prediction, sequence probability, the 'only' constraint, and the most likely pattern.
Hidden states and observable evidence, the TPM and EPM, the urn game, and the commute example.
Filtering, prediction, smoothing, and most likely explanation via Viterbi.
Computing the probability of an evidence sequence by propagating forward variables through the HMM.
The professor's exam strategy: first-order Markov, TPM conventions, filtering versus Viterbi.
Real-world uses: speech recognition, language modeling, bioinformatics, weather, and finance.
Exam Revision Notes
Below is the distilled, exam-ready core. Every entry comes from the full explanation above. Use this section for rapid review; return to the main notes when a point needs more context.
Temporal Data and the Markov Assumption
Must-know: The first-order Markov assumption: P(X_t | X_{t-1}, ..., X_1) = P(X_t | X_{t-1}). Use first-order only for exams unless told otherwise.
\[P(X_t \mid X_{t-1}, X_{t-2}, \ldots, X_1) = P(X_t \mid X_{t-1})\]
⚠️ Top pitfall: Confusing 'Markov' with 'memoryless' — the state variable must be rich enough to capture all relevant history.
Self-check: If a student's exam score depends only on their most recent quiz score, what order Markov model is this?
Connects to: 14.2.
Markov Models and the Transition Probability Matrix
Must-know: TPM convention: columns = current state (t), rows = previous state (t-1). Each column sums to 1. The TPM is generally NOT symmetric.
\[\text{TPM} = \begin{pmatrix} 0.4 & 0.6 \\ 0.2 & 0.8 \end{pmatrix}\]
⚠️ Top pitfall: Mixing up rows and columns — always check: if a customer is loyal to Media, the bottom-right cell should be high.
Self-check: In the shop example TPM, what is P(Media today | Computer yesterday)?
Connects to: 14.1, 14.3.
Inferencing from Markov Models
Must-know: Four query types: Type 1 (matrix multiply), Type 2 (product of transitions), Type 3 ('only' forces complement), Type 4 (greedy pick). Read 'only' carefully — it changes the sequence.
\[P(C,M,M,C) = 1 \times 0.6 \times 0.8 \times 0.2 = 0.096\]
⚠️ Top pitfall: Confusing Type 2 (multiply probabilities) with Type 4 (compare and pick). Also: missing the 'only' keyword in Type 3.
Self-check: Starting from Media, what is the most likely next two states?
Connects to: 14.2, 14.4.
Hidden Markov Models
Must-know: HMM requires two matrices: TPM (hidden-to-hidden) and EPM (hidden-to-evidence). The exam will provide both. For the first node, assume equal probability if not given.
\[\text{TPM} = \begin{pmatrix} 0.2 & 0.6 & 0.2 \\ \ldots \end{pmatrix}, \quad \text{EPM} = \begin{pmatrix} 0.5 & 0.5 \\ 0.7 & 0.3 \\ 0.6 & 0.4 \end{pmatrix}\]
⚠️ Top pitfall: Confusing TPM and EPM — TPM is hidden-to-hidden, EPM is hidden-to-evidence.
Self-check: In the commute example, what is P(Late | Meeting)?
Connects to: 14.3, 14.5.
HMM Query Types
Must-know: Filtering and Viterbi are the two exam query types. Filtering uses SUM, Viterbi uses MAX. Do not concatenate marginal filtering results to get the most likely sequence.
\[P(X_t \mid E_1,\ldots,E_t) \quad \text{(filtering)}, \quad \arg\max_{X_1,\ldots,X_t} P(X_1,\ldots,X_t \mid E_1,\ldots,E_t) \quad \text{(Viterbi)}\]
⚠️ Top pitfall: Confusing filtering (marginal at each step) with Viterbi (joint most likely sequence). They can give different answers.
Self-check: What is the difference between filtering and smoothing?
Connects to: 14.4, 14.6.
Forward Propagation Algorithm
Must-know: Forward propagation: compute α_t(s) = P(e_t|s) × Σ α_{t-1}(s') × P(s|s'). Three ingredients: EPM, TPM, previous α. Filtering sums, Viterbi takes max.
\[\alpha_t(s) = P(e_t \mid s) \times \sum_{s'} \alpha_{t-1}(s') \times P(s \mid s')\]
⚠️ Top pitfall: Forgetting to sum both incoming paths, or mixing up TPM and EPM values at each step.
Self-check: In the FPA, what are the three ingredients needed to compute α_t(s)?
Connects to: 14.5, 14.4.