N-Gram Language Model
Build a bigram language model and compute the probability of a sentence.
Training: From the training text, count bigram frequencies and compute: P(wi​∣wi−1​)=count(wi−1​)count(wi−1​,wi​)​
Use Laplace smoothing: P(wi​∣wi−1​)=count(wi−1​)+Vcount(wi−1​,wi​)+1​
Where V is the vocabulary size (unique words in training).
Add special tokens: <s> for sentence start and </s> for sentence end.
Input format:
- Line 1: Number of training sentences N
- Lines 2 to N+1: Training sentences (lowercase words)
- Line N+2: Test sentence (lowercase words)
Output: Log probability (base e) of the test sentence, rounded to 4 decimal places.
Example:
2 i love nlp i love coding i love nlp
-3.6636
Training with <s> and </s>:
- <s> i love nlp </s>
- <s> i love coding </s>
Vocabulary: {<s>, i, love, nlp, coding, </s>} => V = 6
Bigram counts:
- (<s>, i): 2, count(<s>): 2 => P(i|<s>) = (2+1)/(2+6) = 3/8
- (i, love): 2, count(i): 2 => P(love|i) = 3/8
- (love, nlp): 1, count(love): 2 => P(nlp|love) = 2/8
- (nlp, </s>): 1, count(nlp): 1 => P(</s>|nlp) = 2/7
Test: <s> i love nlp </s> log P = log(3/8) + log(3/8) + log(2/8) + log(2/7) = -0.9808 + -0.9808 + -1.3863 + -1.2528 = ...
Constraints:
- Add <s> at start and </s> at end of each sentence
- Include <s> and </s> in vocabulary count
- Use Laplace smoothing (add-1)
- Use natural log
- Compute: sum of log P(w_i | w_{i-1}) for each bigram in test sentence
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 language model is a simple type of language model that predicts the next word based on the current word. The probability of a word wi​ given the previous word wi−1​ is calculated using the formula P(wi​∣wi−1​)=count(wi−1​)count(wi−1​,wi​)​. However, this approach can result in zero probability for unseen word pairs, which can be problematic. To address this issue, Laplace smoothing is used, which adds a small value to the numerator and denominator to ensure that all word pairs have a non-zero probability.
In the context of language modeling, vocabulary size (V) refers to the number of unique words in the training data. The special tokens <s> and </s> are used to mark the start and end of a sentence, respectively. These tokens are essential in language modeling as they provide a clear indication of the sentence boundaries. The log probability of a sentence is calculated by summing the log probabilities of each word in the sentence, given the previous word. This is done to avoid underflow issues that can arise when multiplying small probabilities together.
The N-Gram Language Model is a statistical model that predicts the next word in a sequence based on the context of the previous n words. In this problem, we are dealing with a bigram language model, where n=2. The goal is to compute the probability of a sentence using the bigram language model and Laplace smoothing. This involves counting the frequencies of word pairs in the training data, computing the probabilities using the formula, and then calculating the log probability of the test sentence.
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.