Implement the Viterbi algorithm for a hidden Markov model tagger.
What to build
A program that finds the most probable tag sequence for each sentence and its probability.
Requirements
- The model gives start probabilities, a transition row for each tag (columns in tag order) and emission entries
TAG word p; any emission not listed is 0. Sentences are lowercased. - best(first word, t) = start(t) × emit(t, word). For each later word, best(t) = max over previous tags s of best(s) × trans(s, t), times emit(t, word); remember the s that gave the maximum.
- Choose the final tag with the highest best value and follow the back-pointers. Ties always go to the tag that comes first in the tag list.
- Print
word/TAG ...for the best sequence followed byp=Pwith six decimal places, orno pathif the best probability is 0.
Input
Line 1: the tags. Line 2: start probabilities. Then one transition row per tag. Then e and e emission lines. Then m and m sentences.
Output
m lines.
Constraints
At most 10 tags; sentences have at most 30 words.
Example
Input:
NOUN VERB DET
0.3 0.1 0.6
0.2 0.7 0.1
0.3 0.1 0.6
0.9 0.05 0.05
8
NOUN dog 0.4
NOUN can 0.2
NOUN fish 0.4
VERB can 0.5
VERB fish 0.3
VERB runs 0.2
DET the 0.9
DET a 0.1
2
the dog can fish
the can
Output:
the/DET dog/NOUN can/VERB fish/NOUN p=0.008165
the/DET can/NOUN p=0.097200
Why it works
Any best path ending in tag t at word i must extend a best path ending in some tag at word i − 1, so keeping only the best path into each tag (dynamic programming) finds the overall best sequence without trying every combination.
Examples
NOUN VERB DET 0.3 0.1 0.6 0.2 0.7 0.1 0.3 0.1 0.6 0.9 0.05 0.05 8 NOUN dog 0.4 NOUN can 0.2 NOUN fish 0.4 VERB can 0.5 VERB fish 0.3 VERB runs 0.2 DET the 0.9 DET a 0.1 2 the dog can fish the can
the/DET dog/NOUN can/VERB fish/NOUN p=0.008165 the/DET can/NOUN p=0.097200
A B 0.5 0.5 0.9 0.1 0.1 0.9 4 A x 0.6 B x 0.4 A y 0.1 B y 0.9 1 x y
x/B y/B p=0.162000
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Keep one dictionary per word: the best path probability into each tag, plus a dictionary of back-pointers.
Hint 2
Loop over the previous tags in list order and replace the best only when a score is strictly larger; that makes ties go to the earlier tag.
Solution
Show one correct solution (try it yourself first)
tags = input().split()
start = dict(zip(tags, map(float, input().split())))
trans = {a: dict(zip(tags, map(float, input().split()))) for a in tags}
emit = {t: {} for t in tags}
for _ in range(int(input())):
t, w, p = input().split()
emit[t][w] = float(p)
for _ in range(int(input())):
words = input().lower().split()
best = [{t: start[t] * emit[t].get(words[0], 0.0) for t in tags}]
back = []
for w in words[1:]:
col, ptr = {}, {}
for t in tags:
top, src = -1.0, tags[0]
for s in tags:
score = best[-1][s] * trans[s][t]
if score > top:
top, src = score, s
col[t] = top * emit[t].get(w, 0.0)
ptr[t] = src
best.append(col)
back.append(ptr)
last = max(tags, key=lambda t: best[-1][t])
if best[-1][last] == 0:
print("no path")
continue
path = [last]
for ptr in reversed(back):
path.append(ptr[path[-1]])
path.reverse()
print(" ".join(f"{w}/{t}" for w, t in zip(words, path)), f"p={best[-1][last]:.6f}")