Articles
Hidden Markov Model Interview Questions: Forward Probabilities and Viterbi Paths
Practice Hidden Markov Model interview questions with forward likelihoods, Viterbi backpointers, marginal decoding, and stable numerical checks on worked paths.
An interviewer asks for the probability of an observed sequence, then asks for the most likely hidden-state path. Replacing a sum with a maximum changes the question you answer. Hidden Markov Model interview questions become clearer when you define the quantity before writing the recurrence: sequence likelihood, best joint path, and per-position state confidence are different objectives.
Start by labeling every dynamic-programming cell with its probabilistic meaning. That label explains the initialization, recurrence, termination, and whether you need backpointers. It also makes numerical failures easier to diagnose.
Evidence boundary: Official hmmlearn documentation and Mark Stamp's original HMM tutorial establish the model and algorithm facts linked below. The numerical example, debugging cases, and implementation recommendations are original exercises and inference. No candidate reports or employer-specific interview frequencies are claimed. Start with Compute multi-step Markov probabilities and estimate transitions to check your transition-matrix convention.
What is hidden, and what is observed?
Official fact: An HMM has a hidden state sequence with first-order Markov transitions and an observation distribution conditioned on the current state. Initial probabilities, transitions, and emission parameters define the model. hmmlearn distinguishes likelihood calculation, hidden-state inference, and parameter estimation. See its HMM tutorial.
Original exercise: States are A and B. Observations are symbols x and y. The initial distribution is (0.5, 0.5). Transition rows describe the current state; columns describe the next state:
next A next B
A 0.8 0.2
B 0.3 0.7
emit x emit y
A 0.6 0.4
B 0.2 0.8
All rows sum to one. The observed sequence is x, y, x. The state names are arbitrary labels; they are not observations and do not automatically identify real-world regimes.
A path such as A, B, A generates these observations with joint probability 0.5 × 0.6 × 0.2 × 0.8 × 0.3 × 0.6 = 0.00864. The observation likelihood includes that path and every other compatible path. The best-path problem asks which one contributes the largest individual joint probability.
For a fixed observed sequence with positive likelihood, maximizing joint path-and-observation probability also maximizes the path's posterior probability: the normalization denominator is the same for all paths. That does not make the maximum joint probability equal to the observation likelihood.
What does the forward algorithm sum?
Mathematical fact: The forward cell represents the joint probability of the observed prefix and the current hidden state. Dynamic programming sums the predecessor contributions rather than enumerating every whole path. See Mark Stamp's original tutorial.
Using one-based time for the three observations:
alpha_1(j) = pi(j) * emission_j(x_1)
alpha_t(j) = emission_j(x_t) * sum_i[alpha_(t-1)(i) * a(i,j)]
likelihood = sum_j alpha_T(j)
Original forward ledger:
| Observed prefix | alpha(A) | alpha(B) | Prefix likelihood |
|---|---|---|---|
| x | 0.30000 | 0.10000 | 0.40000 |
| x, y | 0.10800 | 0.10400 | 0.21200 |
| x, y, x | 0.07056 | 0.01888 | 0.08944 |
For the second row's A cell, compute (0.3 × 0.8 + 0.1 × 0.3) × 0.4 = 0.108. Both predecessor states contribute. Ignoring B's contribution would discard a valid route into A.
Notice what normalization would change. Dividing the last row by 0.08944 produces a distribution over the final state conditional on all three observations. The raw cells are joint prefix probabilities, not already normalized state probabilities. Calling both quantities “the forward probability” without qualification makes a debugging conversation ambiguous.
For this tiny exercise, all eight length-three paths can be enumerated. Their joint probabilities sum to 0.08944, providing an independent reference for the recurrence. Enumeration supplies an independent reference calculation for this small state space.
How does Viterbi differ?
Mathematical fact: Viterbi retains the largest path probability ending in each state and records the maximizing predecessor. Backtracking recovers a jointly optimal path. That differs from maximizing each position's posterior independently. See the decoding discussion in Stamp's tutorial.
delta_1(j) = pi(j) * emission_j(x_1)
delta_t(j) = emission_j(x_t) * max_i[delta_(t-1)(i) * a(i,j)]
backpointer_t(j) = argmax_i[delta_(t-1)(i) * a(i,j)]
Original best-path ledger for the same model:
| Prefix | delta(A) | delta(B) | Maximizing predecessor into A / B |
|---|---|---|---|
| x | 0.30000 | 0.10000 | Initial / initial |
| x, y | 0.09600 | 0.05600 | A / B |
| x, y, x | 0.04608 | 0.00784 | A / B |
The final winner is A. Its backpointer leads to A at time two, then A at time one, giving A, A, A. The largest joint path probability is 0.04608. Dividing by the observation likelihood gives posterior probability about 0.5152 for that entire path.
This leaves substantial posterior mass on other paths. A best path is a selected hypothesis under the model, not proof that all its states are certain. Forward includes every compatible path's mass; Viterbi keeps only the best predecessor for each ending state.
Selecting the largest delta at every time without backtracking is not the general algorithm. The best prefix endpoint at one time can fail to belong to the globally best full path after later evidence arrives. Preserve predecessor decisions and start backtracking from the final winning state.
Why is marginal decoding a different objective?
A smoothed posterior asks about the state at a position given the entire observation sequence. Forward-backward combines evidence before and after that position. A filtered posterior uses only observations available through that position. State which information is available before calling either result “the state estimate.”
Official API fact: hmmlearn supports viterbi and map decoder algorithms. Its API describes the latter as choosing the most likely individual states given all emissions, in contrast to the most likely sequence. See the hmmlearn API reference.
Original objective matrix:
| Request | Appropriate quantity | Common wrong substitution |
|---|---|---|
| How plausible is the observed sequence? | Sum over hidden paths | Probability of the best path only |
| Which complete path is most likely? | Joint path maximum with backtracking | Independent posterior winner at each position |
| How uncertain is state at time t? | Normalized posterior distribution | Unnormalized forward cell or one selected path |
| What can be known online at time t? | Filtering using available observations | Smoothing with future observations |
With forbidden transitions, independent marginal winners can form a sequence that the transition model does not permit. Even when all transitions are allowed, their combined path need not maximize the joint probability. The loss function matters: minimizing per-position error and selecting the most probable full sequence are different goals.
For an interview follow-up about online decoding, mention the cost of future information. You cannot label an offline smoothed estimate as a real-time prediction without explaining the delay or leakage. Keep the inference objective aligned with how the result will be used.
How do you avoid numerical underflow?
Original implementation recommendation: Long sequences multiply many small quantities. A zero in floating-point arithmetic can represent underflow rather than a genuinely impossible observation. Test those possibilities separately.
Forward computation can use log space, where addition of path probabilities becomes log-sum-exp. Viterbi uses additions of log probabilities and a maximum. Replacing log-sum-exp with max in a forward implementation silently turns it into a different objective; that substitution changes the requested quantity.
A stable log-sum-exp subtracts the largest input before exponentiation. Handle the all-negative-infinity case explicitly so subtracting negative infinity does not create a NaN. A zero transition or emission has log probability negative infinity and should retain its impossibility meaning.
An alternative forward implementation rescales each time step and records the scale factors. Normalized intermediate vectors alone lose the original likelihood unless the factors are retained and combined under a documented convention.
Official API fact: hmmlearn exposes log and scaling implementations. Choose the documented implementation option and compare its returned likelihood and decoder semantics, rather than assuming every method called “score” returns a probability. See the official API.
For continuous emissions, a density is not a probability mass and can exceed one. Do not reject an emission density merely because it is larger than one, or require every sequence density to be below one. The discrete worked example uses probabilities and has a different interpretation.
Which small tests catch real implementation mistakes?
Original test plan: Start with a one-observation sequence. Its likelihood should equal the initial-weighted emission sum; there are no transitions yet. This catches implementations that insert one extra transition or omit the initial emission.
Next, compare forward and Viterbi with exhaustive enumeration for a tiny state space. Forward must match the sum; Viterbi must match the maximum and return a path attaining it. Under the discrete model, the best joint path probability cannot exceed the total likelihood.
Introduce a zero transition and verify that the decoded path never uses it. Introduce an observation impossible under every state and define the API outcome deliberately. A path with a negative-infinity score should not be presented as meaningful confidence.
Test ties with a stated deterministic policy. More than one path can achieve the same maximum; the test should allow valid optimal alternatives unless the API specifically commits to one tie-breaking rule. Checking only the score misses a broken backpointer chain.
Test sequence boundaries when concatenating training or inference inputs. Treating the end of one independent sequence as transitioning into the beginning of the next changes the model's evidence. hmmlearn accepts sequence lengths for this purpose, as explained in working with multiple sequences.
The arithmetic checks for this article enumerate all eight original paths and compare forward, Viterbi, and log-space totals. They are small implementation fixtures, not a claim that a fitted HMM predicts an application well or that every hmmlearn option was integration-tested.
How much work does dynamic programming save?
For T observations and K states with a dense transition matrix, the usual recurrence considers K predecessors for each of K destination states at each step: O(TK²) arithmetic work. Exhaustive path enumeration considers K^T paths. The recurrence reuses prefixes because its cell definition retains exactly the state needed for the next transition.
Likelihood-only forward computation can keep two K-sized rows. Viterbi path recovery usually retains O(TK) backpointers; reducing score-row storage does not eliminate the memory needed for ordinary backtracking. Sparse allowed transitions can change the work, but state the representation and actual edge count.
Parameter fitting is a separate problem. A converged training run does not prove a globally best model, and inferred label A need not match another fit's label A. Compare model behavior and held-out evidence, rather than assuming arbitrary hidden-state labels have intrinsic meaning.
Five questions to extend the reasoning
The bank's related Markov-process questions support transition reasoning; they are not represented as direct HMM or Viterbi candidate reports. The MDP exercise adds actions and rewards, making it useful for explaining what an HMM does not model in this formulation.
| Question | HMM follow-up |
|---|---|
| Compute multi-step Markov probabilities and estimate transitions | Fix matrix orientation before adding emissions. |
| Compute and estimate Markov transition probabilities | Separate observed transitions from hidden-state inference. |
| Solve Markov and distribution expectation problems | Define the random quantity before choosing a recurrence. |
| Explain a stochastic process simply | Explain latent state and observations without conflating them. |
| Explain a Markov Decision Process | Contrast passive sequence inference with action-dependent transitions. |
Continue with Compute and estimate Markov transition probabilities. Add the original emission table, calculate the forward total, and recover the Viterbi path. Explain why their numbers differ before optimizing the code.