NLP: Add-k smoothed sentence probability

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 = X per 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

Example 1 · Input
1
2
i like tea
you like tea
2
i like tea
you like coffee
Expected output
log P = -4.0460
log P = -5.9067
Example 2 · Input
0.5
1
a b
1
a b
Expected output
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}")

Lesson: Language models and smoothing →