The learning goals of this assignment are to:

Understand how to compute language model probabilities using maximum likelihood estimation.

Implement back$-$off.

Have fun using a language model to probabilistically generate texts.

Compare word$-$level langauage models and character$-$level language models.

import random

from collections import $*$

import numpy as np

We'll start by loading the data. The WikiText language modeling dataset is a collection of tokens extracted from the set of verified Good and Featured articles on Wikipedia.

data $=\{\text{'}$test$\text{'}$: $\text{'}\text{'},$ 'train': $\text{'}\text{'},$ 'valid': $\text{'}\text{'}\}$

for data$\_$split in data:

fname $=$ "wiki.$\{\}.$tokens".format$($data$\_$split$)$

with open$($fname$,\text{'}$r$\text{'})$ as f$\_$wiki:

data$[$data$\_$split$]=$ f$\_$wiki.read$().$lower$().$split$()$

vocab $=$ list$($set$($data$[\text{'}$train$\text{'}]))$

Now have a look at the data by running this cell.

print$(\text{'}$train : $\%$s $...\text{'}\%$ data$[\text{'}$train$\text{'}][$:$10])$

print$(\text{'}$dev : $\%$s $...\text{'}\%$ data$[\text{'}$valid$\text{'}][$:$10])$

print$(\text{'}$test : $\%$s $...\text{'}\%$ data$[\text{'}$test$\text{'}][$:$10])$

print$(\text{'}$first $10$ words in vocab: $\%$s$\text{'}\%$ vocab$[$:$10])$

Q$1\mathrm{.}1$: Train N$-$gram language model $(25$ pts$)$

Complete the following train$\_$ngram$\_$lm function based on the following input$/$output specifications. If you've done it right, you should pass the tests in the cell below.

Input:

data: the data object created in the cell above that holds the tokenized Wikitext data

order: the order of the model $($i$.$e$.,$ the $"$n$"$ in $"$n$-$gram" model$).$ If order$=3,$ we compute

$.$

Output:

lm: A dictionary where the key is the history and the value is a probability distribution over the next word computed using the maximum likelihood estimate from the training data. Importantly, this dictionary should include backoff probabilities as well; e$.$g$.,$ for order$=4,$ we want to store

as well as

and

$.$

Each key should be a single string where the words that form the history have been concatenated using spaces. Given a key, its corresponding value should be a dictionary where each word type in the vocabulary is associated with its probability of appearing after the key. For example, the entry for the history $\text{'}$w$1$ w$2\text{'}$ should look like:

lm$[\text{'}$w$1$ w$2\text{'}]=\{\text{'}$w$0\text{'}$: $0\mathrm{.}001,\text{'}$w$1\text{'}$ : $1$e$-6,\text{'}$w$2\text{'}$ : $1$e$-6,\text{'}$w$3\text{'}$: $0\mathrm{.}003,...\}$

In this example, we also want to store lm$[\text{'}$w$2\text{'}]$ and lm$[\text{'}\text{'}],$ which contain the bigram and unigram distributions respectively.

Hint: You might find the defaultdict and Counter classes in the collections module to be helpful.

def train$\_$ngram$\_$lm$($data$,$ order$=3)$:

$"""$

Train n$-$gram language model

$"""$

# pad $($order$-1)$ special tokens to the left

# for the first token in the text

order $-=1$

data $=[\text{'}\text{'}]*$ order $+$ data #

lm $=$ defaultdict$($Counter$)$

for i in range$($len$($data$)-$ order$)$:

$"""$

IMPLEMENT ME$!$

$"""$

pass

def test$\_$ngram$\_$lm$()$:

print$(\text{'}$checking empty history $...\text{'})$

lm$1=$ train$\_$ngram$\_$lm$($data$[\text{'}$train$\text{'}],$ order$=1)$

assert $\text{'}\text{'}$ in lm$1,$ "empty history should be in the language model!"

print$(\text{'}$checking probability distributions $...\text{'})$

lm$2=$ train$\_$ngram$\_$lm$($data$[\text{'}$train$\text{'}],$ order$=2)$

sample $=[$sum$($lm$2[$k$].$values$())$ for k in random.sample$($list$($lm$2),10)]$

assert all$([$a $>0\mathrm{.}999$ and a $<1\mathrm{.}001$ for a in sample$]),"$lm$[$history$][$word$]$ should sum to $1!"$

print$(\text{'}$checking lengths of histories $...\text{'})$

lm$3=$ train$\_$ngram$\_$lm$($data$[\text{'}$train$\text{'}],$ order$=3)$

assert len$($set$([$len$($k$.$split$())$ for k in list$($lm$3)]))==3,"$lm object should store histories of all sizes!"

print$(\text{'}$checking word distribution values $...\text{'})$

assert lm$1[\text{'}\text{'}][\text{'}$the$\text{'}]<0\mathrm{.}064$ and lm$1[\text{'}\text{'}][\text{'}$the$\text{'}]>0\mathrm{.}062$ and $\backslash$

lm$2[\text{'}$the$\text{'}][\text{'}$first$\text{'}]<0\mathrm{.}017$ and lm$2[\text{'}$the$\text{'}][\text{'}$first$\text{'}]>0\mathrm{.}016$ and $\backslash$

lm$3[\text{'}$the first'$][\text{'}$time$\text{'}]<0\mathrm{.}106$ and lm$3[\text{'}$the first'$][\text{'}$time$\text{'}]>0\mathrm{.}105,\backslash$

"values do not match!"

print$("$Congratulations$,$ you passed the ngram check!"$)$

test$\_$ngram$\_$lm$()$