Next Word Prediction

• News, Twitter and Blogs data in English from HC Corpora (over 4 million lines) are loaded .
• R Routines built for data processing, data cleansing and analysis.
• Data Sampling - 70% Training and 30% Testing/Cross Validation - from each type of data (twitter, news and blogs)

N-Grams - Language Model

• Build ngram language model on the merged training - “seen” data set.
  
  • Ngram : [Phrase (word1 … wordn); frequency count; Conditional Probability]
• The conditional probability of a word is defined by considering the frequency of the words preceding the word and its usage history in the document.
  • p(awesome|This project is)= count(This project is awesome)/count(This project is)
  • p(there|Hi)= count(Hi there)/count(Hi)
• NGram Reduction - Ngram model size was reduced by omitting the lower frequency ngrams.

Prediction Algorithm - Katz Backoff

• Get input phrase, clean and tokenize it
• If phrase has three or more words, look for evidence in quadgrams (fourgrams), use it when evidence found;
• Otherwise backoff to trigram with highest conditional probability, use it when evidence found;
• Otherwise backoff to bigram; otherwise use maximum likelihood estimate (MLE) of a partially matched unigram.

Additional Features

• When first word is being typed, algorithm uses unigrams to predict; when match is found it returns the word; otherwise it returns “the” or “and” as begining words.
• When first space is entered it looks for evidence in bigrams, uses it when found; if not it backtracks to unigram. So based on the number of spaces in the phrase it decides which highest ngram to start with before backing off to lower grams.

Future Enhancements

• Spell correction; Handle numeric data; Process sentences
• Improve algorithm performance
• Incorporate parallel computing options