I'm working in a project trying to implement the Kneser-Key algorithm. I think I got up to the step of implementing this formula for bigrams:

$P_{(KN)}(w_i|w_{i-1}) = \frac{max(c(w_{-1}, w_{1}) - \delta, 0)}{\sum_{w'}{c(w_{i-1}, w')}} + \lambda_{w_{i-1}}P_{continuation}(w_i) $

But this is not the final formula. The final formula includes a recursion, where you consider more than 2 gram levels. I intend to use from 4grams to unigrams in my code. So, the formula with the recursion is as follows:

enter image description here

Source: https://lagunita.stanford.edu/c4x/Engineering/CS-224N/asset/slp4.pdf

I'm not too familiar with this notation, so not sure how to add up the 4grams probability with the 3 grams, bigrams and unigrams.

Thanks a lot


1 Answer 1


It means that in order to compute the $k$-gram probability distribution, you first need to compute the $(k-1)$-gram probability distribution.

  • $\begingroup$ Thank you Franck, I think I got the recursion. So if I want to compute a trigram, just take my previus calculation for the corresponding bigram, and weight it using Lambda. So, if my trigram is "this is it", where the first termi is.. lets say: 0.8, and the KN probability for the bigram "is it" is 0.4, then the KN probability for the trigram will be 0.8 + Lambda * 0.4 Does it makes sense? $\endgroup$ Commented Jun 26, 2016 at 21:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.