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

UNIT 2: NATURAL LANGUAGE PROCESSING (NLP)

I. Introduction to NLP

• Definition: NLP is a field of AI focused on enabling computers to understand, interpret, manipulate, and generate human language.

• Key Challenges:

  • Ambiguity: Words/sentences have multiple meanings (lexical, syntactic, pragmatic).

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

  • Implicit Knowledge: Requires vast world knowledge and common sense.

  • Non-Standard Text: Handling slang, typos, and informal language.

  • Sparsity: Rare word combinations in large vocabularies.

• Basic Text Processing:

  • Tokenization: Segmenting text into words, phrases, or symbols (tokens). Challenging for languages without spaces (e.g., Chinese) or with contractions (e.g., "don't").

  • Normalization: Converting text to a standard form (e.g., lowercasing, removing punctuation, stemming/lemmatization).

• Role of Dictionaries and Thesauri:

  • Dictionaries: Provide definitions, part-of-speech (POS), pronunciation. Used for Word Sense Disambiguation (WSD).

  • Thesauri: Provide synonym sets (synsets) and hierarchical relations (hypernymy/hyponymy). Used for WSD and semantic similarity.

• First-Order Logic (FOL) in NLP:

  • Used for semantic representation and logical inference.

  • Represents entities, properties, and relations (e.g., Loves(John, Mary)).

  • Allows quantification (∀, ∃) to capture meaning of sentences like "Every student read a book."

[!TIP] Exam often asks for challenges and basic preprocessing steps. Be ready to give examples for ambiguity and tokenization issues.

II. Text Preprocessing and Spelling Correction

• Regular Expressions (Regex):

  • Patterns for matching/ extracting text.

  • Common Patterns:

    • \w+ : Word characters

    • \d : Digit

    • [A-Z][a-z]+ : Capitalized word

    • \b\w+ing\b : Words ending with "ing"

    • ^ : Start of string, $ : End of string

  • Applications: Tokenization, extracting email/phone numbers, pattern-based text cleaning.

  • Example: r'\b[A-Z][a-z]*\b' matches capitalized words (potential proper nouns).

• Spelling Error Detection & Correction:

  • Challenges: Non-word errors (e.g., "teh") vs. real-word errors (e.g., "their" vs. "there"); context dependence.

  • Approaches:

    1. Detect: Use dictionary lookup (non-word errors).

    2. Correct: Generate candidate corrections (via edit distance) and rank them (using language model probability or context).

• Minimum Edit Distance (Levenshtein Distance):

  • Minimum number of insertions, deletions, substitutions to transform string A into B.

  • Dynamic Programming Algorithm:

    Let D[i,j] = distance between first i chars of source and first j chars of target.

$$ 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)} \end{cases} $$

    where `cost = 0` if chars match, else `1`.

*   **Backtracking** from `D[m,n]` gives the optimal edit sequence.

[!TIP] Always illustrate Minimum Edit Distance with a small table (e.g., "kitten" → "sitting"). Exam loves this algorithmic derivation.

III. Statistical Language Modeling

• N-gram Models:

  • Predict next word based on previous (n-1) words.

  • Unigram: P(w_i) (independent of context).

  • Bigram: P(w_i | w_{i-1}) = \frac{count(w_{i-1}, w_i)}{count(w_{i-1})}.

  • Trigram/Higher: Use more context but face data sparsity.

  • Probability Calculation: Chain rule + Markov assumption.

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

• Smoothing Techniques:

  • Necessity: Assign non-zero probability to unseen N-grams.

  • Laplace (Add-One) Smoothing:

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

    where `V` = vocabulary size.

*   **Other Methods**: Good-Turing, Kneser-Ney, Backoff, Interpolation.

• Perplexity:

  • Measures how well a probability model predicts a test set.

  • Definition: Exponential of average negative log-likelihood per word.

$$\text{Perplexity}(W) = P(w_1, w_2, ..., w_m)^{-\frac{1}{m}}$$

*   Lower perplexity = better model.

• Grammarians Language Model (Grammar-based LM):

  • Uses Context-Free Grammar (CFG) rules to assign probabilities to parse trees.

  • Captures syntactic structure, unlike simple N-grams.

  • Probability of a sentence = sum of probabilities of all its possible parse trees.

[!TIP] Distinguish smoothing (handles unseen N-grams) from backoff/interpolation (using lower-order models). Know the Laplace formula by heart.

IV. Part-of-Speech Tagging

• Rule-Based Tagging:

  • Uses hand-crafted rules (e.g., "words ending in -ly are likely adverbs").

  • Relies on morphological clues and dictionary lookups.

  • Limitation: Rules are brittle and hard to maintain.

• Transformation-Based Tagging (Brill Tagger):

  • Learning: Start with a baseline (e.g., most frequent tag), then apply ordered transformation rules (e.g., "change tag from NN to VB if previous word is 'to'").

  • Rules are learned from annotated corpus using error-driven learning.

  • Advantage: Rules are linguistically interpretable, often rivaling statistical models.

• Hidden Markov Models (HMMs) for Tagging:

  • States = POS tags, Observations = words.

  • Components:

    1. Transition Probabilities: P(t_i | t_{i-1}) (tag sequence).

    2. Emission Probabilities: P(w_i | t_i) (word given tag).

    3. Initial State Probabilities.

  • Decoding: Use Viterbi Algorithm to find most likely tag sequence for a sentence.

$$v_t(j) = \max_{i} [v_{t-1}(i) \cdot a_{ij}] \cdot b_j(o_t)$$

    where `a_ij` = transition, `b_j` = emission.

[!TIP] Viterbi algorithm is crucial. Be able to trace it on a small example (2-3 words, 2-3 tags). Contrast rule-based (hand-crafted) vs. transformation-based (learned rules).

V. Syntactic Analysis

• Context-Free Grammars (CFGs):

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

  • Captures hierarchical phrase structure (constituency).

  • Limitation: Cannot handle long-distance dependencies (e.g., agreement, subcategorization).

• Dependency Grammar:

  • Represents syntax as directed dependencies between words (head-dependent relations).

  • Each word has exactly one head (except root).

  • Example: In "She eats apples", "eats" is head of "She" (nsubj) and "apples" (dobj).

  • Advantage: More directly models predicate-argument structure; useful for languages with free word order.

• Syntactic Parsing:

  • Process: Assigning a syntactic structure (parse tree) to a sentence.

  • Types:

    1. Constituency Parsing: Builds tree based on CFG (phrases as nodes).

    2. Dependency Parsing: Builds dependency tree (words as nodes).

  • Output: Parse tree showing grammatical relations.

• Probabilistic Parsing & PCFGs:

  • Probabilistic CFG (PCFG): Assigns probability to each CFG production.

$$P(\text{tree}) = \prod_{\text{productions}} P(\text{rhs} | \text{lhs})$$

*   **Probabilistic CYK (Cocke-Kasami-Younger)**:

    1.  Convert CFG to **Chomsky Normal Form (CNF)**.

    2.  Fill triangular table `C[i,j,X]` = probability that non-terminal `X` spans words `i` to `j`.

    3.  Use dynamic programming: `C[i,j,X] = max_{i≤k<j} [P(X → Y Z) * C[i,k,Y] * C[k+1,j,Z]]`.

    4.  Final answer = `C[1,n,S]` (probability of start symbol spanning full sentence).

• Treebanks:

  • Construction: Manually annotate large corpora with syntactic parse trees (constituency or dependency).

  • Role:

    1. Development: Train probabilistic parsers (PCFGs, dependency parsers).

    2. Evaluation: Standard test sets (e.g., Penn Treebank) for comparing parser accuracy (precision, recall, F1-score).

• Ambiguity in Parse Trees:

  • A sentence can have multiple valid parse trees.

  • Example: "I saw the man with the telescope."

    • Interpretation 1: I used a telescope to see the man. (Saw(I, man(with telescope)))

    • Interpretation 2: I saw a man who had a telescope. (Saw(I, man) with telescope).

  • Resolution: Requires semantic knowledge, context, or statistical disambiguation (using PCFG probabilities).

[!TIP] Know the difference between constituency (phrases) and dependency (word-to-word). For CYK, remember the CNF requirement and the dynamic programming recurrence. Treebanks are gold-standard annotated corpora.

VI. Semantic Analysis

• Word Sense Disambiguation (WSD):

  • Task: Determine the correct meaning (sense) of a word in context.

  • Methods:

    • Supervised: Train a classifier (e.g., using Naïve Bayes, SVM) on sense-annotated data. Features: surrounding words, POS, collocations.

    • Dictionary-Based (Knowledge-Based): Use WordNet or other lexicons. Measure overlap between dictionary definition of each sense and the context (e.g., Lesk algorithm).

    • Thesaurus-Based: Use synsets from thesaurus. Assign sense whose synonyms are most frequent in the local context.

• Compositional Semantics:

  • Principle: Meaning of a complex expression is determined by meanings of its parts and the rules used to combine them.

  • Example: "Blue bird" → Color(blue) ∧ Bird(bird) ∧ HasColor(bird, blue).

  • Formalisms: First-Order Logic (FOL), ** λ-calculus** (for function words like verbs).

  • Contribution: Enables systematic interpretation of novel sentences.

• Quantifiers in Semantic Interpretation:

  • Quantifiers: "every", "some", "no", "most".

  • Scope Ambiguity: "Every student read a book" can mean:

    1. ∀x (Student(x) → ∃y (Book(y) ∧ Read(x,y))) (each student read some book, possibly different).

    2. ∃y (Book(y) ∧ ∀x (Student(x) → Read(x,y))) (there is one specific book all students read).

  • Resolution: Requires syntactic structure (c-command relations) and pragmatic context.

[!TIP] WSD methods are frequently asked. Be precise: Supervised uses ML on labeled data; Dictionary-based uses definitions (Lesk); Thesaurus-based uses synonym sets. For quantifiers, always draw the two possible FOL formulas.

VII. NLP Applications

• Speech Recognition:

  • Process: Audio → Feature extraction (MFCCs) → Acoustic model (HMM/DNN) → Language model (N-gram/RNN) → Decoding (find best word sequence).

  • NLP Enhancement: Language model rescoring (re-ranks ASR hypotheses), grammar constraints, handling homophones ("write" vs. "right").

• Machine Translation (MT) - Transfer Model:

  • Phases:

    1. Analysis: Parse source sentence (syntactic/semantic).

    2. Transfer: Map source representation to target representation (using bilingual dictionary + transfer rules).

    3. Generation: Generate target language sentence from transferred representation.

  • Limitation: Requires deep linguistic analysis for each language pair.

• NLP in Word Processors & Commercial Apps:

  • Spell & Grammar Checkers (using dictionaries, rules, statistical LM).

  • Auto-complete/Smart Compose (N-gram or neural LMs).

  • Style Suggestions (readability scores, passive voice detection).

  • Search & Indexing (tokenization, stemming, synonym expansion).

  • Chatbots & Virtual Assistants (intent recognition, dialogue management).

  • Sentiment Analysis: Classify opinion polarity (positive/negative/neutral) from text (using lexicon-based or ML methods).

[!TIP] For MT, know the three phases of Transfer Model. For commercial apps, list 3-4 concrete examples with the NLP technique used (e.g., "Auto-complete uses N-gram language models").

VIII. Additional Models and Techniques

• Finite-State Automata (FSA):

  • Definition: Abstract machine with states and transitions, processing input string symbol by symbol.

  • Types:

    • Finite-State Acceptor: Accepts/rejects strings (e.g., regex pattern matching).

    • Finite-State Transducer (FST): Maps input string to output string (e.g., morphological analysis: "running" → "run+V+ing").

  • Role in NLP: Efficient for morphological analysis, text normalization, simple pattern matching. Forms basis for lexicon processing.

[!NOTE] Evaluation Metrics for LMs (Perplexity) are covered in Section III. Word Sense is covered in Section VI.