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

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?

• My understanding is that a sequence n-1 may occur more frequently at the end of sentences, but your model won't take this into account unless you use </s>. – fenceop Feb 24 '15 at 16:18
• This is the intuitive way to implement ngrams. I played with them a few times for markov chains when I was younger, without formal stuff like this to tell me what to do. It was obvious to have a special start and end token. Did you try another way to implement it? Is it as simple? – hippietrail Feb 24 '15 at 17:02
• I agree with both of you. That's really intuitive. But let's suppose you have a bad text, with just a few periods (some people seem to replace them by commas). In such a context, it would not be easy to mark sentence endings with end-symbols. Then is it right to infer from the book that probabilities would just blow up and the use of n-grams would become invalid? – mcrisc Feb 24 '15 at 19:17
• Ah well now you're talking about a real problem! I think many people implement punctuation in various ways. I tried one token per symbol and one token per run of symbols, where symbol means neither a letter nor whitespace. The terms you should read up on are "sentence segmentation" and "sentence splitting". Segmentation is also a general problem at every level of spoken and written NLP. – hippietrail Feb 25 '15 at 3:43
• You've thrown some light on the problem. I think my mistake was not considering that n-grams should be counted in the context of sentence boundaries. So, my real problem is finding those boundaries. Thanks for your help! – mcrisc Feb 25 '15 at 15:11

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!

• Am I reading you well that after adding <sentence_start> and <sentence_end> tokens the sum of probabilities for all possible sentences generated from given corpus (given n-grams) magically becomes 1? Can you point to a proof of this magic? – Sergey Bushmanov Sep 25 '19 at 19:29
• @SergeyBushmanov I'll look for one; the proof isn't too hard (I had to write it all out once for an exam) but it's also really tedious with a lot of intermediate values. – Draconis Sep 25 '19 at 19:45
• Well, if you say adding <eos> tag is enough to make probability distribution well behaving and it's provable that's enough. Thank you! Though, having a link to proof may still be useful. Many thanks again for taking your time! – Sergey Bushmanov Sep 25 '19 at 20:04
• @SergeyBushmanov Intuitive explanation: without an <eos> tag, there's no distinction between "the probability of seeing two words next to each other" and "the probability of seeing a two-word sentence". The <eos> tag lets you distinguish the two, which is good, because the sum of "the probability of seeing an N-word sentence" for all N should be 1, but the sum of "the probability of seeing N words next to each other" for all N should be significantly higher than that (because the probability of seeing one word, ever, at all, should be extremely high—and that's just the N=1 case!). – Draconis Sep 25 '19 at 20:37