HMM Forward Message

Problem

Compute the unnormalized forward message of a hidden Markov model. Start with alpha[0][i] = initial[i] * emissions[0][i], then iterate alpha[t][j] = emissions[t][j] times the sum over i of alpha[t-1][i] * transition[i][j]. Return the final alpha vector, or initial itself when there are no emission rows; return an empty list for mismatched shapes.

Hint

Each step propagates the message through the transition matrix, then multiplies by the emission.

Test cases

case 1

in: [[0.6,0.4],[[0.7,0.3],[0.4,0.6]],[[0.5,0.5]]]

expected: [0.3,0.2]

case 2

in: [[0.6,0.4],[[0.7,0.3],[0.4,0.6]],[[0.5,0.5],[0.9,0.1]]]

expected: [0.26100000000000007,0.021]

case 3

in: [[0.6,0.4],[[0.7,0.3],[0.4,0.6]],[]]

expected: [0.6,0.4]

case 4

in: [[1,0],[[1,0],[0,1]],[[0.2,0.8],[0.5,0.5],[1,1]]]

expected: [0.1,0]

case 5

in: [[0.5,0.5],[[0.9,0.1]],[[0.5,0.5]]]

expected: []

Starter codePython

def hmm_forward_message(initial, transition, emissions):
    # Your code here
    pass

5 test cases · run your code against them in the editor