Hidden Markov Models: Forward and Viterbi

A hidden Markov model has hidden states that follow a Markov chain and emit observations. With initial probabilities pi: (S,), transitions A: (S, S) (A[i, j] = P(next = j | current = i)) and emissions B: (S, O):

• the forward algorithm computes the probability of an observation sequence by summing over all hidden paths
• the Viterbi algorithm finds the single most likely hidden path