Smoothing: Laplace and Kneser-Ney

This small script compares MLE, Laplace, and interpolated Kneser-Ney on the same context.

pairs = {
    ("new", "york"): 1,
    ("new", "models"): 1,
    ("old", "york"): 1,
    ("near", "york"): 1,
    ("old", "san"): 1,
    ("near", "san"): 1,
    ("san", "francisco"): 3,
    ("smart", "models"): 1,
}

candidates = ["york", "models", "san", "francisco"]
context = "new"
D = 0.75

def count(h, w):
    return pairs.get((h, w), 0)

def total(h):
    return sum(n for (left, _), n in pairs.items() if left == h)

def histories(w):
    return {left for (left, right), n in pairs.items() if right == w and n > 0}

V = len(candidates)
T = total(context)
types_after_context = sum(1 for w in candidates if count(context, w) > 0)
bigram_types = sum(1 for n in pairs.values() if n > 0)
reserved = D * types_after_context / T

for w in candidates:
    mle = count(context, w) / T
    laplace = (count(context, w) + 1) / (T + V)
    continuation = len(histories(w)) / bigram_types
    kn = max(count(context, w) - D, 0) / T + reserved * continuation
    print(f"{w:10s} MLE={mle:.3f} Laplace={laplace:.3f} KN={kn:.3f}")

The important comparison is not just "zero or nonzero." It is whether the smoother has a reason to prefer one unseen continuation over another.