NLP: Compare models by perplexity

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: M with the two perplexities to two decimal places, where M is bigram or unigram, whichever perplexity is lower (tie if 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

Example 1 · Input
2
a b
a b
2
a b
b a
Expected output
unigram 3.00 bigram 1.67 better: bigram
unigram 3.00 bigram 5.00 better: unigram
Example 2 · Input
2
i like tea
i like coffee
1
i like tea
Expected output
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}")

Lesson: Language models and smoothing →