HardNLPnlp-129

Kneser-Ney Discount (Lite)

Problem

Estimate the Kneser-Ney discount from a list of bigram counts using counts of counts: D = n1 / (n1 + 2 * n2), where n1 is the number of bigrams seen exactly once and n2 the number seen exactly twice.

Return 0.0 when the denominator is 0 or the list is empty.

Hint

Count singletons and doubletons, then apply the closed-form estimate.

Test cases

case 1

in: [[1,1,2,3]]

expected: 0.5

case 2

in: [[3,4]]

expected: 0

case 3

in: [[2,2]]

expected: 0

case 4

in: [[1,1,1]]

expected: 1

case 5

in: [[]]

expected: 0

Starter codePython

def kneser_ney_discount_lite(bigram_counts):
    # Your code here
    pass

5 test cases · run your code against them in the editor