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, printP(word | prev) = c/t = Xwhere 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}")