Special Tokens
In the second part of this week's online lesson, we'll pick up on the other loose thread from the lecture: the fact that the first probability in the Markov language model (as written on the board and in the slides) looks out of place.
A Strange Probability
To quickly recap the problem: when we were deriving the math for the bigram language model on the board, we ended up with the following:
$$ P(w_1,w_2,\dots,w_k) \approx P(w_1)P(w_2|w_1)P(w_3|w_2) \dots P(w_k|w_{k-1}) $$
Notice how we can almost reduce this to a single product:
$$ \approx \prod_{i=1}^k P(w_i|w_{i-1}) $$
The thing that's stopping us is that first probability for \( w_1 \). Expanding that product would tell us that the first term should be \( P(w_1|w_0) \), but that's not what we wrote on the board—because there is no \( w_0 \).
...or is there?
Oh, the suspense!
Defining \( w_0 \)
Without a \( w_0 \), we were forced to make the first probability look different from the rest, as just \( P(w_1) \) with no conditioning. Let's take a step back to analyze what this actually means. \( P(w_1) \) is the unigram probability of token \( w_1 \); in other words, the probability of a particular token (like "Angeles") appearing at all, regardless of context. That means we're saying that to start generating a new sentence, the model should just randomly sample a token from the context-free distribution of all possible tokens.
But in the same way that we intuitively think that prior context should inform the probability of the next token (e.g., "Angeles" is much more likely after "Los"), it also makes intuitive sense to think that the context of being at the start of the sentence should inform the probability of the first token (e.g., "Angeles" is unlikely to be the very first word of a sentence, because we expect it to usually be preceded by "Los"). To formalize this intuition, we need some way of representing the concept of "being at the start of the sentence" as context in the Markov model.
Hmm, I almost feel like I've seen something kind of like this before...
-
Do tell!
-
Well, last week we talked about replacing out-of-vocabulary tokens with a generic
<OOV>token, right? 
Oh yeah! And if we did that, sometimes
<OOV>would appear in the context window of a Markov language model, despite not being a "real word"!-
Exactly! And one way to interpret something like \( P(w_i| \)
<OOV>\( ) \) is the probability of \( w_i \) following an out-of-vocabulary token. 
Oh! So if the context can include a "symbolic" token like
<OOV>, which symbolizes the concept of an unknown token...-
...could we also have a special token that symbolizes the concept of the start of the sentence?
-
Great teamwork, everyone!
Indeed, the solution to this problem will be introducing a new special token. Given any sentence in the data, represented as a token sequence \( w_1,w_2,\dots,w_n \), when training the model we will pretend the sentence was preceded by a special token \( w_0 \). By custom, we will use a string like "<SOS>" (not a distress call, but instead an acronym for "start of sentence") to denote this special token. \( w_1 \) will still be the first "real" token, but now the probability \( P(w_1|w_0) \) makes sense. Specifically, it represents the probability of seeing token \( w_1 \) as the first token in the sentence!
And now that we have a defined \( w_0 \), the short-form product \( \prod_i P(w_i|w_{i-1}) \) actually works as a concise formula for the Markov language model!
-
All's well that ends well!
-
Oh, speaking of endings...
The Halting Problem (no, not that one)
Special tokens aren't just useful for denoting the start of sentences, but also the end of sentences as well! This helps us solve a problem that you might not have realized during lecture: how does a Markov language model know when to stop generating? One idea might be to stop as soon as we reach a punctuation mark, but there are two problems with this. First, the vocabulary might exclude punctuation. Second, even if punctuation is included, we saw in Lab 1 that not all punctuation represents the end of a sentence.
So instead, what we typically do is not only add <SOS> to the start of sentences during training, but also add another special token <EOS> to the end of sentences. Then the model will know to stop generating if it happens to generate the <EOS> token.
"End of Service"? Noooo, what's gonna happen to all my rare gacha pulls?
-
Relax—in this case,
<EOS>stands for "end of sentence".
Higher-order \( n \)-gram Language Models
Above, we showed the math for bigram language models, but the same math generalizes to larger context sizes (i.e., larger values of \( n \)). The general formula for an \( n \)-gram language model (which, again as a reminder, has context size \( n-1 \)) is:
$$ P(w_1,w_2,\dots,w_k) \approx \prod_{i=1}^k P(w_i|w_{i-1},w_{i-2},\dots,w_{i-n-1}) $$
Hay, wait! If you expand that first term for, say, \( n = 3 \), you get \( P(w_1|w_0,w_{-1}) \)!
-
\( w_{-1} \)??? I'm scared, Mom come pick me up!
Technically, to make the above math work, we'd need to add more <SOS> tokens to the start of each sentence; for any \( n \)-gram model the context window contains \( n-1 \) tokens, so you'd need to add \( n-1 \) <SOS> tokens to have a complete context preceding \( w_1 \). But this is clunky and annoying, so in practice what we do instead is stick with only one <SOS> token, and use backoff to reduce the first probability to the bigram probability \( P(w_1|w_0) \).
(When logged in, completion status appears here.)