HardNLPnlp-121

Viterbi POS Step

Problem

Perform one Viterbi step over a hidden Markov model. prev_scores maps each previous state to its best log score, transitions maps 'from to' keys to probabilities, and emissions maps each current state to the emission probability of the observed symbol.

Return [best_state, best_score], the current state maximizing prev score + log transition + log emission, breaking ties alphabetically. Return ['', float('-inf')] when no state is reachable.

Hint

Scores are log-space, so combine them by addition; skip zero-probability states.

Test cases

case 1

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

expected: ["X",-1.416290731874155]

case 2

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

expected: ["B",-1.8971199848858813]

case 3

in: [{"A":0},{"A B":0.5},{"A":0,"B":0.5}]

expected: ["B",-1.3862943611198906]

case 4

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

expected: ["X",-0.6931471805599453]

Starter codePython

import math
def viterbi_step(prev_scores, transitions, emissions):
    # Your code here
    pass

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