Chan Ching Chuen
2024-05-26
The project is inspired by the use case where a user typing texts using a keyboard, the keyboard predicts what the next words is going to be and perhaps give a choice of candidates for the most frequent words.
For this project we will make an app which accept text input from user and output a list of prediction for the next word in English.
The project involves an attempt at natural language processing (NLP), dealing with potentially large data set (a corpus), modeling work to compute the most likely next words, and making a Shiny app that loads the data and run the model in real time.
The modelling approach we are going to adopt is the n-gram approach in NLP. For instance, a bi-gram is a 2-words combination, and for a given set of corpus one can sort out all the bi-grams and the associated frequencies that appear. A prediction is possible, then, by looking at the last word of the input and look for continuation that results in bi-grams that appears at the highest frequencies. In simple term, if \(count(w_1w_2)\) is the frequency of the sequence of words \(w_1\) followed by \(w_2\), then the conditional probability of \(w_2\) being the next word given the user type in \(w_1\) is \(S(w_2|w_1)=count(w_1w_2)/\sum_v count(w_1v)\).
A bi-gram approach does not take into account any context of sentence being typed in by user. A possible approach is to use longer word combinations e.g., a 5-gram would take into account the last 4 words of the input and returns a prediction accordingly.
For the purpose of this project we are using the HC Corpa, which was collected by a web crawler. For more information please see the web archive for “About the Corpora”.
For the modeling approach, to capture some context we will use a 5-gram approach. A simple 5-gram approach is straight forward to implement in R - after pre-processing the corpus (e.g., removing numbers, puntuations and changing to small caps) one can use R-package such as n-gram to produce a full list of 5-grams and the associating frequency. However, as it is conceivable that an input would not necessarily has a matching 5-gram from the corpus, which will result in no match, it is better to adopt a smoothing or back-off strategy. We adopted the so-called Stupid-Backoff (see “Jusrafsky & Martin”, p.19), where if there is no match of a 5-gram with the input, then one back-off to 4-gram with adjustment to the probability, and if there is no 4-gram match we further back-off to 3-gram and so on. For a 5-gram (setting \(N=5\) below): \[S(w_i|w_{i-N+1:i})=\begin{cases}count(w_{i-N+1:i})/\sum_v count(w_{i-N+1:i-1}v) &\text{if } count(w_{i-N+1:i})>0 \\ \lambda S(w_i|w_{i-N+2:i}) &\text{otherwise}\end{cases}\\\]
In this work we take \(\lambda=0.4\). The iteration terminates at the uni-gram.[^1]
Hence we will need the n-grams and associated frequencies for 5-gram down to uni-gram. To make the data manageable, we truncated n-grams with low frequency, which may not be a very good approximation of the likelihood anyway due to sparse data. For this implementation we ditched all n-grams that appears less than 5 times in the corpus, and this reduced the data size and enhanced performance significantly.
The app requires binary search for matching n-grams from very large data set, and using data.table package with appropriate keys greatly enhance the efficiency.
The app “NextWord” has a simple interface: the user can type in text in the input text box, and then press the “Predict” button. The app then lists 5 predictions, in order of likelihood, of the next word. The prediction loads within second, performance is reasonable.