When doing natural language processing, one can take a corpus and evaluate the probability of the next word occurring in a sequence of n. n is usually chosen as 2 or 3 (bigrams and trigrams).
Is there a known point at which tracking the data for the nth chain becomes counterproductive, given the amount of time it takes to classify a particular corpus once at that level? Or given the amount of time it would take to look up the probabilities from a (data structure) dictionary?
Is there a known point at which tracking the data for the nth chain becomes counterproductive, given the amount of time it takes to classify a particular corpus once at that level?
You should be looking for perplexity vs. n-gram size tables or plots.
Examples:
http://www.itl.nist.gov/iad/mig/publications/proceedings/darpa97/html/seymore1/image2.gif :
http://images.myshared.ru/17/1041315/slide_16.jpg :
http://images.slideplayer.com/13/4173894/slides/slide_45.jpg :
The perplexity depends on your language model, n-gram size, and data set. As usual, there is a trade-off between the quality of the language model, and how long it takes to run. The best language models nowadays are based on neural networks, so the choice of n-gram size is less of an issue (but then you need to choose the filter size(s) if you use CNN, amongst other hyperparameters…).
Your measure of "counter productive" could be arbitrary - eg. with lots of fast memory it could be processed faster (more reasonably).
After saying that, exponential growth comes into it and from my own observations it seems to be around the 3-4 mark. (I haven't seen any specific studies).
Trigrams do have an advantage over bigrams but it is small. I've never implemented a 4-gram but the improvement is going to be much less. Probably a similar order of magnitude decrease. Eg. if trigrams improve things 10% over bigrams, then a reasonable estimate for 4-grams might be 1% improvement over trigrams.
However the real killer is the memory and the dilution of numeric counts. With a $10,000$ unique word corpus, then a bigram model needs $10000^2$ values; a trigram model will need $10000^3$; and a 4-gram will need $10000^4$. Now, okay, these are going to be sparse arrays, but you get the picture. There's an exponential growth in the number of values, and the probabilities get much smaller due to a dilution of frequency counts. The difference between 0 or 1 observation becomes much more important and yet frequency observations of individual 4-grams are going to drop.
You are going to require a huge corpus to compensate for the dilution effect, but Zipf's Law says a huge corpus is also going to have even more unique words...
I speculate that this is why we see a lot of bigram and trigram models, implementations, and demos; but no fully working 4-gram examples.
