How to perform Kneser-Ney smoothing in NLTK at word-level for bigram language model?

Question

From the nltk package, I see we can implement Kneser-Ney smoothing only using trigrams but it throws error when I try to use the same function on bigrams. Is there a way we can implement smoothing on bigrams?

## Working code for trigrams 
tokens = "What a piece of work is man! how noble in reason! how infinite in faculty! in \
    form and moving how express and admirable! in action how like an angel! in apprehension how like a god! \
    the beauty of the world, the paragon of animals!".split()
gut_ngrams = nltk.ngrams(tokens,3)
freq_dist = nltk.FreqDist(gut_ngrams)
kneser_ney = nltk.KneserNeyProbDist(freq_dist)

user_610569 · Answer

Firstly, lets look at the code and implementation.

When we use bigrams:

import nltk

tokens = "What a piece of work is man! how noble in reason! how infinite in faculty! in \
    form and moving how express and admirable! in action how like an angel! in apprehension how like a god! \
    the beauty of the world, the paragon of animals!".split()
gut_ngrams = nltk.ngrams(tokens,2)
freq_dist = nltk.FreqDist(gut_ngrams)
kneser_ney = nltk.KneserNeyProbDist(freq_dist)

The code throws an error:

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
 in 
      4 gut_ngrams = nltk.ngrams(tokens,2)
      5 freq_dist = nltk.FreqDist(gut_ngrams)
----> 6 kneser_ney = nltk.KneserNeyProbDist(freq_dist)

~/.pyenv/versions/3.8.0/lib/python3.8/site-packages/nltk/probability.py in __init__(self, freqdist, bins, discount)
   1737         self._trigrams_contain = defaultdict(float)
   1738         self._wordtypes_before = defaultdict(float)
-> 1739         for w0, w1, w2 in freqdist:
   1740             self._bigrams[(w0, w1)] += freqdist[(w0, w1, w2)]
   1741             self._wordtypes_after[(w0, w1)] += 1

ValueError: not enough values to unpack (expected 3, got 2)

If we look at the implementation, https://github.com/nltk/nltk/blob/develop/nltk/probability.py#L1700

class KneserNeyProbDist(ProbDistI):
    def __init__(self, freqdist, bins=None, discount=0.75):
        if not bins:
            self._bins = freqdist.B()
        else:
            self._bins = bins
        self._D = discount

        # cache for probability calculation
        self._cache = {}

        # internal bigram and trigram frequency distributions
        self._bigrams = defaultdict(int)
        self._trigrams = freqdist

        # helper dictionaries used to calculate probabilities
        self._wordtypes_after = defaultdict(float)
        self._trigrams_contain = defaultdict(float)
        self._wordtypes_before = defaultdict(float)
        for w0, w1, w2 in freqdist:
            self._bigrams[(w0, w1)] += freqdist[(w0, w1, w2)]
            self._wordtypes_after[(w0, w1)] += 1
            self._trigrams_contain[w1] += 1
            self._wordtypes_before[(w1, w2)] += 1

We see that in the initialization there's some assumptions made when computing the n-gram before and the n-gram after the current word:

 for w0, w1, w2 in freqdist:
        self._bigrams[(w0, w1)] += freqdist[(w0, w1, w2)]
        self._wordtypes_after[(w0, w1)] += 1
        self._trigrams_contain[w1] += 1
        self._wordtypes_before[(w1, w2)] += 1

In that case, only trigrams works with the KN smoothing for the KneserNeyProbDist object!!

Lets try it with a fourgram:

tokens = "What a piece of work is man! how noble in reason! how infinite in faculty! in \
    form and moving how express and admirable! in action how like an angel! in apprehension how like a god! \
    the beauty of the world, the paragon of animals!".split()
gut_ngrams = nltk.ngrams(tokens,4)
freq_dist = nltk.FreqDist(gut_ngrams)
kneser_ney = nltk.KneserNeyProbDist(freq_dist)

[out]:

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
 in 
      4 gut_ngrams = nltk.ngrams(tokens,4)
      5 freq_dist = nltk.FreqDist(gut_ngrams)
----> 6 kneser_ney = nltk.KneserNeyProbDist(freq_dist)

~/.pyenv/versions/3.8.0/lib/python3.8/site-packages/nltk/probability.py in __init__(self, freqdist, bins, discount)
   1737         self._trigrams_contain = defaultdict(float)
   1738         self._wordtypes_before = defaultdict(float)
-> 1739         for w0, w1, w2 in freqdist:
   1740             self._bigrams[(w0, w1)] += freqdist[(w0, w1, w2)]
   1741             self._wordtypes_after[(w0, w1)] += 1

ValueError: too many values to unpack (expected 3)

Voila!! It doesn't work too!!!

Q: So does that mean it's not possible to get the KN smoothing to work in NLTK for language modeling?

A: That's not exactly true. There's a proper Language Model module in NLTK nltk.lm and here's an tutorial example to use it https://www.kaggle.com/alvations/n-gram-language-model-with-nltk/notebook#Training-an-N-gram-Model

But that just show the usage of a normal MLE model. I want an LM with Kneser-Ney Smoothing

Then you just have to define the right Language Model object correct =)

TL;DR

from nltk.lm import KneserNeyInterpolated
from nltk.lm.preprocessing import padded_everygram_pipeline

tokens = "What a piece of work is man! how noble in reason! how infinite in faculty! in \
    form and moving how express and admirable! in action how like an angel! in apprehension how like a god! \
    the beauty of the world, the paragon of animals!".split()

n = 4 # Order of ngram
train_data, padded_sents = padded_everygram_pipeline(n, tokens)

model = KneserNeyInterpolated(n) 
model.fit(train_data, padded_sents)