Natural Language Processing (NLP) is a dynamic field within Artificial Intelligence focused on developing computational models to understand, interpret, and generate human language. As NLP technologies become increasingly embedded in our daily lives, understanding its fundamentals is crucial for both leveraging its potential and enhancing our interaction with language-based systems.

This course is designed to build a robust foundation in the core principles of modern NLP. We begin with text processing techniques that show how to manipulate textual data for model development. We then progress to language models, enabling computational models to comprehend and generate human language, and vector space models that convert textual data into machine-readable formats. Advanced topics include distributional semantics for creating context-aware word embeddings, and contextual encoding for analyzing word relationships within their surrounding text.

The latter part of the course focuses on practical application through team projects. Students will have the opportunity to work with cutting-edge NLP technologies, such as large language models, to develop real-world applications. This hands-on approach encourages creativity and innovation, with students proposing their own ideas and presenting demonstrations to their peers.

Learning assessment combines concept quizzes to reinforce theoretical understanding with hands-on programming assignments that develop practical implementation skills. By the conclusion of the course, students will have gained the knowledge and skills to navigate and contribute to the rapidly evolving field of NLP.

Prerequisites

• Introduction to Python Programming

• Introduction to Machine Learning

Sections

General

• Time: MW 4 - 5:15 PM

• Location: MSC W201

Instructors

• • Associate Professor of Computer Science, Quantitative Theory and Methods, Linguistics

  • Office Hours and Location: MW 5:30 - 6:30 PM, White Hall 218

  • GitHub: jdchoi77

• • Ph.D. Student in Computer Science and Informatics

  • Office Hours and Location:

    • Hours: Wed 1:30 - 3:30 PM and Fri 12:30 - 1:30 PM

    • Location: Math & Science Center E308 (Computer Lab)

  • GitHub: byunsj

• • Ph.D. Student in Computer Science and Informatics

  • Office Hours and Location:

    • Hours: Mon 10:30 AM - 1:30 PM

    • Location: Math & Science Center E308 (Computer Lab)

  • GitHub: swati-rajwal

Grading

• Homework: 65%

• Team Project: 35%

Homework

• Each topic will include homework that combines concept 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%. They will not be accepted after the solutions are discussed in class.

Concept 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 and invoke APIs provided in this book.

• 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 corresponding directory.

• Usage of packages not covered in the assigned 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:

  • Form a team of 3-4 members.

  • Provide individual feedback on other teams' presentations and demonstrations.

Project Grading

• Team members receive the same grade for the pitch presentation, live demonstration, and demonstration video.

• Peer evaluations from other teams factor into your team grade.

• Your feedbacks to other teams are graded individually.

For the project and final reports, you are required to indicate the contribution percentage of each team member, which impacts the individual grades for the assignment.

Contribution

If your team of two members received 4 out of 5 points, for example, and you indicate that your contribution was 60% while your teammate's was 40%, the points are distributed as follows:

• You receive: 4 (team points) ⨉ 60 (your contributions) / 60 (max contributions) = 4 points.

• Your teammate receive: 4 (team points) ⨉ 40 (your teammate's contributions) / 60 (max contributions) = 2.67 points.

This approach ensures that the grading reflects the effort and input of each team member, promoting fairness and accountability.

Consensus

• Each team is required to submit a single, agreed-upon chart detailing the contribution percentages of all members for each team assignment. This means that you and your teammates must reach a consensus on the contribution rates before submitting your work.

• Open communication and transparency are essential in this process. Disagreements should be resolved within the team, ensuring that the final submission reflects the true division of labor and contributions.

By adhering to these guidelines, you not only produce a strong research paper but also develop key skills in teamwork and fair assessment of contributions.

This guide will help you set up your development environment by installing required tools: Python programming language, GitHub for version control, and PyCharm IDE.

Python

GitHub

2. Login to GitHub.

3. Create a new repository named "nlp-essentials" and set its visibility to Private.
4. Go to [Settings] in your repository, and select [Collaborators and teams].

5. Click [Add people], and add each instructor using their GitHub usernames:

   2. Enter each username and send the collaboration invitation.

6. Verify that all instructors have been added as collaborators.

PyCharm

1. 2. The following instructions are based on PyCharm 2024.3.x Professional Edition.

2. Configure your GitHub account:

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

   2. Press [+], select [Log in via GitHub], and follow the browser prompts to authorize PyCharm with your GitHub account.

   3. Once connected, you will be able to access GitHub directly from PyCharm for version control operations.

1. Create a new PyCharm project from GitHub:

   1. On the PyCharm welcome screen, click [Clone Repository].

   2. In the new window, select [GitHub] from the left menu, choose your nlp-essentials repository, and click [Clone] (verify the directory name is "nlp-essentials").

2. Set Up a Python virtual environment:

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

   2. Click [Add Interpreter] and choose [Add Local Interpreter].

3. In the prompted menu, choose [Add Local Environment], configure as follows, then click [OK]:

   • Environment: Generate new

   • Type: Virtualenv

   • Base python: the Python version you installed above

   • Location: YOUR_LOCAL_PATH/nlp-essentials/.venv

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.

• 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

We want to develop a lemmatizer that normalizes all variations into their respective lemmas.

Lemma Lexica

Let us create lexica for lemmatization:

import json
import os
from types import SimpleNamespace

def get_lexica(res_dir: str) -> SimpleNamespace:
    with open(os.path.join(res_dir, 'nouns.txt')) as fin: nouns = {noun.strip() for noun in fin}
    with open(os.path.join(res_dir, 'verbs.txt')) as fin: verbs = {verb.strip() for verb in fin}
    with open(os.path.join(res_dir, 'nouns_irregular.json')) as fin: nouns_irregular = json.load(fin)
    with open(os.path.join(res_dir, 'verbs_irregular.json')) as fin: verbs_irregular = json.load(fin)
    with open(os.path.join(res_dir, 'nouns_rules.json')) as fin: nouns_rules = json.load(fin)
    with open(os.path.join(res_dir, 'verbs_rules.json')) as fin: verbs_rules = json.load(fin)

    return SimpleNamespace(
        nouns=nouns,
        verbs=verbs,
        nouns_irregular=nouns_irregular,
        verbs_irregular=verbs_irregular,
        nouns_rules=nouns_rules,
        verbs_rules=verbs_rules
    )

• L1: res_dir: the path to the root directory where all lexica files are located.

We then verify that all lexical resources are loaded correctly:

print(len(lexica.nouns))
print(len(lexica.verbs))
print(lexica.nouns_irregular)
print(lexica.verbs_irregular)
print(lexica.nouns_rules)
print(lexica.verbs_rules)

91
27
{'children': 'child', 'crises': 'crisis', 'mice': 'mouse'}
{'is': 'be', 'was': 'be', 'has': 'have', 'had': 'have', 'bought': 'buy'}
[['ies', 'y'], ['es', ''], ['s', ''], ['men', 'man'], ['ae', 'a'], ['i', 'us']]
[['ies', 'y'], ['ied', 'y'], ['es', ''], ['ed', ''], ['s', ''], ['d', ''], ['ying', 'ie'], ['ing', ''], ['ing', 'e'], ['n', ''], ['ung', 'ing']]

Lemmatizing

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

def lemmatize(lexica: SimpleNamespace, word: str) -> str:
    def aux(word: str, vocabs: dict[str, str], irregular: dict[str, str], rules: list[tuple[str, str]]):
        lemma = irregular.get(word, None)
        if lemma is not None: return lemma

        for p, s in rules:
            lemma = word[:-len(p)] + s
            if lemma in vocabs: return lemma

        return None

    word = word.lower()
    lemma = aux(word, lexica.verbs, lexica.verbs_irregular, lexica.verbs_rules)

    if lemma is None:
        lemma = aux(word, lexica.nouns, lexica.nouns_irregular, lexica.nouns_rules)

    return lemma if lemma else word

• 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:

nouns = ['studies', 'crosses', 'areas', 'gentlemen', 'vertebrae', 'alumni', 'children', 'crises']
nouns_lemmatized = [lemmatize(lexica, word) for word in nouns]
for word, lemma in zip(nouns, nouns_lemmatized): print('{} -> {}'.format(word, lemma))

verbs = ['applies', 'cried', 'pushes', 'entered', 'takes', 'heard', 'lying', 'studying', 'taking', 'drawn', 'clung', 'was', 'bought']
verbs_lemmatized = [lemmatize(lexica, word) for word in verbs]
for word, lemma in zip(verbs, verbs_lemmatized): print('{} -> {}'.format(word, lemma))

studies -> study
crosses -> cross
areas -> area
gentlemen -> gentleman
vertebrae -> vertebra
alumni -> alumnus
children -> child
crises -> crisis

applies -> apply
cried -> cry
pushes -> push
entered -> enter
takes -> take
heard -> hear
lying -> lie
studying -> study
taking -> take
drawn -> draw
clung -> cling
was -> be
bought -> buy

from collections import Counter
from src.tokenization import tokenize

corpus = 'dat/emory-wiki.txt'
delims = {'"', "'", '(', ')', '[', ']', ':', '-', ',', '.'}
words = [lemmatize(lexica, word) for word in tokenize(corpus, delims)]
counts = Counter(words)

print(f'# of word tokens: {len(words)}')
print(f'# of word types: {len(counts)}')

output = 'dat/word_types-token-lemma.txt'
with open(output, 'w') as fout:
    for key in sorted(counts.keys()): fout.write(f'{key}\n')

# of word tokens: 363
# of word types: 177

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

Task 1: Getting Started

In this assignment, you will:

1. Set up your development environment,

2. Install your first Python package using pip within a virtual environment,

3. Run a test program to verify the installation and environment configuration, and

4. Commit your changes and push them to your GitHub repository.

This will ensure your development workspace is properly configured for this course.

Package Installation

1. Open Terminal in PyCharm:

   2. Select the [View] > [Tool Windows] > [Terminal] menu).

2. Copy

   python -m pip install --upgrade pip

3. Copy

   pip install setuptools

4. Copy

   pip install elit_tokenizer

5. You will know the installation is successful when you see "Successfully installed ..." messages for each package in the terminal output.

Test Program

1. Create the project structure:

   3. PyCharm will automatically create __init__.py files in both directories to mark them as Python packages.

2. Create your first program:

   2. Copy the following code into the file:

   Copy

   from elit_tokenizer import EnglishTokenizer
   
   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)

3. Run the program:

   1. Choose the [Run] > [Run 'getting_started'] menu, or

   2. Use the green run button next to the main block.
4. Verify the output; your program is working correctly if you see this output:

   Copy

   ['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', '.']
   [(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, 50), (51, 58), (59, 61), (62, 67), (68, 70), (71, 75), (76, 78), (79, 83), (83, 84), (85, 88), (89, 93), (94, 96), (97, 98), (99, 108), (109, 111), (112, 117), (118, 128), (128, 129)]

Commit & Push

1. 1. Create the file in your nlp-essentials root directory

   2. Add the following lines to exclude unnecessary files:

   Copy

   .idea/
   .venv/

2. Stage your files for commit:

   1. Add the following files to Git by right-clicking them and selecting [Git] > [Add]:

      Copy

      .gitignore
      src/__init__.py
      src/homework/__init__.py
      src/homework/getting_started.py

   2. Files should turn green when successfully added. If files do not change color, restart PyCharm and try again.

3. Commit and push your changes:

   1. Right-click the nlp-essentials directory.

   2. Select [Git] > [Commit Directory].

   3. Write a descriptive commit message (e.g., "Initial setup and tokenizer test")

   4. Click [Commit and Push] (not just Commit)

   5. Click [Push] in the next dialog to upload to your GitHub repository.

4. Verify your submission:

   1. Visit your GitHub repository in a web browser.

   2. Confirm that all files are properly present and contain the correct content.

Submission

Submit the URL of your GitHub repository to Canvas.

Task 2: Project Ideas

Rubric

• GitHub Setup (0.2 points):

  • Private repository created.

  • All instructors added as collaborators.

• Project Organization (0.2 points):

  • Correct directory structure.

  • No unnecessary files committed

• Version Control (0.3 points):

  • All required files committed and successfully pushed to GitHub.

  • Content of the files are correct.

• Code Implementation (0.3 points):

  • The program executes without errors.

  • Produces correct tokenizer output.

• Project Ideas (1 point)

  • Is the team project idea well described?

• Attendance is mandatory for all Project Pitches and Live Demonstrations sessions.

Entropy

Entropy has several properties, including:

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.

Perplexity

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.

Core Syntax

Metacharacters

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

• .: any single character except a newline character

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

• [ ]: a character set matching any character within the brackets

  e.g., [aeiou] matches any vowel.

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

  e.g., \d\d\d searches for "170" in "CS170".

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

  e.g., \D\D searches for "kg" in "100kg".

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

  e.g., \s searches for the space " " in "Hello World".

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

  e.g., \S searches for "H" in " Hello".

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

  e.g., \w\w searches for "1K" in "$1K".

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

  e.g., \W searches for "!" in "Hello!".

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

  e.g., \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:

• *: the preceding character or group appears zero or more times

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

• +: the preceding character or group appears one or more times

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

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

  e.g., https? matches both "http" and "https".

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

  e.g., \d{3} is equivalent to \d\d\d.

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

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

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

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

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

  e.g., <.+> matches the entire string of "<Hello> and <World>".

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

  e.g., <.+?> 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 ).

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

  e.g., (cat|dog) matches either "cat" or "dog".

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

• (?: ): 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

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

  e.g., (\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".

• You can nest groups within other groups to create more complex patterns

  e.g., (\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.

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

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

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

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

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

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

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

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

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

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

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

  e.g., 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.":

import re

re_mr = re.compile(r'M[rs]\.')
m = re_mr.match('Mr. Wayne')

print(m)
if m: print(m.start(), m.end())

<re.Match object; span=(0, 3), match='Mr.'>
0 3

group()

Currently, no group has been specified for re_mr:

print(m.groups())

()

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

re_mr = re.compile(r'(M[rs])(\.)')
m = re_mr.match('Ms.')

print(m)
print(m.group())
print(m.groups())
print(m.group(0), m.group(1), m.group(2))

<re.Match object; span=(0, 3), match='Ms.'>
Ms.
('Ms', '.')
Ms. Ms .

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

m = RE_MR.match('Mrs.')
print(m)

None

search()

Let us match the following strings with re_mr:

s1 = 'Mr. and Ms. Wayne are here'
s2 = 'Here are Mr. and Ms. Wayne'

print(re_mr.match(s1))
print(re_mr.match(s2))

<re.Match object; span=(0, 3), match='Mr.'>
None

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:

print(re_mr.search(s1))
print(re_mr.search(s2))

<re.Match object; span=(0, 3), match='Mr.'>
<re.Match object; span=(9, 12), match='Mr.'>

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:

print(re_mr.findall(s1))
print(re_mr.findall(s2))

[('Mr', '.'), ('Ms', '.')]
[('Mr', '.'), ('Ms', '.')]

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:

ms = re_mr.finditer(s1)
for m in ms: print(m)

ms = re_mr.finditer(s2)
for m in ms: print(m)

<re.Match object; span=(0, 3), match='Mr.'>
<re.Match object; span=(8, 11), match='Ms.'>
<re.Match object; span=(9, 12), match='Mr.'>
<re.Match object; span=(17, 20), match='Ms.'>

sub()

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

print(re_mr.sub('Dr.', 'I met Mr. Wayne and Ms. Kyle.'))

I met Dr. Wayne and Dr. Kyle.

Tokenization

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

def tokenize(text: str) -> list[str]:
    re_tok = re.compile(r'([",.]|\s+|n\'t)')
    tokens, prev_idx = [], 0

    for m in re_tok.finditer(text):
        t = text[prev_idx:m.start()].strip()
        if t: tokens.append(t)
        t = m.group().strip()
        
        if t:
            if tokens and tokens[-1] in {'Mr', 'Ms'} and t == '.':
                tokens[-1] = tokens[-1] + t
            else:
                tokens.append(t)
        
        prev_idx = m.end()

    t = text[prev_idx:]
    if t: tokens.append(t)
    return tokens

• 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:

text = 'Mr. Wayne isn\'t the hero we need, but "the one" we deserve.'
print(tokenize(text))

text = 'Ms. Wayne is "Batgirl" but not "the one".'
print(tokenize(text))

['Ms.', 'Wayne', 'is', '"', 'Batgirl', '"', 'but', 'not', '"', 'the', 'one', '"']
['Ms.', 'Wayne', 'is', '"', 'Batgirl', '"', 'but', 'not', '"', 'the', 'one', '"', '.']

References

A vector space model is a computational framework to represent text documents as vectors in a high-dimensional space such that each document is represented as a vector, and each dimension of the vector corresponds to a particular term in the vocabulary.

Contents

Unigram Smoothing

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:

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:

• L3: Define a constant representing the unknown word.

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

• L8: Increment each unigram count by 1.

• L9: Add the unknown word to the unigrams with a probability of 1 divided by the total count.

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:

Bigram Smoothing

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

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:

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

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

• L13: Calculate the probability for an unknown current word.

• L16: Add a probability for an unknown previous word.

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

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

Reference

Task 1: Chronicles of Narnia

Data Collection

For each book, gather the following details:

• Book Title (preserve exact spacing as shown in text)

• Year of Publishing (indicated in the title)

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

• Chapter Number (as Arabic numeral)

• Chapter Title

• Token Count of the Chapter Content

  • Each word, punctuation mark, and symbol counts as a separate token.

  • Count begins after chapter title and ends at next chapter heading or book end. Do not include chapter number and chapter title in count.

Implementation

1. • Each token is separated by whitespace.

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:

   • Takes a file path pointing to the text file.

   • Returns a dictionary with the structure shown below.

   • Books must be stored as key-value pairs in the main dictionary.

   • Chapters must be stored as lists within each book's dictionary/

   • Chapter lists must be sorted by chapter number in ascending order.

Task 2: Regular Expressions

Define a function named regular_expressions() in src/homework/text_processing.py that takes a string and returns one the four types, "email", "date", "url", "cite", or None if nothing matches:

Submission

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

Rubric

• Task 1: Chronicles of Narnia (7 points)

• Task 2: Regular Expressions (3 points)

• Concept Quiz (2 points)

Term Frequency

The frequency of a word $w$'s occurrences in a document $D$ is called the Term Frequency (TF) of $w \in D$. TF is often used to determine the importance of a term within a document such that terms that appear more frequently are considered more relevant to the document's content.

However, TF alone does not always reflect the semantic importance of a term. To demonstrate this limitation, let us define a function that takes a filepath to a corpus and returns a list of documents, with each document represented as a separate line in the corpus:

from typing import Callable

def read_corpus(filename: str, tokenizer: Callable[[str], list[str]] | None = None) -> list[Document]:
    fin = open(filename)
    if tokenizer is None: tokenizer = lambda s: s.split()
    return [tokenizer(line) for line in fin]

from src.bag_of_words_model import vocabulary

corpus = read_corpus('dat/chronicles_of_narnia.txt')
vocab = vocabulary(corpus)

from src.bag_of_words_model import bag_of_words, Document, Vocab

def print_tfs(vocab: Vocab, documents: list[Document]):
    tfs = [bag_of_words(vocab, document) for document in documents]
    words = [word for word, _ in sorted(vocab.items(), key=lambda x: x[1])]
    for tf in tfs:
        print([(words[index], count) for index, count in sorted(tf.items(), key=lambda x: x[1], reverse=True)])

• L5: The underscore (_) is used to indicate that the variable is not being used in the loop.

At last, let us print the TFs of all terms in the following three documents:

from elit_tokenizer import EnglishTokenizer

ds = [
    "As dawn broke, the first light kissed the golden mane of Aslan, the rightful king of Narnia.",
    "The White Witch's icy breath froze the once lush meadows, casting a shadow over Narnia.",
    "Lucy's footsteps echoed in the halls of Cair Paravel, where legends were born."
]

etok = EnglishTokenizer()
documents = [etok.decode(d).tokens  for d in ds]
print_tfs(vocab, documents)

[('the', 3), (',', 2), ('of', 2), ('.', 1), ('As', 1), ('Aslan', 1), ('Narnia', 1), ('broke', 1), ('dawn', 1), ('first', 1), ('golden', 1), ('king', 1), ('kissed', 1), ('light', 1), ('mane', 1), ('rightful', 1)]
[("'s", 1), (',', 1), ('.', 1), ('Narnia', 1), ('The', 1), ('White', 1), ('Witch', 1), ('a', 1), ('breath', 1), ('casting', 1), ('froze', 1), ('icy', 1), ('once', 1), ('over', 1), ('shadow', 1), ('the', 1)]
[("'s", 1), (',', 1), ('.', 1), ('Cair', 1), ('Lucy', 1), ('Paravel', 1), ('born', 1), ('echoed', 1), ('footsteps', 1), ('halls', 1), ('in', 1), ('legends', 1), ('of', 1), ('the', 1), ('were', 1), ('where', 1)]

In the first document, terms that are typically considered semantically important, such as "Aslan" or "Narnia," receive a TF of 1, whereas functional terms such as "the" or punctuation like "," or "." receive higher TFs.

Stopwords

One simple approach to addressing this issue is to discard common terms with little sematnic values, referred to as stop words, which occur frequently but do not convey significant information about the content of the text. By removing stop words, the focus can be placed on the more meaningful content words, which are often more informative for downstream tasks.

from string import punctuation

stopwords = {line.strip().lower() for line in open('dat/stopwords.txt')}
is_stopwords = lambda w: w.lower() in stopwords or w in punctuation

Next, we define a tokenizer that excludes stop words during the tokenization process, and use it to retrieve the vocabulary:

sw_tokenizer = lambda s: [word for word in s.split() if not is_stopwords(word)]
corpus = read_corpus('dat/chronicles_of_narnia.txt', sw_tokenizer)
vocab = vocabulary(corpus)

Finally, let us print the TFs of the same documents using the updated vocabulary:

print_tfs(vocab, documents)

[('Aslan', 1), ('Narnia', 1), ('broke', 1), ('dawn', 1), ('golden', 1), ('king', 1), ('kissed', 1), ('light', 1), ('mane', 1), ('rightful', 1)]
[("'s", 1), ('Narnia', 1), ('White', 1), ('Witch', 1), ('breath', 1), ('casting', 1), ('froze', 1), ('icy', 1), ('shadow', 1)]
[("'s", 1), ('Cair', 1), ('Lucy', 1), ('Paravel', 1), ('born', 1), ('echoed', 1), ('footsteps', 1), ('halls', 1), ('legends', 1)]

Document Frequency

Filtering out stop words allows us to generate less noisy vector representations. However, in the above examples, all terms now have the same TF of 1, treating them equally important. A more sophisticated weighting approach involves incorporating information about terms across multiple documents.

Document Frequency (DF) is a measure to quantify how often a term appears across a set of documents within a corpus such that it represents the number of documents within the corpus that contain a particular term.

Let us define a function that takes a vocabulary dictionary and a corpus, and returns a dictionary whose keys are term IDs and values are their corresponding document frequencies:

from collections import Counter
from src.types import SparseVector

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

We then compare the term and document frequencies of all terms in the above documents:

corpus = read_corpus('dat/chronicles_of_narnia.txt')
vocab = vocabulary(corpus)
words = [word for word, _ in sorted(vocab.items(), key=lambda x: x[1])]

dfs = document_frequencies(vocab, corpus)
for document in documents:
    bow = bag_of_words(vocab, document)
    tf_df = [(words[tid], tf, dfs[tid]) for tid, tf in sorted(bow.items())]
    tf_df = sorted(tf_df, key=lambda x: (-x[1], x[2]))
    print(' '.join(document))
    print('\n'.join(['{:>10}  {}  {:>5}'.format(*t) for t in tf_df]))