Perplexity tells how surprised a model is by real text. Compute it for a sentence under a bigram model.
What to build
A program that scores a sentence with a table of next-word probabilities and reports its average loss and perplexity.
Requirements
- For each pair of neighbouring words, print
P(NEXT | PREV) = Pwith 4 decimal places; a pair missing from the table has probability 0.000001. - Print
average loss L(the mean of −ln P) with 4 decimal places. - Print
perplexity X, e^L, with 2 decimal places.
Input
Line 1: m. Then m lines prev next probability. Then a line with the sentence (at least 2 words).
Output
One line per pair, then two lines.
Constraints
1 ≤ m ≤ 10,000; 2 to 1000 words in the sentence; probabilities are greater than 0 and at most 1.
Example
Input:
3
the cat 0.5
cat sat 0.25
sat . 1.0
the cat sat .
Output:
P(cat | the) = 0.5000
P(sat | cat) = 0.2500
P(. | sat) = 1.0000
average loss 0.6931
perplexity 2.00
Why it works
The average negative log probability is the cross-entropy of the model on this text; raising e to it gives the size of an equally uncertain uniform choice, which is easier to read.
Examples
3 the cat 0.5 cat sat 0.25 sat . 1.0 the cat sat .
P(cat | the) = 0.5000 P(sat | cat) = 0.2500 P(. | sat) = 1.0000 average loss 0.6931 perplexity 2.00
1 a b 0.1 a b
P(b | a) = 0.1000 average loss 2.3026 perplexity 10.00
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Store the pair probabilities in a dictionary keyed by (previous, next); a missing pair has probability 0.000001.
Hint 2
Each step's loss is −ln p; average the losses over the steps.
Hint 3
Perplexity is e raised to the average loss.
Solution
Show one correct solution (try it yourself first)
import math
m = int(input())
table = {}
for _ in range(m):
a, b, p = input().split()
table[(a, b)] = float(p)
words = input().split()
losses = []
for a, b in zip(words, words[1:]):
p = table.get((a, b), 0.000001)
print(f"P({b} | {a}) = {p:.4f}")
losses.append(-math.log(p))
average = sum(losses) / len(losses)
print(f"average loss {average:.4f}")
print(f"perplexity {math.exp(average):.2f}")