Source code for nltk.test.unit.lm.test_models

# Natural Language Toolkit: Language Model Unit Tests
#
# Copyright (C) 2001-2022 NLTK Project
# Author: Ilia Kurenkov <ilia.kurenkov@gmail.com>
# URL: <https://www.nltk.org/>
# For license information, see LICENSE.TXT
import math
from operator import itemgetter

import pytest

from nltk.lm import (
    MLE,
    AbsoluteDiscountingInterpolated,
    KneserNeyInterpolated,
    Laplace,
    Lidstone,
    StupidBackoff,
    Vocabulary,
    WittenBellInterpolated,
)
from nltk.lm.preprocessing import padded_everygrams


[docs]@pytest.fixture(scope="session") def vocabulary(): return Vocabulary(["a", "b", "c", "d", "z", "<s>", "</s>"], unk_cutoff=1)
[docs]@pytest.fixture(scope="session") def training_data(): return [["a", "b", "c", "d"], ["e", "g", "a", "d", "b", "e"]]
[docs]@pytest.fixture(scope="session") def bigram_training_data(training_data): return [list(padded_everygrams(2, sent)) for sent in training_data]
[docs]@pytest.fixture(scope="session") def trigram_training_data(training_data): return [list(padded_everygrams(3, sent)) for sent in training_data]
[docs]@pytest.fixture def mle_bigram_model(vocabulary, bigram_training_data): model = MLE(2, vocabulary=vocabulary) model.fit(bigram_training_data) return model
[docs]@pytest.mark.parametrize( "word, context, expected_score", [ ("d", ["c"], 1), # Unseen ngrams should yield 0 ("d", ["e"], 0), # Unigrams should also be 0 ("z", None, 0), # N unigrams = 14 # count('a') = 2 ("a", None, 2.0 / 14), # count('y') = 3 ("y", None, 3.0 / 14), ], ) def test_mle_bigram_scores(mle_bigram_model, word, context, expected_score): assert pytest.approx(mle_bigram_model.score(word, context), 1e-4) == expected_score
[docs]def test_mle_bigram_logscore_for_zero_score(mle_bigram_model): assert math.isinf(mle_bigram_model.logscore("d", ["e"]))
[docs]def test_mle_bigram_entropy_perplexity_seen(mle_bigram_model): # ngrams seen during training trained = [ ("<s>", "a"), ("a", "b"), ("b", "<UNK>"), ("<UNK>", "a"), ("a", "d"), ("d", "</s>"), ] # Ngram = Log score # <s>, a = -1 # a, b = -1 # b, UNK = -1 # UNK, a = -1.585 # a, d = -1 # d, </s> = -1 # TOTAL logscores = -6.585 # - AVG logscores = 1.0975 H = 1.0975 perplexity = 2.1398 assert pytest.approx(mle_bigram_model.entropy(trained), 1e-4) == H assert pytest.approx(mle_bigram_model.perplexity(trained), 1e-4) == perplexity
[docs]def test_mle_bigram_entropy_perplexity_unseen(mle_bigram_model): # In MLE, even one unseen ngram should make entropy and perplexity infinite untrained = [("<s>", "a"), ("a", "c"), ("c", "d"), ("d", "</s>")] assert math.isinf(mle_bigram_model.entropy(untrained)) assert math.isinf(mle_bigram_model.perplexity(untrained))
[docs]def test_mle_bigram_entropy_perplexity_unigrams(mle_bigram_model): # word = score, log score # <s> = 0.1429, -2.8074 # a = 0.1429, -2.8074 # c = 0.0714, -3.8073 # UNK = 0.2143, -2.2224 # d = 0.1429, -2.8074 # c = 0.0714, -3.8073 # </s> = 0.1429, -2.8074 # TOTAL logscores = -21.6243 # - AVG logscores = 3.0095 H = 3.0095 perplexity = 8.0529 text = [("<s>",), ("a",), ("c",), ("-",), ("d",), ("c",), ("</s>",)] assert pytest.approx(mle_bigram_model.entropy(text), 1e-4) == H assert pytest.approx(mle_bigram_model.perplexity(text), 1e-4) == perplexity
[docs]@pytest.fixture def mle_trigram_model(trigram_training_data, vocabulary): model = MLE(order=3, vocabulary=vocabulary) model.fit(trigram_training_data) return model
[docs]@pytest.mark.parametrize( "word, context, expected_score", [ # count(d | b, c) = 1 # count(b, c) = 1 ("d", ("b", "c"), 1), # count(d | c) = 1 # count(c) = 1 ("d", ["c"], 1), # total number of tokens is 18, of which "a" occurred 2 times ("a", None, 2.0 / 18), # in vocabulary but unseen ("z", None, 0), # out of vocabulary should use "UNK" score ("y", None, 3.0 / 18), ], ) def test_mle_trigram_scores(mle_trigram_model, word, context, expected_score): assert pytest.approx(mle_trigram_model.score(word, context), 1e-4) == expected_score
[docs]@pytest.fixture def lidstone_bigram_model(bigram_training_data, vocabulary): model = Lidstone(0.1, order=2, vocabulary=vocabulary) model.fit(bigram_training_data) return model
[docs]@pytest.mark.parametrize( "word, context, expected_score", [ # count(d | c) = 1 # *count(d | c) = 1.1 # Count(w | c for w in vocab) = 1 # *Count(w | c for w in vocab) = 1.8 ("d", ["c"], 1.1 / 1.8), # Total unigrams: 14 # Vocab size: 8 # Denominator: 14 + 0.8 = 14.8 # count("a") = 2 # *count("a") = 2.1 ("a", None, 2.1 / 14.8), # in vocabulary but unseen # count("z") = 0 # *count("z") = 0.1 ("z", None, 0.1 / 14.8), # out of vocabulary should use "UNK" score # count("<UNK>") = 3 # *count("<UNK>") = 3.1 ("y", None, 3.1 / 14.8), ], ) def test_lidstone_bigram_score(lidstone_bigram_model, word, context, expected_score): assert ( pytest.approx(lidstone_bigram_model.score(word, context), 1e-4) == expected_score )
[docs]def test_lidstone_entropy_perplexity(lidstone_bigram_model): text = [ ("<s>", "a"), ("a", "c"), ("c", "<UNK>"), ("<UNK>", "d"), ("d", "c"), ("c", "</s>"), ] # Unlike MLE this should be able to handle completely novel ngrams # Ngram = score, log score # <s>, a = 0.3929, -1.3479 # a, c = 0.0357, -4.8074 # c, UNK = 0.0(5), -4.1699 # UNK, d = 0.0263, -5.2479 # d, c = 0.0357, -4.8074 # c, </s> = 0.0(5), -4.1699 # TOTAL logscore: −24.5504 # - AVG logscore: 4.0917 H = 4.0917 perplexity = 17.0504 assert pytest.approx(lidstone_bigram_model.entropy(text), 1e-4) == H assert pytest.approx(lidstone_bigram_model.perplexity(text), 1e-4) == perplexity
[docs]@pytest.fixture def lidstone_trigram_model(trigram_training_data, vocabulary): model = Lidstone(0.1, order=3, vocabulary=vocabulary) model.fit(trigram_training_data) return model
[docs]@pytest.mark.parametrize( "word, context, expected_score", [ # Logic behind this is the same as for bigram model ("d", ["c"], 1.1 / 1.8), # if we choose a word that hasn't appeared after (b, c) ("e", ["c"], 0.1 / 1.8), # Trigram score now ("d", ["b", "c"], 1.1 / 1.8), ("e", ["b", "c"], 0.1 / 1.8), ], ) def test_lidstone_trigram_score(lidstone_trigram_model, word, context, expected_score): assert ( pytest.approx(lidstone_trigram_model.score(word, context), 1e-4) == expected_score )
[docs]@pytest.fixture def laplace_bigram_model(bigram_training_data, vocabulary): model = Laplace(2, vocabulary=vocabulary) model.fit(bigram_training_data) return model
[docs]@pytest.mark.parametrize( "word, context, expected_score", [ # basic sanity-check: # count(d | c) = 1 # *count(d | c) = 2 # Count(w | c for w in vocab) = 1 # *Count(w | c for w in vocab) = 9 ("d", ["c"], 2.0 / 9), # Total unigrams: 14 # Vocab size: 8 # Denominator: 14 + 8 = 22 # count("a") = 2 # *count("a") = 3 ("a", None, 3.0 / 22), # in vocabulary but unseen # count("z") = 0 # *count("z") = 1 ("z", None, 1.0 / 22), # out of vocabulary should use "UNK" score # count("<UNK>") = 3 # *count("<UNK>") = 4 ("y", None, 4.0 / 22), ], ) def test_laplace_bigram_score(laplace_bigram_model, word, context, expected_score): assert ( pytest.approx(laplace_bigram_model.score(word, context), 1e-4) == expected_score )
[docs]def test_laplace_bigram_entropy_perplexity(laplace_bigram_model): text = [ ("<s>", "a"), ("a", "c"), ("c", "<UNK>"), ("<UNK>", "d"), ("d", "c"), ("c", "</s>"), ] # Unlike MLE this should be able to handle completely novel ngrams # Ngram = score, log score # <s>, a = 0.2, -2.3219 # a, c = 0.1, -3.3219 # c, UNK = 0.(1), -3.1699 # UNK, d = 0.(09), 3.4594 # d, c = 0.1 -3.3219 # c, </s> = 0.(1), -3.1699 # Total logscores: −18.7651 # - AVG logscores: 3.1275 H = 3.1275 perplexity = 8.7393 assert pytest.approx(laplace_bigram_model.entropy(text), 1e-4) == H assert pytest.approx(laplace_bigram_model.perplexity(text), 1e-4) == perplexity
[docs]def test_laplace_gamma(laplace_bigram_model): assert laplace_bigram_model.gamma == 1
[docs]@pytest.fixture def wittenbell_trigram_model(trigram_training_data, vocabulary): model = WittenBellInterpolated(3, vocabulary=vocabulary) model.fit(trigram_training_data) return model
[docs]@pytest.mark.parametrize( "word, context, expected_score", [ # For unigram scores by default revert to regular MLE # Total unigrams: 18 # Vocab Size = 7 # count('c'): 1 ("c", None, 1.0 / 18), # in vocabulary but unseen # count("z") = 0 ("z", None, 0 / 18), # out of vocabulary should use "UNK" score # count("<UNK>") = 3 ("y", None, 3.0 / 18), # 2 words follow b and b occurred a total of 2 times # gamma(['b']) = 2 / (2 + 2) = 0.5 # mle.score('c', ['b']) = 0.5 # mle('c') = 1 / 18 = 0.055 # (1 - gamma) * mle + gamma * mle('c') ~= 0.27 + 0.055 ("c", ["b"], (1 - 0.5) * 0.5 + 0.5 * 1 / 18), # building on that, let's try 'a b c' as the trigram # 1 word follows 'a b' and 'a b' occurred 1 time # gamma(['a', 'b']) = 1 / (1 + 1) = 0.5 # mle("c", ["a", "b"]) = 1 ("c", ["a", "b"], (1 - 0.5) + 0.5 * ((1 - 0.5) * 0.5 + 0.5 * 1 / 18)), # P(c|zb) # The ngram 'zbc' was not seen, so we use P(c|b). See issue #2332. ("c", ["z", "b"], ((1 - 0.5) * 0.5 + 0.5 * 1 / 18)), ], ) def test_wittenbell_trigram_score( wittenbell_trigram_model, word, context, expected_score ): assert ( pytest.approx(wittenbell_trigram_model.score(word, context), 1e-4) == expected_score )
############################################################################### # Notation Explained # ############################################################################### # For all subsequent calculations we use the following notation: # 1. '*': Placeholder for any word/character. E.g. '*b' stands for # all bigrams that end in 'b'. '*b*' stands for all trigrams that # contain 'b' in the middle. # 1. count(ngram): Count all instances (tokens) of an ngram. # 1. unique(ngram): Count unique instances (types) of an ngram.
[docs]@pytest.fixture def kneserney_trigram_model(trigram_training_data, vocabulary): model = KneserNeyInterpolated(order=3, discount=0.75, vocabulary=vocabulary) model.fit(trigram_training_data) return model
[docs]@pytest.mark.parametrize( "word, context, expected_score", [ # P(c) = count('*c') / unique('**') # = 1 / 14 ("c", None, 1.0 / 14), # P(z) = count('*z') / unique('**') # = 0 / 14 # 'z' is in the vocabulary, but it was not seen during training. ("z", None, 0.0 / 14), # P(y) # Out of vocabulary should use "UNK" score. # P(y) = P(UNK) = count('*UNK') / unique('**') ("y", None, 3 / 14), # We start with P(c|b) # P(c|b) = alpha('bc') + gamma('b') * P(c) # alpha('bc') = max(unique('*bc') - discount, 0) / unique('*b*') # = max(1 - 0.75, 0) / 2 # = 0.125 # gamma('b') = discount * unique('b*') / unique('*b*') # = (0.75 * 2) / 2 # = 0.75 ("c", ["b"], (0.125 + 0.75 * (1 / 14))), # Building on that, let's try P(c|ab). # P(c|ab) = alpha('abc') + gamma('ab') * P(c|b) # alpha('abc') = max(count('abc') - discount, 0) / count('ab*') # = max(1 - 0.75, 0) / 1 # = 0.25 # gamma('ab') = (discount * unique('ab*')) / count('ab*') # = 0.75 * 1 / 1 ("c", ["a", "b"], 0.25 + 0.75 * (0.125 + 0.75 * (1 / 14))), # P(c|zb) # The ngram 'zbc' was not seen, so we use P(c|b). See issue #2332. ("c", ["z", "b"], (0.125 + 0.75 * (1 / 14))), ], ) def test_kneserney_trigram_score( kneserney_trigram_model, word, context, expected_score ): assert ( pytest.approx(kneserney_trigram_model.score(word, context), 1e-4) == expected_score )
[docs]@pytest.fixture def absolute_discounting_trigram_model(trigram_training_data, vocabulary): model = AbsoluteDiscountingInterpolated(order=3, vocabulary=vocabulary) model.fit(trigram_training_data) return model
[docs]@pytest.mark.parametrize( "word, context, expected_score", [ # For unigram scores revert to uniform # P(c) = count('c') / count('**') ("c", None, 1.0 / 18), # in vocabulary but unseen # count('z') = 0 ("z", None, 0.0 / 18), # out of vocabulary should use "UNK" score # count('<UNK>') = 3 ("y", None, 3 / 18), # P(c|b) = alpha('bc') + gamma('b') * P(c) # alpha('bc') = max(count('bc') - discount, 0) / count('b*') # = max(1 - 0.75, 0) / 2 # = 0.125 # gamma('b') = discount * unique('b*') / count('b*') # = (0.75 * 2) / 2 # = 0.75 ("c", ["b"], (0.125 + 0.75 * (2 / 2) * (1 / 18))), # Building on that, let's try P(c|ab). # P(c|ab) = alpha('abc') + gamma('ab') * P(c|b) # alpha('abc') = max(count('abc') - discount, 0) / count('ab*') # = max(1 - 0.75, 0) / 1 # = 0.25 # gamma('ab') = (discount * unique('ab*')) / count('ab*') # = 0.75 * 1 / 1 ("c", ["a", "b"], 0.25 + 0.75 * (0.125 + 0.75 * (2 / 2) * (1 / 18))), # P(c|zb) # The ngram 'zbc' was not seen, so we use P(c|b). See issue #2332. ("c", ["z", "b"], (0.125 + 0.75 * (2 / 2) * (1 / 18))), ], ) def test_absolute_discounting_trigram_score( absolute_discounting_trigram_model, word, context, expected_score ): assert ( pytest.approx(absolute_discounting_trigram_model.score(word, context), 1e-4) == expected_score )
[docs]@pytest.fixture def stupid_backoff_trigram_model(trigram_training_data, vocabulary): model = StupidBackoff(order=3, vocabulary=vocabulary) model.fit(trigram_training_data) return model
[docs]@pytest.mark.parametrize( "word, context, expected_score", [ # For unigram scores revert to uniform # total bigrams = 18 ("c", None, 1.0 / 18), # in vocabulary but unseen # bigrams ending with z = 0 ("z", None, 0.0 / 18), # out of vocabulary should use "UNK" score # count('<UNK>'): 3 ("y", None, 3 / 18), # c follows 1 time out of 2 after b ("c", ["b"], 1 / 2), # c always follows ab ("c", ["a", "b"], 1 / 1), # The ngram 'z b c' was not seen, so we backoff to # the score of the ngram 'b c' * smoothing factor ("c", ["z", "b"], (0.4 * (1 / 2))), ], ) def test_stupid_backoff_trigram_score( stupid_backoff_trigram_model, word, context, expected_score ): assert ( pytest.approx(stupid_backoff_trigram_model.score(word, context), 1e-4) == expected_score )
############################################################################### # Probability Distributions Should Sum up to Unity # ###############################################################################
[docs]@pytest.fixture(scope="session") def kneserney_bigram_model(bigram_training_data, vocabulary): model = KneserNeyInterpolated(order=2, vocabulary=vocabulary) model.fit(bigram_training_data) return model
[docs]@pytest.mark.parametrize( "model_fixture", [ "mle_bigram_model", "mle_trigram_model", "lidstone_bigram_model", "laplace_bigram_model", "wittenbell_trigram_model", "absolute_discounting_trigram_model", "kneserney_bigram_model", pytest.param( "stupid_backoff_trigram_model", marks=pytest.mark.xfail( reason="Stupid Backoff is not a valid distribution" ), ), ], ) @pytest.mark.parametrize( "context", [("a",), ("c",), ("<s>",), ("b",), ("<UNK>",), ("d",), ("e",), ("r",), ("w",)], ids=itemgetter(0), ) def test_sums_to_1(model_fixture, context, request): model = request.getfixturevalue(model_fixture) scores_for_context = sum(model.score(w, context) for w in model.vocab) assert pytest.approx(scores_for_context, 1e-7) == 1.0
############################################################################### # Generating Text # ###############################################################################
[docs]def test_generate_one_no_context(mle_trigram_model): assert mle_trigram_model.generate(random_seed=3) == "<UNK>"
[docs]def test_generate_one_from_limiting_context(mle_trigram_model): # We don't need random_seed for contexts with only one continuation assert mle_trigram_model.generate(text_seed=["c"]) == "d" assert mle_trigram_model.generate(text_seed=["b", "c"]) == "d" assert mle_trigram_model.generate(text_seed=["a", "c"]) == "d"
[docs]def test_generate_one_from_varied_context(mle_trigram_model): # When context doesn't limit our options enough, seed the random choice assert mle_trigram_model.generate(text_seed=("a", "<s>"), random_seed=2) == "a"
[docs]def test_generate_cycle(mle_trigram_model): # Add a cycle to the model: bd -> b, db -> d more_training_text = [padded_everygrams(mle_trigram_model.order, list("bdbdbd"))] mle_trigram_model.fit(more_training_text) # Test that we can escape the cycle assert mle_trigram_model.generate(7, text_seed=("b", "d"), random_seed=5) == [ "b", "d", "b", "d", "b", "d", "</s>", ]
[docs]def test_generate_with_text_seed(mle_trigram_model): assert mle_trigram_model.generate(5, text_seed=("<s>", "e"), random_seed=3) == [ "<UNK>", "a", "d", "b", "<UNK>", ]
[docs]def test_generate_oov_text_seed(mle_trigram_model): assert mle_trigram_model.generate( text_seed=("aliens",), random_seed=3 ) == mle_trigram_model.generate(text_seed=("<UNK>",), random_seed=3)
[docs]def test_generate_None_text_seed(mle_trigram_model): # should crash with type error when we try to look it up in vocabulary with pytest.raises(TypeError): mle_trigram_model.generate(text_seed=(None,)) # This will work assert mle_trigram_model.generate( text_seed=None, random_seed=3 ) == mle_trigram_model.generate(random_seed=3)