Executive Summary

The aim of this project is to produce a next-word prediction algorithm using R, which will be implemented in a Shiny app. The app will predict the user’s next word based on text inputed by them.

The algorithm will be trained on a corpora collected from public sources, made available as part of this Course’s materials.

In this milestone report, I provide a summary of the data and outline plans for creating the algorithm and the app.

Data Summary

The algorithm will be trained on text from three files, each corresponding to a different type of text: blogs, news articles, and twitter posts.

The table below provides a summary of each file’s size and number of words and lines.

File Statistics
File Name Word Count Line Count File Size (MB)
data/en_US/en_US.blogs.txt 37,334,131 899,288 200.42
data/en_US/en_US.news.txt 34,372,530 1,010,242 196.28
data/en_US/en_US.twitter.txt 30,373,543 2,360,148 159.36

Due to the size of the files, the exploratory data analysis presented here is based on a sample: 10,000 lines were drawn randomly from each file and combined to form a sample file of 30,000 lines. A list of profane terms was then used to remove profanity from the combined sample. I then applied three tokenization processes to the data, creating files of single words, bigrams and trigrams. The single word file drawn from the 30,000 lines of text contains 877,314 words.

The histogram and word cloud below respectively display the 50 and 250 most popular words in the sample. Unsurprisingly, the five most frequent words in the sample are “the”, “to”, “and”, “a”, and “of”.

The following graph displays, in blue, the number of unique words that must be included in a “dictionary” to cover different percentages of word instances in the sample. For example, with a dictionary of just 2,500 words, we cover around 80% of word instances in our list of 877,314 words. If we use a dictionary of lemmatized words - that is, if we group all the inflected forms of a word into a single root word - we can see, in the gold curve, that coverage rises for any number of unique words included. For example, with a dictionary of 2,500 root or lemmatized words we now obtain over 85% of coverage against the previous 80%.

Finally, I checked how many of the words present in the sample are not contained in an external english dictionary sourced here. As the table below shows, around 3.7% of all words in the sample are not in a dictionary. Visual inspection shows that these missing words include “modern” terms related to the internet (like blog or html), names of companies and brands, unusual last names, and foreign words.

## 
##      FALSE       TRUE 
## 0.03669952 0.96330048

We can also see the most common bigrams and trigrams:

Note that the NA term in the trigram graph simply indicates that it is relatively common for some lines to contain less than three words.

Algorithm Modeling

Building the Basic N-gram model

The model will be trained on a sample drawn from the three text files. The key steps are: - Pre-processing: like the data used in this report for exploratory analysis, the training text data will be pre-processed to remove punctuation, numbers, profanity and stop words. - Tokenization: Using the tokenizers package, the text will be split into n-grams (from n=1 to n=4). - Frequency/probability calculation: we’ll calculate frequency counts of n-grams, and convert them into conditional probabilities that indicate how likely each n-gram is given the words that came before. - Store the n-gram probability model in a data.table structure. Each n-gram level will be a separate table with columns for the n-gram components and their probabilties. - Indexing: ensure fast retrieval of n-grams during prediction by setting keys in the data.table structures. - Pruning: implement a pruning step to remove low-frequency n-grams (below a certain threshold) to reduce the size of the model. - Normalization: ensure that the probabilities for each context sum to 1.

Handling Unseen N-grams

The algorithm will use a backoff model to estimate the probability of an n-gram when it is not observed in the training data. The idea is to back off to shorter, more frequent n-grams if the longer ones are not found. This is done by: 1) starting with the highest-order n-gram in our model (trigram for a three-word context, for example). If the trigram is found, use its probability. 2) back off to lower-order n-grams: if the trigram is not found, back off to the bigram. If the bigram is found, use its probability. 3) fall back to unigrams: if the bigram is not found, use the unigram probability as the finall fallback. 4) normalization: after obtaining the probability from the highest available n-gram, ensure that the probabilities are normalized to sum to 1. 5) applying smoothing techniques, like the Kneser-Ney Smoothing method, which adjusts the probability based on the frequency of lower-order n-grams, ensuring that even rare n-grams receive non-zero probability.

Efficient Storage using Markov Chains

The n-grams will be stored as a Markov chain where each state represents a word or a sequence of words, and transitions represent the probability of moving from one state to another.

How Many Parameters

Using longer n-grams can capture more context, but increases model size and complexity. I will start with tetragrams, and adjust if the model is too slow or large.

Evaluating Performance

The original corpora will be used to create training and test sets. A perplexity calculation and accuracy metrics will then be used to compare predicted words against words actual words in the test set.