natural language toolkit language model unit tests c 20012023 nltk project ilia kurenkov ilia kurenkovgmail com url https www nltk org for license information see license txt unseen ngrams should yield 0 unigrams should also be 0 n unigrams 14 count a 2 count y 3 ngrams seen during training 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 in mle even one unseen ngram should make entropy and perplexity infinite 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 countd b c 1 countb c 1 countd c 1 countc 1 total number of tokens is 18 of which a occurred 2 times in vocabulary but unseen out of vocabulary should use unk score countd c 1 countd c 1 1 countw c for w in vocab 1 countw c for w in vocab 1 8 total unigrams 14 vocab size 8 denominator 14 0 8 14 8 counta 2 counta 2 1 in vocabulary but unseen countz 0 countz 0 1 out of vocabulary should use unk score countunk 3 countunk 3 1 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 05 4 1699 unk d 0 0263 5 2479 d c 0 0357 4 8074 c s 0 05 4 1699 total logscore 24 5504 avg logscore 4 0917 logic behind this is the same as for bigram model if we choose a word that hasn t appeared after b c trigram score now basic sanitycheck countd c 1 countd c 2 countw c for w in vocab 1 countw c for w in vocab 9 total unigrams 14 vocab size 8 denominator 14 8 22 counta 2 counta 3 in vocabulary but unseen countz 0 countz 1 out of vocabulary should use unk score countunk 3 countunk 4 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 for unigram scores by default revert to regular mle total unigrams 18 vocab size 7 count c 1 in vocabulary but unseen countz 0 out of vocabulary should use unk score countunk 3 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 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 mlec a b 1 pczb the ngram zbc was not seen so we use pcb see issue 2332 notation explained for all subsequent calculations we use the following notation 1 placeholder for any wordcharacter e g b stands for all bigrams that end in b b stands for all trigrams that contain b in the middle 1 countngram count all instances tokens of an ngram 1 uniquengram count unique instances types of an ngram pc count c unique 1 14 pz count z unique 0 14 z is in the vocabulary but it was not seen during training py out of vocabulary should use unk score py punk count unk unique we start with pcb pcb alpha bc gamma b pc alpha bc maxunique bc discount 0 unique b max1 0 75 0 2 0 125 gamma b discount unique b unique b 0 75 2 2 0 75 building on that let s try pcab pcab alpha abc gamma ab pcb alpha abc maxcount abc discount 0 count ab max1 0 75 0 1 0 25 gamma ab discount unique ab count ab 0 75 1 1 pczb the ngram zbc was not seen so we use pcb see issue 2332 for unigram scores revert to uniform pc count c count in vocabulary but unseen count z 0 out of vocabulary should use unk score count unk 3 pcb alpha bc gamma b pc alpha bc maxcount bc discount 0 count b max1 0 75 0 2 0 125 gamma b discount unique b count b 0 75 2 2 0 75 building on that let s try pcab pcab alpha abc gamma ab pcb alpha abc maxcount abc discount 0 count ab max1 0 75 0 1 0 25 gamma ab discount unique ab count ab 0 75 1 1 pczb the ngram zbc was not seen so we use pcb see issue 2332 for unigram scores revert to uniform total bigrams 18 in vocabulary but unseen bigrams ending with z 0 out of vocabulary should use unk score count unk 3 c follows 1 time out of 2 after b c always follows ab the ngram z b c was not seen so we backoff to the score of the ngram b c smoothing factor probability distributions should sum up to unity generating text we don t need randomseed for contexts with only one continuation when context doesn t limit our options enough seed the random choice add a cycle to the model bd b db d test that we can escape the cycle should crash with type error when we try to look it up in vocabulary this will work natural language toolkit language model unit tests c 2001 2023 nltk project ilia kurenkov ilia kurenkov gmail com url https www nltk org for license information see license txt unseen ngrams should yield 0 unigrams should also be 0 n unigrams 14 count a 2 count y 3 ngrams seen during training 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 in mle even one unseen ngram should make entropy and perplexity infinite 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 count d b c 1 count b c 1 count d c 1 count c 1 total number of tokens is 18 of which a occurred 2 times in vocabulary but unseen out of vocabulary should use unk 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 total unigrams 14 vocab size 8 denominator 14 0 8 14 8 count a 2 count a 2 1 in vocabulary but unseen count z 0 count z 0 1 out of vocabulary should use unk score count unk 3 count unk 3 1 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 logic behind this is the same as for bigram model if we choose a word that hasn t appeared after b c trigram score now 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 total unigrams 14 vocab size 8 denominator 14 8 22 count a 2 count a 3 in vocabulary but unseen count z 0 count z 1 out of vocabulary should use unk score count unk 3 count unk 4 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 for unigram scores by default revert to regular mle total unigrams 18 vocab size 7 count c 1 in vocabulary but unseen count z 0 out of vocabulary should use unk score count unk 3 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 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 p c zb the ngram zbc was not seen so we use p c b see issue 2332 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 p c count c unique 1 14 p z count z unique 0 14 z is in the vocabulary but it was not seen during training p y out of vocabulary should use unk score p y p unk count unk unique 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 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 p c zb the ngram zbc was not seen so we use p c b see issue 2332 for unigram scores revert to uniform p c count c count in vocabulary but unseen count z 0 out of vocabulary should use unk score count unk 3 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 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 p c zb the ngram zbc was not seen so we use p c b see issue 2332 for unigram scores revert to uniform total bigrams 18 in vocabulary but unseen bigrams ending with z 0 out of vocabulary should use unk score count unk 3 c follows 1 time out of 2 after b c always follows ab the ngram z b c was not seen so we backoff to the score of the ngram b c smoothing factor probability distributions should sum up to unity generating text we don t need random_seed for contexts with only one continuation when context doesn t limit our options enough seed the random choice add a cycle to the model bd b db d test that we can escape the cycle should crash with type error when we try to look it up in vocabulary this will work
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


@pytest.fixture(scope="session")
def vocabulary():
    return Vocabulary(["a", "b", "c", "d", "z", "<s>", "</s>"], unk_cutoff=1)


@pytest.fixture(scope="session")
def training_data():
    return [["a", "b", "c", "d"], ["e", "g", "a", "d", "b", "e"]]


@pytest.fixture(scope="session")
def bigram_training_data(training_data):
    return [list(padded_everygrams(2, sent)) for sent in training_data]


@pytest.fixture(scope="session")
def trigram_training_data(training_data):
    return [list(padded_everygrams(3, sent)) for sent in training_data]


@pytest.fixture
def mle_bigram_model(vocabulary, bigram_training_data):
    model = MLE(2, vocabulary=vocabulary)
    model.fit(bigram_training_data)
    return model


@pytest.mark.parametrize(
    "word, context, expected_score",
    [
        ("d", ["c"], 1),
        
        ("d", ["e"], 0),
        
        ("z", None, 0),
        
        
        ("a", None, 2.0 / 14),
        
        ("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


def test_mle_bigram_logscore_for_zero_score(mle_bigram_model):
    assert math.isinf(mle_bigram_model.logscore("d", ["e"]))


def test_mle_bigram_entropy_perplexity_seen(mle_bigram_model):
    
    trained = [
        ("<s>", "a"),
        ("a", "b"),
        ("b", "<UNK>"),
        ("<UNK>", "a"),
        ("a", "d"),
        ("d", "</s>"),
    ]
    
    
    
    
    
    
    
    
    
    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


def test_mle_bigram_entropy_perplexity_unseen(mle_bigram_model):
    
    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))


def test_mle_bigram_entropy_perplexity_unigrams(mle_bigram_model):
    
    
    
    
    
    
    
    
    
    
    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


@pytest.fixture
def mle_trigram_model(trigram_training_data, vocabulary):
    model = MLE(order=3, vocabulary=vocabulary)
    model.fit(trigram_training_data)
    return model


@pytest.mark.parametrize(
    "word, context, expected_score",
    [
        
        
        ("d", ("b", "c"), 1),
        
        
        ("d", ["c"], 1),
        
        ("a", None, 2.0 / 18),
        
        ("z", None, 0),
        
        ("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


@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


@pytest.mark.parametrize(
    "word, context, expected_score",
    [
        
        
        
        
        ("d", ["c"], 1.1 / 1.8),
        
        
        
        
        
        ("a", None, 2.1 / 14.8),
        
        
        
        ("z", None, 0.1 / 14.8),
        
        
        
        ("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
    )


def test_lidstone_entropy_perplexity(lidstone_bigram_model):
    text = [
        ("<s>", "a"),
        ("a", "c"),
        ("c", "<UNK>"),
        ("<UNK>", "d"),
        ("d", "c"),
        ("c", "</s>"),
    ]
    
    
    
    
    
    
    
    
    
    
    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


@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


@pytest.mark.parametrize(
    "word, context, expected_score",
    [
        
        ("d", ["c"], 1.1 / 1.8),
        
        ("e", ["c"], 0.1 / 1.8),
        
        ("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
    )


@pytest.fixture
def laplace_bigram_model(bigram_training_data, vocabulary):
    model = Laplace(2, vocabulary=vocabulary)
    model.fit(bigram_training_data)
    return model


@pytest.mark.parametrize(
    "word, context, expected_score",
    [
        
        
        
        
        
        ("d", ["c"], 2.0 / 9),
        
        
        
        
        
        ("a", None, 3.0 / 22),
        
        
        
        ("z", None, 1.0 / 22),
        
        
        
        ("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
    )


def test_laplace_bigram_entropy_perplexity(laplace_bigram_model):
    text = [
        ("<s>", "a"),
        ("a", "c"),
        ("c", "<UNK>"),
        ("<UNK>", "d"),
        ("d", "c"),
        ("c", "</s>"),
    ]
    
    
    
    
    
    
    
    
    
    
    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


def test_laplace_gamma(laplace_bigram_model):
    assert laplace_bigram_model.gamma == 1


@pytest.fixture
def wittenbell_trigram_model(trigram_training_data, vocabulary):
    model = WittenBellInterpolated(3, vocabulary=vocabulary)
    model.fit(trigram_training_data)
    return model


@pytest.mark.parametrize(
    "word, context, expected_score",
    [
        
        
        
        
        ("c", None, 1.0 / 18),
        
        
        ("z", None, 0 / 18),
        
        
        ("y", None, 3.0 / 18),
        
        
        
        
        
        ("c", ["b"], (1 - 0.5) * 0.5 + 0.5 * 1 / 18),
        
        
        
        
        ("c", ["a", "b"], (1 - 0.5) + 0.5 * ((1 - 0.5) * 0.5 + 0.5 * 1 / 18)),
        
        
        ("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
    )













@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


@pytest.mark.parametrize(
    "word, context, expected_score",
    [
        
        
        ("c", None, 1.0 / 14),
        
        
        
        ("z", None, 0.0 / 14),
        
        
        
        ("y", None, 3 / 14),
        
        
        
        
        
        
        
        
        ("c", ["b"], (0.125 + 0.75 * (1 / 14))),
        
        
        
        
        
        
        
        ("c", ["a", "b"], 0.25 + 0.75 * (0.125 + 0.75 * (1 / 14))),
        
        
        ("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
    )


@pytest.fixture
def absolute_discounting_trigram_model(trigram_training_data, vocabulary):
    model = AbsoluteDiscountingInterpolated(order=3, vocabulary=vocabulary)
    model.fit(trigram_training_data)
    return model


@pytest.mark.parametrize(
    "word, context, expected_score",
    [
        
        
        ("c", None, 1.0 / 18),
        
        
        ("z", None, 0.0 / 18),
        
        
        ("y", None, 3 / 18),
        
        
        
        
        
        
        
        ("c", ["b"], (0.125 + 0.75 * (2 / 2) * (1 / 18))),
        
        
        
        
        
        
        
        ("c", ["a", "b"], 0.25 + 0.75 * (0.125 + 0.75 * (2 / 2) * (1 / 18))),
        
        
        ("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
    )


@pytest.fixture
def stupid_backoff_trigram_model(trigram_training_data, vocabulary):
    model = StupidBackoff(order=3, vocabulary=vocabulary)
    model.fit(trigram_training_data)
    return model


@pytest.mark.parametrize(
    "word, context, expected_score",
    [
        
        
        ("c", None, 1.0 / 18),
        
        
        ("z", None, 0.0 / 18),
        
        
        ("y", None, 3 / 18),
        
        ("c", ["b"], 1 / 2),
        
        ("c", ["a", "b"], 1 / 1),
        
        
        ("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
    )







@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


@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







def test_generate_one_no_context(mle_trigram_model):
    assert mle_trigram_model.generate(random_seed=3) == "<UNK>"


def test_generate_one_from_limiting_context(mle_trigram_model):
    
    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"


def test_generate_one_from_varied_context(mle_trigram_model):
    
    assert mle_trigram_model.generate(text_seed=("a", "<s>"), random_seed=2) == "a"


def test_generate_cycle(mle_trigram_model):
    
    more_training_text = [padded_everygrams(mle_trigram_model.order, list("bdbdbd"))]

    mle_trigram_model.fit(more_training_text)
    
    assert mle_trigram_model.generate(7, text_seed=("b", "d"), random_seed=5) == [
        "b",
        "d",
        "b",
        "d",
        "b",
        "d",
        "</s>",
    ]


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>",
    ]


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)


def test_generate_None_text_seed(mle_trigram_model):
    
    with pytest.raises(TypeError):
        mle_trigram_model.generate(text_seed=(None,))

    
    assert mle_trigram_model.generate(
        text_seed=None, random_seed=3
    ) == mle_trigram_model.generate(random_seed=3)