HMM forward algorithm for sequence likelihood

Probability of an observation sequence under an HMM

A hidden Markov model has initial probabilities pi (length K), a transition matrix A (K by K, row i gives p(next state j | state i)), and an emission matrix B (K by M, row i gives p(symbol m | state i)). Observations are integers in 0..M-1.

The forward recursion computes p(obs) without enumerating state paths:

• alpha_0(i) = pi_i * B[i, o_0]
• alpha_t(j) = (sum_i alpha_(t-1)(i) A[i, j]) * B[j, o_t]
• p(obs) = sum_i alpha_(T-1)(i)

Implement forward_likelihood(pi, A, B, obs) and return p(obs) as a float.

Constraints

• pi sums to 1. Each row of A and of B sums to 1. All entries are nonnegative.
• Each observation must be an integer in 0..M-1. Otherwise raise ValueError.
• The observation sequence must not be empty.
• Shape mismatches raise ValueError.
• Do not modify the inputs.

Hints