Next Word Prediction

• Next word prediction is the task of suggesting the most probable word a user will type next.
• This model uses n-gram probability distribution to predict the next word.
• Corpus is divided into train(70%) and test(30%). 10% random sample of the train corpus is used to build the model.
• The train corpus is first cleaned and then tokenized into n-grams, with largest n used by the model being 4.
• Kneser-Ney smoothing is used to reduce the data sparsity by adjusting the probability distribution of unseen sequences.
• The idea of Kneser-Ney smoothing is to optimize the calculation of lower-order n-gram probabilities in case the higher-order n-gram was unseen in the corpus. It is thereby a backoff smoothing algorithm.

• Good-Turing Estimate is based on the assumption that the probability of unseen sequences can be estimated based on \( N_{1} \) which is the number of n-grams that occured once in the Corpus.
• Since the probability mass of unseen n-grams is now greater than 0, the probability mass of seen n-grams needs to be reduced to let the total probability sum to 1. This is achieved with

\[ \begin{aligned} p_r = \frac{\substack{r^*}} {\substack{N}} \end{aligned} \] where \[ \begin{aligned} r^* = (r+1) \frac{\substack{N_r+1}} {\substack{N_r}} \end{aligned} \]

• Here \( N_r \) is the frequency of n-grams that were seen r times in the corpus and \( r^* \) is the adjusted frequency r.

• Church et. al empirically show that the discount \( (r-r^*) \) applied at the Good-Turing estimate is generally constant for \( r \geq 3 \)
• Ney et. al estimate the discount value D based on the total number of n-grams occuring exactly once \( (n_1) \) and twice \( (n_2) \) \[ \begin{aligned} D = \frac{\substack{n_1}} {\substack{n_1 + 2n_2}} \end{aligned} \]
• Based on this \[ \begin{aligned} P_{absolutediscount}(w_i|w_{i-1}) = \frac{\substack{c(w_{i-1},w_i) - D}} {\substack{c(w_i-1)}} + \lambda{(w_{i-1})} P(w) \end{aligned} \]
• Kneser-Ney smoothing is a modified version of absolute discounting, where instead of the unigram probability P(w) we use \( P_{continuation}(w) \)
• \( P_{continuation}(w) \) gives ,“How likely is w to appear as a novel continuation”, and \( \lambda \) is a nomalizing constant; the probability mass we have discounted

• The app loads n-gram (n being 1-4) probability tables at startup, where each probability table has the n-gram and it's corresponding Kneser-Ney probability.
• The algorithm accepts a string, and uses the last n-grams to predict the next word. The next word with highest KN probability is returned. When exact match is not found, algorithm backs off to \( (n-1)^{th} \) gram.
• User can also specify max. number of predictions that he/she wants from the algorithm, and they are returned sorted by their KN probability.