Decide which of two language models predicts new sentences better.
What to build
A program that computes add-one unigram and add-one bigram perplexity for test sentences.
Requirements
- Lowercase and split sentences, and add
<s>and</s>. N is the number of training tokens other than<s>; V is the number of distinct training tokens other than<s>. - Unigram model: P(w) = (count(w) + 1) ÷ (N + V). Bigram model: P(w given prev) = (count(prev w) + 1) ÷ (count(prev) + V), where count(prev) is the number of training pairs starting with prev. Both predict every token after
<s>, including</s>. - For each test sentence print
unigram U bigram B better: Mwith the two perplexities to two decimal places, where M isbigramorunigram, whichever perplexity is lower (tieif they are exactly equal).
Input
Line 1: n. Then n training sentences. Then m and m test sentences.
Output
m lines.
Constraints
n ≤ 500; m ≤ 100.
Example
Input:
2
a b
a b
2
a b
b a
Output:
unigram 3.00 bigram 1.67 better: bigram
unigram 3.00 bigram 5.00 better: unigram
Why it works
Perplexity is the inverse of the geometric mean probability per token, so the model that gives the test sentence's actual tokens higher probability has the lower perplexity; context helps the bigram model only when the test text uses familiar word pairs.
Examples
2 a b a b 2 a b b a
unigram 3.00 bigram 1.67 better: bigram unigram 3.00 bigram 5.00 better: unigram
2 i like tea i like coffee 1 i like tea
unigram 4.80 bigram 2.75 better: bigram
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Unigram: P(w) = (count(w) + 1) / (N + V), where N counts every training token after `<s>` (including `</s>`). Bigram: (count(prev w) + 1) / (count(prev) + V).
Hint 2
Perplexity = `math.exp(-log_sum / m)`, where m is the number of predicted tokens: the words of the sentence plus `</s>`.
Solution
Show one correct solution (try it yourself first)
import math
uni, contexts, pairs, total = {}, {}, {}, 0
for _ in range(int(input())):
words = ["<s>"] + input().lower().split() + ["</s>"]
for prev, w in zip(words, words[1:]):
uni[w] = uni.get(w, 0) + 1
total += 1
contexts[prev] = contexts.get(prev, 0) + 1
pairs[(prev, w)] = pairs.get((prev, w), 0) + 1
V = len(uni)
for _ in range(int(input())):
words = ["<s>"] + input().lower().split() + ["</s>"]
lu = lb = 0.0
for prev, w in zip(words, words[1:]):
lu += math.log((uni.get(w, 0) + 1) / (total + V))
lb += math.log((pairs.get((prev, w), 0) + 1) / (contexts.get(prev, 0) + V))
m = len(words) - 1
pu, pb = math.exp(-lu / m), math.exp(-lb / m)
better = "bigram" if pb < pu else "unigram" if pu < pb else "tie"
print(f"unigram {pu:.2f} bigram {pb:.2f} better: {better}")