Hidden Structure
Tagging with Viterbi.
The word book can be a noun or a verb. To decide which, a tagger has to look at the whole sentence. Trying every combination would be impossibly slow, even for a short sentence. In nineteen sixty seven, Andrew Viterbi found a shortcut, which is now in every mobile phone on Earth.
- Book: noun or verb?
- Every combination is too slow
- Viterbi's shortcut
One word, many roles
Here's the problem in action. The same word is used in three sentences. Run it. SpaCy tags book as a verb, a noun, and a verb, purely from context. How can a program do that? Neighbouring tags help. After the word a, a noun is much more likely than a verb.
import spacy
nlp = spacy.load("en_core_web_sm")
for text in ["I book a flight.", "I read a book.", "Book the table."]:
print([(t.text, t.pos_) for t in nlp(text) if t.lower_ == "book"], text)[('book', 'VERB')] I book a flight.
[('book', 'NOUN')] I read a book.
[('Book', 'NOUN')] Book the table.The Viterbi algorithm
A hidden Markov model has two tables. How likely each tag is to follow another, and how likely each tag is to produce each word. Viterbi walks left to right, and at each step, it keeps only the best path to each tag. That turns an explosion of possibilities into simple steps. Run it. It finds that fish is a verb after people, and a noun before swim. The same word, tagged correctly by the sentence around it.
import numpy as np
tags = ["NOUN", "VERB"]
start = np.array([0.7, 0.3])
trans = np.array([[0.3, 0.7],
[0.8, 0.2]])
emit = {"fish": [0.7, 0.3], "swim": [0.2, 0.8], "people": [0.9, 0.1]}
def viterbi(words):
v = start * emit[words[0]]
back = []
for w in words[1:]:
scores = v[:, None] * trans * np.array(emit[w])
back.append(scores.argmax(0))
v = scores.max(0)
path = [int(v.argmax())]
for b in reversed(back):
path.append(int(b[path[-1]]))
return [tags[i] for i in reversed(path)]
for s in ["people fish", "fish swim", "people swim"]:
print(s, "->", viterbi(s.split()))people fish -> ['NOUN', 'NOUN'] fish swim -> ['NOUN', 'VERB'] people swim -> ['NOUN', 'VERB']
Fixing spelling
Here's one more classic that you use every day. How does a spell checker work? It generates every word within one edit of the typo, by removing, swapping, replacing, or adding a letter. Then it picks the most common real word. That's counting again. Run it. Four misspellings fixed, using nothing more than word frequencies from some medical discussion posts. A few lines, and it works surprisingly well.
import re
from collections import Counter
from sklearn.datasets import fetch_20newsgroups
text = " ".join(fetch_20newsgroups(subset="train", categories=["sci.med"]).data).lower()
freq = Counter(re.findall(r"[a-z]+", text))
letters = "abcdefghijklmnopqrstuvwxyz"
def edits(w):
split = [(w[:i], w[i:]) for i in range(len(w) + 1)]
gone = [a + b[1:] for a, b in split if b]
swap = [a + b[1] + b[0] + b[2:] for a, b in split if len(b) > 1]
sub = [a + c + b[1:] for a, b in split if b for c in letters]
add = [a + c + b for a, b in split for c in letters]
return set(gone + swap + sub + add)
def fix(w):
if w in freq:
return w
return max((e for e in edits(w) if e in freq), key=freq.get, default=w)
for w in ["docter", "medecine", "paitent", "helth"]:
print(f"{w:<10} -> {fix(w)}")docter -> doctor medecine -> medicine paitent -> patient helth -> health
Summary
Viterbi finds the best path, and counting fixes spelling. Those classics still run all around you. Next, back to Scribe, and a very practical job. Pulling out the important words and the key points from a long document, with no language model at all.
Key takeaways- Context resolves ambiguity
- Viterbi keeps the best path
- Spell check: edits plus counts