HMM Forward Algorithm

Compute the log likelihood of an observation sequence under a hidden Markov model, with the forward algorithm.

An HMM has hidden states that follow a Markov chain, and each state emits an observed symbol. It is defined by:

• pi, shape (n_states,): the start probabilities
• A, shape (n_states, n_states): A[i, j] is the probability of moving from state i to state j
• B, shape (n_states, n_symbols): B[i, k] is the probability that state i emits symbol k

The probability of the observations sums over every possible hidden path. There are exponentially many paths, but the forward algorithm sums them in O(T * n_states^2) with the recursion

alpha_0[j]   = pi[j] * B[j, obs[0]]
alpha_t[j]   = (sum_i alpha_{t-1}[i] * A[i, j]) * B[j, obs[t]]
P(obs)       = sum_j alpha_{T-1}[j]

Return log P(obs). On long sequences the alphas become too small for floating point, so rescale them at each step and add up the logs of the scale factors.

Function signature

def hmm_forward(pi, A, B, obs):

Example

Input

pi = np.array([0.5, 0.5])
A  = np.array([[0.8, 0.2], [0.3, 0.7]])
B  = np.array([[0.6, 0.3, 0.1], [0.1, 0.4, 0.5]])
hmm_forward(pi, A, B, [0, 2, 1])

Output

-3.659903

Reasoning

The first alpha is [0.5 * 0.6, 0.5 * 0.1] = [0.3, 0.05]. After symbol 2 it is [0.0255, 0.0475], and after symbol 1 it is [0.010395, 0.01534]. The sum is 0.025735, and log(0.025735) = -3.6599.

Constraints and notes

• obs is a list or array of symbol indices with length at least 1.
• Use the natural log.
• Your function must stay finite on a sequence of 2000 symbols.