PROBLEM $1$: N$-$gram language models $(35$ points$)$

$1.$ Build a bigram language model on the whole Brown corpus and calculate the probability of the sentence: "The dog barked at the cat.". $(15$ points$)$

Note: To calculate the probability of a sentence, the start token $$ and end token $$ should be considered.

$2.$ Apply Laplace smoothing $($add$-$one smoothing$)$ to the bigram language model and calculate the probilitily of the sentence: $$The dog barked at the cat.$.(10$ points$)$

$3.$ Predict the most probable next $5$ words of the sentence prefix $$I won $200$ using the bigram model. $(10$ points$)$

Template code:

# Bigram Language Model Template

$"""$

This template will help you build a bigram language model using the NLTK library.

You will preprocess the corpus, build the bigram model, calculate probabilities,

and predict the next words given a sentence prefix.

$"""$

import nltk

from nltk import bigrams

from nltk$.$tokenize import word$\_$tokenize

from nltk$.$corpus import brown

from collections import defaultdict, Counter

# Download required NLTK resources if not already downloaded

nltk$.$download$(\text{'}$punkt$\text{'})$

nltk$.$download$(\text{'}$brown$\text{'})$

# Preprocess the corpus: Tokenize, lowercase, and add start$/$end tokens

def preprocess$($corpus$)$:

$"""$

Preprocess the corpus by tokenizing, converting to lowercase, and adding and tokens.

Args:

corpus $($list$)$: List of sentences from the corpus.

Returns:

list: Preprocessed and tokenized corpus.

$"""$

tokenized$\_$corpus $=[]$

for sentence in corpus:

# TODO: Tokenize and lowercase the sentence

# HINT: Use list comprehension and str$.$lower$()$

# TODO: Add $\text{'}\text{'}$ at the start and $\text{'}\text{'}$ at the end of the sentence

pass # Remove this line after implementing

return tokenized$\_$corpus

# Build the bigram model: Create frequency distributions for unigrams and bigrams

def build$\_$bigram$\_$model$($tokenized$\_$corpus$)$:

$"""$

Build bigram and unigram frequency distributions.

Args:

tokenized$\_$corpus $($list$)$: Preprocessed and tokenized corpus.

Returns:

tuple: bigram frequencies and unigram frequencies.

$"""$

bigram$\_$freq $=$ defaultdict$($Counter$)$

unigram$\_$freq $=$ Counter$()$

for document in tokenized$\_$corpus:

# TODO: Update unigram frequencies

# HINT: Use unigram$\_$freq.update$()$

# TODO: Update bigram frequencies

# HINT: Use bigrams from nltk and update bigram$\_$freq

pass # Remove this line after implementing

return bigram$\_$freq, unigram$\_$freq

# Calculate bigram probability with optional smoothing

def bigram$\_$probability$($bigram$\_$freq, unigram$\_$freq, word$1,$ word$2,$ smoothing$=$False$)$:

$"""$

Calculate the probability of word$2$ given word$1$ using bigram frequencies.

If smoothing is True, apply Laplace smoothing.

Args:

bigram$\_$freq $($dict$)$: Bigram frequency distribution.

unigram$\_$freq $($dict$)$: Unigram frequency distribution.

word$1($str$)$: The preceding word.

word$2($str$)$: The current word.

smoothing $($bool$)$: Whether to apply Laplace smoothing.

Returns:

float: Probability of word$2$ given word$1.$

$"""$

# TODO: Implement this function

# HINT:

# $-$ If smoothing is True, add $1$ to the bigram count and adjust unigram count

# $-$ Vocabulary size V is len$($unigram$\_$freq$)$

# $-$ Handle cases where counts might be zero to avoid division by zero

pass # Remove this line after implementing

# Compute the probability of a sentence

def sentence$\_$probability$($bigram$\_$freq, unigram$\_$freq, sentence, smoothing$=$False$)$:

$"""$

Compute the probability of a sentence using the bigram model.

Args:

bigram$\_$freq $($dict$)$: Bigram frequency distribution.

unigram$\_$freq $($dict$)$: Unigram frequency distribution.

sentence $($str$)$: The sentence to compute the probability for.

smoothing $($bool$)$: Whether to apply Laplace smoothing.

Returns:

float: Probability of the sentence.

$"""$

# TODO: Tokenize and lowercase the sentence, add start$/$end tokens

# HINT: Use word$\_$tokenize and add $\text{'}\text{'}$ and $\text{'}\text{'}$ tokens

# Initialize the probability to $1\mathrm{.}0$

# Iterate over the bigrams in the sentence and multiply their probabilities

pass # Remove this line after implementing

# Predict the next N words given a sentence prefix

def predict$\_$next$\_$words$($bigram$\_$freq, unigram$\_$freq, sentence$\_$prefix, N$,$ smoothing$=$False$)$:

$"""$

Predict the next N words given a sentence prefix using the bigram model.

Args:

bigram$\_$freq $($dict$)$: Bigram frequency distribution.

unigram$\_$freq $($dict$)$: Unigram frequency distribution.

sentence$\_$prefix $($str$)$: The sentence prefix.

N $($int$)$: Number of words to predict.

smoothing $($bool$)$: Whether to apply Laplace smoothing.

Returns:

str: The predicted next N words.

$"""$

# TODO: Tokenize and lowercase the sen