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

UNIT 3: NATURAL LANGUAGE PROCESSING

I. Introduction to NLP

• Definition & Scope: NLP is a field of AI focused on enabling computers to understand, interpret, manipulate, and generate human language. Its scope includes tasks like translation, sentiment analysis, chatbots, and text summarization.

• Major Challenges:

  1. Ambiguity: Words/sentences have multiple meanings (e.g., "I saw the man with the telescope").

  2. Variability: Many ways to express the same meaning (synonyms, paraphrasing).

  3. Implicit Knowledge: Understanding requires common sense and world knowledge not stated in text.

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

  5. Sparse Data: Infrequent word combinations in large corpora.

  6. Context Dependence: Meaning heavily relies on surrounding words and discourse.

[!TIP] Exam questions often ask for challenges. Always relate them to specific NLP tasks (e.g., ambiguity in POS tagging, variability in machine translation).

II. Text Preprocessing and Basic Techniques

Tokenization

• Definition: The process of breaking a text string into smaller units (tokens), typically words, numbers, or punctuation.

• Example: "Hello, world!" → ["Hello", ",", "world", "!"]

• Challenges: Handling contractions (don't → ["do", "n't"] or ["don't"]), punctuation in numbers (3.14), and language-specific rules (e.g., Chinese word segmentation).

Regular Expressions (Regex)

• Role: Powerful tool for pattern matching and text manipulation. Used for tokenization, extracting specific patterns (emails, dates), and simple preprocessing.

• Basic Patterns & Examples:

  • . : Matches any single character (except newline). c.t matches cat, cot, c3t.

  • * : Matches 0 or more repetitions of preceding element. ab*c matches ac, abc, abbc.

  • + : Matches 1 or more repetitions. ab+c matches abc, abbc, not ac.

  • ? : Matches 0 or 1 repetition. colou?r matches color and colour.

  • [] : Matches any one character in brackets. [aeiou] matches any vowel.

  • | : OR operator. cat|dog matches cat or dog.

  • ^ : Start of string/line. ^Hello matches Hello at start.

  • $` : End of string/line. `world$ matches world at end.

  • \d : Matches a digit. \d+ matches one or more digits.

  • \w : Matches a word character (alphanumeric + underscore).

  • \s : Matches a whitespace character.

• Example Use: Extracting hashtags: #(\w+) captures the word after #.

Finite-State Automata (FSA)

• A computational model with states and transitions, used in NLP for pattern recognition (e.g., simple lexical analysis, morphological parsing). An FSA accepts or rejects a string based on whether it follows a defined path from start to final state.

• Types: Deterministic (DFSA) vs. Non-deterministic (NFSA).

Spelling Error Detection and Correction

• Challenges:

  1. Non-Word Errors: Result in strings not in dictionary (e.g., teh).

  2. Real-Word Errors: Result in a valid dictionary word but incorrect in context (e.g., I went to the sea instead of I went to the see). Much harder.

  3. Context Dependency: Correct choice depends on surrounding words.

  4. Noisy Channel Model: Assumes observed error w was intended to be some correct word c. Finds argmax_c P(c|w) ∝ P(w|c) * P(c).

Minimum Edit Distance Algorithm (Levenshtein Distance)

• Definition: The minimum number of single-character edit operations (insertion, deletion, substitution) required to change one string into another.

• Algorithm (Dynamic Programming):

  Let D[i,j] be distance between first i chars of string s1[1..i] and first j chars of s2[1..j].

$$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 `s1[i] == s2[j]`, else `cost = 1`.

• Initialization: D[0,j] = j, D[i,0] = i.

• Result: D[m,n] is the minimum edit distance for full strings of length m and n.

[!TIP] Be prepared to trace the algorithm for a small example (e.g., "intention" vs "execution"). The backtrace pointer matrix is key for finding the actual edit sequence.

III. Language Modeling

N-gram Models

• Definition: A probabilistic model that predicts the next word based on the previous (n-1) words. Assumes Markov property (word depends only on previous n-1 words).

• Bigram Probability Calculation:

$$P(w_i | w_{i-1}) = \frac{count(w_{i-1}, w_i)}{count(w_{i-1})}$$

*Example*: `P(eat | I) = count("I eat") / count("I")`.

• Evaluation Metric: Perplexity

  • Measures how well a probability model predicts a sample. Lower perplexity = better model.

  • For a test set of N words:

$$\text{Perplexity}(W) = \left( \prod_{i=1}^{N} \frac{1}{P(w_i | w_{i-n+1}^{i-1})} \right)^{1/N}$$

*   Often computed using log probabilities to avoid underflow.

Smoothing Techniques

• Need (Zero Probability Problem): In a corpus, many possible n-grams never occur. Assigning them probability 0 is unrealistic and harms model performance. Smoothing redistributes some probability mass to unseen events.

• Laplace Smoothing (Add-One Smoothing):

  • Adds 1 to every count, including unseen ones.

  • For unigram:

$$P_{\text{Laplace}}(w) = \frac{count(w) + 1}{N + V}$$

  where `N` = total words, `V` = vocabulary size.

*   For bigram: 

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

*   **Criticism**: Overestimates probability of unseen events; not optimal for large `V`.

Hidden Markov Models (HMM)

• Principles & Components:

  1. Hidden States: Represent underlying linguistic phenomena (e.g., POS tags).

  2. Observations: The actual visible words.

  3. Transition Probabilities: a_{ij} = P(state_j at t+1 | state_i at t).

  4. Emission Probabilities: b_j(o) = P(observation o | state_j).

  5. Initial State Probabilities: π_i = P(state_i at t=1).

• Key Problems:

  1. Evaluation: Given model λ and observation sequence O, find P(O|λ). Solved by Forward Algorithm.

  2. Decoding: Given O and λ, find most likely state sequence. Solved by Viterbi Algorithm.

  3. Learning: Given O, find λ that maximizes P(O|λ). Solved by Baum-Welch (EM).

• Applications in NLP: POS tagging, speech recognition, named entity recognition.

Grammarians Language Model

• Key Components:

  1. Lexicon: Mapping from words to their possible parts-of-speech (tags) with probabilities.

  2. Grammar Rules: Context-Free Grammar (CFG) rules with probabilities (like a PCFG).

• Functioning: Combines a probabilistic CFG with a lexicon. Computes the probability of a parse tree as the product of rule probabilities and word emission probabilities from tags. Used in statistical parsing.

IV. Part-of-Speech (POS) Tagging

• Rule-based Tagging: Uses hand-crafted linguistic rules (e.g., "words ending in -ly are likely adverbs"). Fast but brittle, low accuracy (~77%).

• Transformation-based Tagging (Brill's Tagger):

  • Process: Starts with a simple baseline (e.g., assign most frequent tag). Iteratively applies transformation rules (e.g., "change tag NN to VB if previous tag is TO") learned from training data to correct errors.

  • Advantage: Rules are human-readable, captures contextual patterns, accuracy ~96%.

• Statistical Tagging using HMM:

  • Model: States = POS tags, Observations = words.

  • Goal: Find most likely tag sequence T* for word sequence W: T* = argmax_T P(T|W) ∝ argmax_T P(W|T) * P(T).

  • Solved by Viterbi algorithm. Uses emission probabilities P(word|tag) and transition probabilities P(tag_i | tag_{i-1}).

V. Syntax and Parsing

Formal Grammars

• Context-Free Grammars (CFGs):

  • Key Components:

    • Terminals (T): The actual words/tokens in the language.

    • Non-Terminals (N): Syntactic categories (e.g., S, NP, VP).

    • Rules (R): Productions of form A → α where A ∈ N, α ∈ (N ∪ T)*.

    • Start Symbol (S): The root non-terminal (usually S for sentence).

  • Example:

    
    S → NP VP
    
    NP → Det N | "John"
    
    VP → V NP
    
    Det → "the" | "a"
    
    N → "man" | "ball"
    
    V → "saw" | "hit"
    
    

  • Captures hierarchical, recursive structure (e.g., S → NP VP → Det N V NP → the man saw a ball).

• Dependency Grammar:

  • Represents syntactic structure as directed dependencies between words (lexical items).

  • Each word (except root) has exactly one head (governor) and a dependency relation (e.g., nsubj, dobj, amod).

  • Example: In "John saw the ball", saw is root. John → nsubj(saw), ball → dobj(saw), the → det(ball).

  • Often represented as a tree with words as nodes.

• Probabilistic Context-Free Grammars (PCFGs):

  • Extends CFG by assigning a probability P(A → α) to each rule A → α.

  • Probability of a parse tree T is the product of probabilities of its rules: P(T) = ∏_{r∈T} P(r).

  • The probability of a string s is the sum of probabilities of all parse trees that generate s.

Parsing Techniques

• Syntactic Parsing Process: Given a sentence and a grammar, find its parse tree (constituency) or dependency structure.

• Parsing Algorithms:

  • CYK Algorithm (Cocke-Younger-Kasami):

    1. Input: CFG in Chomsky Normal Form (CNF: A → BC or A → a).

    2. Table: n x n triangular table P[i,j,X] = probability/non-zero flag that non-terminal X spans words from i to j.

    3. Fill:

       • Diagonal (i,i): For each word w_i, for each rule A → w_i, set P[i,i,A] = true.

       • Off-diagonal: For span (i,j) and split k (i ≤ k < j), if P[i,k,B] and P[k+1,j,C] are true and there's rule A → B C, then P[i,j,A] = true.

    4. Result: Parse exists if P[1,n,S] is true (for sentence of n words).

  • Probabilistic CYK: Same process, but stores probabilities and uses max over splits and rules: P[i,j,A] = max_{A→BC, k} [ P[i,k,B] * P[k+1,j,C] * P(A→BC) ]. Also stores backpointers to recover best tree.

• Ambiguity in Parse Trees:

  • Structural Ambiguity: A sentence has multiple valid parse trees.

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

    • Interpretation 1 (PP attachment to VP): [S [NP I] [VP [V saw] [NP [Det the] [N man]] [PP [P with] [NP [Det the] [N telescope]]]]] (I used the telescope to see).

    • Interpretation 2 (PP attachment to NP): [S [NP I] [VP [V saw] [NP [Det the] [N man] [PP [P with] [NP [Det the] [N telescope]]]]]] (The man had the telescope).

  • PCFGs/Probabilistic parsing can assign probabilities to disambiguate.

Treebanks

• Construction Process:

  1. Annotation: Human linguists manually parse a large corpus of sentences, creating tree structures (constituency like Penn Treebank or dependency like UD).

  2. Guidelines: Strict annotation manuals ensure consistency.

  3. Quality Control: Adjudication of disagreements.

• Role:

  • Development: Primary training data for statistical parsers (PCFGs, neural parsers). Provides frequencies of rules/structures.

  • Evaluation: Standard test sets (e.g., Wall Street Journal section of Penn Treebank) allow objective comparison of parser performance using metrics like Parseval (precision, recall, F1 on labeled constituents).

VI. Semantics and Word Sense

Word Sense Disambiguation (WSD)

• Definition: The task of determining which sense (meaning) of a word is used in a given sentence.

• Example: "Bank" could mean financial_institution or river_edge.

• Methods:

  • Supervised Methods:

    • Treat as a classification problem.

    • Features: Surrounding words (bag-of-words), POS tags, syntactic dependencies, collocations.

    • Models: Train classifiers (Naive Bayes, SVM, neural networks) on sense-annotated corpora (e.g., SemCor).

  • Dictionary-based Methods (Knowledge-Based):

    • Use semantic networks (e.g., WordNet) to measure relatedness between word senses and context.

    • Lesk Algorithm: Choose sense with maximum overlap between its dictionary definition/gloss and the context words.

  • Thesaurus-based Methods:

    • Similar to dictionary-based, but use thesaurus structure (synsets, hypernym/hyponym relations) to find the most plausible sense based on proximity to other disambiguated words in the context.

Dictionaries and Thesauri in NLP

• Dictionaries (e.g., WordNet): Provide senses, definitions (glosses), example sentences, and semantic relations (synonymy, antonymy, hypernymy, hyponymy, meronymy). Crucial for WSD, semantic similarity, and information retrieval.

• Thesauri: Primarily list synonyms and sometimes antonyms. Used for query expansion, text simplification, and as a resource for WSD.

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.

• Example: "John loves Mary". Meaning(loves) + Meaning(John) + Meaning(Mary) + syntactic structure (subject-predicate) → propositional meaning.

• Contribution: Allows systematic interpretation of novel sentences. Formalized using lambda calculus and first-order logic.

Quantifiers in Natural Language

• Words like all, some, no, most, every that specify quantity/scope.

• Example: "Every student read a book" has two readings:

  1. Surface Scope: ∀x (student(x) → ∃y (book(y) ∧ read(x,y))) (Each student read some book, possibly different).

  2. Inverse Scope: ∃y (book(y) ∧ ∀x (student(x) → read(x,y))) (There is one book that every student read).

• Challenge: Correct scope interpretation requires deep syntactic and semantic analysis.

First-Order Logic (FOL) in NLP

• A formal language for representing propositions, objects, and relations.

• Key Elements: Constants (john), variables (x), predicates (Read(john, book1)), quantifiers (∀, ∃), logical connectives (∧, ∨, →, ¬).

• Use in NLP: To represent the logical form of a sentence, enabling inference (e.g., from All men are mortal and Socrates is a man, infer Socrates is mortal). Used in semantic parsing and question answering.

Word Sense (Concept)

• A word sense is a distinct meaning a word can have, often listed in a dictionary as separate numbered definitions.

• Example: "Crane" has at least senses: bird, machine, person (who cranes neck).

• Granularity: Sense distinctions can be fine-grained (WordNet) or coarse-grained. WSD aims to assign the correct sense label from a predefined inventory.

VII. Applications of NLP

Speech Recognition

• How it Works:

  1. Acoustic Processing: Convert audio signal to feature vectors (e.g., MFCCs).

  2. Acoustic Model: (Often HMM/DNN) Maps acoustic features to phonemes or sub-word units.

  3. Language Model: (N-gram, neural LM) Assigns probabilities to word sequences.

  4. Decoder: Finds the most likely word sequence W* given acoustic input A: W* = argmax_W P(A|W) * P(W). This is the core search problem.

• Enhancement by NLP: NLP components (LM, pronunciation lexicon, syntactic/semantic constraints) dramatically reduce error rates by providing top-down, linguistic knowledge that constrains the vast search space of possible word sequences.

Machine Translation (MT)

• Transfer Model (Classic Rule-Based):

  1. Analysis: Parse source language sentence into an intermediate syntactic/semantic representation (e.g., dependency tree, logical form).

  2. Transfer: Map the source representation to a target language representation using bilingual dictionaries and transfer rules (e.g., reordering rules for SVO→SOV languages).

  3. Generation: Generate the final target language sentence from the transferred representation using a target language grammar and lexicon.

• Phases: Analysis → Transfer → Generation.

Commercial Applications (Improving User Experience)

• Search Engines: Query understanding, document ranking, snippet generation.

• Chatbots & Virtual Assistants: Intent recognition, dialogue management (e.g., Siri, Alexa).

• Sentiment Analysis: Monitor brand reputation, analyze product reviews.

• Content Recommendation: Understanding article/video content for personalized feeds.

• Customer Support: Automating ticket classification and routing.

• Social Media Monitoring: Trend detection, hate speech detection.

NLP in Word Processors

• Making Processors Smarter:

  • Grammar & Style Checking: Beyond spell-check, detects passive voice, complex sentences, clichés, plagiarism.

  • Smart Compose/Completion: Predicts and suggests next words/phrases (like Gmail).

  • Summarization: Auto-generates document abstracts.

  • Readability Scoring: Estimates grade level needed to understand text.

  • Translation: Integrated real-time translation (e.g., Word, Google Docs).

  • Accessibility: Text-to-speech, speech-to-text, describing images for visually impaired.

[!TIP] For application questions, link the NLP technique to the specific problem. E.g., "Sentiment Analysis uses lexicon-based methods or supervised classification (Naive Bayes, LSTM) on text features."