Words, Tokens, and Basic NLP Processing Techniques

Introduction to ELIZA and Early NLP Systems

• Definition of ELIZA: An early natural language processing (NLP) system developed by Weizenbaum in 1966 that could maintain limited conversations. It functioned by imitating the responses of a Rogerian psychotherapist.
• ELIZA's Mechanism: It used a simple pattern-matching program to recognize specific phrases and transform them into outputs. For example, recognizing "I need X" would result in "What would it mean to you if you got X?".
• Historical Impact: Despite its simplicity, ELIZA's mimicry was successful enough that users believed the system understood them, prompting researchers to consider the ethical impacts of chatbots on human users (Weizenbaum, 1976).
• Dialogue Example (Weizenbaum, 1966):   - User: I need some help, that much seems certain.   - ELIZA: WHAT WOULD IT MEAN TO YOU IF YOU GOT SOME HELP   - User: Perhaps I could learn to get along with my mother.   - ELIZA: TELL ME MORE ABOUT YOUR FAMILY   - User: My mother takes care of me.   - ELIZA: WHO ELSE IN YOU FAMILY TAKES CARE OF YOU   - User: My father.   - ELIZA: YOUR FATHER   - User: You are like my father in some ways.

Defining the Word and Tokenization

• Tokenization: The first step in modern NLP, which involves separating or "tokenizing" words and word parts from running text. It spans from simple pattern-based approaches to complex data-driven algorithms.
• Challenges in Defining "Words": Determining what constitutes a word depends heavily on the task and language.   - The Punctuation Factor: In the sentence "They picnicked by the pool, then lay back on the grass and looked at the stars.", there are 16 words excluding punctuation, but 18 if punctuation (period and comma) is included.   - Punctuation Utility: Commas and periods signal boundaries; question marks and exclamation points identify nuances of meaning. Large language models (LLMs) typically treat punctuation as separate words.
• Terminology of Spoken Language:   - Utterance: The spoken correlate of a sentence.   - Disfluency: Interruptions in the flow of speech.   - Fragment: Broken-off words (e.g., "main-" in "mainly").   - Fillers / Filled Pauses: Words like "uh" and "um".   - Application of Disfluencies: In speech recognition, fillers are often kept as they help predict restarts in clauses or identify specific speakers. Clark and Fox Tree (2002) demonstrated that "uh" and "um" possess distinct meanings in English.

Word Statistics: Types, Instances, and Corpus Growth

• Word Types: The number of distinct words in a set (vocabulary $V$). The size is denoted as $|V|$.
• Word Instances: The total number of running words ($N$). Traditionally referred to as "tokens," though "token" now specifically refers to the output of subword tokenization algorithms.
• Case Study: Picnic Sentence: "They picnicked by the pool, then lay back on the grass and looked at the stars." contains 16 instances but only 14 types (excluding punctuation).
• Capitalization: Whether "They" and "they" are the same type depends on the task. Some models keep two versions: one cased and one uncased.
• Herdan’s Law / Heaps’ Law: Describes the relationship between vocabulary size ($|V|$) and corpus size ($N$).   - Formula: $|V| = kN^\beta$   - Constants: $k$ and $\beta$ are positive constants, where 0 < \beta < 1. Typically, $\beta$ ranges from $0.44$ to $0.56$.   - Interpretation: Vocabulary size grows slightly faster than the square root of the corpus length.
• Word Classes:   - Function Words: Grammatical words (e.g., "a", "of") that belong to a fixed, finite set.   - Content Words: Nouns, verbs, and adjectives that grow indefinitely as new names, technical terms, and events emerge.
• The Unknown Word Problem: Since word types grow without bound, computational models will inevitably encounter words not seen during training. This necessitates subword tokenization.

Cross-Lingual Word Definitions

• Orthographic Differences: English uses spaces, but Chinese, Japanese, and Thai do not.
• Chinese Word Segmentation:   - Hanzi: Chinese characters. Each usually represents a single morpheme and one syllable. Words average 2.4 characters long.   - Segmentation Standards:     - Chinese Treebank: Names (Family + Personal) are one word (e.g., "YaoMing" as 1 word).     - Peking University Standard: Names are separate units (e.g., "Yao" and "Ming" as 2 words).     - Character-as-Word: Treating the sentence as 7 individual characters (e.g., Yao, Ming, Enter, Enter, Overall, Decision, Game).
• Language Specifics: Character-level segmentation works for Chinese but fails for Japanese and Thai as characters are too small a unit.

Morphology: The Study of Morphemes

• Morpheme: The minimal meaning-bearing unit in a language.
• Morphology: The study of how morphemes form words.
• Categories of Morphemes:   - Root: The central morpheme providing the main meaning (e.g., "work" in "worked").   - Affix: Added to roots to provide additional meaning.
• Types of Affixes:   - Inflectional Morphemes: Productive, often obligatory grammatical markers (e.g., plural "-s", past tense "-ed").   - Derivational Morphemes: Idiosyncratic markers that often change the grammatical class of the root (e.g., "-ful" turns the noun "care" into the adjective "careful").
• Clitics: Morphemes that function syntactically as words but are reduced and attached to other words (e.g., "'ve" in "I've", "'s" in "teacher's", or French "l'" in "l'opera").
• Morphological Typology Dimensions:   - Morphemes per Word:     - Isolating Languages: Approximately one morpheme per word (e.g., Vietnamese, Cantonese).     - Synthetic/Polysynthetic Languages: Many morphemes per word, often representing entire sentences (e.g., Koryak).   - Segmentability:     - Agglutinative Languages: Clean boundaries between morphemes (e.g., Turkish).     - Fusion Languages: Single affixes conflate multiple meanings (e.g., Russian "-om" or English "-s" which denotes both 3rd person singular and present tense).

The Unicode Standard and Character Representation

• Unicode: A method for representing text for any character in any script.
• ASCII (American Standard Code for Information Interchange): An English-specific subset using 1 byte per character. It only uses 95 printable characters (decimal 32-126) and some control codes.   - Examples: 'A' is hex 41 (dec 65), 'a' is hex 61 (dec 97).
• Unicode 16.0 Scope: Over 150,000 characters and 168 scripts (including CJKV, Devanagari, Emojis, and dead languages like Sumerian cuneiform).
• Code Point: A unique hexadecimal ID assigned to every character, prefixed with "U+" (ranges from U+0000 to U+10FFFF).   - Examples: a (U+0061), \u00f9 (U+00F9), \u8fdb (U+8FDB).
• Glyph: The visual representation of a character (stored in fonts). A single code point (e.g., U+0061) can have many glyphs depending on the font (bold, italic, Times Roman).

UTF-8 Encoding

• UTF-8 (Unicode Transformation Format 8): The most frequent encoding on the web.
• Variable-Length Encoding: Uses different numbers of bytes (1-4) based on the code point.   - 1 Byte: First 127 ASCII characters (backwards compatible).   - 2 Bytes: European, Middle Eastern, and African scripts.   - 3 Bytes: Most Common Chinese, Japanese, and Korean (CJKV) characters.   - 4 Bytes: Rare CJKV, emojis, and symbols.
• Bit Mapping Table:   - Range U+0000-U+007F: Uses format 0xxxxxxx (1 byte).   - Range U+0080-U+07FF: Uses format 110yyyyy 10xxxxxx (2 bytes).   - Range U+0800-U+FFFF: Uses format 1110zzzz 10yyyyyy 10xxxxxx (3 bytes).   - Range U+10000-U+10FFFF: Uses format 11110uuu 10uuzzzz 10yyyyyy 10xxxxxx (4 bytes).
• Advantages: Efficient, no zero bytes (good for old ASCII systems), self-synchronizing (errors don't corrupt the whole file).

Byte-Pair Encoding (BPE) Algorithm

• Introduction: BPE is a data-driven approach used to define tokens that eliminate the unknown word problem by using subwords.
• Components: A trainer (induces vocabulary) and an encoder (segments test data).
• Training Process (Iterative Merging):   1. Start with a vocabulary of individual characters/bytes.   2. Identify the most frequent adjacent pair of tokens in the corpus.   3. Merge them into a new single token and update the vocabulary.   4. Repeat for $k$ number of merges.
• Pre-tokenization: BPE is usually applied within word boundaries. Inputs are often first split by whitespace/punctuation using regular expressions.
• Encoding Process: Applies learned merges greedily in the order they were learned during training.
• Practical Scale: Modern systems use 50,000 to 200,000 merges. GPT-4o uses 200K tokens.
• Specialized BPE Variants:   - SuperBPE / BoundlessBPE: Allow merges across spaces and punctuation for higher efficiency.   - Efficiency Metric: Measured in bytes-per-token.
• Multilingual Tokenization Issues: Tokenizers trained on English-heavy data often oversegment non-English languages.   - Example: In Spanish, "hondo" might be split into "h" and "ondo", increasing costs and reducing semantic cohesion.

Corpora and Linguistic Variation

• Dimensions of Variation: Language (7,097 known languages), genre, demographic characteristics of authors, and time.
• Dialectal Variation: Includes African American English (AAE or AAVE). Features like "iont" (I don't) or "talmbout" (talking about) affect segmentation.
• Code Switching: The use of multiple languages in a single utterance.
• Datasheets and Data Statements: Methods for documenting corpus details.   - Motivation: Why and who funded the collection.   - Situation: Context (monologue/dialogue, task-based).   - Language variety: Dialects/regions.   - Speaker demographics: Age/gender.   - Collection/Annotation process: Sampling and training of annotators.   - Distribution: Copyright restrictions.

Regular Expressions (Regex)

• Regex Definition: An algebraic notation for specifying sets of strings. Used in tokenization, text search, and substitution.
• Character Disjunction: Square brackets [] match any character inside (e.g., [mM]ary).
• Ranges: Use a dash - to specify sequences (e.g., [A-Z] for uppercase letters, [0-9] for digits).
• Negation: Use the caret ^ as the first character in brackets to match what isn't there (e.g., [^a] is any char except 'a').
• Counting and Optionality:   - ?: 0 or 1 occurrence (e.g., colou?r).   - * (Kleene star): 0 or more occurrences.   - + (Kleene plus): 1 or more occurrences.   - {n}: Exactly $n$ occurrences.
• Wildcard: The period . matches any character except a newline.
• Anchors:   - ^: Start of line.   - $: End of line.   - \b: Word boundary.   - \B: Non-word boundary.
• Precedence Hierarchy (Highest to Lowest):   1. Parenthesis ()   2. Counters * + ? {}   3. Sequences and anchors (e.g., ^my, the)   4. Disjunction | (the pipe symbol)
• Greedy vs. Non-greedy: Regex defaults to matching the largest possible string (greedy). Adding a ? after a counter (e.g., *?, +?) makes it non-greedy.
• Capture Groups: Use parentheses () to store matched values for later use in substitutions (referenced as \1, \2, etc.).
• Lookahead Assertions:   - (?= pattern): Positive lookahead; true if pattern follows, but doesn't move pointer (zero-width).   - (?! pattern): Negative lookahead; true if pattern does not follow.

Rule-Based Tokenization and Unix Tools

• Unix Pipeline Example: Count word frequency in Shakespeare (sh.txt):   - tr -sc 'A-Za-z' '\n' < sh.txt | tr A-Z a-z | sort | uniq -c | sort -n -r   - tr -sc: Replaces non-alphabetical chars with newlines, squeezing multiple instances into one.   - sort -n -r: Sorts numerically in reverse order.
• Penn Treebank Tokenization Standard:   - Separates clitics (e.g., "doesn't" $\rightarrow$ "does" + "n't").   - Keeps hyphenated words together.   - Separates punctuation as distinct tokens.
• Sentence Segmentation: Punctuations like ? and ! are relatively unambiguous, but . is ambiguous between a boundary and an abbreviation (e.g., "Dr.", "Inc.").

Minimum Edit Distance

• Definition: The minimum number of operations (insertions, deletions, substitutions) to transform one string into another.
• Alignment: A visualization of the correspondence between substrings of two sequences.
• Levenshtein Distance:   - Standard: Deletion = 1, Insertion = 1, Substitution = 1.   - Alternative version (Eq 2.20): Deletion = 1, Insertion = 1, Substitution = 2 (treating substitution as one deletion + one insertion).
• Minimum Edit Distance Algorithm: Uses Dynamic Programming (Bellman, 1957) to solve subproblems and store results in a matrix $D$.
• Recurrence Relation:   - $D[i, j] = \min \begin{cases} D[i-1, j] + \text{del-cost}(\text{source}[i]) \ D[i, j-1] + \text{ins-cost}(\text{target}[j]) \ D[i-1, j-1] + \text{sub-cost}(\text{source}[i], \text{target}[j]) \end{cases}$
• Backtrace: Following backpointers from the final cell $(n,m)$ to the starting cell $(0,0)$ to generate the optimal string alignment.
• Significance of Naming: Bellman chose the term "dynamic programming" in the 1950s because the term "research" was disliked by the Secretary of Defense, and "dynamic" sounded precise and impossible to view pejoratively.