# In Kneser-Ney smoothing, how are unseen words handled?

From what I have seen, the (second-order) Kneser-Ney smoothing formula is in some way or another given as

\begin{align} P^2_{KN}(w_n|w_{n-1}) &= \frac{\max \left\{ C\left(w_{n-1}, w_n\right) - D, 0\right\}}{\sum_{w'} C\left(w_{n-1}, w'\right)} + \lambda(w_{n-1}) \times P_{cont}(w_n) \end{align}

with the normalizing factor $\lambda(w_{n-1})$ given as

\begin{align} \lambda(w_{n-1}) &= \frac{D}{\sum_{w'} C\left(w_{n-1}, w'\right)} \times N_{1+}\left(w_{n-1}\bullet\right) \end{align}

and the continuation probability $P_{cont}(w_n)$ of a word $w_n$

\begin{align} P_{cont}(w_n) &= \frac{N_{1+}\left(\bullet w_{n}\right)}{\sum_{w'} N_{1+}\left(\bullet w'\right)} \end{align}

where $N_{1+}\left(\bullet w\right)$ is the number of contexts $w$ was seen in or, simplier, the number of distinct words $\bullet$ that precede the given word $w$. From what I've understood, the formula can be applied recursively.

Now this handles known words in unknown contexts nicely for different n-gram lengths, but what it doesn't explain is what to do when there are out-of-dictionary words. I tried following this example which states that in the recursion step for unigrams, $P_{cont}(/) = P^0_{KN}(/) = \frac{1}{V}$. The document then uses this - quoting Chen and Goodman - to justify the above formula as $P^1_{KN}(w) = P_{cont}(w)$.

I fail to see how it works out in the presence of an unknown word $w = \text{unknown}$ though. In these cases $P_{cont}(\text{unknown}) = \frac{0}{\text{something}}$ since, obviously, the unknown word doesn't continue anything regarding the training set. Likewise the count of n-grams is going to be $C\left(w_{n-1}, \text{unknown}\right) = 0$.

Furthermore, the whole $\sum_{w'} C\left(w_{n-1}, w'\right)$ term might be zero if a sequence of unknown words - say, a trigram of OOD words - is encountered.

What am I missing?

• I am struggling with KN too. I think the probability of an unseen bigram P(w1w2) could backoff to the continuation probability of the last unigram w2. When you are left with an unseen unigram you had nothing. What to do next? I don't know. Sep 19, 2014 at 7:37
• I'm trying to implement KN myself at the moment and am stuck with this same issue. Did either of you two manage to find a solution? Jul 14, 2015 at 19:50
• I fell back to Good-Turing smoothing for unseen unigrams (fitting a power function to the frequencies and frequency-of-frequencies) ... with varying results. Jul 14, 2015 at 22:11

At the termination of the recursion, unigrams are interpolated with the uniform distribution:

\begin{align} P_{KN}(w) = \frac{\max(c_{KN}(w)-d,0)}{\sum_{w'}c_{KN}(w')}+\lambda(\epsilon)\frac{1}{|V|} \end{align}

If we want to include an unknown word <UNK>, it’s just included as a regular vocabulary entry with count zero, and hence its probability will be:

\begin{align} \frac{\lambda(\epsilon)}{|V|} \end{align}

I've tried to find out what this means, but am not sure if $\epsilon$ just means $\lim_{x\rightarrow0}x$. If this is the case, and you assume that as the count goes to zero, maybe $\lambda(\epsilon)$ goes to $d$, according to:

\begin{align} \lambda(w_{i-1}) = \frac{d}{c(w_{i-1})}\vert\{w:c(w_{i-1},w)>0\}\vert \end{align}

then the unknown word just gets assigned a fraction of the discount, i.e.:

\begin{align} \frac{\lambda(\epsilon)}{|V|} = \frac{d}{|V|} \end{align}

Update: Digging around some more, it seems like $\epsilon$ is typically used to denote the empty string (""), but it's still not clear how this affects the calculation of $\lambda$. $\frac{d}{|V|}$ is still my best guess

• Good answer but like you I'm not 100% confident in it. I implemented a version of the perl script research.microsoft.com/en-us/um/redmond/groups/srg/papers/… in python - but realized it only works as-is if you have a closed vocabulary (0 prob issue) - i.e. all test unigrams are also in train. As suggested by Jan lagunita.stanford.edu/c4x/Engineering/CS-224N/asset/slp4.pdf I replaced each word's first instance with <UNK> during pre-processing. However, when partitioning, there are some test unigrams not in train like "goofedup". So I used d/|V| here. Thanks! May 21, 2016 at 16:32

There are many ways to train a model with <UNK> though Jurafsky suggests to choose those words that occur very few times in training and simply change them to <UNK>.

Then simply train the probabilities as you normally would.

See this video starting at 3:40 –

https://class.coursera.org/nlp/lecture/19

Another approach is to simply consider a word as <UNK> the very first time it is seen in training, though from my experience this approach assigns too much of the probability mass to <UNK>.

Just a few thoughts, I am far from being an expert on the matter so I do not intend to provide an answer to the question but to analyze it.

The simple thing to do would be to calculate $\lambda(\epsilon)$ by forcing the sum to be one. This is reasonable since the empty string is never seen in the training set (nothing can be predicted out of nothing) and the sum has to be one. If this is the case, $\lambda(\epsilon)$ can be estimated by: $$\lambda(\epsilon)=1-\frac{\sum_w{max(C_{KN}(w) - d, 0)}}{\sum_{w'}{C_{KN}(w)}}$$ Remember that here $C_{KN}(w)$ is obtained from the bigram model.

Another option would be to estimate the <unk> probability with the methods mentioned by Randy and treating it as a regular token.

I think this step is made to ensure that the formulas are consistent. Notice that the term $\frac{\lambda(\epsilon)}{|V|}$ does not depend on the context and assigns fixed values to the probabilities of every token. If you want to predict the next word you can prescind this term, on the other hand if you want to compare the Kneser - Ney probability assigned to each token under two or more different contexts you might want to use it.

• Answers are suppose to be for actual answers. Jul 14, 2017 at 3:57