N-Gram Language Model

mediumPROLanguage ModelingNLP 3: Advanced

Build a bigram language model and compute the probability of a sentence.

Training: From the training text, count bigram frequencies and compute: $P(w_i | w_{i-1}) = \frac{\text{count}(w_{i-1}, w_i)}{\text{count}(w_{i-1})}$

Use Laplace smoothing: $P(w_i | w_{i-1}) = \frac{\text{count}(w_{i-1}, w_i) + 1}{\text{count}(w_{i-1}) + V}$

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

Input

2
i love nlp
i love coding
i love nlp

Output

-3.6636

Reasoning

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

Learn this in

Probability & StatisticsFoundations Introduction to LLMsLLM Study Plan Text RepresentationNLP Study Plan Language ModelingNLP Study Plan

More from NLP 3: Advanced

Temperature Samplereasy ROUGE-1 Score Calculatoreasy Context Window Findereasy Keyword Answer Extractoreasy Levenshtein Distanceeasy

Concept primerPREVIEW

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 $w_i$ given the previous word $w_{i-1}$ is calculated using the formula $P(w_i | w_{i-1}) = \frac{\text{count}(w_{i-1}, w_i)}{\text{count}(w_{i-1})}$ . 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.

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

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.

solution.py

Python 3.13

Test results