Perplexity of a sentence

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) = P with 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

Example 1 · Input
3
the cat 0.5
cat sat 0.25
sat . 1.0
the cat sat .
Expected output
P(cat | the) = 0.5000
P(sat | cat) = 0.2500
P(. | sat) = 1.0000
average loss 0.6931
perplexity 2.00
Example 2 · Input
1
a b 0.1
a b
Expected output
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}")

Lesson: Next-token prediction →