This is my own proof for this problem. Hope it helps someone who are struggling with this problem himself.
Why do we need the end-of-sentence(eos) marker at all?
It boils down to this interesting definition of "what is a sentence"?
- 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.
- 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