|
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? |
||||
|
|
|
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. |
|||||||
|
