NLP: Estimate HMM probabilities

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 state START, and every tag is a transition from the previous tag (or from START).
  • Query T prev tag: print P(tag | prev) = c/t = X, where c counts prev → tag transitions and t all transitions leaving prev.
  • Query E tag word: print P(word | tag) = c/t = X with 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 seen instead.

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

Example 1 · 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
Expected 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
Example 2 · Input
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
Expected output
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")

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