TDM 30200: Project 10 - Large Language Models (LLMs): N-gram model

Last project, you looked into basic text processing and some basic text statistics like word count, letter frequency, etc. In this project, we will look into n-grams, which are a more complex way of statistically analyzing text. N-grams are sequences of n items (words, letters, etc.) from a given text. For example, in the word "hello!", we could analyze the 2-grams (bigrams) of "he", "el", "ll", "lo", and "o!". We could similarly analyze 3-grams, 4-grams, etc. Alternatively, we could analyze the sentence "Large Language Models are great!" and analyze n-grams on a per-word basis. In this case, we have the following 2-grams: "Large Language", "Language Models", "Models are", "are great!".

To start, let’s create a generic n-gram class to store any data and functions we need. The code below serves as a good starting point. Throughout this project, we will fill in each function.

Firstly, let’s figure out how to add some data to our NGram class. The set_data function should take in a list of elements that we can generate n-grams from. These elements could either be strings if we want an n-gram on a per character basis, or they could be list of strings for making an n-gram on a per word basis. At the very least, we should ensure that the data passed in is a list. If not, we should not do anything. For our data, we will continue to use the Amazon music dataset. Please copy your read_lines and clean_text functions from last project. Additionally, you will need to make a couple of modifications to your clean_text function. Firstly, please lowercase all letters. There are other techniques to ensure that the model understands that words with different capitalization are the same, but we will look into those in future projects. Then, add the following line of code to your clean_text function to ensure that only alphabetic characters are kept in the text. This will help us avoid any issues with punctuation and special characters.

Now that we have our data helper functions, let’s implement the set_data function. This function should take in a list of strings, along with the stored flag that indicates whether we want to generate n-grams on a per character basis or a per word basis. If the flag is set to True, we should generate n-grams on a per character basis. If the flag is set to False, we should generate n-grams on a per word basis. In total, your function should take this list of strings, clean it using the clean_text function, ensure that it is in the correct format for per word or per character n-grams, and then store it in the self.data variable.

To test that your set_data function is working, you can use the following code:

After you have n-gram generation working, we can begin looking at the frequencies of each n-gram. The generate_ngrams function should use the stored self.n and self.data and create each n-gram, along with counting how many times that n-gram appears in the data. This should be stored in a dictionary, where the key is the n-gram and the value is the frequency of that n-gram. For example, if we are analyzing 'hello yellow' on a per character basis, we would have the following n-grams and frequencies:

The resulting dictionary should be stored in the self.ngram_frequencies variable AND returned by the function. If self.data is empty or is not a list, the function should return an empty dictionary. Please implement this functionality and run the below test cases to ensure that it is working. You can use the following code to test your generate_ngrams function:

Now that we have our n-grams and their frequencies, let’s look at the probabilities of each n-gram. Our probability table will essentially be a nested dictionary, where the first key is n-1 part of the n-gram and its value is another dictionary. In this second dictionary, each key is the last part of the n-gram and the value is the probability of that n-gram. For example, if we are analyzing 'hey help' on a per character basis with n=3, we would have the following n-grams and probabilities:

In the above example, half of the time after 'he' we see 'y' and half of the time we see 'l'. This is a very simple example, but it shows how we can use n-grams to predict the next word in a sequence. The generate_ngram_probabilities function should generate the n-gram frequencies by calling the generate_ngrams function and use the returned value to calculate the probabilities of each n-gram. This should be stored in the self.ngram_probabilities variable AND returned by the function. If self.ngram_frequencies is empty or is not a dictionary, the function should return an empty dictionary.

The following code should be used to test your generate_ngram_probabilities function:

Now that we have our n-gram probabilities, we can finally try and use our n-gram model to generate some text. The get_next_word function should take in a string of previous words/letters and 'predict' the next word/letter in the sequence. This function can either be used in 'random', 'common', or 'uncommon' mode. In random mode, the function should use the probabilities in conjunction with np.random.choice to randomly select the next word/letter. In common mode, the function will select the most common next word/letter. In uncommon mode, the function will select the least common next word/letter. The function should return the next word/letter as a string. If self.ngram_probabilities is empty or is not a dictionary, the function should return an empty string.

Something that may be useful is an example of using np.random.choice with probabilities. Typically, you would provide just a list of items to choose from, and the random choice would assume a uniform probability distribution. However, if you want to provide a custom probability distribution, we can use the p parameter, which is a list of probabilities for each item in the list. For example, if we have a list of items ['a', 'b', 'c'] and we want to select one of them with the following probabilities: {'a': 0.1, 'b': 0.3, 'c': 0.6}, we can use the following code:

A keen eye may notice that this is simply our dictionary.keys() as the first parameter and the dictionary.values() as the second parameter.

Please implement the get_next_word function and run the following test cases to ensure that it is working. You can use the following code to test your get_next_word function:

One metric that is commonly used to evaluate the performance of n-gram models is the concept of perplexity. Perplexity is a measure of how well a probability distribution predicts a sample. In the context of n-gram models, perplexity is a measure of how well the model predicts the next word in a sequence. The lower the perplexity, the better the model is at predicting the next word.

We can calculate the perplexity of our n-gram model using the following formula:

where: - N is the number of words in the sequence - P(w_i|w_1, w_2, …​, w_n-1) is the probability of the i-th word given the previous n-1 words - ln is the natural logarithm

Essentially, we find perplexity by giving the model some string of text. for each n-gram within the text, we calculate the probability of our model generating that n-gram based on the previous n-1 words. We then take the log of that probability, sum all of those values, divide it by the number of words in the text, multiply it by negative 1, and finally take the exponential of that value. This will give us a single number that represents how well our model is able to predict the next word in the sequence. These values can range from 1 to infinity, with lower values indicating a better model. A value of 1 would indicate that the model is perfect and is able to predict the next word with 100% accuracy. A value of infinity would indicate that the model is unable to predict the next word at all.

For example, let’s say we have a 3-gram model and input the following string: 'apples and bananas taste good' We want to find the probability that our 3-gram model will predict bananas given the previous 2 words apples and, taste given the previous 2 words and bananas, and good given the previous 2 words bananas taste. Each of these probabilities is calculated using the probabilities we generated in step 3, then their natural log is taken, then they are multiplied by -1 and divided by the total number of words in our input string (5 words). Finally, we sum all of these values and take 2 to the power of that value. This will give us a single number that represents how well our model is able to predict the next word in the sequence.

To summarize what these values actually mean, a theoretical perfect model would have a perplexity of 1, where it has no doubts about what the next word in a sequence is. A higher perplexity indicates that the model is less certain about what the next word in a sequence is. This is not necessarily a bad thing, as it shows that the model is able to generate a wider variety of text.

Please implement the get_perplexity function and run the following test cases to ensure that it is working as expected. You can use the following code to test your get_perplexity function: