0
$\begingroup$

I read the great book Foundations of Statistical Natural Language Processing. by Christopher D. Manning and Hinrich Schütze.

My question is regarding counting the number of ngrams for a given vocabulary.

For example, in the book, the given vocabulary has a size of 20000 words and the number of ngrams are as following

bigram model: $20, 000 × 19, 999 = 400 $ million

trigram model: $20, 000^2 × 19, 999 = 8 $ trillion

four-gram model: $20, 000^3 × 19, 999 = 1.6 × 10^{17}$

But why it actually so, why the last element is one less than the previous, I thought is should be simpler for bigrams just square of vocabulary.

$\endgroup$
1
$\begingroup$

If you already have $V-1$ word probabilities $P(w_i|\cdot)$, then the last one is simply one minus the sum of the rest. So there are only $V-1$ parameters to estimate.

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

It appears he is discounting all n-grams where a word appears n times. Perhaps he has defined an n-gram to be defined in that way. Most definitions for n-grams that I have seen is word coocurrences of length n. So in that case it could be $V^n$ - although in practice this is likely to be a very loose upper bound.

Here are some of the counts of unique n-grams for wikipedia:

1gram 7955768

2gram 95650278

3gram 376671416

4gram 729036093

5gram 998402245

6gram 1162239794

7gram 1253270154

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