Perplexity Calculator
Calculate the perplexity of a language model on a test sentence.
Perplexity measures how well a probability model predicts a sample: Perplexity=exp(−N1∑i=1NlogP(wi∣wi−1))
Where N is the number of tokens in the test sentence (including </s> but not <s>).
Use the same bigram model with Laplace smoothing as the N-Gram Language Model problem.
Input format:
- Line 1: Number of training sentences
- Following lines: Training sentences
- Last line: Test sentence
Output: Perplexity rounded to 4 decimal places.
Example:
2 the cat sat the dog sat the cat ran
3.1202
Build bigram model (same as N-Gram LM problem)
Test: <s> the cat ran </s> N = 4 tokens (the, cat, ran, </s>)
Compute log probs for each bigram, sum them, divide by -N, then exp.
Perplexity = exp(-log_prob_sum / N)
Constraints:
- N counts all tokens in test after <s> (including </s>)
- Use Laplace-smoothed bigram probabilities
- Use natural log and exp
- Round to 4 decimal places
Background Knowledge
Language Modeling is a fundamental task in Natural Language Processing (NLP) that involves predicting the next word in a sequence of words. A bigram model is a type of language model that predicts the next word based on the previous word. The probability of a word wi given the previous word wi−1 is denoted as P(wi∣wi−1). Laplace smoothing is a technique used to avoid zero probabilities by adding a small value to the numerator and denominator of the probability calculation.
The concept of perplexity is used to evaluate the performance of a language model. It measures how well the model predicts a sample of text. A lower perplexity indicates better performance. The perplexity calculation involves summing the log probabilities of each word in the test sentence and then exponentiating the average of these log probabilities. This calculation provides a measure of how well the model predicts the test sentence.
In the context of this problem, we need to calculate the perplexity of a language model on a test sentence using a bigram model with Laplace smoothing. This requires understanding the concepts of language modeling, bigram models, Laplace smoothing, and perplexity calculation. We also need to be familiar with the input and output formats specified in the problem description.
Algorithm/Approach
The general approach to solving this problem involves the following steps:
- Train a bigram model using the provided training sentences
- Calculate the probability of each word in the test sentence using the trained model and Laplace smoothing
- Calculate the perplexity of the test sentence using the log probabilities of each word
- Output the perplexity rounded to 4 decimal places
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.