Entropy

Entropy is a measure of the uncertainty, randomness, or information content of a random variable or a probability distribution. The entropy of a random variable $X = \{x_1, \ldots, x_n\}$ is defined as:

$P(x_i)$ is the probability distribution of $x_i$. The self-information of $x_i$ is defined as $-\log P(x)$, which measures how much information is gained when $x_i$ occurs. The negative sign indicates that as the occurrence of $x_i$ increases, its self-information value decreases.

Entropy has several properties, including:

• It is non-negative: .

• It is at its minimum when is entirely predictable (all probability mass on a single outcome).

• It is at its maximum when all outcomes of are equally likely.

Sequence Entropy

Sequence entropy is a measure of the unpredictability or information content of the sequence, which quantifies how uncertain or random a word sequence is.

Assume a long sequence of words, , concatenating the entire text from a language . Let be a set of all possible sequences derived from , where is the shortest sequence (a single word) and is the longest sequence. Then, the entropy of can be measured as follows:

The entropy rate (per-word entropy), , can be measured by dividing by the total number of words :

In theory, there is an infinite number of unobserved word sequences in the language . To estimate the true entropy of , we need to take the limit to as approaches infinity:

The implies that if the language is both stationary and ergodic, considering a single sequence that is sufficiently long can be as effective as summing over all possible sequences to measure because a long sequence of words naturally contains numerous shorter sequences, and each of these shorter sequences reoccurs within the longer sequence according to their respective probabilities.

By applying this theorem, can be approximated:

Consequently, is approximated as follows, where :

Perplexity

Perplexity measures how well a language model can predict a set of words based on the likelihood of those words occurring in a given text. The perplexity of a word sequence is measured as:

Hence, the higher is, the lower its perplexity becomes, implying that the language model is "less perplexed" and more confident in generating .

Perplexity, , can be directly derived from the approximated entropy rate, :

References

1. , Wikipedia

2. , Wikipedia

Task 1: Bigram Modeling

Your goal is to build a bigram model using (1) Laplace smoothing with normalization and (2) initial word probabilities by adding the artificial token $w_0$ at the beginning of every sentence.

Implementation

1. Create a file in the directory.

2. Define a function named bigram_model() that takes a file path pointing to the text file, and returns a dictionary of bigram probabilities estimated in the text file.

3. Use the following constants to indicate the unknown and initial probabilities:

Notes

1. Test your model using .

2. Each line should be treated independently for bigram counting such that the INIT token should precede the first word of each line.

3. Use such that all probabilities must sum to 1.0 for any given previous word.

Task 2: Sequence Generation

Your goal is to write a function that takes a word and generates a sequence that includes the input as the initial word.

Implementation

Under , define a function named sequence_generator() that takes the following parameters:

• A bigram model (the resulting dictionary of Task 1)

• The initial word (the first word to appear in the sequence)

• The length of the sequence (the number of tokens in the sequence)

This function aims to generate a sequence of tokens that adheres to the following criteria:

• It must have the precise number of tokens as specified.

• Not more than 20% of the tokens can be punctuation. For instance, if the sequence length is 20, a maximum of 4 punctuation tokens are permitted within the sequence. Use floor of 20% (e.g., if the sequence length is 21, a maximum of puncuation tokens are permitted).

• Excluding punctuation, there should be no redundant tokens in the sequence.

The goal of this task is not to discover a sequence that maximizes the overall , but rather to optimize individual bigram probabilities. Hence, it entails a greedy search approach rather than an exhaustive one. Given the input word , a potential strategy is as follows:

1. Identify the next word where the bigram probability is maximized.

2. If fulfills all the stipulated conditions, include it in the sequence and proceed. Otherwise, search for the next word whose bigram probability is the second highest. Repeat this process until you encounter a word that meets all the specified conditions.

3. Make and repeat the #1 until you reach the specific sequence length.

Finally, the function returns a tuple comprising the following two elements:

• The list of tokens in the sequence

• The log-likelihood estimating the sequence probability using the bigram model. Use the logarithmic function to the base , provided as the math.log() function in Python.

Extra Credit

Create a function called sequence_generator_plus() that takes the same input parameters as the existing sequence_generator() function. This new function should generate sequences with higher probability scores and better semantic coherence compared to the original implementation.

Submission

Commit and push the language_models.py file to your GitHub repository.

Rubric

• Task 1: Bigram Modeling (5 points)

• Task 2: Sequence Generator (4.6 points), Extra Credit (2 points)

• Concept Quiz (2.4 points)

Maximum likelihood estimation (MLE) is a statistical method used to estimate the parameters of a probability distribution based on observed data. MLE aims to find the values of the model's parameters that make the observed data most probable under the assumed statistical model.

Sequence Probability

Let us examine a model that takes a sequence of words and generates the next word. Given a word sequence "I am a", the model aims to predict the most likely next word by estimating the probabilities associated with potential continuations, such as "I am a student" or "I'm a teacher," and selecting the one with the highest probability.

The conditional probability of the word "student" occurring after the word sequence "I am a" can be estimated as follows:

The joint probability of the word sequence "I am a student" can be measured as follows:

Counting the occurrences of n-grams, especially when n can be indefinitely long, is neither practical nor effective, even with a vast corpus. In practice, we address this challenge by employing two techniques: and .

Chain Rule

By applying the chain rule, the above joint probability can be decomposed into:

Thus, the probability of any given word sequence can be measured as:

The chain rule effectively decomposes the original problem into subproblems; however, it does not resolve the issue because measuring is as challenging as measuring .

Markov Assumption

The Markov assumption (aka. Markov property) states that the future state of a system depends only on its present state and is independent of its past states, given its present state. In the context of language modeling, it implies that the next word generated by the model should depend solely on the current word. This assumption dramatically simplifies the chain rule mentioned above:

The joint probability can now be measured by the product of unigram and bigram probabilities.

Initial Word Probability

Let us consider the unigram probabilities of and . In general, "the" appears more frequently than "The" such that:

Let be an artificial token indicating the beginning of the text. We can then measure the bigram probabilities of "the" and "The" appearing as the initial words of the text, denoted as and , respectively. Since the first letter of the initial word in formal English writing is conventionally capitalized, it is likely that:

Thus, to predict a more probable initial word, it is better to consider the bigram probability rather than the unigram probability when measuring sequence probability:

This enhancement allows us to elaborate the sequence probability as a simple product of bigram probabilities:

The multiplication of numerous probabilities can often be computationally infeasible due to slow processing and the potential for decimal points to exceed system limits. In practice, logarithmic probabilities are calculated instead:

References

1. , Wikipedia

Unigram Smoothing

The unigram model in the previous section faces a challenge when confronted with words that do not occur in the corpus, resulting in a probability of 0. One common technique to address this challenge is smoothing, which tackles issues such as zero probabilities, data sparsity, and overfitting that emerge during probability estimation and predictive modeling with limited data.

Laplace smoothing (aka. add-one smoothing) is a simple yet effective technique that avoids zero probabilities and distributes the probability mass more evenly. It adds the count of 1 to every word and recalculates the unigram probabilities:

Thus, the probability of any unknown word with Laplace smoothing is calculated as follows:

The unigram probability of an unknown word is guaranteed to be lower than the unigram probabilities of any known words, whose counts have been adjusted to be greater than 1.

Note that the sum of all unigram probabilities adjusted by Laplace smoothing is still 1:

Let us define a function unigram_smoothing() that takes a file path and returns a dictionary with bigrams and their probabilities as keys and values, respectively, estimated by Laplace smoothing:

• L1: Import the unigram_count() function from the package.

• L3: Define a constant representing the unknown word.

• L7: Increment the total count by the vocabulary size.

We then test unigram_smoothing() with a text file :

Compared to the unigram results without smoothing (see the "Comparison" tab above), the probabilities for these top unigrams have slightly decreased.

The unigram probability of any word (including unknown) can be retrieved using the UNKNOWN key:

• L2: Use to retrieve the probability of the target word from probs. If the word is not present, default to the probability of the UNKNOWN token.

Bigram Smoothing

The bigram model can also be enhanced by applying Laplace smoothing:

Thus, the probability of an unknown bigram where is known but is unknown is calculated as follows:

Let us define a function bigram_smoothing() that takes a file path and returns a dictionary with unigrams and their probabilities as keys and values, respectively, estimated by Laplace smoothing:

• L1: Import the bigram_count() function from the package.

• L5: Create a set vocab containing all unique .

• L6-7: Add all unique to vocab

We then test bigram_smoothing() with the same text file:

Finally, we test the bigram estimation using smoothing for unknown sequences:

• L2: Retrieve the bigram probabilities of the previous word, or set it to None if not present.

• L3: Return the probability of the current word given the previous word with smoothing. If the previous word is not present, return the probability for an unknown previous word.

Normalization

Unlike the unigram case, the sum of all bigram probabilities adjusted by Laplace smoothing given a word is not guaranteed to be 1. To illustrate this point, let us consider the following corpus comprising only two sentences:

There are seven word types in this corpus, {"I", "You", "a", "and", "are", "student", "students"}, such that . Before Laplace smoothing, the bigram probabilities of are estimated as follows:

However, after applying Laplace smoothing, the bigram probabilities undergo significant changes, and their sum no longer equals 1:

The bigram distribution for can be normalized to 1 by adding the total number of word types occurring after , denoted as , to the denominator instead of :

Consequently, the probability of an unknown bigram can be calculated with the normalization as follows:

For the above example, . Once you apply to , the sum of its bigram probabilities becomes 1:

A major drawback of this normalization is that the probability cannot be measured when is unknown. Thus, we assign the minimum unknown probability across all bigrams as the bigram probability of , where the previous word is unknown, as follows:

Reference

1. Source:

2. , Wikipedia

A language model is a computational model designed to understand, generate, and predict human language. It captures language patterns, learns the likelihood of a specific term occurring in a given context, and assigns probabilities to word sequences through training on extensive text data.

Contents

An n-gram is a contiguous sequence of n items from text data. These items can be:

• Words (most common in language modeling)

• Characters (useful for morphological analysis)

• Subword tokens (common in modern NLP)

• Bytes or other units

For the sentence "I'm a computer scientist.", we can extract different n-grams:

• 1-gram (unigram): {"I'm", "a", "computer", "scientist."}

• 2-gram (bigram): {"I'm a", "a computer", "computer scientist."}

• 3-gram (trigram): {"I'm a computer", "a computer scientist."}

In the above example, "I'm" and "scientist." are recognized as individual tokens, which should have been as ["I", "'m"] and ["scientist", "."].

Unigram Estimation

Given a large corpus, a unigram model assumes word independence and calculates the probability of each word as:

Where:

• : the count of word in the corpus.

• : the vocabulary (set of all unique words).

• The denominator represents the total word count.

Let us define the Unigram type:

• L1: .

• L3: A dictionary where the key is a unigram and the value is its probability.

Let us also define a function unigram_count() that takes a file path and returns a Counter with all unigrams and their counts in the file as keys and values, respectively:

We then define a function unigram_estimation() that takes a file path and returns a dictionary with unigrams and their probabilities as keys and values, respectively:

• L3: Calculate the total count of all unigrams in the text.

• L4: Return a dictionary where each word is a key and its probability is the value.

Finally, let us define a function test_unigram() that takes a file path as well as an estimator function, and test unigram_estimation() with a text file :

• L1: Import the type from the typing module.

• L3: The second argument accepts a function that takes a string and returns a Unigram.

• L4: Call the estimator with the text file and store the result in unigrams.

This distribution shows the most common unigrams in the text meeting the conditions in L8, dominated by the first-person pronoun "I", followed by proper nouns - specifically character names such as "Aslan", "Lucy", and "Edmund".

Bigram Estimation

A bigram model calculates the conditional probability of the current word given the previous word as follows (: the total occurrences of in the corpus in that order, : a set of all word types occurring after ):

Where:

• : the total occurrences of in the corpus in that order.

• : a set of all word types occurring after .

Let us define the Bigram type:

• A dictionary where the key is and the value is a nested dictionary representing the unigram distribution of all given , or a for .

Let us also define a function bigram_count() that takes a file path and returns a dictionary with all bigrams and their counts in the file as keys and values, respectively:

• L1: Import the class from the package.

• L2: import the Bigram from the package.

• L5: Create a defaultdict with Counters as default values to store bigram frequencies.

We then define a function bigram_estimation() that takes a file path and returns a dictionary with bigrams and their probabilities as keys and values, respectively:

• L8: Calculate the total count of all bigrams with the same previous word.

• L9: Calculate and store the probabilities of each current word given the previous word.

Finally, let us define a function test_bigram() that takes a file path and an estimator function, and test bigram_estimation() with the text file:

• L2: Call the bigram_estimation() function with the text file and store the result.

• L5: Create a bigram list given the previous word, sorted by probability in descending order.

• L6: Iterate through the top 10 bigrams with the highest probabilities for the previous word.

References

1. Source: .

2. , Speech and Language Processing (3rd ed. draft), Jurafsky and Martin.