What's the real need for an end-symbol in n-gram models?

Question

There's a footnote in Jurafsky & Martin (2008, p.89) pointing out that, without an end-symbol, an n-gram model would not be "a true probability distribution". Even after seeking the paper they've referenced, I could not get the point. Here is the example and the footnote:

<s> I am Sam </s>
<s> Sam I am </s>
<s> I do not like green eggs and ham </s>

About the end-symbol, </s>, the authors say:

"We need the end-symbol to make the bigram grammar a true probability distribution. Without an end-symbol, the sentence probabilities for all sentences of a given length would sum to one, and the probability of the whole language would be infinite."

Could someone help me to interpret the quoted part above? Or, does anybody know about some resource that could help me understand what is the need for an end-symbol in n-gram models?

Answer 1

Without loss of generality, let's consider a bigram model (looking at two words at a time), without a beginning or end marker. Let's also assume our language has at least one sentence of length two, at least one sentence of length three, and at least one sentence of length four.

What's the probability of seeing the sentence "I am", with nothing before or after it? In our model, it would be $P("I") \times P("am"|"I")$: the odds of seeing "I", times the odds of seeing "am" when you've already seen "I".

Now, what's the probability of seeing any sentence of length two in this model? We can see it should be $\sum_v \sum_w P(v) \times P(w|v)$: same as above, but summing over all possible words instead of just "I" and "am".

But this is the same as $\sum_v P(v) \sum_w P(w|v) = \sum_v P(v) \times 1$, by laws of probability. And we know that $\sum_v P(v) = 1$. Therefore the probability of having a sentence of length two is 1.

And this is a problem. Because we know that there are also sentences that are not length two. You can repeat this proof with length three, and find that the probability of having a sentence of length three is also 1. And same for four, and so on…

But we want the probability of seeing a sentence to be 1, because that's how probability works, which means the probability of seeing a sentence of length two (and the probability of seeing a sentence with length three, and…) has to be less than 1.

It turns out, adding a sentence-end marker fixes this. Because now when we're taking that sum over $v$ and $w$, we can specify that $w="</s>"$, and the sum becomes $\sum_v P(v,"</s>")$, which is significantly less than 1. I won't prove it here, but you can go through some tedious probability math to show that adding beginning and ending markers makes the probability distribution valid (the probability of seeing a sentence at all is now 1).

P.S. If you find the LaTeX source fragments annoying to read, vote here to get proper rendering support on this site!

Answer 2

It turns out Bigram will give a true probability distribution

The previous version of the textbook shows its reference for this statement (you can search it online)

"Chen and Goodman (1998) We need the end-symbol to make the bigram grammar a true probability distribution. Without an end-symbol, the sentence probabilities for all sentences of a given length would sum to one, and the probability of the whole language would be infinite.”

I found the paper Chen and Goodman (1998).

bi-gram is just an approximation of n-gram.

If you work on the exercise from the book 3.5, by appending </s>:

<s> a b </s>
<s> b b </s>
<s> b a </s>
<s> a a </s>

P(a | <s>) = 0.25
P(a | a) = 0.25
p(</s> | a) = 0.5

# you get a tree
            <s>
      a             b
   a  b </s>     a  b </s>
...

P(L=1) = 0.5, P(L=2) = 0.25 ... P(L = N) = P(L=N-1) / 2

The sum of all P(L) will be 1.

helpful deck: https://courses.grainger.illinois.edu/cs447/fa2020/Slides/Lecture03.pdf

Answer 3

This is my own proof for this problem. Hope it helps someone who are struggling with this problem himself.

The problem:

Why do we need the end-of-sentence(eos) marker at all?

It boils down to this interesting definition of "what is a sentence"?

1. Without a eos marker: We're compelled to this definition:

A sentence of length n is a word sequence of length n.

As @Draconis pointed out, there's no real difference between a n-long word sequence and a n-long sentence! This is what causes the problem here. The sum of probability of all sentence of length n is equals to 1, which is something we don't want because we want the model to output something more useful: the probability of a n-long sentence in the sample space of all sentences(arbitrary length), not in the sample space of sentences of length n.

2. With a eos marker(game-changer): We have the new definition of a sentence:

A sentence of length n is a word sequence of length (n + 1) with the last word being eos

Problem solved! The sum of probability of all sentence of length 2 is now:

$\sum_v \sum_w P(v,w,eos) <= \sum_v \sum_w \sum_t P(vwt) = 1$. So are sentence of length n

What's left is to prove: $sum_u P(u,eos) = 1$ for all u is the word sequence of a sentence.

sum_u P(u, eos) = sum_u(P(?, eos) * P(u | eos)) = P(?, eos) * sum_u P(u |eos). I claim that sum_u P(u | eos) = 1 / P(?, eos).

Indeed, we denote:

number of word occurrences(including duplicates) as C_w.
number of word sequence (u, eos) as C(u, eos)
number of word sequence that ends with eos as C(?, eos)

Now, P(?, eos) = C(?, eos) / C_w. Furthemore:

Sum_u P(u | eos) = sum_u C(u, eos) / C(?, eos) = (sum_u C(u, eos)) / C(?, eos) = C_w / C(?, eos) = 1 / P(eos). Q.E.D