Questions: Hidden Markov Models

Question 1

In an HMM, the Viterbi algorithm is used to find which of the following?

• A. The probability of the observed sequence given the model
• B. The most likely state at each individual time step, independently
• C. The single most likely complete sequence of hidden states
• D. Updated transition and emission probabilities from unlabeled data

Answer: (C)

Viterbi finds the most probable entire path — the complete sequence of hidden states that jointly maximizes the probability of the observations. This is subtly different from finding the individually most likely state at each time step (which the posterior marginals from the forward-backward algorithm provide). The distinction matters: it is possible for the Viterbi path to pass through states that are not the individually most probable at each step, because the joint probability of the full sequence depends on valid transitions. Option A is the evaluation problem (solved by the forward algorithm); option D is learning (solved by Baum-Welch).

Question 2

A speech recognizer observes a sequence of acoustic feature vectors. It uses an HMM where hidden states represent phonemes. What are the 'emissions' in this model?

• A. The phonemes — they are inferred from the audio signal
• B. The acoustic feature vectors — the directly observed output at each time step
• C. The words — they are the final decoded output
• D. The transition probabilities between phonemes

Answer: (B)

In an HMM, emissions are the observable outputs produced by each hidden state. Here, the acoustic feature vectors (measurable quantities from the audio) are the emissions — they are what you directly observe. The phonemes are the hidden states — they are what you are trying to infer. This is the core HMM structure: hidden states (phonemes) generate observable emissions (acoustic features) according to emission probabilities, and your goal is to decode the most likely state sequence from the observations.

Question 3

The forward algorithm computes the probability of an observation sequence by dynamic programming, avoiding the need to enumerate all possible hidden state sequences.

• T. True
• F. False

Answer: True

True. For a sequence of length T with K hidden states, the brute-force approach would sum over all K^T possible state sequences — exponential in T. The forward algorithm exploits the Markov property: the probability of being in state i at time t, having generated observations up to t, depends only on the probability of being in each state at time t-1 (not on earlier history). This allows left-to-right dynamic programming that runs in O(K²T) time rather than O(K^T).

Question 4

Baum-Welch is very likely to find the globally optimal HMM parameters if run to convergence.

• T. True
• F. False

Answer: False

False. Baum-Welch is an instance of the Expectation-Maximization (EM) algorithm, which converges to a *local* maximum of the likelihood function, not necessarily the global one. The final parameters depend on initialization — different starting points can lead to different local optima. In practice, multiple random restarts are used to improve the chance of finding a good solution. Global optimality would require exhaustive search over parameter space, which is computationally intractable.

Question 5

Explain why finding 'the most likely state sequence' (Viterbi) is a different problem from finding 'the most likely state at each time step,' and describe a case where the two answers could differ.

Model answer: The most likely state sequence maximizes the joint probability P(s₁, s₂, ..., sT | observations). The most likely state at each time step maximizes the marginal posterior P(sₜ | observations) independently. These can differ because the Viterbi path must follow valid transitions — a high-probability path through a state sequence must remain internally consistent. For example, if being in state A at time 2 is individually probable, but the transition from the best state at time 1 to A is very unlikely, the Viterbi algorithm might assign state B at time 2, even though B is marginally less probable at that step, because the overall joint sequence probability is higher.

This distinction matters for applications like gene finding or speech recognition where you need a coherent, consistent sequence rather than a set of independent per-step guesses. The per-step marginals (computed via the forward-backward algorithm) are useful for other tasks — computing expected state occupancies for Baum-Welch or quantifying uncertainty — but they can produce contradictory sequences (e.g., consecutive states with zero-probability transitions between them). Viterbi always produces a valid path.