NLP: Tag a sentence with Viterbi

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 by p=P with six decimal places, or no path if 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

Example 1 · 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
Expected output
the/DET dog/NOUN can/VERB fish/NOUN p=0.008165
the/DET can/NOUN p=0.097200
Example 2 · Input
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
Expected output
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}")

Lesson: Part-of-speech tagging with an HMM →