Unit 1: Foundations of NLP and Text Processing

1. Introduction to Natural Language Processing (NLP)

Natural Language Processing (NLP) is an interdisciplinary field at the intersection of computer science, artificial intelligence, and computational linguistics. Its primary objective is to enable computational systems to understand, interpret, synthesize, and manipulate human language in a manner that is both semantically valid and contextually appropriate.

CODECopy Code
+-----------------------------------------------------------------------------------+
|                        THE INTERDISCIPLINARY SPECTRUM OF NLP                      |
+-----------------------------------------------------------------------------------+
|  Computer Science      | Algorithms, Data Structures, Complexity, Systems Eng.     |
|  Artificial Intelligence| Machine Learning, Deep Neural Networks, Probabilistic PGM|
|  Linguistics           | Syntax, Semantics, Morphology, Phonology, Pragmatics      |
|  Cognitive Science     | Human Language Acquisition, Mental Lexicon, Comprehension|
+-----------------------------------------------------------------------------------+

1.1 The Linguistic Hierarchy

Human language is organized as a layered, hierarchical symbolic system. Computational processing typically decomposes natural language along these classical linguistic strata:

CODECopy Code
               [ Pragmatics & Discourse ]   (Context, Intent, Multi-Sentence Coherence)
                           ^
               [       Semantics        ]   (Literal Meaning, Truth Conditions, Roles)
                           ^
               [        Syntax          ]   (Grammar, Parse Trees, Dependency Graphs)
                           ^
               [      Morphology        ]   (Morphemes, Stems, Roots, Affixes)
                           ^
               [  Phonology / Orthography]  (Sound Waves, Phonemes, Alphabetic Tokens)

1. Phonetics and Phonology:
   • Studies the physical production (phonetics) and systematic cognitive patterns (phonology) of speech sounds.
   • Core units: Phones (acoustic waveforms) and Phonemes (minimal sound units distinguishing words, e.g., /p/ vs. /b/ in "pat" vs. "bat").
2. Morphology:
   • The study of word structure and the rules governing how minimal units of meaning (morphemes) combine.
   • Free Morphemes: Can stand alone as independent words (e.g., dog, play, govern).
   • Bound Morphemes: Must attach to other morphemes as prefixes, suffixes, or infixes (e.g., un-, -ed, -ment, -s).
   • Inflectional Morphology: Modifies grammatical form without changing lexical category (e.g., walk $\to$ walks, walked, walking).
   • Derivational Morphology: Creates new lexical concepts or alters grammatical category (e.g., govern (verb) $\to$ government (noun) $\to$ governmental (adjective)).
3. Syntax:
   • The structural rules governing how words combine into grammatical phrases, clauses, and sentences.
   • Formalized using context-free grammars (CFGs), constituency parse trees (phrase structure), and dependency grammars (head-dependent governor relationships).
4. Semantics:
   • The study of literal meaning expressed by words, phrases, and compositional sentences, independent of subjective context.
   • Encompasses lexical semantics (synonymy, antonymy, hyponymy, polysemy) and compositional semantics (Frege's principle: the meaning of a whole sentence is a mathematical function of the meanings of its constituent parts).
5. Pragmatics:
   • How context, social conventions, background knowledge, and speaker intentions influence meaning.
   • Decodes non-literal expressions, sarcasm, metaphors, and speech acts (e.g., "Can you pass the salt?" is a pragmatic request to take action, not a query regarding physical capability).
6. Discourse Analysis:
   • Understanding linguistic meaning across sequences of connected sentences, handling anaphora resolution, coreference chains, and rhetorical structure.

2. Inherent Challenges and Ambiguities in Natural Language

Unlike formal programming languages (such as Python, C++, or SQL) which possess deterministic context-free grammars and unambiguous compilation rules, human languages are inherently fluid, dynamic, and laden with multifaceted ambiguity.

2.1 Taxonomy of Linguistic Ambiguity

CODECopy Code
+----------------------------------------------------------------------------------------------------+
|                                    TAXONOMY OF NLP AMBIGUITIES                                     |
+------------------------------------+---------------------------------------------------------------+
| Ambiguity Type                     | Illustrative Example & Computational Problem                  |
+------------------------------------+---------------------------------------------------------------+
| Lexical Ambiguity (Polysemy)       | "I deposited money in the bank" vs "He sat on the river bank".|
|                                    | (The token 'bank' possesses completely distinct senses).      |
+------------------------------------+---------------------------------------------------------------+
| Syntactic Ambiguity (Structural)   | "I saw the man with a telescope."                             |
|                                    | (Did I use a telescope to see him, or did the man hold one?)  |
+------------------------------------+---------------------------------------------------------------+
| Semantic Ambiguity (Scope)         | "Every student loves a professor."                            |
|                                    | (Does a single professor get loved by all, or does each       |
|                                    |  student love a different professor?)                         |
+------------------------------------+---------------------------------------------------------------+
| Pragmatic / Anaphoric Ambiguity    | "The trophy did not fit in the suitcase because it was too    |
|                                    |  big." (What does 'it' refer to? The trophy or the suitcase?)|
+------------------------------------+---------------------------------------------------------------+

1. Lexical Ambiguity:
   • Occurs when a single word token exhibits multiple meanings:
     • Homonymy: Unrelated concepts sharing the exact same orthographic spelling and pronunciation (e.g., bank as a financial institution vs. river bank).
     • Polysemy: Related senses derived from an underlying conceptual root (e.g., wood as a forested area vs. the structural material from trees).
   • Resolved via Word Sense Disambiguation (WSD) algorithms using context vectors.
2. Syntactic (Structural) Ambiguity:
   • Arises when a sequence of tokens can generate multiple valid hierarchical syntax trees.
   • Prepositional Phrase (PP) Attachment Ambiguity:
     In "The chef cooked the pasta with garlic", the PP attaches to the verb phrase (cooked with garlic). In "The chef cooked the pasta with clams", the PP attaches to the noun phrase (pasta with clams). Resolving this requires world knowledge regarding culinary semantics.
3. Anaphoric / Coreference Ambiguity:
   • Winograd Schema challenges demonstrate pragmatic ambiguity:
     • "The city councilmen refused the demonstrators a permit because they feared violence." $\to$ they = councilmen.
     • "The city councilmen refused the demonstrators a permit because they advocated violence." $\to$ they = demonstrators.
   • Resolving pronouns requires deep contextual reasoning and world knowledge beyond surface grammar.

3. Text Preprocessing and Normalization Pipelines

Before unstructured textual corpora can be processed by machine learning algorithms or neural networks, text must undergo rigorous cleaning, segmentation, and normalization.

CODECopy Code
Raw Text Document
      |
[Sentence Segmentation]  --> Divides document into discrete sentences
      |
[Word Tokenization]      --> Divides sentences into token streams
      |
[Case Normalization]     --> Lowercasing (conditional)
      |
[Stopword Removal]       --> Strips high-frequency syntactic glue (task-dependent)
      |
[Morphological Parsing]  --> Stemming or Lemmatization
      v
Cleaned Token Sequence

3.1 Sentence Segmentation (Sentence Boundary Disambiguation)

• Sentence segmentation identifies boundary delimiters separating consecutive sentences.
• The Period Delimiter Problem: Periods do not solely denote sentence terminations; they mark abbreviations (e.g., Dr., Inc., U.S.A.), decimal numbers (3.1415), ellipses (...), and email/web addresses (info@lpu.in).
• Techniques:
  • Regular expression heuristic rules (e.g., match uppercase letter following period and whitespace).
  • Machine learning classifiers (e.g., Punkt tokenizer in NLTK): unsupervised rule-based clustering of abbreviation candidates based on collocations and capitalization patterns.

3.2 Tokenization Paradigms

Tokenization partitions a continuous string of characters into meaningful atomic units termed tokens.

1. Whitespace Tokenization:
   • Splits text strictly along whitespace characters ( , \t, \n).
   • Failure Modes: Fails on punctuation boundaries ("Hello, world!" $\to$ ["Hello,", "world!"]), contracted forms ("don't" $\to$ ["don't"] instead of ["do", "n't"]), and non-segmented writing systems (Chinese, Japanese, Thai) that feature no whitespace between words.
2. Penn Treebank Rule-Based Tokenization:
   • Separates clitics and contractions: "they'll" $\to$ ["they", "'ll"], "isn't" $\to$ ["is", "n't"].
   • Isolates terminal punctuation while preserving abbreviations and internal hyphens.

3.3 Stopword Filtering

• Stopwords: Extremely high-frequency functional words that carry little distinctive semantic information in classical bag-of-words retrieval models (e.g., the, is, at, which, on, and).
• When to Remove: Information retrieval, keyword extraction, topic modeling (LDA), document classification using TF-IDF.
• When NOT to Remove: Machine translation, sentiment analysis, text generation, and modern Transformer-based pretrained models (BERT, GPT). In transformers, self-attention uses stopwords to establish syntactic scaffolding and coreference connections (e.g., stripping "not" completely inverts sentiment in "not good").

3.4 Stemming vs. Lemmatization

CODECopy Code
+-----------------------------------------------------------------------------------+
|                         STEMMING VS. LEMMATIZATION COMPARISON                     |
+--------------------------+----------------------------+---------------------------+
| Dimension                | Stemming                   | Lemmatization             |
+--------------------------+----------------------------+---------------------------+
| Primary Approach         | Crude heuristic suffix     | Morphological analysis    |
|                          | stripping rules            | using lexical dictionaries|
+--------------------------+----------------------------+---------------------------+
| Part of Speech Awareness | Completely unaware of POS  | Strictly requires POS tag |
+--------------------------+----------------------------+---------------------------+
| Output Validity          | Often yields non-words     | Always yields valid base  |
|                          | (e.g., 'studi', 'univers') | dictionary lemmas ('study')|
+--------------------------+----------------------------+---------------------------+
| Computational Speed      | Extremely fast, lightweight| Slower, requires lexicon  |
|                          | memory footprint           | lookup & morphological DB |
+--------------------------+----------------------------+---------------------------+

Stemming Algorithms: Porter vs. Lancaster

• Porter Stemmer (Porter, 1980):
  • Consists of 5 sequential heuristic condition-action phases.
  • Relies on the measure $m$ of alternating vowel-consonant sequences: $[C](VC)^m[V]$.
  • Example: generalizations $\to$ generalize $\to$ general $\to$ gener.
  • Errors:
    • Over-stemming: Merging words with distinct meanings to the same root (e.g., universe, university, universal all reduced to univers).
    • Under-stemming: Failing to reduce words with the same root together (e.g., adhere and adhesion reduced to different roots).
• Lancaster (Paice-Husk) Stemmer:
  • Employs aggressive rule tables. Highly prone to over-stemming (e.g., policy $\to$ pol).

Lemmatization: WordNet Lemmatizer

• Reduces inflected word forms to their linguistically valid base form (lemma) using a vocabulary database (e.g., Princeton WordNet).
• Crucial POS Dependency: The word "meeting":
  • If tagged as a Noun ($\text{POS} = n$): lemma = "meeting" (an event).
  • If tagged as a Verb ($\text{POS} = v$): lemma = "meet".
  • The word "better":
    • If tagged as Adjective ($\text{POS} = a$): lemma = "good".

4. Subword Tokenization Algorithms

Modern neural language models (BERT, RoBERTa, GPT-4, LLaMA) require fixed-size vocabularies (typically $30,000 - 100,000$ tokens) capable of representing arbitrary open-domain text without suffering from Out-Of-Vocabulary (OOV) issues.

CODECopy Code
Character Tokenization          Subword Tokenization              Word Tokenization
[c, a, t, s, b, e, d]       [cat, ##s, bed]                   [cats, bed]
(Vocab: ~100; Seq: Long)    (Vocab: ~32k; Balanced, No OOV)   (Vocab: >1M; Huge, Many OOVs)

4.1 Byte-Pair Encoding (BPE)

Pioneered for data compression by Gage (1994) and adapted for NLP subword tokenization by Sennrich, Haddow, and Birch (ACL 2016).

The BPE Training Algorithm

1. Initialize vocabulary $V$ with all unique characters present in the training corpus, plus a special end-of-word symbol (e.g., </w>).
2. Represent every word in the training corpus as a sequence of individual character symbols.
3. Count the frequency of all adjacent symbol pairs across the entire tokenized corpus.
4. Identify the most frequent adjacent pair $(c_1, c_2)$ and merge it into a single new symbol $c_{new} = c_1 c_2$.
5. Add $c_{new}$ to vocabulary $V$.
6. Repeat steps 3–5 iteratively until reaching a predefined target vocabulary size or merge threshold.

CODECopy Code
BPE Step-by-Step Toy Example:
Corpus: {"l o w </w>": 5, "l o w e r </w>": 2, "n e w e s t </w>": 6, "w i d e s t </w>": 3}

Iteration 1:
Pair counts: ('e', 's'): 9, ('s', 't'): 9, ('e', 'w'): 8, ('l', 'o'): 7, ('o', 'w'): 7
Merge ('e', 's') -> 'es'.
Corpus: {"l o w </w>": 5, "l o w e r </w>": 2, "n e w es t </w>": 6, "w i d es t </w>": 3}

Iteration 2:
Most frequent pair: ('es', 't') -> count: 9.
Merge ('es', 't') -> 'est'.
Corpus: {"l o w </w>": 5, "l o w e r </w>": 2, "n e w est </w>": 6, "w i d est </w>": 3}

Iteration 3:
Most frequent pair: ('est', '</w>') -> count: 9.
Merge ('est', '</w>') -> 'est</w>'.
Corpus: {"l o w </w>": 5, "l o w e r </w>": 2, "n e w est</w>": 6, "w i d est</w>": 3}

4.2 Byte-Level BPE (BBPE)

• Standard BPE operating on Unicode characters struggles across multilingual corpora with rare Unicode glyphs (emojis, complex scripts), causing vocabulary bloat.
• Radfor et al. (GPT-2) introduced Byte-level BPE: initializes the base vocabulary with all $256$ raw byte values of UTF-8.
• Advantage: Any sequence of text in any language can be represented without ever producing an unknown token (<unk>).

4.3 WordPiece Tokenizer

Developed by Schuster & Nakajima (2012) and adopted in Google's BERT (Devlin et al., 2018).

• Difference from BPE: Instead of selecting the symbol pair with the highest raw co-occurrence frequency, WordPiece selects the pair that maximizes the likelihood of the training corpus under a unigram language model.
• Score for candidate pair $(u, v)$:
  $\text{Score}(u, v) = \frac{\text{Count}(uv)}{\text{Count}(u) \times \text{Count}(v)}$
  High scores reward pairs whose joint frequency is significantly higher than expected by independent chance.
• In BERT, subwords that occur inside words rather than at prefixes are preceded by a double-hash prefix (##):
  "unaffable" $\to$ ["un", "##aff", "##able"].

4.4 Unigram Language Model Tokenizer (SentencePiece)

Introduced by Kudo (2018):

• Operates in a top-down pruning direction, unlike BPE's bottom-up merging.
• Starts with an enormous initial seed vocabulary (e.g., all characters + thousands of common substrings).
• Fits a unigram language model over the corpus.
• At each step, calculates how much the total corpus likelihood would decrease if each candidate subword were removed from the vocabulary.
• Prunes the bottom $p\%$ (e.g., $20\%$) of subwords causing the least likelihood loss.
• Repeats until reaching the desired vocabulary size. At inference time, uses the Viterbi algorithm to find the optimal subword segmentation that maximizes overall probability.

5. Statistical Language Modeling and Vector Space Models

Before deep recurrent or transformer networks, NLP relied on statistical vector space representations and N-gram Markov models.

5.1 Bag-of-Words (BoW) Representation

• Represents a document as an unordered collection of word counts, completely discarding syntax, word order, and grammar.
• Let vocabulary $V = \{w_1, w_2, \dots, w_{|V|}\}$. A document $d$ is mapped to a vector $\mathbf{x} \in \mathbb{R}^{|V|}$ where each coordinate $x_i$ equals the frequency of term $w_i$ in $d$.
• Limitations:
  1. Extreme Sparsity: If vocabulary $|V| = 100,000$ and a sentence contains 10 words, $99.99\%$ of vector coordinates are zero.
  2. Total Loss of Sequential Context: "Not bad, really good" and "Not good, really bad" yield identical vectors.
  3. Frequency Bias: Ubiquitous non-informative words (the, is) dominate magnitude over rare informative terms (photosynthesis).

5.2 Term Frequency - Inverse Document Frequency (TF-IDF)

TF-IDF attenuates the influence of ubiquitous terms while boosting domain-specific keywords.

CODECopy Code
+-----------------------------------------------------------------------------------+
|                            THE TF-IDF MATHEMATICAL FORMULATION                    |
+-----------------------------------------------------------------------------------+
| Term Frequency: TF(t, d) = f_{t, d} / sum_{t'} f_{t', d}                          |
|                                                                                   |
| Inverse Doc Frequency: IDF(t, D) = log( (1 + N) / (1 + |{d in D : t in d}|) ) + 1|
|                                                                                   |
| Combined Weight: TF-IDF(t, d, D) = TF(t, d) * IDF(t, D)                           |
+-----------------------------------------------------------------------------------+

1. Term Frequency (TF): Measures how frequently term $t$ appears within document $d$:
   $\text{TF}(t, d) = \frac{f_{t, d}}{\sum_{t' \in d} f_{t', d}}$
2. Inverse Document Frequency (IDF): Measures the informativeness of term $t$ across corpus $D$ containing $N$ total documents:
   $\text{IDF}(t, D) = \log \left( \frac{N}{|\{d \in D : t \in d\}|} \right)$
   If a term appears in every document ($|\{d\}| = N$), $\text{IDF} = \log(1) = 0$, completely nullifying its weight.
3. TF-IDF Vector:
   $\text{TF-IDF}(t, d, D) = \text{TF}(t, d) \times \text{IDF}(t, D)$
   Vectors are typically normalized to unit $\ell_2$-norm: $\mathbf{v}_{norm} = \frac{\mathbf{v}}{\|\mathbf{v}\|_2}$.

5.3 Vector Similarity Metrics: Cosine Similarity

To compare two documents represented by TF-IDF vectors $\mathbf{u}$ and $\mathbf{v}$:
$\text{Cosine Similarity}(\mathbf{u}, \mathbf{v}) = \frac{\mathbf{u} \cdot \mathbf{v}}{\|\mathbf{u}\|_2 \|\mathbf{v}\|_2} = \frac{\sum_{i=1}^{|V|} u_i v_i}{\sqrt{\sum_{i=1}^{|V|} u_i^2} \sqrt{\sum_{i=1}^{|V|} v_i^2}}$

• Invariant to document length: Two documents with identical topic proportions but different lengths produce an identical cosine similarity of 1.0.

6. N-Gram Language Models and Smoothing Techniques

A Language Model (LM) computes a joint probability distribution over word sequences $W = (w_1, w_2, \dots, w_m)$:
$P(W) = P(w_1, w_2, \dots, w_m)$
Applying the chain rule of probability decomposes this joint distribution:
$P(w_1, \dots, w_m) = \prod_{i=1}^m P(w_i \mid w_1, \dots, w_{i-1})$

6.1 The Markov Assumption and N-Gram Formulations

Conditioning on the entire preceding history $w_1, \dots, w_{i-1}$ is computationally intractable because long word sequences never repeat in finite training data.

The Markov Assumption: The probability of an upcoming word depends only on the preceding $n - 1$ words:
$P(w_i \mid w_1, \dots, w_{i-1}) \approx P(w_i \mid w_{i-n+1}, \dots, w_{i-1})$

• Unigram Model ($n=1$): Words are independent:
  $P(w_1, \dots, w_m) = \prod_{i=1}^m P(w_i)$
• Bigram Model ($n=2$): Depends only on the immediate predecessor:
  $P(w_1, \dots, w_m) = \prod_{i=1}^m P(w_i \mid w_{i-1})$
• Trigram Model ($n=3$): Depends on preceding two words:
  $P(w_1, \dots, w_m) = \prod_{i=1}^m P(w_i \mid w_{i-2}, w_{i-1})$

6.2 Maximum Likelihood Estimation (MLE)

Using relative frequency counts from a training corpus:
$P_{MLE}(w_i \mid w_{i-1}) = \frac{C(w_{i-1}, w_i)}{C(w_{i-1})}$
$P_{MLE}(w_i \mid w_{i-2}, w_{i-1}) = \frac{C(w_{i-2}, w_{i-1}, w_i)}{C(w_{i-2}, w_{i-1})}$

6.3 The Zero-Probability Pathology & Smoothing Algorithms

If a valid word sequence was never observed during training ($C(w_{i-1}, w_i) = 0$), then $P_{MLE}(w_i \mid w_{i-1}) = 0$. Under the chain rule, a single zero probability forces the entire document probability to zero:
$P(W) = 0$

To fix this, smoothing reallocates probability mass from frequent N-grams to unobserved N-grams.

1. Laplace (Add-1) Smoothing

Adds 1 to every N-gram count:
$P_{Laplace}(w_i \mid w_{i-1}) = \frac{C(w_{i-1}, w_i) + 1}{C(w_{i-1}) + |V|}$
Where $|V|$ is vocabulary size.
Limitation: Adds far too much probability mass to unseen events when $|V|$ is large ($|V| \approx 10^5$), severely degrading performance.

2. Add-k (Lidstone) Smoothing

Replaces 1 with a fractional parameter $k \in (0, 1)$ (typically $k = 0.05$):
$P_{Add-k}(w_i \mid w_{i-1}) = \frac{C(w_{i-1}, w_i) + k}{C(w_{i-1}) + k |V|}$

3. Jelinek-Mercer Linear Interpolation

Linearly combines higher-order and lower-order N-gram probabilities using interpolation weights $\lambda_i \in [0, 1]$ satisfying $\sum \lambda_i = 1$:
$P_{Interp}(w_i \mid w_{i-2}, w_{i-1}) = \lambda_3 P_{MLE}(w_i \mid w_{i-2}, w_{i-1}) + \lambda_2 P_{MLE}(w_i \mid w_{i-1}) + \lambda_1 P_{MLE}(w_i)$

4. Kneser-Ney Smoothing

The gold standard in classical statistical N-gram modeling. Incorporates continuation probability:

• Consider the word "York". It is very frequent, but almost exclusively follows "New".
• If a unigram model encounters a novel context, standard unigram probability would rank "York" highly, which is erroneous.
• Continuation Probability $P_{cont}(w)$ measures how likely word $w$ is to complete an unobserved context by counting the number of unique preceding words:
  $P_{cont}(w) = \frac{|\{w_{i-1} : C(w_{i-1}, w) > 0\}|}{\sum_{w'} |\{w_{i-1} : C(w_{i-1}, w') > 0\}|}$
• Interpolated Kneser-Ney Bigram Formula:
  $P_{KN}(w_i \mid w_{i-1}) = \frac{\max(C(w_{i-1}, w_i) - d, 0)}{C(w_{i-1})} + \lambda(w_{i-1}) P_{cont}(w_i)$
  Where $d \in (0, 1)$ is an absolute discount parameter, and $\lambda(w_{i-1}) = \frac{d}{C(w_{i-1})} |\{w : C(w_{i-1}, w) > 0\}|$ normalizes the distribution.

7. Evaluating Language Models: Perplexity

How do we measure the quality of a language model without deploying it in an end-to-end downstream system?

7.1 Cross-Entropy and Perplexity

For a test corpus $W = (w_1, w_2, \dots, w_N)$ containing $N$ total tokens, the average cross-entropy per word is:
$H(W) = -\frac{1}{N} \log_2 P(w_1, w_2, \dots, w_N) = -\frac{1}{N} \sum_{i=1}^N \log_2 P(w_i \mid w_1, \dots, w_{i-1})$

The Perplexity (PPL) is mathematically defined as 2 raised to the power of the cross-entropy:
$\text{PPL}(W) = 2^{H(W)} = P(w_1, w_2, \dots, w_N)^{-\frac{1}{N}} = \sqrt[N]{\prod_{i=1}^N \frac{1}{P(w_i \mid w_{i-1})}}$

CODECopy Code
+-----------------------------------------------------------------------------------+
|                        PERPLEXITY (PPL) INTUITIVE INTERPRETATION                  |
+-----------------------------------------------------------------------------------+
|  Intuition: The effective weighted "branching factor" of the language model.      |
|                                                                                   |
|  - If PPL = 50: At each prediction step, the model is as confused as if it were   |
|    choosing uniformly at random among 50 equally probable words.                  |
|  - A lower Perplexity indicates a superior language model that assigns higher     |
|    probabilities to real human-written text.                                      |
|  - A perfect model predicting the exact word with P=1.0 has Perplexity = 1.0.     |
+-----------------------------------------------------------------------------------+

8. Summary Comparison of Tokenization and Representation Methods