Score sentences with a smoothed bigram model, so that unseen word pairs no longer give zero.
What to build
A program that trains an add-k bigram model and prints the log probability of test sentences.
Requirements
- Lowercase and split sentences on whitespace, and add
<s>and</s>to training and test sentences alike. - For each pair (prev, w) of a test sentence, P = (count(prev w) + k) ÷ (count(prev) + k × V), where count(prev) is the number of training pairs starting with prev and V is the number of distinct tokens other than
<s>in the training sentences (</s>included). - Print
log P = Xper test sentence: the natural log of the sentence probability (the sum of the logs), with four decimal places.
Input
Line 1: k. Line 2: n. Then n training sentences. Then m and m test sentences.
Output
m lines.
Constraints
n ≤ 500; m ≤ 100; k > 0.
Example
Input:
1
2
i like tea
you like tea
2
i like tea
you like coffee
Output:
log P = -4.0460
log P = -5.9067
Why it works
Adding k to every pair count and k × V to every total keeps each conditional distribution summing to 1 while giving unseen pairs a small probability, so no sentence is impossible.
Examples
1 2 i like tea you like tea 2 i like tea you like coffee
log P = -4.0460 log P = -5.9067
0.5 1 a b 1 a b
log P = -1.5325
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
V is the number of distinct tokens that appear after something in training: every word plus `</s>`, but not `<s>`.
Hint 2
P = (count(prev w) + k) / (count(prev) + k × V); a context never seen in training has count 0. Sum `math.log(P)` over the pairs.
Solution
Show one correct solution (try it yourself first)
import math
k = float(input())
contexts, pairs, vocab = {}, {}, []
for _ in range(int(input())):
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
if w not in vocab:
vocab.append(w)
V = len(vocab)
for _ in range(int(input())):
words = ["<s>"] + input().lower().split() + ["</s>"]
logp = 0.0
for prev, w in zip(words, words[1:]):
logp += math.log((pairs.get((prev, w), 0) + k) / (contexts.get(prev, 0) + k * V))
print(f"log P = {logp:.4f}")