NLP: Bigram probabilities

Estimate the conditional probabilities of a bigram language model.

What to build

A program that trains bigram counts and answers probability queries.

Requirements

  • Lowercase each training sentence, split it on whitespace and add <s> at the start and </s> at the end.
  • For each query prev word, print P(word | prev) = c/t = X where c is the count of the pair, t the number of pairs that start with prev, and X = c ÷ t with four decimal places.
  • If prev never starts a pair, print P(word | prev): unknown context.

Input

Line 1: n. Then n sentences. Then q and q queries; a query may use the markers <s> and </s>.

Output

q lines.

Constraints

n ≤ 500; q ≤ 100.

Example

Input:

3
I like green tea
I like black tea
you like green apples
3
<s> i
like green
tea </s>

Output:

P(i | <s>) = 2/3 = 0.6667
P(green | like) = 2/3 = 0.6667
P(</s> | tea) = 2/2 = 1.0000

Why it works

The maximum-likelihood estimate of a conditional probability is the fraction of times prev was followed by word, which is exactly the pair count divided by the context count.

Examples

Example 1 · Input
3
I like green tea
I like black tea
you like green apples
3
<s> i
like green
tea </s>
Expected output
P(i | <s>) = 2/3 = 0.6667
P(green | like) = 2/3 = 0.6667
P(</s> | tea) = 2/2 = 1.0000
Example 2 · Input
1
a b a b
3
a b
b a
b c
Expected output
P(b | a) = 2/2 = 1.0000
P(a | b) = 1/2 = 0.5000
P(c | b) = 0/2 = 0.0000

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Wrap each sentence as `["<s>"] + words + ["</s>"]` and count every neighbouring pair and every word used as the first of a pair.

Hint 2

P(word given prev) = count(prev word) / count(prev as the first of a pair).

Solution

Show one correct solution (try it yourself first)
n = int(input())
contexts, pairs = {}, {}
for _ in range(n):
    words = ["<s>"] + input().lower().split() + ["</s>"]
    for prev, w in zip(words, words[1:]):
        contexts[prev] = contexts.get(prev, 0) + 1
        pairs[(prev, w)] = pairs.get((prev, w), 0) + 1
for _ in range(int(input())):
    prev, w = input().split()
    if prev not in contexts:
        print(f"P({w} | {prev}): unknown context")
        continue
    c = pairs.get((prev, w), 0)
    print(f"P({w} | {prev}) = {c}/{contexts[prev]} = {c / contexts[prev]:.4f}")

Lesson: Language models and smoothing →