How to update a dynamic language model dataset?

Question

I'm a statistics novice and I need help with a natural language problem.

I'm writing a word-prediction algorithm for a mobile app. I'm using a unigram language model of word/count pairs where count is the number of times that word appears in a corpus. The algorithm is pre-loaded with a set of words and probabilities, but it must also update the probabilities and learn new words as the user types.

Here is a sample of the pre-loaded table:

word                count
----------        -------
you               1222421
I                 1052546
the                823661
to                 770161
a                  563578
and                480214
...
spangles                5
moustached              5

The prediction algorithm is simple enough (rank predictions by descending count). My question is how to update this table so the algorithm learns quickly as the user types. If I simply add new words with a count of 1, and increment count by 1 with each usage, the algorithm will learn too slowly.

For example, suppose the user types "to" more often than "the". It will take over 50,000 usages before "to" outranks "the". That's slow learning! Similarly, suppose the user's name is "andy" and so he types that word more often than anything else. He'll have to type "andy" nearly half a million times before it outranks "and"!

How do I compute new probabilities so that so that it doesn't take hundreds of thousands of word usages to make a difference?

P.S. Computational efficiency is very important since this is for a mobile app. Sorry if I'm asking for too much!

Thanks in advance!

Answer 1

I'd consider using two models. One is the original baseline model that never changes (or maybe just changes infrequently, like when you update versions). The other is a per user model that keeps only things the user has typed. Then I'd combine the baseline and dynamic model with simple linear interpolation to make the prediction. EG, use say, .8 * baseline + .2 * user model to do prediction. This way I don't need to munge up the nice, meaningful data in the baseline model with the per user data. Likewise, the per user data is clear and interprettable. I'd have a clean single trade off parameter between baseline and user estimates. The next step to improve prediction quality would be to increase the weight for the user model as it gets larger.