General

• Book: http://emory.gitbook.io/nlp-essentials/

• GitHub: https://github.com/emory-courses/nlp-essentials/

• Time: TBA

• Location: TBA

Instructors

• Jinho Choi : Associate Professor of Computer Science : Office Hours → TBA

• Catherine Baker : MS Student in Computer Science : Office Hours → TuTh 11 AM - 12:30 PM, Zoom (ID: 964 3750 1501, PW: posted in Canvas)

• Zelin Zhang : Ph.D. student in Computer Science and Informatics : Office Hours → MW 11:20 AM - 12:50 PM, Zoom (ID: 975 2341 9724, PW: posted in Canvas)

Grading

• Homework: 70%

• Team Formation: 3%

• Project Proposal: 12%

• Live Demonstration: 15%

• Your work is governed by the Emory Honor Code. Honor code violations (e.g., copies from any source, including colleagues and internet sites) will be referred to the Emory Honor Council.

• Requests for absence/rescheduling due to severe personal events (such as health, family, or personal reasons) impacting course performance must be supported by a letter from the Office of Undergraduate Education.

Homework

• Each topic will include homework that combines quizzes and programming assignments to assess your understanding of the subject matter.

• Assignments must be submitted individually. While discussions are allowed, your work must be original.

• Late submissions within a week will be accepted with a grading penalty of 15% but will not be accepted after the solutions are discussed in class.

Quizzes

• Each section incorporates questions to explore the content more comprehensively, with their corresponding answers slated for discussion in the class.

• While certain questions may have multiple valid answers, the grading will be based on the responses discussed in class, and alternative answers will be disregarded. This approach allows us to distinguish between answers discussed in class and those generated by AI tools like ChatGPT.

Programming Assignments

• You are encouraged to use any code examples provided in this book.

• You can invoke any APIs provided in the course packages (under the src/ directory).

• Feel free to create additional functions and variables in the assigned Python file. For each homework, ensure that all your implementations are included in the respective Python file located under the src/homework/ directory.

• Usage of packages not covered in the corresponding chapter is prohibited. Ensure that your code does not rely on the installation of additional packages, as we will not be able to execute your program for evaluation if external dependencies are needed.

Team Project

• You are expected to:

  • Group a team of 3-4 members.

  • Give a pitch presentation to showcase your idea for the project.

  • Provide a live demonstration to illustrate the details and potential of your project.

• Everyone in the same group will receive the same grade for the project, except for the individual portion.

• Your project will undergo evaluation based on various criteria, including originality, feasibility, and potential impact.

• Your project will also undergo peer assessment, which will factor into your project grade.

• Participation in project presentations and live demonstrations is compulsory. Failure to attend any of these events will result in a zero grade for the respective activity. In the event of unavoidable absence due to severe personal circumstances, a formal letter from the Office of Undergraduate Education must accompany any excuses.

Book Revision

• You can earn up to 3 extra credits by helping us improve this online book. If you wish to contribute, please submit an issue to our GitHub repository using the "Online Book" template. Upon verification, you will receive credits based on the following criteria:

  • Content enhancements (e.g., additional explanations, test codes): 0.3 points

  • Code bug fixes: 0.2 points

  • Identification and correction of typos (and other obvious mistakes): 0.1 points

• Prior to submission, please check for existing issues to avoid duplication. If multiple submissions of the same (or very similar) issues occur, only the first one will be credited.

Natural Language Processing (NLP) is a vibrant field in Artificial Intelligence that seeks to create computational models to understand, interpret, and generate human language. NLP technology has become deeply ingrained in our daily lives through various applications, evolving at an unprecedented pace. Understanding how NLP works enables you to maximize the utilization of these applications, ultimately enhancing your lifestyle.

This course focuses on establishing a solid foundation in the core principles essential for modern NLP techniques. Starting with the basics of text processing, you will learn how to manipulate text to enhance data quality for developing NLP models. Next, we will delve into language modeling that enables computational systems to understand and generate human language and explore vector space models that convert human language into machine-readable vector representations.

Moving forward, we will cover distributional semantics, a technique for creating word embeddings based on their global contextual usage, and adapt them for sequence modeling to tackle NLP tasks that are inherently structured around sequences of words. We will also delve into contextual representations that capture the subtleties and nuances of language by considering local context. Finally, we will explore cutting-edge topics, including large language models and their effects on NLP tasks and applications.

Throughout the course, several quizzes and Python programming assignments will further deepen your understanding of the concepts and the practice of NLP. By the end of the term, you can expect to possess the knowledge and skills necessary to navigate the swiftly evolving landscape of NLP.

Prerequisites

• Introduction to Python Programming

• Introduction to Machine Learning

Notations

• Each section has its own set of references. We highly recommend you read the ones marked with asterisks (*), as they provide an in-depth understanding of those subjects.

Environment Setup

Python

• Install Python version 3.10 or higher. Earlier versions are not compatible with this course.

• You are encouraged to install the latest version of Python. Please review the new features introduced in each version.

GitHub

1. Login to GitHub (create an account if you do not have one).

2. Create a new repository called nlp-essentials and set it to private.

3. From the [Settings] menu, add the following as a collaborator to this repository: EmoryTA.

PyCharm

Install PyCharm on your local machine:

• The following instructions assume that you have "PyCharm 2023.3.x Professional Edition".

• You can get the professional version by applying for an academic license.

Configure your GitHub account:

1. Go to [Settings] - [Version Control] - [GitHub].

2. Press [+], select Log in via GitHub, and follow the procedure.

Create a new project:

1. Press the [Get from VCS] button on the Welcome prompt.

2. Choose [GitHub] on the left menu, select the nlp-essentials repository, and press [Clone] (make sure the directory name is nlp-essentials).

Setup an interpreter:

1. Go to [Settings] - [Project: nlp-essentials] - [Project Interpreter].

2. Click Add Interpreter and select Add Local Interpreter.

3. In the prompted window, choose [Virtualenv Environment] on the left menu, configure as follows, then press [OK]:

   • Environment: New

   • Location: SOME_LOCAL_PATH/nlp-essentials/venv

   • Base interpreter: Python 3.11 (or the Python version you installed)

https://plugins.jetbrains.com/plugin/10081-jetbrains-academy

Tasks

Install Package

1. Open a terminal by clicking [Terminal] at the bottom (or go to [View] - [Terminal]).

2. Upgrade pip (if necessary) by entering the following command into the terminal:

   Copy

   python -m pip install --upgrade pip

3. Install setuptools (if necessary) using the following command:

   Copy

   pip install setuptools

4. Install the ELIT Tokenizer with the following command:

   Copy

   pip install elit_tokenizer

5. If the terminal prompts "Successfully installed ...", the packages are installed on your machine.

Run Program

1. Create a package called src under the nlp-essentials directory.

2. Create a homework package under the src package.

3. Create a Python file called getting_started.py under homework and copy the code:

from elit_tokenizer import EnglishTokenizer
__author__ = 'Jinho D. Choi'

if __name__ == '__main__':
    text = 'Emory NLP is a research lab in Atlanta, GA. It was founded by Jinho D. Choi in 2014. Dr. Choi is a professor at Emory University.'
    tokenizer = EnglishTokenizer()
    sentence = tokenizer.decode(text)
    print(sentence.tokens)
    print(sentence.offsets)

4. Run the program by clicking [Run] - [Run 'getting_started']. An alternative way is to click the green triangle (L20) and select Run 'getting_started':

5. If you see the following output, your program runs successfully.

['Emory', 'NLP', 'is', 'a', 'research', 'lab', 'in', 'Atlanta', ',', 'GA', '.', 'It', 'is', 'founded', 'by', 'Jinho', 'D.', 'Choi', 'in', '2014', '.', 'Dr.', 'Choi', 'is', 'a', 'professor', 'at', 'Emory', 'University', '.']
[(0, 5), (6, 9), (10, 12), (13, 14), (15, 23), (24, 27), (28, 30), (31, 38), (38, 39), (40, 42), (42, 43), (44, 46), (47, 49), (50, 57), (58, 60), (61, 66), (67, 69), (70, 74), (75, 77), (78, 82), (82, 83), (84, 87), (88, 92), (93, 95), (96, 97), (98, 107), (108, 110), (111, 116), (117, 127), (127, 128)]

Commit & Push

1. Create a .gitignore file under the nlp-essentials directory and copy the content:

.idea/
venv/

2. Add the following files to git by right-clicking on them and selecting [Git] - [Add] (if not already):

• getting_started.py

• .gitignore

3. Commit and push your changes to GitHub:

• Right-click on nlp-essentials.

• Select [Git] - [Commit Directory].

• Enter a commit message (e.g., Submit Quiz 0).

• Press the [Commit and Push] button.

4. Check if the above files are properly pushed to your GitHub repository.

Submission

Submit the URL of your GitHub repository to Canvas.

Text processing refers to the manipulation and analysis of textual data through techniques applied to raw text, making it more structured, understandable, and suitable for various applications.

Sections

Consider the following text from Wikipedia about (as of 2023-10-18):

Word Count

Our task is to determine the number of word tokens and unique word types in this text. A simple way of accomplishing this task is to split the text with whitespaces and count the strings:

Top-k Frequent Words

In this task, we want to check the top-k most or least frequently occurring words in this text:

Notice that the top-10 least-frequent word list contains unnormalized words such as "Atlanta," (with the comma) or "Georgia." (with the period). This is because the text was split only by whitespaces without considering punctuation. As a result, these words are separately recognized from the word types "Atlanta" or "Georgia", respectively. Hence, the counts of word tokens and types processed above do not necessarily represent the distributions of the text accurately.

Save Output

Finally, save all word types in alphabetical order to a file:

References

Sometimes, it is more appropriate to consider the canonical forms as tokens instead of their variations. For example, if you want to analyze the usage of the word "transformer" in NLP literature for each year, you want to count both "transformer" and 'transformers' as a single item.

Lemmatization is a task that simplifies words into their base or dictionary forms, known as lemmas, to simplify the interpretation of their core meaning.

When analyzing the obtained by the tokenizer in the previous section, the following tokens are recognized as separate word types:

• Universities

• University

• universities

• university

Two variations are applied to the noun "university": capitalization, generally used for proper nouns or initial words, and pluralization, which indicates multiple instances of the term. On the other hand, verbs can also take several variations regarding tense and aspect:

• study

• studies

• studied

• studying

get_lemma_lexica()

We want to develop a lemmatizer that normalizes all variations into their respective lemmas. Let us start by creating lexica for lemmatization:

• Lexica:

lemmatize()

Next, let us write the lemmatize() function that takes a word and lemmatizes it using the lexica:

• L2: Define a nested function aux to handle lemmatization.

  • L6-7: Try applying each rule in the rules list to word.

  • L8: If the resulting lemma is in the vocabulary, return it.

  • L10: If no lemma is found, return None.

• L12: Convert the input word to lowercase for case-insensitive processing.

• L13: Try to lemmatize the word using verb-related lexica.

• L15-16: If no lemma is found among verbs, try to lemmatize using noun-related lexica.

• L18: Return the lemma if found or the decapitalized word if no lemmatization occurred.

We now test our lemmatizer for nouns and verbs:

When the words are further normalized by lemmatization, the number of word tokens remains the same as without lemmatization, but the number of word types is reduced from 197 to 177.

References

Regular expressions, commonly abbreviated as regex, form a language for string matching, enabling operations to search, match, and manipulate text based on specific patterns or rules.

• Online Interpreter:

Metacharacters

Regex provides metacharacters with specific meanings, making it convenient to define patterns:

1. .: any single character except a newline character.

2. [ ]: a character set matching any character within the brackets.

3. \d: any digit, equivalent to [0-9].

4. \D: any character that is not a digit, equivalent to [^0-9].

5. \s: any whitespace character, equivalent to [ \t\n\r\f\v].

6. \S: any character that is not a whitespace character, equivalent to [^ \t\n\r\f\v].

7. \w: any word character (alphanumeric or underscore), equivalent to [A-Za-z0-9_].

8. \W: any character that is not a word character, equivalent to [^A-Za-z0-9_].

9. \b: a word boundary matching the position between a word character and a non-word character.

Examples:

1. M.\. matches "Mr." and "Ms.", but not "Mrs." (\ escapes the metacharacter .).

2. [aeiou] matches any vowel.

3. \d\d\d searches for "170" in "CS170".

4. \D\D searches for "kg" in "100kg".

5. \s searches for the space " " in "Hello World".

6. \S searches for "H" in " Hello".

7. \w\w searches for "1K" in "$1K".

8. \W searches for "!" in "Hello!".

9. \bis\b matches "is", but does not match "island" nor searches for "is" in "basis".

Repetitions

Repetitions allow you to define complex patterns that can match multiple occurrences of a character or group of characters:

1. *: the preceding character or group appears zero or more times.

2. +: the preceding character or group appears one or more times.

3. ?: the preceding character or group appears zero or once, making it optional.

4. {m}: the preceding character or group appears exactly m times.

5. {m,n}: the preceding character or group appears at least m times but no more than n times.

6. {m,}: the preceding character or group appears at least m times or more.

7. By default, matches are "greedy" such that patterns match as many characters as possible.

8. Matches become "lazy" by adding ? after the repetition metacharacters, in which case, patterns match as few characters as possible.

Examples:

1. \d* matches "90" in "90s" as well as "" (empty string) in "ABC".

2. \d+ matches "90" in "90s", but no match in "ABC".

3. https? matches both "http" and "https".

4. \d{3} is equivalent to \d\d\d.

5. \d{2,4} matches "12", "123", "1234", but not "1" or "12345".

6. \d{2,} matches "12", "123", "1234", and "12345", but not "1".

7. <.+> matches the entire string of "<Hello> and <World>".

8. <.+?> matches "<Hello>" in "<Hello> and <World>", and searches for "<World>" in the text.

Groupings

Grouping allows you to treat multiple characters, subpatterns, or metacharacters as a single unit. It is achieved by placing these characters within parentheses ( and ).

1. |: a logical OR, referred to as a "pipe" symbol, allowing you to specify alternatives.

2. ( ): a capturing group; any text that matches the parenthesized pattern is "captured" and can be extracted or used in various ways.

3. (?: ): a non-capturing group; any text that matches the parenthesized pattern, while indeed matched, is not "captured" and thus cannot be extracted or used in other ways.

4. \num: a backreference that refers back to the most recently matched text by the num'th capturing group within the same regex.

5. You can nest groups within other groups to create more complex patterns.

Examples:

1. (cat|dog) matches either "cat" or "dog".

2. (\w+)@(\w+.\w+) has two capturing groups, (\w+) and (\w+.\w+), and matches email addresses such as "john@emory.edu" where the first and second groups capture "john" and "emory.edu", respectively.

3. (?:\w+)@(\w+.\w+) has one non-capturing group (?:\w+) and one capturing group (\w+.\w+). It still matches "john@emory.edu" but only captures "emory.edu", not "john".

4. (\w+) (\w+) - (\2), (\1) has four capturing groups, where the third and fourth groups refer to the second and first groups, respectively. It matches "Jinho Choi - Choi, Jinho" where the first and fourth groups capture "Jinho" and the second and third groups capture "Choi".

5. (\w+.(edu|org)) has two capturing groups, where the second group is nested in the first group. It matches "emory.edu" or "emorynlp.org", where the first group captures the entire texts while the second group captures "edu" or "org", respectively.

Assertions

Assertions define conditions that must be met for a match to occur. They do not consume characters in the input text but specify the position where a match should happen based on specific criteria.

1. A positive lookahead assertion (?= ) checks that a specific pattern is present immediately after the current position.

2. A negative lookahead assertion (?! ) checks that a specific pattern is not present immediately after the current position.

3. A positive look-behind assertion (?<= ) checks that a specific pattern is present immediately before the current position.

4. A negative look-behind assertion (?<! ) checks that a specific pattern is not present immediately before the current position.

5. ^ asserts that the pattern following the caret must match at the beginning of the text.

6. $ asserts that the pattern preceding the dollar sign must match at the end of the text.

Examples:

1. apple(?=[ -]pie) matches "apple" in "apple pie" or "apple-pie", but not in "apple juice".

2. do(?!(?: not|n't)) matches "do" in "do it" or "doing", but not in "do not" or "don't".

3. (?<=\$)\d+ matches "100" in "$100", but not in "100 dollars".

4. (?<!not )(happy|sad) searches for "happy" in "I'm happy", but does not search for "sad" in "I'm not sad".

5. not searches for "not" in "note" and "cannot", whereas ^not matches "not" in "note" but not in "cannot".

6. not$ searches for "not" in "cannot" but not in "note".

Functions

Python provides several functions to make use of regular expressions.

match()

Let us create a regular expression that matches "Mr." and "Ms.":

group()

Currently, no group has been specified for re_mr:

Let us capture the letters and the period as separate groups:

If the pattern does not find a match, it returns None.

search()

Let us match the following strings with re_mr:

s1 matches "Mr." but not "Ms." while s2 does not match any pattern. It is because the match() function matches patterns only at the beginning of the string. To match patterns anywhere in the string, we need to use search() instead:

findall()

The search() function matches "Mr." in both s1 and s2 but still does not match "Ms.". To match them all, we need to use the findall() function:

finditer()

While the findall() function matches all occurrences of the pattern, it does not provide a way to locate the positions of the matched results in the string. To find the locations of the matched results, we need to use the finditer() function:

sub()

Finally, you can replace the matched results with another string by using the sub() function:

Tokenization

Finally, let us write a simple tokenizer using regular expressions. We will define a regular expression that matches the necessary patterns for tokenization:

• L2: Create a regular expression to match delimiters and a special case:

  • Delimiters: ',', '.', or whitespaces ('\s+').

  • The special case: 'n't' (e.g., "can't").

• L3: Create an empty list tokens to store the resulting tokens, and initialize prev_idx to keep track of the previous token's end position.

• L5: Iterate over matches in text using the regular expression pattern.

  • L6: Extract the substring between the previous token's end and the current match's start, strip any leading or trailing whitespace, and assign it to t.

  • L7: If t is not empty (i.e., it is not just whitespace), add it to the tokens list.

  • L8: Extract the matched token from the match object strip any leading or trailing whitespace, and assign it to t.

  • L10: If t is not empty (i.e., the pattern is matched):

    • L11-12: Check if the previous token in tokens is "Mr" or "Ms" and the current token is a period ("."), in which case, combine them into a single token.

    • L13-14: Otherwise, add t to tokens.

• L18-19: After the loop, there might be some text left after the last token. Extract it, strip any leading or trailing whitespace, and add it to tokens.

Test cases for the tokenizer:

References

Task 1: Chronicles of Narnia

Your goal is to extract specific information from each book in the . For each book, gather the following details:

• Book Title

• Year of Publishing

For each chapter within a book, collect the following information:

• Chapter Number

• Chapter Title

• Token count of the chapter content (excluding the chapter number and title), considering each symbol and punctuation as a separate token.

Steps

1. Download the file and place it under the directory. Note that the text file is already tokenized using the .

2. Create a file in the directory.

3. Define a function named chronicles_of_narnia() that takes a file path pointing to the text file and returns a dictionary structured as follows:

Notes

• For each book, ensure that the list of chapters is sorted in ascending order based on chapter numbers. For every chapter across the books, your program should produce the same list for both the original and modified versions of the text file.

• If your program encounters difficulty locating the text file, please verify the working directory specified in the run configuration: [Run - Edit Configurations] -> text_processing. Confirm that the working directory path is set to the top directory, nlp-essentials.

Task 2: Regular Expressions

• RE_Abbreviation: Dr., U.S.A.

• RE_Apostrophe: '80, '90s, 'cause

• RE_Concatenation: don't, gonna, cannot

• RE_Hyperlink: https://emory.gitbook.io/nlp-essentials

• RE_Number: 1/2, 123-456-7890, 1,000,000

• RE_Unit: $10, #20, 5kg

Notes

• Your regular expressions will be assessed based on typical cases beyond the examples mentioned above.

Submission

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

Tokenization is the process of breaking down a text into smaller units, typically words or subwords, known as tokens. Tokens serve as the basic building blocks used for a specific task.

When examining the from the previous section, you notice several words that need further tokenization, where many of them can be resolved by leveraging punctuation:

• "R1: -> ['"', "R1", ":"]

• (R&D) -> ['(', 'R&D', ')']

• 15th-largest -> ['15th', '-', 'largest']

• Atlanta, -> ['Atlanta', ',']

• Department's -> ['Department', "'s"]

• activity"[26] -> ['activity', '"', '[26]']

• centers.[21][22] -> ['centers', '.', '[21]', '[22]']

delimit()

Let us write the delimit() function that takes a word and a set of delimiters and returns a list of tokens by splitting the word using the delimiters:

• L3: If no delimiter is found, return a list containing word as a single token.

• L5: If a delimiter is found, create a list tokens to store the individual tokens.

• L6: If the delimiter is not at the beginning of word, add the characters before the delimiter as a token to tokens.

• L7: Add the delimiter itself as a separate token to tokens.

We now test delimit() using the following cases:

postprocess()

When reviewing the above output, the first four test cases yield accurate results, while the last five are not handled correctly, which should have been tokenized as follows:

• Department's -> ['Department', "'s"]

• activity"[26] -> ['activity', '"', '[26]']

• centers.[21][22] -> ['centers', '.', '[21]', '[22]']

• 149,000 -> ['149,000']

• U.S. -> ['U.S.']

To handle these special cases, let us post-process the tokens generated by delimit():

• L2: Initialize variables i for the current position and new_tokens for the resulting tokens.

• L4: Iterate through the input tokens.

• L5: Case 1: Handling apostrophes for contractions like "'s" (e.g., it's).

  • L6: Combine the apostrophe and "s" and append it as a single token.

  • L7: Move the position indicator by 1 to skip the next character.

• L8-10: Case 2: Handling numbers in special formats like [##], ###,### (e.g., [42], 12,345).

  • L11: Combine the special number format and append it as a single token.

  • L12: Move the position indicator by 2 to skip the next two characters.

• L13: Case 3: Handling acronyms like "U.S.".

  • L14: Combine the acronym and append it as a single token.

  • L15: Move the position indicator by 3 to skip the next three characters.

• L16-17: Case 4: If none of the special cases above are met, append the current token.

• L18: Move the position indicator by 1 to process the next token.

• L20: Return the list of processed tokens.

Once the post-processing is applied, all outputs are handled correctly:

tokenize()

At last, we write the tokenize() function that takes a file path to a corpus and a set of delimiters and returns a list of tokens from the corpus:

• L2: Read the contents of a file (corpus) and split it into words.

Compared to the original tokenization, where all words are split solely by whitespaces, the more advanced tokenizer increases the number of word tokens from 305 to 363 and the number of word types from 180 to 197 because all punctuation symbols, as well as reference numbers, are now introduced as individual tokens.

References

Task 1

Your goal is to develop a bigram model that uses the following techniques:

• Laplace smoothing with

• Measure the initial word probability by adding the artificial token at the beginning of every sentence.

Test your model using .

Steps

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 found in the text file.

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

Task 2

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

Steps

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

2. The initial word (the first word to appear in the sequence)

3. 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.

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

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

• The list of tokens in the sequence

Extra Credit

Define a function named sequence_generator_max() that accepts the same parameters but returns a sequence with the highest sequence probability among all possible sequences using exhaustive search. To generate long sequences, dynamic programming needs to be adapted.

Submission

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

Overview

In the bag-of-words model, a document is represented as a set or a "bag" of words, disregarding any structure but maintaining information about the frequency of every word.

Consider a corpus containing the following two tokenized documents:

D1 = ['John', 'bought', 'a', 'book', '.', 'The', 'book', 'was', 'funny', '.']
D2 = ['Mary', 'liked', 'the', 'book', '.', 'John', 'gave', 'it', 'to', 'Mary', '.']

The corpus contains a total of 14 words, and the entire vocabulary can be represented as a list of all word types in this corpus:

W = [
    '.',        # 0
    'John',     # 1
    'Mary',     # 2
    'The',      # 3
    'a',        # 4
    'book',     # 5
    'bought',   # 6
    'funny',    # 7
    'gave',     # 8
    'it',       # 9
    'liked',    # 10
    'the',      # 11
    'to',       # 12
    'was'       # 13
]

Let $D_i = [w_{i,1}, \ldots, w_{i,n}]$ be a document, where $w_{i,j}$is the $j$'th word in $D_i$. A vector representation for $D_i$ can be defined as $v_i = [\mathrm{count}(w_j \in D_i) : \forall w_j \in W] \in \mathbb{R}^{|W|}$, where $w_j$ is the $j$'th word in $W$ and each dimension in $v_i$ is the frequency of $w_j$'s occurrences in $D_i$ such that:

#     0  1  2  3  4  5  6  7  8  9 10 11 12 13 
v1 = [2, 1, 0, 1, 1, 2, 1, 1, 0, 0, 0, 0, 0, 1]
v2 = [2, 1, 2, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0]

Notice that the bag-of-words model often results in a highly sparse vector, with many dimensions in $v_i$ being 0 in practice, as most words in the vocabulary $W$ do not occur in document $D_i$. Therefore, it is more efficient to represent $v_i$ as a sparse vector:

v1 = {0:2, 1:1, 3:1, 4:1, 5:2, 6:1, 7:1, 13:1}
v2 = {0:2, 1:1, 2:2, 5:1, 8:1, 9:1, 10:1, 11:1, 12:1}

Implementation

Let us define a function that takes a list of documents, where each document is represented as a list of tokens, and returns a dictionary, where keys are words and values are their corresponding unique IDs:

from src.types import Document, Vocab

def vocabulary(documents: list[Document]) -> Vocab:
    vocab = set()

    for document in documents:
        vocab.update(document)

    return {word: i for i, word in enumerate(sorted(list(vocab)))}

We then define a function that takes the vocabulary dictionary and a document, and returns a bag-of-words in a sparse vector representation:

from collections import Counter
from src.types import SparseVector

def bag_of_words(vocab: Vocab, document: Document) -> SparseVector:
    counts = Counter(document)
    return {vocab[word]: count for word, count in sorted(counts.items()) if word in vocab}

Finally, let us our bag-of-words model with the examples above:

documents = [
    ['John', 'bought', 'a', 'book', '.', 'The', 'book', 'was', 'funny', '.'],
    ['Mary', 'liked', 'the', 'book', '.', 'John', 'gave', 'it', 'to', 'Mary', '.']
]

vocab = vocabulary(documents)
print(vocab)

print(bag_of_words(vocab, documents[0]))
print(bag_of_words(vocab, documents[1]))

{
    '.': 0,
    'John': 1,
    'Mary': 2,
    'The': 3,
    'a': 4,
    'book': 5,
    'bought': 6,
    'funny': 7,
    'gave': 8,
    'it': 9,
    'liked': 10,
    'the': 11,
    'to': 12,
    'was': 13
}
{0: 2, 1: 1, 3: 1, 4: 1, 5: 2, 6: 1, 7: 1, 13: 1}
{0: 2, 1: 1, 2: 2, 5: 1, 8: 1, 9: 1, 10: 1, 11: 1, 12: 1}

References

Source: bag_of_words_model.py

• Bag-of-Words Model, Wikipedia

• Bags of words, Working With Text Data, scikit-learn Tutorials

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: $H(X) \geq 0$.

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

• It is at its maximum when all outcomes of $x_i$ 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, $W = [w_1, \ldots, w_n]$, concatenating the entire text from a language $\mathcal{L}$. Let $\mathcal{S} = \{S_1, \ldots, S_m\}$ be a set of all possible sequences derived from $W$, where $S_1$ is the shortest sequence (a single word) and $S_m = W$ is the longest sequence. Then, the entropy of $W$ can be measured as follows:

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

In theory, there is an infinite number of unobserved word sequences in the language $\mathcal{L}$. To estimate the true entropy of $\mathcal{L}$, we need to take the limit to $H'(W)$ as $n$ approaches infinity: