0
$\begingroup$

How would I go about predicting the next word in a sentence if I have a n-gram model available? A intuitive solution would be to just ask the probability of all the words that can come next and see which has the highest. But this would be dreadfully slow if I have a very large set of n-grams wouldn't it?

If anyone could point me in the right direction that would be great!

Here is what I have so far. We have a data structure and this data structure will allow lookup of context(so the previous words) via hashing. This can be done in O(m) with m the length of the context but since this is always very short it is safe to say lookup can be done in O(1). Now let's say the previous words are "I want to" I would look this up in my ngram model in O(1) time and then check all the possible words that could follow and check which has the highest chance to come next. But with something as generic as "I want to" I can imagine this would be quite a few words. Our application must run on mobile devices so I would like to know if there is a more efficient way to get the word with the highest chance. I was thinking about maybe sorting the ngrams but since we are using some sort of hashtable this isn't really an option.

The more I think about this however the more I realize that even if it would be lets say 500 words that can come next, that this is still a fairly small number and even a slow processor could easily go over those very quickly so maybe I am over thinking things.

|cite|improve this question
$\endgroup$
  • $\begingroup$ It won't be dreadfully slow since you'll do it in a smart way, using dynamic programming. $\endgroup$ – Yuval Filmus Feb 22 '17 at 12:14
  • $\begingroup$ Could you link me an algorithm or give me a name of a 'smart way'. $\endgroup$ – Lasse Jacobs Feb 22 '17 at 12:21
  • $\begingroup$ Using dynamic programming. $\endgroup$ – Yuval Filmus Feb 22 '17 at 12:23
  • $\begingroup$ Oke I will have a look at it, thank you for your reply. $\endgroup$ – Lasse Jacobs Feb 22 '17 at 15:58
  • $\begingroup$ Why do you think it will be dreadfully slow? Try writing down exactly what algorithm you plan to use and an estimate of how many steps of computation your method will use, then edit the question to show your work so far. $\endgroup$ – D.W.♦ Feb 22 '17 at 17:53
2
$\begingroup$

Store the n-grams in a tree or trie, with one level per word, starting from the leftmost word. Then given some context, e.g., "I want to", you traverse the tree/trie (follow the edge out of the root that is labelled "I", then the edge labelled "want", then the edge labelled "to") and find all children of the resulting node.

|cite|improve this answer
$\endgroup$
2
$\begingroup$

With N-Grams, N represents the number of words you want to use to predict the next word.

You take a corpus or dictionary of words and use, if N was 5, the last 5 words to predict the next. I will use letters (characters, to predict the next letter in the sequence, as this it will be less typing :D) as an example.

Say you have a corpus or input stream such as wwwaasssssdddaawww ? Let us use bi-grams (n=2) and we want to predict the next character in the sequence: ?

To do this, we first get all the distinct letters: w,a,s,d Next, we define a prefix as being the past (most recent) 2 letters: prefix = ww.

We then want to know, given the last two letters were ww, what is the probability of seeing another w? an a? a s? a d?

The first thing to do is work out how many times the prefix appears: 4 times.

So, we build our frequency distribution and we see that within the corpus, a w appears after the sequence ww twice. An a appears 1 time after ww, s appears 0 and d appears 0 times.

From this, we can conclude that the probability of seeing a w next, is 4/2 = 2/4 = 50%. An a: 25%, s: 0, d: 0.

Obviously, having zero probability is not correct. If the words are unknown, you can assign them some dummy character/word like ???. If the words are not unknown, but just not seen given the prefix, you should use some sort of smoothing algorithm (like Laplace).

That is the 'just' of it. I learned about N-Grams from the following resource: https://lagunita.stanford.edu/c4x/Engineering/CS-224N/asset/slp4.pdf

As for your data issue... You can create a data structure where each unique possible prefix is the key in, for example, a dictionary.

Your dictionary keys would look something like this (based on the above corpus):

'ww', 'wa', 'aa', 'as', 'ss', 'sd', 'dd', 'da', 'aw'

Every time you encounter a new unique prefix, you add a new entry to your dictionary.

Each key in the dictionary could have an object as a value with n-properties, where n is the number of distinct possible words/characters and each stores the count of observations (initialised to 0). EG:

'ww': w = 0,a = 0,s = 0,d = 0

Then every time you see a word/letter come in, you grab the prefix (in our case ww) and increment the count for the observed character/word:

'ww': w = 2, a = 1, s = 0, d = 0

Now when you see another ww and then get a w, just increment...

'ww': w = 3, a = 1, s = 0, d = 0

To get the probability, just grab the KVP for the given prefix, choose the property with the greatest count and divide it by the number of unique properties.

This means that instead of storing aaaaaall the data, you are just storing counts! Much more data efficient. Further, information is the far past may not be a very good indicator of what is likely to be seen in the near future, so you could limit your corpus to say, 1000 wrods... as they come in, you remove the oldest and add the new incoming one (a stack...), but you will have to play a bit to find out what works best.

Hope this helps!

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.