Tagging with Hidden Markov Models

Book is a noun in, read the book. And it's a verb in, book the table. So how does a computer tell them apart? You look at the neighbours. And the algorithm that does this was invented for sending signals through noisy telephone lines, in nineteen sixty seven. Today, it's still in your phone.

• 'Book' can be a noun or a verb
• Look at the neighbours
• Invented for telephone lines

Finding the best path

The start table says how sentences tend to begin. The transition table says which tags follow which. After a determiner, a noun is very likely. And the emission table says which words each tag produces. Viterbi walks along the sentence, and for each tag, it keeps only the best path so far. Run it. In, book the dog, book is a verb. In, the book reads, the same word is a noun. It worked that out only from the surrounding tags. That's the power of a sequence model. Rather than deciding one word at a time, it finds the best whole path.

import numpy as np

tags = ["DET", "NOUN", "VERB"]
start = {"DET": .7, "NOUN": .2, "VERB": .1}
trans = {"DET": {"DET": .01, "NOUN": .95, "VERB": .04},
         "NOUN": {"DET": .1, "NOUN": .3, "VERB": .6},
         "VERB": {"DET": .6, "NOUN": .3, "VERB": .1}}
emit = {"DET": {"the": .9, "a": .1},
        "NOUN": {"dog": .4, "book": .4, "bark": .2},
        "VERB": {"book": .3, "bark": .5, "reads": .2}}

def viterbi(words):
    best = {t: (np.log(start[t] * emit[t].get(words[0], 1e-6)), [t]) for t in tags}
    for w in words[1:]:
        best = {t: max((best[p][0] + np.log(trans[p][t] * emit[t].get(w, 1e-6)), best[p][1] + [t])
                       for p in tags) for t in tags}
    return max(best.values())[1]

print(viterbi("the dog bark".split()))
print(viterbi("book the dog".split()))
print(viterbi("the book reads".split()))

['DET', 'NOUN', 'VERB']
['VERB', 'DET', 'NOUN']
['DET', 'NOUN', 'VERB']

Sequence thinking

Viterbi has a huge family. It decodes speech and mobile signals. Conditional random fields use the same trick, and they often sit on top of neural taggers. The beam search that large language models use is a close cousin too. Whenever each choice depends on the last one, think about finding the best path, rather than the best step.

Summary