Building a Predictive Typing Model

All Words

df1grams <- getNgrams(dfSentences, 1)
dim(df1grams)
[1] 26453     2
wordsOfFreq1 <- df1grams %>% group_by(freq) %>% summarise(n = sum(freq)) %>% dplyr::filter(freq == 1) %>% .$n

There are 26453 words in the corpus, that shows how vast Shakespeare’s vocabulary was. Let’s see a wordcloud of top 100 words. No surprise, the most commonly used words are: the, and, i, to, of. Excluding these commonly used ‘stop words’, in the second wordcloud, we can see the words Shakespeare used most frequently. We can see a lot of references to royalty and nobility, present specially in Shakespearean tragedies. Some names are mentioned quite frequently - Richard, John, Caesar, Brutus and Henry. Some English counties or shires are mentioned quite often - Warwick, York and Gloucester.

Unigrams

Let’s see a plot of the distribution of words in corpus by usage.

Here’s a strategy for building ngram tables:

• There is a long tail of 10522 words in the corpus that appear exactly once. Replace all words appearing just once, by UNK as a placeholder for a word not known from the corpus. There are a couple of motivations behind this:
  • It reduces the size of ngram tables.
  • More importantly, when an unknown word is encountered, the model knows how to tackle it before predicting the next set of words.
• Re-summarise and rearrange the table by frequency.
• Assign an index to each word.
• Convert to data.table format. Some of the biggest benefits of this approach are:
  • Rows could be assigned and referenced by a key. This makes it extremely simple to look up a row value.
  • Lookup by a key is very fast compared to matching character strings.
  • When we create tables for bigrams and higher order ngrams, we can replace the words by their corresponding integer indexes. It saves a lot of memory as compared to creating tibbles with character strings.

vTopUnigrams <- df1grams %>% dplyr::filter(freq >= 2) %>% .$word
df1grams <- df1grams %>% 
    mutate(word = ifelse(word %in% vTopUnigrams, word, "UNK")) %>% 
    group_by(word) %>% 
    summarise(freq = sum(freq)) %>% 
    arrange(desc(freq)) %>% 
    mutate(index1 = row_number()) %>% 
    select(index1, freq, word)

dt1grams <- as.data.table(df1grams)
# set key to word
dt1grams <- dt1grams[,.(index1,freq),key=word]
# create another table with key=index1
dt1gramsByIndex <- dt1grams[,.(word,freq),key=index1]
# print dimensions
dim(dt1grams)
[1] 15932     3

Here are the top 10 unigrams. UNK replaces the long tail of words appearing once. Finally, we are left with 15932 unigrams in our table.

Bigrams

A data table of bigrams is created where the index of the first word is the lookup key. The second word cannot be UNK since it is a word used for making predictions from the bigram table.

df2grams <- getNgrams(dfSentences, 2) %>% 
    separate(word, c("word1", "word2"), sep = " ") %>% 
    mutate(word1 = ifelse(word1 %in% vTopUnigrams, word1, "UNK")) %>% 
    dplyr::filter(word2 %in% vTopUnigrams) %>% 
    group_by(word1, word2) %>% 
    summarise(freq = sum(freq)) %>% 
    arrange(desc(freq))

dt2grams <- as.data.table(df2grams)
dt2grams$index1 <- dt1grams[dt2grams$word1]$index1
dt2grams$index2 <- dt1grams[dt2grams$word2]$index1
dt2grams <- dt2grams[,.(index1,index2,freq)]
setkey(dt2grams, index1)

# print dimensions
dim(dt2grams)
[1] 254884      3

Here are the top 10 bigrams:

Trigrams

Similarly, a data table of trigrams is created where indexes of the first and second words form the lookup key. The third word cannot be UNK since it is a word used for making predictions from the trigram table.

df3grams <- getNgrams(dfSentences, 3) %>% 
    separate(word, c("word1", "word2", "word3"), sep = " ") %>% 
    mutate(word1 = ifelse(word1 %in% vTopUnigrams, word1, "UNK")) %>% 
    mutate(word2 = ifelse(word2 %in% vTopUnigrams, word2, "UNK")) %>% 
    dplyr::filter(word3 %in% vTopUnigrams) %>% 
    group_by(word1, word2, word3) %>% 
    summarise(freq = sum(freq)) %>% 
    arrange(desc(freq))

dt3grams <- as.data.table(df3grams)
dt3grams$index1 <- dt1grams[dt3grams$word1]$index1
dt3grams$index2 <- dt1grams[dt3grams$word2]$index1
dt3grams$index3 <- dt1grams[dt3grams$word3]$index1
dt3grams <- dt3grams[,.(index1,index2,index3,freq)]
setkey(dt3grams, index1,index2)

# print dimensions
dim(dt3grams)
[1] 476098      4

From the top 10 trigrams, we can get an idea how UNK will be useful in this context. the UNK of is one of the most frequently used word sequences in the trigram table, which implies that if we encounter an unknown word after ‘the’, then ‘of’ is the most likely word to be predicted from the trigram table.

Quadrigrams

Here are the top 10 quadrigrams:

Pentagrams

Here are the top 10 pentagrams:

These ngram tables comprise all the information needed for the prediction model.

Memory Usage Comparison

As mentioned above, storing words as integer indexes in a data table is far more efficient as compared to a data frame with character strings. For instance, here’s how a pentagram data table looks like that contains just the integer indexes of the words:

In a comparison of memory needed for all ngram tables, we see a difference of a factor of 5 between the two approaches.

print(object.size(df1grams)+object.size(df2grams)+object.size(df3grams)+
          object.size(df4grams)+object.size(df5grams), units = "auto")
158 Mb

print(object.size(dt1grams)+object.size(dt1gramsByIndex)+object.size(dt2grams)+object.size(dt3grams)+
          object.size(dt4grams)+object.size(dt5grams), units = "auto")
30.4 Mb

Test Cases

The first test is to confirm whether the word predictions from the unigram table, match with what we expect. The top 10 unigram table contains 3 words beginning with the letter ‘t’ - the(1), to(4), that(10). And sure enough, this is what we get from our prediction function.

predictNextWords("t")
[1] "Predictions from 1grams: the,to,that,this,thou"
[1] "Top 3 Final Predictions: the,to,that"

From the bigram table, we could see that i am, i have and i will are among the top 10. So, the next test is to confirm these.

predictNextWords("i ")
[1] "Predictions from 2grams: am,have,will,do,would"
[1] "Top 3 Final Predictions: am,have,will"

Narrowing down to words that begin with letter ‘h’ gives us:

predictNextWords("i h")
[1] "Predictions from 2grams: have,had,hope,hear,heard"
[1] "Top 3 Final Predictions: have,had,hope"

Let’s predict some trigrams. i am not and i am a are among the top 10 trigrams, so that’s what we expect to see.

predictNextWords("i am ")
[1] "Predictions from 3grams: not,a,sure,glad,the"
[1] "Top 3 Final Predictions: not,a,sure"

Now let’s examine the UNK feature. We know that the UNK of is number 5 most common sequence in the trigram table so we should expect to see ‘of’ as the first prediction if the input text has an unknown word after ‘the’. So let’s input some gibberish after ‘the’ to make sure this word doesn’t exist in our vocabulary:

predictNextWords("the sjdhsbhbfh ")
[1] "Predictions from 3grams: of,and,in,that,the"
[1] "Top 3 Final Predictions: of,and,in"

Now that the known test cases are working well, let’s see the backoff algorithm in action:

predictNextWords("to be or not ")
[1] "Predictions from 5grams: to"
[1] "Predictions from 4grams: to"
[1] "Predictions from 3grams: to,at,i,allow'd,arriv'd"
[1] "Top 3 Final Predictions: to,at,i"
predictNextWords("to be or not to ")
[1] "Predictions from 5grams: be"
[1] "Predictions from 4grams: be,crack"
[1] "Predictions from 3grams: be,crack,the,have,me,do"
[1] "Top 3 Final Predictions: be,crack,the"
predictNextWords("be or not to ")
[1] "Predictions from 5grams: be"
[1] "Predictions from 4grams: be,crack"
[1] "Predictions from 3grams: be,crack,the,have,me,do"
[1] "Top 3 Final Predictions: be,crack,the"
predictNextWords("to be or not to be ")
[1] "Predictions from 5grams: that"
[1] "Predictions from 4grams: that,found,gone,endur'd,endured,seen"
[1] "Top 3 Final Predictions: that,found,gone"
predictNextWords("to be or not to be, that ")
[1] "Predictions from 5grams: is"
[1] "Predictions from 4grams: is,which"
[1] "Predictions from 3grams: is,which,you,he,i,thou,can"
[1] "Top 3 Final Predictions: is,which,you"
predictNextWords("to be or not to be, that is ")
[1] "Predictions from 5grams: the"
[1] "Predictions from 4grams: the"
[1] "Predictions from 3grams: the,not,my,to,a"
[1] "Top 3 Final Predictions: the,not,my"
predictNextWords("to be or not to be, that is the ")
[1] "Predictions from 5grams: question"
[1] "Predictions from 4grams: question,very,way,humour,best,brief"
[1] "Top 3 Final Predictions: question,very,way"
predictNextWords("be that is the ")
[1] "Predictions from 5grams: question"
[1] "Predictions from 4grams: question,very,way,humour,best,brief"
[1] "Top 3 Final Predictions: question,very,way"

Using one of the most well known speeches from Hamlet, we can see that the algorithm gets the first word prediction from the pentagram table. But since we are looking for the next 3 words, the algorithm backoffs to predictions from quadrigram and trigram tables, until it has atleast 3 words. In this case, the pentagram table gives us the best match that we are looking for. We can also observe that once we have atleast 4 words in our input text, the words prior to those do not matter for the next word predictions.

Let’s see another example:

predictNextWords("What a lovely day ")
[1] "Predictions from 5grams: "
[1] "Predictions from 4grams: "
[1] "Predictions from 3grams: "
[1] "Predictions from 2grams: and,to,is,of,i"
[1] "Top 3 Final Predictions: and,to,is"
predictNextWords("a lovely day ")
[1] "Predictions from 4grams: "
[1] "Predictions from 3grams: "
[1] "Predictions from 2grams: and,to,is,of,i"
[1] "Top 3 Final Predictions: and,to,is"
predictNextWords("lovely day ")
[1] "Predictions from 3grams: "
[1] "Predictions from 2grams: and,to,is,of,i"
[1] "Top 3 Final Predictions: and,to,is"
predictNextWords("day ")
[1] "Predictions from 2grams: and,to,is,of,i"
[1] "Top 3 Final Predictions: and,to,is"

Here we see that even though there are enough words to start matching from the higher ngram tables, the matches are gotten only from the bigram table using ‘day’ as the first word.

Another one:

predictNextWords("Beware the ides of ")
[1] "Predictions from 5grams: march"
[1] "Predictions from 4grams: march"
[1] "Predictions from 3grams: march"
[1] "Predictions from 2grams: march,the,my,his,a,this"
[1] "Top 3 Final Predictions: march,the,my"
predictNextWords("Beware the ides of mar")
[1] "Predictions from 5grams: march"
[1] "Predictions from 4grams: march"
[1] "Predictions from 3grams: march"
[1] "Predictions from 2grams: march,marriage,marcius,marcus,mars"
[1] "Top 3 Final Predictions: march,marriage,marcius"
predictNextWords("Beware the ides of march")
[1] "Predictions from 5grams: march"
[1] "Predictions from 4grams: march"
[1] "Predictions from 3grams: march"
[1] "Predictions from 2grams: march,marching"
[1] "Predictions from 1grams: march,marching,march'd,marches,marchioness"
[1] "Top 3 Final Predictions: march,marching,march'd"