Estimate the tables of a hidden Markov model tagger by counting a tagged corpus.
What to build
A program that answers transition and emission probability queries from tagged sentences.
Requirements
- Training items are
word/TAG(the tag after the last/); words are lowercased. Each sentence starts from the stateSTART, and every tag is a transition from the previous tag (or from START). - Query
T prev tag: printP(tag | prev) = c/t = X, where c counts prev → tag transitions and t all transitions leaving prev. - Query
E tag word: printP(word | tag) = c/t = Xwith the word lowercased, where c counts the word with that tag and t all uses of the tag. - X has four decimal places. If t is 0, print
P(... | ...): never seeninstead.
Input
Line 1: n. Then n tagged sentences. Then q and q queries.
Output
q lines.
Constraints
n ≤ 1,000; q ≤ 100.
Example
Input:
2
the/DET dog/NOUN barks/VERB
the/DET cat/NOUN sleeps/VERB
4
T START DET
T DET NOUN
E NOUN dog
E VERB runs
Output:
P(DET | START) = 2/2 = 1.0000
P(NOUN | DET) = 2/2 = 1.0000
P(dog | NOUN) = 1/2 = 0.5000
P(runs | VERB) = 0/2 = 0.0000
Why it works
Maximum-likelihood estimates are relative frequencies: how often prev is followed by tag among everything that follows prev, and how often a tag produces a word among all its uses.
Examples
2 the/DET dog/NOUN barks/VERB the/DET cat/NOUN sleeps/VERB 4 T START DET T DET NOUN E NOUN dog E VERB runs
P(DET | START) = 2/2 = 1.0000 P(NOUN | DET) = 2/2 = 1.0000 P(dog | NOUN) = 1/2 = 0.5000 P(runs | VERB) = 0/2 = 0.0000
3 they/PRON can/AUX fish/VERB fish/NOUN swim/VERB I/PRON fish/VERB 3 T PRON VERB T START NOUN E VERB FISH
P(VERB | PRON) = 1/2 = 0.5000 P(NOUN | START) = 1/3 = 0.3333 P(fish | VERB) = 2/3 = 0.6667
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Walk through each sentence with `prev = "START"`, counting (prev, tag) transitions and (tag, word) emissions, then set `prev = tag`.
Hint 2
A transition's denominator is the number of transitions that leave prev; an emission's denominator is the number of times the tag is used.
Solution
Show one correct solution (try it yourself first)
n = int(input())
trans, emit, leaving, tag_counts = {}, {}, {}, {}
for _ in range(n):
prev = "START"
for item in input().split():
word, tag = item.rsplit("/", 1)
word = word.lower()
trans[(prev, tag)] = trans.get((prev, tag), 0) + 1
leaving[prev] = leaving.get(prev, 0) + 1
emit[(tag, word)] = emit.get((tag, word), 0) + 1
tag_counts[tag] = tag_counts.get(tag, 0) + 1
prev = tag
for _ in range(int(input())):
kind, a, b = input().split()
if kind == "T":
c, total, name = trans.get((a, b), 0), leaving.get(a, 0), f"P({b} | {a})"
else:
b = b.lower()
c, total, name = emit.get((a, b), 0), tag_counts.get(a, 0), f"P({b} | {a})"
print(f"{name} = {c}/{total} = {c / total:.4f}" if total else f"{name}: never seen")