UNIT 4: NATURAL LANGUAGE PROCESSING - CORE TECHNIQUES & APPLICATIONS
A. FOUNDATIONS & PREPROCESSING
Introduction to NLP
-
Definition: NLP is a field of AI focused on enabling computers to understand, interpret, manipulate, and generate human language.
-
Need: To bridge the human-computer communication gap, automate text/speech analysis, and extract insights from vast unstructured text data.
-
Broad Application Classes:
-
Information Extraction & Retrieval (e.g., search engines).
-
Machine Translation.
-
Text Summarization & Question Answering.
-
Sentiment Analysis & Opinion Mining.
-
Speech Recognition & Synthesis.
-
-
Core Challenges:
-
Ambiguity (Lexical, Syntactic, Semantic).
-
Variability (Different ways to express same meaning).
-
Informativeness (Language is often imprecise, relies on context).
-
Non-standard Text (typos, slang, code-mixing in Indian languages).
-
Lack of Resources for many Indian languages (annotated corpora, tools).
-
[!TIP] Exam Focus: Be ready to list and explain at least 4-5 challenges with concrete examples (e.g., "I saw the man with the telescope" – syntactic ambiguity).
Text Preprocessing & Regular Expressions
-
Role of RegEx: Pattern matching for tokenization, extraction, cleaning, and normalization.
-
Basic Patterns:
-
\w+: Word characters. -
\s+: Whitespace. -
[A-Z][a-z]+: Capitalized words (proper nouns). -
\d+: Digits. -
^/$: Start/end of string.
-
-
Tokenization vs. Word Segmentation:
-
Tokenization (Space-delimited languages like English): Splitting text into words/punctuation using spaces/RegEx.
-
Word Segmentation (Non-space languages like Chinese, Thai, some Indian scripts): Complex task of identifying word boundaries within a continuous character stream.
-
-
Spelling Error Correction Challenges:
-
Non-word errors: "teh" → "the" (dictionary lookup).
-
Real-word errors: "their" vs. "there" (requires context, WSD).
-
Context dependency: Need n-gram or syntactic/semantic models.
-
Indian Language Specific: Phonetic similarity in Devanagari/other scripts, code-mixing (Hinglish).
-
Corpora & Morphology
-
Corpora:
-
Definition: Structured collections of written/spoken text used for linguistic analysis and NLP model training.
-
Types: Monolingual, Parallel (for MT), Annotated (POS-tagged, parsed, named-entity).
-
Significance: Provide empirical data for statistical models, enable study of language patterns, benchmark for system evaluation.
-
-
Morphology:
-
Study of word formation (stems, affixes, inflection, derivation).
-
Relation to Finite State Automata (FSA): Morphological analyzers/generators for concatenative morphology (like English) are efficiently implemented using FSA. An FSA can recognize all valid word forms of a lexicon by traversing states representing morphemes.
-
-
Morphology of Indian Languages:
-
Agglutinative/Suffixing (e.g., Telugu, Tamil, Kannada, Malayalam).
-
Inflectional richness (case, gender, number, tense markers attached to stems).
-
Sandhi/Samasa (phonological/morphological compounding rules at word boundaries).
-
Challenges: Complex suffix chains, non-concatenative processes, script variations.
-
-
Phonological Rules & Minimum Edit Distance:
-
Phonological Rules: Describe sound changes in context (e.g., plural /s/ → /z/ after voiced sounds). Useful for modeling pronunciation variations in speech recognition.
-
Minimum Edit Distance (Levenshtein Distance):
-
Minimum number of insertions, deletions, substitutions to transform string A into B.
-
Dynamic Programming Algorithm:
-
-
$$D[i,j] = \min \begin{cases} D[i-1,j] + 1 \quad \text{(deletion)} \\ D[i,j-1] + 1 \quad \text{(insertion)} \\ D[i-1,j-1] + \text{cost} \quad \text{(substitution)} \end{cases}$$
where $$\displaystyle \text{cost}=0 $$ if $$\displaystyle A[i]=B[j] $$, else $1$.
* **Applications**: Spelling correction, string similarity, bio-sequence alignment.
[!TIP] Common Pitfall: Confusing Morphology (study of words) with Morphological Processing (using FSA to analyze/generate words). Be clear on the link.
B. LANGUAGE MODELING
N-gram Models
-
Concept: Probabilistic model that predicts next word based on previous n-1 words.
-
Bigram: $$\displaystyle P(w_i | w_{i-1}) = \frac{C(w_{i-1}, w_i)}{C(w_{i-1})} $$
-
Trigram: $$\displaystyle P(w_i | w_{i-2}, w_{i-1}) = \frac{C(w_{i-2}, w_{i-1}, w_i)}{C(w_{i-2}, w_{i-1})} $$
-
-
Perplexity: Evaluation metric; inverse of geometric average probability of test set.
$$PP(W) = P(w_1 w_2 ... w_N)^{-\frac{1}{N}} = \sqrt[N]{\frac{1}{P(w_1 w_2 ... w_N)}}$$
Lower perplexity = better model.
-
Smoothing:
-
Necessity: To assign non-zero probability to unseen n-grams (zero-probability problem).
-
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$ = vocabulary size.
\boxed{P_{Lap}(w_i | w_{i-1}) = \frac{C(w_{i-1}, w_i) + 1}{C(w_{i-1}) + V}}
* Other methods: Good-Turing, Kneser-Ney, Witten-Bell.
Probabilistic Models for Tagging & Sequence Labeling
-
Hidden Markov Models (HMMs) for POS Tagging:
-
Components: States (POS tags), Observations (words), Transition probs $$\displaystyle A_{ij}=P(t_i|t_{i-1}) $$, Emission probs $$\displaystyle B_i(o)=P(w|t) $$.
-
Viterbi Algorithm: Decodes most likely tag sequence for a given word sequence.
-
Training: Supervised (from tagged corpus) using Maximum Likelihood Estimation.
-
-
Maximum Entropy Model (MaxEnt):
-
Discriminative model. Uses features (e.g., word itself, suffixes, context words) to estimate $P(tag|features)$.
-
Maximizes entropy subject to constraints from training data.
-
Often outperforms HMMs by incorporating diverse, overlapping features.
-
-
Transformation-Based Tagging (TBL):
-
Brill's Tagger: Rule-based, learns transformation rules from an initial state (e.g., most frequent tag) to correct errors.
-
Process: Start with baseline tags → apply ordered rules (e.g., "Change tag NN to VB if previous tag is TO") to maximize score.
-
Advantage: Produces human-interpretable rules, high accuracy.
-
-
Rule-Based POS Tagging Principles:
-
Uses hand-crafted linguistic rules (morphology, context) and lexicon.
-
Example: If word ends in "-ing" and preceded by auxiliary, tag as VERB.
-
Limitation: Labor-intensive, poor coverage, cannot handle ambiguity/novel words well.
-
[!TIP] Exam Comparison: Be prepared to differentiate HMM (generative) vs. MaxEnt (discriminative) and explain why TBL is effective (learns error-correcting rules from data).
C. SYNTAX & PARSING
Formal Grammars
-
Context-Free Grammars (CFGs):
-
Components: $$\displaystyle G = (N, \Sigma, R, S) $$
-
$N$: Non-terminal symbols (syntactic categories: S, NP, VP).
-
$\Sigma$: Terminal symbols (words).
-
$R$: Production rules (e.g., $$\displaystyle S \rightarrow NP\ VP $$).
-
$S$: Start symbol.
-
-
Captures hierarchical, recursive structure (e.g., $$\displaystyle NP \rightarrow Det\ N $$).
-
Limitation: Cannot handle long-distance dependencies (e.g., agreement, subcategorization).
-
-
Probabilistic CFGs (PCFGs):
-
Extends CFG by assigning probabilities to rules.
-
$$\displaystyle P(A \rightarrow \beta) $$ where $$\displaystyle \sum_{\beta} P(A \rightarrow \beta) = 1 $$ for each $A$.
-
Parse probability: Product of rule probabilities in the tree.
-
Enables disambiguation of ambiguous parses.
-
-
Dependency Grammar:
-
Represents syntactic structure as directed links (dependencies) between words (tokens), not phrases.
-
Head of a phrase governs its dependents.
-
Example: In "She eats apples", "eats" is head, "She" (nsubj) and "apples" (dobj) depend on it.
-
Advantage: More directly models predicate-argument structure, useful for many languages (including Indian languages).
-
Parsing Techniques
-
Syntactic Parsing: Process of analyzing a sentence to determine its syntactic structure (constituency or dependency).
-
Constituency vs. Dependency Parsing:
| Constituency (Phrase-Structure) | Dependency | | :--- | :--- | | Groups words into phrases (NP, VP). | Creates binary relations between words. | | Tree nodes = phrases. | Tree nodes = words. | | Rules = CFG productions. | Rules = dependency relations (nsubj, dobj, etc.). | | Example: Penn Treebank format. | Example: Universal Dependencies format. |
-
Synthetic (Rule-Based) vs. Statistical Parsers:
-
Synthetic/Rule-Based: Uses hand-written grammar rules. Precise but brittle, poor coverage.
-
Statistical: Learns probabilities from treebanks. Robust, handles ambiguity via probability (e.g., PCFG, neural parsers).
-
-
Probabilistic CYK Algorithm:
-
Extension of CYK for CFGs to find most probable parse.
-
Uses dynamic programming table. For each span $i,j$ and non-terminal $A$, computes:
-
$$P(A \rightarrow w_i...w_j) = \max_{A\rightarrow BC, k} \left[ P(A\rightarrow BC) \times P(B \rightarrow w_i...w_k) \times P(C \rightarrow w_{k+1}...w_j) \right]$$
-
Ambiguity in Parse Trees:
-
Structural Ambiguity: Multiple valid CFG derivations (e.g., "I saw the man with the telescope" – PP attachment).
-
Attachment Ambiguity: Where a modifier (PP, relative clause) attaches.
-
Coordination Ambiguity: "old men and women" – (old men) and women vs. old (men and women).
-
Treebanks
-
Construction:
-
Text Selection (balanced corpus).
-
Sentence Segmentation & Tokenization.
-
Manual Annotation of syntactic structure (constituency or dependencies) by linguists.
-
Adjudication to resolve disagreements.
-
Quality Control.
-
-
Role:
-
Development: Primary training data for statistical/neural parsers.
-
Assessment: Gold-standard test set for evaluating parser accuracy (Parseval metrics: precision, recall, F1 on labeled constituents/dependencies).
-
[!TIP] Key Distinction: Constituency = "What are the phrases?" (tree of phrases). Dependency = "Which word modifies which?" (graph of word-to-word links). Know the CYK algorithm's purpose (chart parsing for CFGs in $$\displaystyle O(n^3) $$).
D. SEMANTICS & DISAMBIGUATION
Word Sense Disambiguation (WSD)
-
Concept: Task of determining which sense (meaning) of a polysemous word is used in a given context.
-
Importance: Crucial for machine translation, information retrieval, text understanding.
-
Methods:
-
Supervised: Treat as classification. Train on sense-tagged corpus (e.g., using Naive Bayes, MaxEnt). Needs large labeled data.
-
Dictionary-Based (Knowledge-Based): Uses sense definitions (e.g., from WordNet) and overlap between dictionary glosses and context. Lesk Algorithm.
-
Thesaurus-Based: Uses semantic similarity between context words and sense synonyms (e.g., Patwardhan & Pedersen using WordNet based measures like Resnik, Lin).
-
Semantic Analysis
-
Compositional Semantics: Principle that the meaning of a complex expression is determined by the meaning of its parts and the rules used to combine them.
-
Example: Meaning of "red car" = combine meaning(red) + meaning(car) + modification rule.
-
Enables understanding of novel sentences.
-
-
Bootstrapping Methods:
-
Start with small seed set of known examples (e.g., known named entities, sentiment words).
-
Use patterns/extractors to find more examples from unlabeled text.
-
Train new model on expanded dataset → iterate.
-
Used for semantic role labeling, relation extraction, WSD.
-
-
Anaphora Resolution vs. Named Entity Resolution:
| Anaphora Resolution | Named Entity Resolution (NER) | | :--- | :--- | | Links pronouns (he, she, it) or definite NPs (the company) to their antecedent. | Identifies and classifies named entities (PERSON, ORG, LOC) in text. | | Goal: "Who/what does 'it' refer to?" | Goal: "What are the entities and their types?" | | Requires coreference across sentences. | Often within sentence/document scope. | | Techniques: Hobbs algorithm, ML models, mention-pair models. | Techniques: CRFs, BiLSTM-CRF, Transformers. |
Logical Representation
-
First-Order Logic (FOL):
-
Formal language for representing objects, properties, relations.
-
Components: Constants (John), Variables (x), Predicates (Loves(John, Mary)), Functions (FatherOf(John)), Quantifiers ($\forall$, $\exists$), Connectives ($$\displaystyle \land, \lor, \rightarrow, \neg $$).
-
Use in NLP: To represent meaning of sentences in a unambiguous, computable form for reasoning.
-
Example: "Every student reads a book" → $$\displaystyle \forall x (Student(x) \rightarrow \exists y (Book(y) \land Reads(x,y))) $$.
-
[!TIP] WSD Methods: Know the core idea of each: Supervised (classification), Lesk (dictionary overlap), Thesaurus (similarity to seed words). For Anaphora vs. NER, remember: Anaphora = linking references; NER = finding & classifying names.
E. APPLICATIONS & ADVANCED TOPICS
Machine Translation
-
Transfer Model (Classic, Rule-Based/Statistical MT):
-
Analysis: Parse source sentence into source language syntactic/semantic representation.
-
Transfer: Transform source representation into target language representation (using transfer rules/dictionaries).
-
Generation: Generate fluent target language sentence from target representation.
- Limitation: Requires deep linguistic analysis for both languages; transfer rules are complex.
-
Speech Recognition
-
How it Works (Acoustic + NLP):
-
Acoustic Front-end: Convert audio signal to feature vectors (MFCCs).
-
Acoustic Model: Maps features to phonemes (HMMs, DNNs).
-
Pronunciation Model (Bayesian): Maps phoneme sequences to word sequences using lexicon and phonological rules.
-
$P(W|A) \propto P(A|W) P(W)$ where $A$=acoustic, $W$=word sequence.
-
$P(W)$ is the language model (N-grams).
-
-
Decoding: Search for most likely word sequence given acoustic evidence.
-
-
Role of NLP: Provides the language model ($P(W)$) and pronunciation lexicon to constrain and guide the acoustic search, ensuring syntactically/semantically plausible output.
Commercial & Practical Applications of NLP
-
Smart Work Processors & User Interaction:
-
Grammar/style checking (e.g., Grammarly).
-
Autocomplete, text prediction.
-
Voice typing, command recognition.
-
Document summarization.
-
-
Improving User Experience:
-
Chatbots & virtual assistants (Siri, Alexa).
-
Sentiment analysis on reviews/social media.
-
Personalized content recommendation.
-
Search query understanding.
-
-
Specific Application Domains (AI in Healthcare):
-
AI in Disease Detection: NLP extracts symptoms, medications, family history from clinical notes (EHR) to flag risk (e.g., sepsis, diabetes).
-
Virtual Health Assistants & Chatbots: Symptom checking, appointment scheduling, medication Q&A, mental health support.
-
Medication Adherence: Analyzing patient notes/reminders to identify non-adherence patterns; generating personalized reminders.
-
Sentiment Analysis: On patient feedback, social media posts about drugs/treatments for pharmacovigilance.
-
Improving EHR Systems: Auto-coding diagnoses/procedures (ICD-10), filling structured fields from free text, clinical trial matching.
-
[!TIP] MT & Speech: For Transfer Model, memorize the 3 phases. For Speech Recognition, emphasize the Bayesian framework: $P(Words|Acoustic) \propto P(Acoustic|Words) \times P(Words)$. $P(Words)$ is the NLP component.
Evaluation Metrics
-
Classification Tasks (e.g., NER, Sentiment):
-
Precision = $$\displaystyle \frac{TP}{TP+FP} $$ (How many selected items are relevant?)
-
Recall = $$\displaystyle \frac{TP}{TP+FN} $$ (How many relevant items are selected?)
-
F1-Score = $$\displaystyle 2 \times \frac{Precision \times Recall}{Precision + Recall} $$ (Harmonic mean).
-
Accuracy = $$\displaystyle \frac{TP+TN}{Total} $$ (Useful for balanced classes).
-
-
Parsing: Parseval (constituency): labeled precision/recall on bracketed constituents. UAS/LAS (dependency): Unlabeled/Labeled Attachment Score (percentage of words with correct head/label).
-
Machine Translation: BLEU (n-gram precision with brevity penalty), ROUGE (recall-oriented), METEOR (synonym-aware).
F. SPECIAL TOPICS & INTEGRATED CONCEPTS
Survival Analysis in Medical NLP (From AI in Healthcare context)
-
Goal: Model time-to-event data (e.g., time to disease progression, death).
-
Linear Prognostic Models: Cox Proportional Hazards model.
-
Hazard function: $$\displaystyle h(t|X) = h_0(t) \exp(\beta^T X) $$
-
$$\displaystyle h_0(t) $$: baseline hazard, $X$: features (from NLP-extracted clinical text), $\beta$: coefficients.
-
Does not assume specific baseline hazard distribution.
-
-
Survival Models vs. Time Survival Models:
-
Survival Model: General term for any model predicting survival probability over time.
-
Time Survival Model: Specifically models time-varying covariates (features that change over time, e.g., lab values extracted from longitudinal notes). More complex.
-
-
Nelson-Aalen Estimator:
-
Non-parametric estimator of the cumulative hazard function $H(t)$.
-
$$\displaystyle \hat{H}(t) = \sum_{i: t_i \leq t} \frac{d_i}{n_i} $$
-
$$\displaystyle t_i $$: distinct event times.
-
$$\displaystyle d_i $$: number of events at $$\displaystyle t_i $$.
-
$$\displaystyle n_i $$: number at risk just before $$\displaystyle t_i $$.
-
-
Survival Function Estimate: $$\displaystyle \hat{S}(t) = \exp(-\hat{H}(t)) $$.
-
-
Survival Tree:
-
Tree-based model (like CART) for survival data.
-
Splits nodes based on features to maximize difference in survival distributions between child nodes (e.g., using log-rank test).
-
Example: Root split on "contains symptom 'chest pain'?" → left branch (high risk, short median survival), right branch (low risk).
-
-
CATE (Conditional Average Treatment Effect):
-
Definition: The average difference in outcome between treatment and control for a subpopulation with specific features $$\displaystyle X=x $$.
-
$$\displaystyle CATE(x) = E[Y|T=1, X=x] - E[Y|T=0, X=x] $$
-
Why use it?: To provide personalized treatment effect estimates. NLP can extract $X$ (patient characteristics from notes) to compute CATE for individual patients.
-
Addressing Model Limitations (Overfitting)
-
Techniques:
-
Regularization: Add penalty to loss function (L1/Lasso, L2/Ridge) to constrain model weights.
-
Dropout (Neural Nets): Randomly "drop" units during training to prevent co-adaptation.
-
Early Stopping: Stop training when validation performance degrades.
-
Data Augmentation: Create synthetic training data (e.g., synonym replacement, back-translation).
-
Cross-Validation: Robust estimation of model performance.
-
Simplify Model: Reduce parameters (e.g., smaller n-grams, fewer layers).
-
Ensemble Methods: Bagging (Random Forest) reduces variance.
-
[!TIP] Survival Analysis: Link NLP's role → extracting features (X) from clinical text to feed into these models. CATE is about personalization. Nelson-Aalen estimates cumulative hazard non-parametrically.
UNIT 4 QUICK RECAP (Exam Priority Order):
-
POS Tagging (HMM, MaxEnt, TBL, Rule-based).
-
Parsing (CFG/PCFG, Dependency, Ambiguity, CYK, Treebanks).
-
N-grams & Smoothing (Perplexity, Laplace).
-
WSD (Supervised, Lesk, Thesaurus).
-
Commercial Apps & Healthcare NLP (EHR, Disease Detection, Chatbots).
-
RegEx & Preprocessing (Tokenization vs. Segmentation).
-
Morphology & FSA (Indian languages).
-
Semantics (Compositional, Anaphora vs. NER, FOL).
-
MT & Speech (Transfer Model, Bayesian pronunciation).
-
Survival Analysis (Cox, Nelson-Aalen, CATE – from Healthcare paper).
-
Evaluation Metrics (Precision/Recall/F1, Parseval, BLEU).
-
Overfitting Techniques.