Next Word Prediction App - Coursera Data Science Capstone

This simple Predict Next Word app invites the user to enter a word or phrase into a text box, click the “Predict Next Word” button, and returns the most likely next word, based on an advanced probabilistic model.

The algorithm behind the app is a probabilistic model based on a large body of English text, available for download here. The steps for building the algorithm are:

• Reducing the dataset (use sampling) for faster computations.
• Tokenizing the data into n word phrases, known as n-grams.
• Calculating the probabilities of different last words for trigrams and bigrams and returning the most likely option (“Top Prediction”), like so:

A simple probablity model overestimates the true probability of an n-gram. The most effective adjustment method discovered to date is Modified Kneser-Ney Smoothing, which was used in the algorithm.

Resources for understanding the formula:

• A Stanford tutorial on smoothing technniques
• The Chen and Goodman paper introducing MKN
• An explanation of MKN on Quora
• An application in code of various smoothing equations
• Coursera student Phil Ferriere's plain-English explanation of MKN