MediumNLPnlp-277

Viterbi Backpointer Count

Problem

Count distinct backpointers chosen in one Viterbi step. prev_scores maps previous states to log scores, transitions maps 'from to' keys to probabilities, and emissions maps current states to emission probabilities for the observed symbol.

A current state is reachable when its emission is positive and it has at least one positive incoming transition. Ties for the best predecessor are broken alphabetically. Return the number of distinct predecessors selected as a backpointer.

Hint

For each reachable current state keep its alphabetical argmax predecessor, then count the distinct choices.

Test cases

case 1

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

expected: 1

case 2

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

expected: 2

case 3

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

expected: 0

case 4

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

expected: 1

case 5

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

expected: 2

Starter codePython

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

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