Computational Intelligence (AL-504 (C)) - Unit 1 Short Notes

UNIT 1: FOUNDATIONS OF NATURAL LANGUAGE PROCESSING (NLP)

I. INTRODUCTION TO NLP

Definition & Scope: NLP is a subfield of AI and linguistics focused on enabling computers to understand, interpret, manipulate, and generate human language. Its core objective is to bridge the gap between human communication and computer understanding.

Fundamental Challenges:

• Ambiguity: Words/phrases have multiple meanings (lexical, syntactic, semantic).

• Variability: Numerous ways to express the same idea (synonyms, paraphrasing).

• Scale & Noise: Massive, unstructured, and often erroneous text data.

• Common Sense & World Knowledge: Requires background knowledge not explicitly stated.

• Non-standard Language: Slang, typos, domain-specific jargon.

[!TIP] Exam Focus: Be prepared to list and illustrate each challenge with a concrete example (e.g., "I saw the man with the telescope" – prepositional phrase attachment ambiguity).

II. TEXT PREPROCESSING & BASIC TECHNIQUES

Tokenization

• Principle: Segment raw text into smaller units (tokens) like words, sentences, or subwords.

• Types:

  • Word Tokenization: Splitting on whitespace/punctuation. Challenging for languages without spaces (e.g., Chinese) or contractions ("can't").

  • Sentence Tokenization: Identifying sentence boundaries. Challenging with abbreviations (e.g., "Dr.").

  • Subword Tokenization (e.g., Byte-Pair Encoding, WordPiece): Used in modern models (BERT, GPT) for handling rare words and large vocabularies.

• Key Challenge: Language-specific rules; no universal tokenizer.

Regular Expressions (Regex) in NLP

• Basic Metacharacters: . (any char), * (0+), + (1+), ? (0/1), [] (set), ^ (start), $ (end), \d (digit), \w (word char), \s (whitespace).

• Practical Applications:

  • Pattern matching & extraction (e.g., email IDs, phone numbers).

  • Text cleaning (removing special characters, HTML tags).

  • Simple tokenization or normalization.

[!TIP] Exam Focus: Expect to write a regex pattern for a given extraction task (e.g., "Extract all hashtags from a tweet").

Spelling Error Detection and Correction

• Challenges in Noisy Text: Non-word errors ("teh") vs. real-word errors ("form" vs. "from"); context is crucial for real-word errors.

• Common Approaches:

  1. Detection: Dictionary lookup (non-word errors); language model probability (real-word errors).

  2. Correction:

     • Edit Distance: Generate candidate corrections within a maximum edit distance (usually 1 or 2).

     • Candidate Ranking: Use frequency, n-gram context, or phonetic similarity (Soundex) to select the best correction.

     • Noisy Channel Model: $P(w|c) \propto P(c|w) \cdot P(w)$, where $w$ is the original noisy word, $c$ is a candidate correction.

III. LANGUAGE MODELING

N-gram Models

• Concept: Predict the next word based on the previous $n-1$ words. Assumes Markov property (limited context).

  • Unigram: $$\displaystyle P(w_i) $$

  • Bigram: $$\displaystyle P(w_i | w_{i-1}) $$

  • Trigram: $$\displaystyle P(w_i | w_{i-2}, w_{i-1}) $$

• Probability Calculation (Bigram):

$$P(w_1, w_2, ..., w_n) = \prod_{i=1}^{n} P(w_i | w_{i-1})$$

where $$\displaystyle P(w_i | w_{i-1}) = \frac{C(w_{i-1}, w_i)}{C(w_{i-1})} $$ (Maximum Likelihood Estimation).

• Training: Count n-grams in a training corpus to estimate probabilities.

Smoothing Techniques

• Necessity: To handle zero-probability n-grams (not seen in training) which would make entire sentence probability zero.

• Laplace (Add-One) Smoothing:

$$P_{Lap}(w_i | w_{i-1}) = \frac{C(w_{i-1}, w_i) + 1}{C(w_{i-1}) + V}$$

where $V$ is the vocabulary size. Adds 1 to all counts.

• Other Methods:

  • Good-Turing: Reallocates probability mass from seen to unseen events based on frequency of frequencies.

  • Kneser-Ney: A sophisticated method that uses discounted counts and a backoff model. Particularly effective for higher-order n-grams.

[!TIP] Exam Focus: Be ready to apply Laplace smoothing to a small example and compute a probability.

Evaluation of Language Models: Perplexity

• Definition: Perplexity is the exponential of the average negative log-likelihood per word. It measures how "surprised" the model is by the test data.

• Calculation for a test sentence of $N$ words:

$$PP(W) = \sqrt[N]{\frac{1}{P(W)}} = \exp\left(-\frac{1}{N} \sum_{i=1}^{N} \log P(w_i | \text{context})\right)$$

• Interpretation: Lower perplexity = better model. It's equivalent to the geometric mean of inverse probabilities.

Grammarians' Language Model

• Key Components: A formal grammar (e.g., Context-Free Grammar) that defines syntactic rules of a language.

• Functioning: Assigns a probability to a sentence by summing the probabilities of all possible parse trees that generate it. It combines syntactic structure with probabilistic scoring.

• Role: Provides a linguistically plausible, structured alternative to flat n-gram models, capturing long-range dependencies.

IV. PART-OF-SPEECH (POS) TAGGING

Rule-Based Tagging

• Principle: Uses a set of hand-crafted linguistic rules (e.g., "words ending in -ly are likely adverbs") and a dictionary of possible tags for each word.

• Implementation: Apply rules sequentially to disambiguate. Often uses a morphological analyzer.

• Limitation: Labor-intensive, domain-specific, and brittle to exceptions.

Transformation-Based Tagging (Brill Tagger)

• Mechanism:

  1. Start with an initial tagging (e.g., assign most frequent tag to each word).

  2. Learn transformation rules from a tagged corpus: IF (condition) THEN change tag X to Y.

  3. Apply learned rules in order of decreasing accuracy to the initial tagging.

• Contribution: Achieves high accuracy with a small set of human-readable rules, combining the transparency of rule-based systems with the data-driven nature of ML.

Probabilistic Approaches: Hidden Markov Models (HMM)

• Components for POS Tagging:

  • States: POS tags (hidden).

  • Observations: Words in the sentence (observed).

  • Transition Probabilities: $$\displaystyle a_{ij} = P(tag_j | tag_i) $$ – probability of moving from tag $i$ to tag $j$.

  • Emission Probabilities: $$\displaystyle b_j(o) = P(word_o | tag_j) $$ – probability of seeing word $o$ given tag $j$.

• Decoding: Viterbi Algorithm

  • Finds the single most likely sequence of hidden states (tags) for the observed word sequence.

  • Dynamic Programming: Uses backpointers to store the best path to each state at each time step.

  • Recurrence: $$\displaystyle \delta_t(j) = \max_{i} [\delta_{t-1}(i) \cdot a_{ij}] \cdot b_j(w_t) $$

  • Backtracking after filling the trellis yields the optimal tag sequence.

[!TIP] Exam Focus: Draw and explain the Viterbi trellis for a small example sentence. Know the difference between generative (HMM) and discriminative (e.g., CRF) models.

V. SYNTAX & PARSING

Formal Grammars

• Context-Free Grammars (CFGs):

  • Components: Set of terminals (words), non-terminals (syntactic categories like S, NP, VP), productions (rules), and a start symbol (S).

  • How it Captures Structure: Defines constituency – how words group into hierarchical phrases (e.g., S -> NP VP). Generates parse trees.

• Probabilistic Context-Free Grammars (PCFG):

  • Assigns a probability $$\displaystyle P(\alpha \rightarrow \beta) $$ to each CFG rule $$\displaystyle \alpha \rightarrow \beta $$.

  • Probability of a parse tree $T$: $$\displaystyle P(T) = \prod_{r \in \text{rules}(T)} P(r) $$.

  • Enables ranking of ambiguous parses.

Syntactic Parsing

• Process: Convert a flat sentence into a structured parse tree representing its syntactic composition.

• Types:

  • Constituency Parsing: Builds phrase structure trees (CFG-style). Outputs nested brackets: [S [NP ...] [VP ...]].

  • Dependency Parsing: Models head-dependent relationships between words. Outputs a directed graph where each word (except the root) has exactly one head.

Dependency Grammar

• Principles: Syntax is about asymmetric binary relationships (head → dependent). The head determines the syntactic category of the phrase.

• Representation: A dependency tree where edges are labeled with grammatical relations (e.g., nsubj, dobj, amod).

• Example: "She eats apples" → eats (root) → She (nsubj), apples (dobj).

Parsing Algorithms

• Probabilistic CYK (Cocke-Kasami-Younger):

  1. Input: Sentence, PCFG in Chomsky Normal Form (CNF: $$\displaystyle A \rightarrow B C $$ or $$\displaystyle A \rightarrow a $$).

  2. Dynamic Programming Table: Fill a triangular table $$\displaystyle P_{i,j}(A) $$ = probability that non-terminal $A$ spans words $i$ to $j$.

  3. Recurrence: For span length $l$, split at $s$:

$$P_{i,j}(A) = \max_{A \rightarrow B C} \left[ P_{i,s}(B) \cdot P_{s+1,j}(C) \cdot P(A \rightarrow B C) \right]$$

4.  **Output**: The parse tree with the highest probability for the start symbol spanning the whole sentence.

Parse Tree Ambiguity

• Types:

  • Structural/Attachment Ambiguity: Where a phrase attaches (e.g., "I saw the man with the telescope" – PP modifies "saw" or "man"?).

  • Lexical Ambiguity: A word has multiple POS tags (e.g., "can" as modal verb or noun).

• Resolution: Parser must choose the most plausible tree, often using probabilities from a PCFG or more complex models.

Treebanks

• Construction Process:

  1. Annotation: Human linguists manually parse sentences (constituency or dependency) following a specific annotation scheme (e.g., Penn Treebank, Universal Dependencies).

  2. Corpus Development: Annotate a large, representative corpus of text.

• Critical Role:

  • Training: Provide gold-standard data to estimate probabilities for PCFGs and train statistical parsers (HMM, PCFG, neural).

  • Assessment: Standard test sets (e.g., Wall Street Journal section of Penn Treebank) allow objective comparison of parser performance (using metrics like F1-score on labeled constituents/dependencies).

VI. SEMANTICS & MEANING REPRESENTATION

Word Sense Disambiguation (WSD)

• Goal: Determine the intended sense of an ambiguous word in context.

• Methods:

  • Supervised Methods: Treat as a classification task. Train a classifier (e.g., SVM, neural net) on sense-tagged corpora using contextual features (surrounding words, POS).

  • Dictionary-Based Methods: Use sense definitions from a machine-readable dictionary (e.g., WordNet). Match definition words to context (e.g., Lesk algorithm).

  • Thesaurus-Based Methods: Use synonym sets (synsets) from a thesaurus like WordNet. Select the sense whose synonyms are most prevalent in the local context.

Compositional Semantics

• Principle: The meaning of a complex expression is a function of the meanings of its parts and the rules used to combine them.

• Contribution: Provides a systematic way to build logical forms (e.g., in First-Order Logic) from syntactic parse trees. For example, combining the meanings of "every" and "student" yields a quantified expression $$\displaystyle \forall x (student(x) \rightarrow ...) $$.

First-Order Logic (FOL) in NLP

• Basic Syntax: Uses objects, predicates (relations/functions), variables, logical connectives ($$\displaystyle \land, \lor, \neg, \rightarrow $$), and quantifiers ($\forall, \exists$).

• Use for Representing Meaning: Provides a precise, unambiguous formal language to represent propositions and relationships extracted from text. Serves as an intermediate representation for tasks like question answering and inference.

  • Example: "Every student reads a book" → $$\displaystyle \forall x (student(x) \rightarrow \exists y (book(y) \land reads(x,y))) $$.

Quantifiers (in Logical Form)

• Explanation: Operators that specify the quantity of objects satisfying a predicate.

  • Universal Quantifier ($\forall$): "For all". $\forall x P(x)$ means $P(x)$ is true for every $x$ in the domain.

  • Existential Quantifier ($\exists$): "There exists". $\exists x P(x)$ means there is at least one $x$ for which $P(x)$ is true.

• Scope: The part of the formula to which the quantifier applies. Ambiguity in scope leads to different meanings (e.g., "Every student reads a book" vs. "There is a book that every student reads").

VII. ADVANCED TOPICS & KEY APPLICATIONS

Speech Recognition (End-to-End Overview)

1. Acoustic Signal Processing: Convert analog audio to digital, extract features (e.g., MFCCs).

2. Acoustic Model: Maps acoustic features to phonemes or subword units (often using HMMs or DNNs).

3. Language Model: Provides word-level probabilities (e.g., n-grams, neural LMs) to resolve acoustic ambiguities.

4. Decoder: Searches for the most likely word sequence given the acoustic and language model scores (e.g., using Viterbi or beam search).

• How NLP Enhances: Modern systems use deep neural network language models (RNNs, Transformers) trained on vast text corpora, dramatically improving accuracy by providing rich contextual understanding.

Machine Translation: Transfer Model

• Three Phases:

  1. Analysis: Parse the source language sentence into a source-language syntactic/semantic representation.

  2. Transfer: Transform the source representation into a target-language representation. This is the core, often involving rules for structural divergence.

  3. Generation: Generate the target language sentence from the target representation using a target-language grammar.

• Limitation: Requires deep linguistic analysis for both languages and a complex transfer component. Largely superseded by statistical (SMT) and neural (NMT) models.

Finite-State Automata (FSA)

• Role in NLP: Used for lexical analysis (tokenization, morphological analysis) and pattern matching.

  • Finite-State Acceptors (FSA): Recognize strings (e.g., spell-checker dictionary lookup).

  • Finite-State Transducers (FST): Map strings to strings (e.g., morphological analyzer: "running" → "run" + "VBG").

• Advantage: Extremely efficient (linear time) for the tasks they can model.

Minimum Edit Distance Algorithm

• Definition: The minimum number of operations (insert, delete, substitute) required to transform one string into another.

• Dynamic Programming Solution:

  Let $D[i,j]$ be the edit distance between the first $i$ chars of string $s$ and first $j$ chars of string $t$.

  Recurrence:

$$ D[i,j] = \min \begin{cases} D[i-1, j] + 1 & \text{(deletion)} \\ D[i, j-1] + 1 & \text{(insertion)} \\ D[i-1, j-1] + \text{cost} & \text{(substitution, cost=0 if chars match)} \end{cases} $$

**Base Cases**: $$\displaystyle D[0,j]=j $$ (j insertions), $$\displaystyle D[i,0]=i $$ (i deletions).

• Applications: Spelling correction (find closest dictionary word), string alignment (e.g., in computational biology, machine translation evaluation - BLEU score uses n-gram precision based on edit distance).

VIII. COMMERCIAL & PRACTICAL APPLICATIONS OF NLP

Enhancing User Experience

• In Word Processors:

  • Grammar & Style Checking: Rule-based or ML-based detection of errors (subject-verb agreement, tense).

  • Smart Features: Autocomplete, text prediction, readability scores.

• General Commercial Uses:

  • Search Engines: Query understanding, semantic search, snippet generation.

  • Chatbots & Virtual Assistants: Intent recognition, dialogue management.

  • Sentiment Analysis: Brand monitoring, market research.

  • Machine Translation: Real-time translation tools (Google Translate).

  • Text Summarization: News digests, document abstracts.

Lexical Resources

• Dictionaries:

  • Role: Provide definitions, pronunciations, part-of-speech, and usage examples.

  • Use in NLP: For POS tagging (lookup), spelling correction (valid word check), word sense disambiguation (dictionary-based methods).

• Thesauri:

  • Role: Provide synonym and antonym sets (synsets) and sometimes hierarchical relations (hypernymy, hyponymy).

  • Use in NLP: For query expansion in search, text similarity (using synonym overlap), WSD (thesaurus-based methods), and as a key component of WordNet.

[!TIP] Exam Focus: For applications, link the NLP technique to the commercial use (e.g., "Sentiment Analysis uses text classification models to determine the polarity of user reviews for brand monitoring"). For lexical resources, contrast dictionaries (definitions) vs. thesauri (synonymy).