HardNLPnlp-124

Forward Algorithm Step

Problem

Perform one forward algorithm step. alpha_prev maps each state to its previous alpha value, transitions maps 'from to' keys to probabilities, and emissions maps each state to the emission probability of the current observation.

Return new alpha values as a dictionary: alpha[j] = emissions[j] * sum over i of alpha_prev[i] * transition(i, j).

Hint

Sum the incoming probability mass over all previous states, then multiply by the emission.

Test cases

case 1

in: [{"A":0.6,"B":0.4},{"A X":0.5,"A Y":0.5,"B X":0.25,"B Y":0.75},{"X":0.8,"Y":0.2}]

expected: {"X":0.32000000000000006,"Y":0.12000000000000002}

case 2

in: [{"A":1},{"A B":0.3},{"B":0.5}]

expected: {"B":0.15}

case 3

in: [{"A":1},{"A X":1},{"X":0}]

expected: {"X":0}

case 4

in: [{},{"A X":0.5},{"X":0.8}]

expected: {"X":0}

Starter codePython

def forward_step(alpha_prev, transitions, emissions):
    # Your code here
    pass

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