Hidden Markov Models (HMM)

Source: Unit 3 §12

Motivation: hidden state

In a Markov chain the states are observed. Very often they are not: the state is hidden, and all you see are observations that depend on it. Letters in a word, base pairs in DNA and successive phonemes in speech are all examples where the thing you observe depends on a state you do not.

The Karan and Vijay story. Vijay, who lives in Shimoga, tells Karan only his mood each day - Happy or Grumpy. His mood depends on the weather, Sunny or Rainy, which Karan cannot see.

≡FactsMapping the story onto the model

• Hidden states: the weather, Sunny or Rainy.
• Observations: the mood, Happy or Grumpy.
• The new probability this needs - the emission probability: P(observation | hidden state), for example P(Happy | Sunny).

The top row is an ordinary Markov chain that you cannot see. The bottom row is all you get. Every HMM question is about recovering something from the top row using only the bottom row.

HMM formalism

An HMM models a process as a first-order Markov chain of hidden states, with observations emitted from each state.

The parameters are $\lambda = (\pi, A, B)$, also written as the five-tuple {S, K, P, A, B}:

Symbol	Name	Meaning
S = {s₁…s_N}	Hidden states	the N hidden state values
K = {k₁…k_M}	Observations	the M observation values
π (or P) = {pᵢ}	Initial state probabilities	probability of starting in each hidden state
A = {aᵢⱼ}	Transition probabilities	P(state j at t+1 | state i at t)
B = {bᵢₖ}	Emission probabilities	P(observation k | hidden state i)

≡FactsThe two core assumptions

1. Markov assumption: the next state depends only on the current state.
2. The current observation depends only on the current state.

Both are the same slogan: "the past is independent of the future given the present."

⚠GotchaThe same observation can come from different states

Happy could mean Sunny or it could mean Rainy - the emission distributions overlap. That ambiguity is the entire complexity of an HMM. If observations identified states uniquely, the hidden layer would not be hidden and you would be back to a plain Markov chain.

The three HMM problems

#	Problem	Question	Algorithm
1	Likelihood (Evaluation)	Given λ, how likely is an observation sequence P(O|λ)?	Forward (or Backward) algorithm
2	Decoding	Given λ and O, what is the best hidden state sequence?	Viterbi algorithm
3	Learning	Given O, find the model λ = (A, B, π) that best explains it	Baum-Welch (EM)

◎Exam cueThree problems, three algorithms

Likelihood → Forward. Decoding → Viterbi. Learning → Baum-Welch. If a question asks "how likely", it is Forward. If it asks "which states", it is Viterbi. If it hands you observations and no model, it is Baum-Welch.

Warm-up questions from the weather story

#NumbersThe model for these questions

• Transitions: S→S 0.8, S→R 0.2, R→S 0.4, R→R 0.6.
• Emissions: P(Happy|S) = 0.8, P(Grumpy|S) = 0.2, P(Happy|R) = 0.4, P(Grumpy|R) = 0.6.

What is the probability that a random day is sunny or rainy?

This is the steady state: the distribution that the chain settles into and then stops changing.

→StepsSolving for the steady state

1. Write the balance equations from the transition probabilities: $S = 0.8S + 0.4R$ and $R = 0.2S + 0.6R$.
2. Add the normalisation $S + R = 1$, which is what makes the system solvable.
3. Substitute $R = 1 - S$ into the first equation: $S = 0.8S + 0.4(1 - S) = 0.4S + 0.4$.
4. Therefore $0.6S = 0.4$, giving $S = \mathbf{2/3}$ and $R = \mathbf{1/3}$.

If Vijay is Happy today, what is P(sunny)? P(rainy)?

Use Bayes with the steady-state values as the priors, $(2/3, 1/3)$, and the emission probabilities $(0.8, 0.4)$. The transition matrix is ignored here, because the question is about a single day in isolation.

→StepsOne day, one observation

1. Sunny branch: $P(\text{Happy} \mid S) \cdot P(S) = 0.8 \times 2/3 = 0.5333$.
2. Rainy branch: $P(\text{Happy} \mid R) \cdot P(R) = 0.4 \times 1/3 = 0.1333$.
3. Normalise by the total $0.6667$: $P(S \mid \text{Happy}) = \mathbf{0.8}$ and $P(R \mid \text{Happy}) = \mathbf{0.2}$.

If Happy, Grumpy, Happy over three days, what was the weather?

Now the transitions matter, because the answer is a sequence. The brute force method is to enumerate all $2^3 = 8$ state sequences, compute the joint probability of each, and pick the maximum.

◎Exam cueEight is fine, 2^T is not

Enumeration works for three days and is hopeless for thirty - the count is exponential in the sequence length. This is exactly what Viterbi does efficiently, in time linear in the sequence length, by keeping only the best path into each state at each step.