UNIT 1: FUNDAMENTALS OF NATURAL LANGUAGE PROCESSING

I. INTRODUCTION TO NLP

Definition: Natural Language Processing (NLP) is a branch of artificial intelligence that enables computers to understand, interpret, manipulate, and generate human language.

Need for NLP:

• Communication: Enable human-computer interaction via natural language (e.g., chatbots).

• Information Access: Efficient retrieval and extraction from vast unstructured text (e.g., search engines).

• Inference: Draw conclusions, perform reasoning from textual data (e.g., question answering).

Major Challenges:

• Ambiguity: Lexical ("bank"), syntactic (PP attachment), semantic.

• Variability: Multiple expressions for same meaning (e.g., "How are you?" vs "How do you do?").

• Inference: Requires world knowledge not explicitly stated.

• Context: Meaning depends on discourse, speaker intent, situation.

Broad Application Classes:

• Information Retrieval & Extraction: Search engines, document summarization.

• Machine Translation: e.g., Google Translate.

• Speech Recognition & Synthesis: Voice assistants (Siri, Alexa).

• Text Classification & Sentiment Analysis: Spam detection, review sentiment.

• Question Answering & Dialogue Systems: Customer support bots.

• Commercial Uses: Grammar checkers (Grammarly), social media monitoring, smart assistants.

Corpora: Large, structured collections of text (e.g., news articles, tweets). Significance: Provide real-world data for training/evaluating models; enable linguistic analysis of language patterns.

[!TIP] Exam frequently asks for applications and challenges. Always pair each challenge with a concrete example.

II. TEXT PREPROCESSING & LEXICAL ANALYSIS

Tokenization & Word Segmentation

• Tokenization: Splitting text into tokens (words, punctuation, numbers). First step in NLP pipeline.

• Word Segmentation: Specifically for languages without explicit word boundaries (e.g., Chinese, Thai), splitting continuous script into words.

• Challenges:

  • Punctuation: Should "U.S.A." be one token or three?

  • Contractions: "don't" → ["do", "n't"] or ["don't"]?

  • Multi-word expressions: "New York" should be one token.

  • Indian languages: Agglutinative morphology and sandhi (phonological changes at boundaries, e.g., Sanskrit: "रामः" + "अस्ति" → "रामोऽस्ति").

• Difference: Tokenization is broader (includes punctuation, symbols); segmentation focuses solely on word boundaries.

Normalization

• Case Folding: Convert to lowercase (e.g., "Apple" → "apple").

• Stemming: Crudely remove affixes using heuristic rules (e.g., Porter's algorithm: "running" → "run").

• Lemmatization: Use vocabulary and morphological analysis to return dictionary form (e.g., "better" → "good"). More accurate but slower.

Stop Word Removal

• Remove high-frequency, low-information words (e.g., "the", "is", "and") to reduce noise.

Spelling Correction & Edit Distance

• Problem: Noisy text (typos, OCR errors) harms downstream tasks.

• Minimum Edit Distance (Levenshtein): Minimum number of insertions, deletions, substitutions to transform string A into B.

• Dynamic Programming Recurrence:

  \boxed{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 A[i] == B[j], else 2.

• Example: "kitten" → "sitting" (distance = 3).

[!TIP] Edit distance is not always symmetric if insertion/deletion costs differ. Usually all costs = 1.

Regular Expressions & Finite-State Automata

• Regular Expressions (regex): Patterns for matching/ extracting text.

  • Character classes: [a-z], \d (digit), \w (word char).

  • Quantifiers: * (0+), + (1+), ? (0-1), {n,m}.

  • Anchors: ^ (start), $ (end), \b (word boundary).

  • Example: \b\d{3}-\d{2}-\d{4}\b matches SSN.

• Finite-State Automata (FSA): Abstract machine (states, transitions, start/accept states) recognizing regular languages.

• Role in NLP:

  • Lexical analysis (tokenization, pattern extraction).

  • Regex compiled to FSA for efficient matching.

• Relationship with Morphology: Finite-state transducers model morphological processes (e.g., (stem) + (s|es|ies) for English plurals).

[!TIP] Regex is heavily used in preprocessing pipelines. Know common patterns for emails, dates, URLs.

III. MORPHOLOGY

Definition: Study of word formation, structure, and relationship between words.

Morphological Processes:

• Inflection: Modify word for grammatical function (tense, number, case).

  Example: walk → walked (past tense).

• Derivation: Create new word with changed meaning/part-of-speech.

  Example: happy → happiness (adj → noun).

• Compounding: Combine two or more free morphemes.

  Example: notebook = note + book.

Morphology for Indian Languages:

• Agglutinative: Words formed by concatenating clear morphemes (e.g., Telugu, Tamil, Kannada).

• Sandhi: Phonological changes at morpheme/word boundaries (e.g., Sanskrit: राम + अस्ति → रामोऽस्ति).

• Challenges: Complex inflectional paradigms, script variations (Devanagari, Tamil, etc.), rich morphology.

Finite-State Morphology:

• Use finite-state transducers (FST) to map surface forms ↔ lexical forms.

• Analysis: Surface form → underlying morphemes.

• Generation: Underlying morphemes → surface form.

• Example: English plural FST: (stem) + (s|es|ies) with conditions.

IV. LANGUAGE MODELS

N-gram Models

• Motivation: Estimate probability of word sequences; predict next word.

• Calculation:

  • Unigram: $$\displaystyle P(w) = \frac{C(w)}{N} $$

  • Bigram: \boxed{P(w_n|w_{n-1}) = \frac{C(w_{n-1} w_n)}{C(w_{n-1})}}

  • Example: Corpus: ["I am Sam.", "Sam I am."]

    $$\displaystyle P(\text{am}|\text{I}) = \frac{C(\text{I am})}{C(\text{I})} = \frac{2}{2} = 1 $$.

• Training: Count n-grams in training corpus.

• Evaluation: Perplexity on held-out/test data.

Evaluation Metric: Perplexity

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

• Calculation:

  \boxed{PP(W) = \sqrt[N]{\prod_{i=1}^N \frac{1}{P(w_i|w_{i-n+1}^{i-1})}}}

  where $$\displaystyle W = w_1 w_2 ... w_N $$.

  Equivalent to exponential of cross-entropy: $$\displaystyle PP(W) = 2^{H(W)} $$.

Smoothing Techniques

• Problem: Sparse data – many n-grams unseen in training → zero probability → perplexity = ∞.

• Laplace (Add-One) Smoothing: Add 1 to all counts.

  \boxed{P_{\text{Lap}}(w_n|w_{n-1}) = \frac{C(w_{n-1} w_n) + 1}{C(w_{n-1}) + V}}

  where $V$ = vocabulary size.

• Other Methods:

  • Good-Turing: Reallocate probability mass from seen to unseen n-grams based on frequency of frequencies (e.g., count of 1s → estimate for unseen).

  • Kneser-Ney: Uses continuation counts (how many different words follow a given n-gram) for lower-order models. More effective for language modeling.

[!TIP] Smoothing is essential. Know Laplace formula and intuition: why add-one? Why not just ignore unseen?

Grammarians Language Model (Conceptual)

• Historical/Rule-based: Uses hand-crafted grammar rules to generate/parse sentences.

• Components: Lexicon, phrase-structure rules, transformations.

• Functioning: Sentence is grammatical if it can be derived from start symbol using rules.

• Limitation: Not probabilistic, brittle to ambiguity, requires extensive linguistic expertise.

V. SYNTACTIC ANALYSIS

Context-Free Grammars (CFGs)

• Components:

  • Terminals: Words/punctuation (e.g., the, dog, .).

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

  • Productions: Rules like $$\displaystyle S \rightarrow NP\ VP $$.

  • Start symbol: Usually S (sentence).

• How CFGs capture structure: Derive sentences via production rules, yielding parse trees showing hierarchical organization.

• Example:

  
  S → NP VP
  
  NP → Det N
  
  VP → V NP
  
  Det → "the"
  
  N → "cat" | "mouse"
  
  V → "chased"
  
  

  Derivation: S → NP VP → Det N VP → "the" N VP → "the" "cat" VP → "the cat" V NP → "the cat" "chased" NP → "the cat chased" Det N → "the cat chased the mouse".

Parsing

• Goal: Given a sentence and grammar, find one or all parse trees.

• Parsing Algorithms:

  • CYK Algorithm:

    • Requires grammar in Chomsky Normal Form (CNF): $$\displaystyle A \rightarrow BC $$ or $$\displaystyle A \rightarrow a $$.

    • Uses dynamic programming table (triangular). Cell $[i,j]$ contains non-terminals that generate substring from position $i$ of length $j$.

    • Time complexity: $$\displaystyle O(n^3 |G|) $$.

    • DiagramCANVAS: Triangular table with rows representing start positions and columns representing substring lengths. Each cell lists grammar symbols that can generate that substring.

    • Probabilistic CYK (PCFG): Assigns probabilities to CFG rules; finds most probable parse tree.

  • Earley Parser:

    • Top-down, chart-based. Handles any CFG (no CNF restriction).

    • Uses dotted rules (e.g., $$\displaystyle S \rightarrow \bullet NP\ VP $$) and three operations: predictor, scanner, completer.

• Types of Parsers:

  • Rule-Based/Top-Down: Start from S, expand (e.g., recursive descent). Can suffer from left-recursion.

  • Bottom-Up: Start from words, reduce to S (e.g., shift-reduce).

  • Statistical/Probabilistic: Use probabilities from treebanks to choose best parse (e.g., PCFG).

  • Dependency vs Constituency:

    • Constituency (Phrase Structure): Groups words into nested phrases (tree with phrasal nodes like NP, VP).

    • Dependency: Direct binary links between words (head → dependent). No phrasal nodes; represents grammatical relations.

Treebanks

• Construction: Human annotators label sentences with syntactic structure (constituency or dependency). Requires detailed guidelines and measures of inter-annotator agreement.

• Role:

  • Development: Train statistical parsers (e.g., extract PCFG rules from treebank frequencies).

  • Assessment: Evaluate parser accuracy using Parseval metrics (precision, recall, F1 on bracketed constituents or dependency arcs).

Ambiguity in Parse Trees

• Structural Ambiguity: Same string has multiple valid parse trees.

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

  • Interpretation 1 (VP-attachment): I used a telescope to see the man.

    Parse: S → NP VP → ... VP → V PP → saw (NP PP).

  • Interpretation 2 (NP-attachment): I saw the man who had a telescope.

    Parse: S → NP VP → ... NP → NP PP → "the man" (with telescope).

• Resolution: Requires semantic knowledge, world knowledge, or statistical disambiguation (using treebank frequencies).

VI. PART-OF-SPEECH (POS) TAGGING

Introduction & Importance: Assigns a tag (e.g., NN, VBZ) to each word in a sentence. Critical for parsing, NER, machine translation, etc.

Tagging Approaches:

Tagsets:

• Penn Treebank: 45 tags (e.g., NN noun, VB verb, DT determiner).

• Universal Dependencies: 17 core tags (e.g., NOUN, VERB, ADJ) for cross-lingual consistency.

[!TIP] HMM: know Viterbi conceptually (dynamic programming for best path). TBL: rules are learned by minimizing errors on training data.

VII. SEMANTIC ANALYSIS & WORD SENSE

Word Sense Disambiguation (WSD)

• Problem: Polysemy – one word has multiple meanings (e.g., "bank" = financial institution vs river side).

• Methods:

  • Supervised: Train classifier (e.g., SVM, neural net) on labeled contexts. Requires sense-annotated corpus.

  • Dictionary-Based: Use knowledge sources (e.g., WordNet) to match definition/sense to context.

  • Thesaurus-Based: Use synonym sets (synsets) and similarity measures (e.g., Lesk algorithm).

  • Bootstrapping: Start with seed examples for a sense, iteratively find more contexts (e.g., "river" co-occurs with "bank" → river sense).

Compositional Semantics

• Principle: Meaning of complex expression determined by meanings of its parts and rules of combination.

• Example: "red ball" = red (color) + ball (object) → ball that is red.

• Contribution: Enables systematic interpretation of novel sentences, but fails for idioms ("kick the bucket").

Lexical Resources

• Dictionaries: Provide definitions, part-of-speech, usage examples.

• Thesauri: Provide synonyms, hypernyms (is-a), hyponyms (kind-of). WordNet is primary lexical database for English.

First-Order Logic (FOL)

• Role in NLP: Formal language for representing meaning precisely.

• Components: Predicates, variables, quantifiers (∀, ∃), logical connectives.

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

• Use: Semantic parsing, reasoning, question answering.

VIII. DISCOURSE & PRAGMATICS (Brief)

Anaphora Resolution

• Definition: Linking anaphors (pronouns, definite NPs) to their antecedents in discourse.

• Example: "John arrived. He was tired." → "He" refers to "John".

• Importance: Crucial for coherent text understanding, summarization.

Difference from Named Entity Resolution

• Anaphora Resolution: Resolves pronouns/definite NPs to specific entity mentions in the same discourse.

• Named Entity Resolution (NER): Identifies and classifies named entities (PERSON, ORG, LOC) in text. May involve linking to a knowledge base (entity linking).

Coreference Resolution (Conceptual)

• Broader task: identify all expressions that refer to the same entity (includes anaphora, cataphora, and nominal predicates).

  Example: "Apple announced a new iPhone. The company is innovative." → "Apple" ≡ "The company".

IX. ADVANCED TOPICS & APPLICATIONS

Speech Recognition Integration

• ASR Pipeline:

  1. Feature extraction (MFCC).

  2. Acoustic modeling (HMM/DNN).

  3. Language modeling (n-grams, neural LMs) → rescoring.

  4. Decoding (find best word sequence).

• NLP Enhancement: Language model reduces word error rate; NLP techniques for intent/slot extraction (spoken language understanding).

Information Extraction

• Named Entity Recognition (NER): Identify and classify entities (PERSON, ORG, DATE). Often modeled as sequence labeling (HMM, CRF, BiLSTM-CRF).

• Relation Extraction: Identify relationships between entities (e.g., works_at(John, Google)). Uses patterns, supervised learning, or distant supervision.

Machine Translation

• Transfer Model (classical):

  1. Analysis: Parse source sentence into syntactic/semantic representation.

  2. Transfer: Map source representation to target representation (using bilingual dictionaries/rules).

  3. Generation: Generate target sentence from transferred representation.

• Limitation: Requires deep linguistic analysis for each language pair; largely superseded by statistical/neural MT.

Sentiment Analysis & Opinion Mining

• Classify text as positive/negative/neutral or fine-grained (e.g., star ratings).

• Approaches: Lexicon-based (sentiment words), machine learning (SVM, LSTM, Transformers).

AI in Text Processing

• Smart Word Processors: Grammar/style checking (Grammarly), autocomplete, readability scoring.

• Electronic Health Record (EHR) Systems:

  • Extract clinical information (symptoms, medications, diagnoses) from unstructured notes.

  • Automate coding (ICD-10 codes), support clinical decision-making, predict patient outcomes.

X. KEY ALGORITHMS & MODELS SUMMARY

[!NOTE] For NLP exams, prioritize Edit Distance, Viterbi, CYK, TBL. Survival Trees and CATE are more relevant to AI in Healthcare; include only if specifically mentioned in your syllabus variant.