HardNLPnlp-125

Backward Algorithm Step

Problem

Perform one backward algorithm step. states lists the current states to compute beta for, beta_next maps each next state to its beta value, transitions maps 'from to' keys to probabilities, and emissions maps each next state to the emission probability of the observation at the next time step.

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

Hint

Each current state's beta sums over all possible next states weighted by transition, emission, and the next beta.

Test cases

case 1

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

expected: {"A":0.45,"B":0.275}

case 2

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

expected: {"A":0.2}

case 3

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

expected: {"A":0}

case 4

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

expected: {"A":0,"B":0}

Starter codePython

def backward_step(states, beta_next, transitions, emissions):
    # Your code here
    pass

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