HardNLPnlp-278

Viterbi Best Path Score

Problem

Return the log score of the best Viterbi path through an HMM. observations is the list of observed symbols, states lists the hidden states, start_probs maps states to initial probabilities, transitions maps 'from to' keys to transition probabilities, and emissions maps each state to a dictionary of symbol probabilities.

Run max-product dynamic programming in log space and return the maximum final score, or float('-inf') when no path exists.

Hint

Scores are log probabilities, so multiply by adding and choose the best predecessor with max.

Test cases

case 1

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

expected: -0.6931471805599453

case 2

in: [["x","y"],["A","B"],{"A":0.6,"B":0.4},{"A A":0.7,"A B":0.3,"B A":0.4,"B B":0.6},{"A":{"x":0.9,"y":0.2},"B":{"x":0.5,"y":0.8}}]

expected: -2.043302495063963

case 3

in: [["a"],["S"],{"S":0.5},{},{"S":{"a":1}}]

expected: -0.6931471805599453

case 4

in: [["x","y","x"],["A","B"],{"A":1,"B":0},{"A A":0.5,"A B":0.5,"B A":0.8,"B B":0.2},{"A":{"x":0.9,"y":0.1},"B":{"x":0.2,"y":0.8}}]

expected: -1.3501553145040173

case 5

in: [[],["A"],{"A":1},{},{"A":{"x":1}}]

expected: 0

Starter codePython

import math
def viterbi_best_path_score(observations, states, start_probs, transitions, emissions):
    # Your code here
    pass

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