# Curse of dimensionality with language models

In the seminal paper A Neural Probabilistic Language Model, Yoshua Bengio and his colleagues make the following point:

If one wants to model the joint probability distribution of 10 consecutive words in a natural language with a vocabulary $V$ of size $100,000$, there are potentially $100,000^{10}-1$ free parameters.

I guess it's related to degrees of freedom and joint distributions but I just can't get my hands on the exact formula that was used here to come up with $100,000^{10}-1$.

• $100000$ is probably an estimate of the total number of words in the language. – kjetil b halvorsen Dec 1 '15 at 14:16
• @kjetilbhalvorsen 1e5 is the size of the vocabulary, so yes, 1e5 is the total number of unique words in the language, no problem here – Antoine Dec 1 '15 at 14:21

The estimate $100 000^{10}-1$ comes from assuming a discrete model for the $10$ consecutive words, without any simplifications or restrictions, thus using all interactions up to and including order $10$.
It is not important that the words are consecutive, we would get the same count for any ten specified word positions. For each position, it can be any of the $100000$ words, so we need that number of probabilities. So you can build up a cube in $10$-space, wity each dimension cut up in $100000$ boxes. Taking all the combinations, that give $100000^{10}$ boxes, each box giving on possible $10$-word sequence, such as " am I writing now holy blue crap green integrated ideas", which would be a sequence of fairly low probability. Then subtract $1$ to account for the fact that the probabilities must sum to one!
• Many thanks for elaborating. In other words, $100,000^{10}$ gives all the possible 10-element combinations from the vocabulary of size $100,000$. This number is huge but still finite since we're in the discrete case. And estimating the joint probability mass function of a specific 10-word sequence comes down to assigning a probability (probabilities=parameters here I assume) to each portion of that huge but finite discrete sample space. Is that correct? Also, sorry if I'm being dumb but I still don't get why subtracting 1 ensures that the probabilities will sum to one. – Antoine Dec 1 '15 at 15:34
• subtracting one does not by itself secure that the probabilities will sum to one, but it takes care of that restriction . After freely choosing the $100000^{10}-1$ probabilities, you can calculate the last one! – kjetil b halvorsen Dec 1 '15 at 15:55