End-Tokens are Required to make Ngram Models Proper

Question

The standard bigram model, (for example defined here) defines a probability distribution over a corpus $V$ based on the following principles:

1. The marginal probability of a word $w$ is defined as its count in $V$ divided by the total number of words (counting repetitions) in $V$: $P(w) = \text{count}(w) / |V|$
2. The conditional probability of a word to follow another word is defined intuitively as the ratio of the count of the bigram to the count of the first word: $p(w_2|w_1) = \text{count}(w_1 w_2) / \text{count}(w_1)$
3. (Markov Assumption): the probability of a sentence (a sequence of words) can be calculated by the chain rule: $p(w_1 w_2 ... w_n) = p(w_1) p(w_2|w_1) p(w_3|w_1 w_2)... \approx p(w_1) p(w_2|w_1) p(w_3|w_2) ...$

However, this does not seem to define a proper probability distribution. For example, take a corpus $V = \text{"foo bar baz"}$. Then, take the joint distribution defined over all possible bigrams $w_1 w_2$. By our principles:

\begin{equation} p(w_1 w_2) = p(w_1) p(w_2|w_1) = [\text{count}(w_1) / 3][\text{count}(w_1 w_2) / \text{count}(w_1)] \end{equation}

If $w_1 w_2$ is not in the corpus, it is clear that $p(w_1 w_2) = 0$. Therefore, the only nonzero entries in the joint distribution are $p(\text{foo bar}) = p(\text{bar baz}) = 1/3$. The sum of these is $2/3 \neq 1$, so isn't this distribution improper?

Answer 1

In your case here the denominator is not $3$, but $2$, since your simple corpus only contains two 2-word ordered sequences $W_1W_2$ as $\text{"foo bar"}$ and $\text{"bar baz"}$. Therefore $p(\text{foo bar}) = p(\text{bar baz}) = 1/2$, and the distribution becomes proper. In general the approximate formula for $p(W_1W_2)$ should be $count(W_1W_2)/count(\text{total # of 2-word ordered sequence})$.

Answer 2

I found a solution to make it consistent. For an ngram model, we must add $n-1$ end-tokens at the end of the corpus. Then, our possible bigrams in the example become "foo bar", "bar baz", and "baz END".

We can form a proper probability distribution over all bigrams $p(W_1 = w_1, W_2 = w_2) = \text{count}(w_1 w_2)/3$. Then, [1]/[2]/[3] can all be satisfied, since:

1. $p(W_1 = w) = \sum_{w_2} p(W_1 = w, W_2 = w_2) = 1/3$ if $w$ is "foo", "bar", or "baz"
2. $p(W_2 = w_2 | W_1 = w_1) = p(W_1 = w_1, W_2 = w_2) / p(W_1 = w_1)$ which is exactly what we want.

[3] is trickier because we are switching from a probability distribution over bigrams, to a probability distribution over all sentences. It turns out that adding the end token(s) makes this a proper distribution over all sentences (of length $\geq n$) formed by words in the corpus excluding the end-token.

Using our example, the probabilities of all possible 2-grams are "foo bar" = (1/3) * (1/1) = 1/3, "bar baz" = (1/3) * (1/1) = 1/3, and "foo foo" = "foo baz" = "bar foo" = "bar bar" = "baz foo" = "baz bar" = "baz baz" = 0. This sums to 2/3. The only non-zero probability 3-gram is "foo bar baz" with probability 1/3. These probabilities add to 1.

Without the end token, every set of all possible k-grams would sum to probability 1; for example, you can validate this using the corpus $V = [ \text{foo foo}, \text{foo bar}, \text{bar foo} ]$, in which case the probabilities of "foo foo", "foo bar", "bar foo", "bar bar" would sum to 1, as would the probabilities of "foo foo foo", "foo foo bar", ... etc. The end-token adds a down-weighting term for sequences which creates a geometric sequence, such that the probability of all sentences over all k adds to 1.