Natural Language Processing (AL-504 (B)) - Unit 5 Short Notes

UNIT 5: NATURAL LANGUAGE PROCESSING

I. INTRODUCTION & FUNDAMENTALS

Natural Language Processing (NLP) is a subfield of AI and linguistics concerned with enabling computers to understand, interpret, manipulate, and generate human language.

Need for NLP:

• Scale: Human language is vast and constantly evolving.

• Ambiguity: Natural language is inherently ambiguous (lexical, syntactic, semantic).

• Structure: Unstructured text/data needs to be converted to a structured form for computation.

• Automation: To automate tasks like translation, summarization, information extraction, and customer service.

Major Challenges in NLP:

1. Ambiguity: A single word/phrase can have multiple meanings (e.g., "bank", "I saw the man with the telescope").

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

3. Inference & Common Sense: Understanding requires background knowledge not explicitly stated.

4. Non-Standard Text: Handling typos, slang, social media text, code-switching.

5. Resource Scarcity: Lack of annotated data for many languages (low-resource languages).

Broad Classes of NLP Applications:

[!TIP] Exam Focus: Be prepared to define NLP, list its challenges, and categorize applications. Commercial uses are a frequent 7-mark question.

II. TEXT PRE-PROCESSING & LINGUISTIC FOUNDATIONS

Tokenization & Word Segmentation

• Tokenization: Splitting text into words, phrases, or symbols (tokens) based on whitespace/punctuation. Common for space-delimited languages (English).

  • Example: "I love NLP!" → ["I", "love", "NLP", "!"]

• Word Segmentation: Identifying word boundaries in languages without explicit spaces (e.g., Chinese, Thai, Japanese, some Indian scripts like Tamil).

  • Example (Chinese): "我爱自然语言处理" → ["我", "爱", "自然语言", "处理"]

• Challenges for Indian Languages: Complex compound words (samāsa), inflectional morphology, and schwa deletion in Hindi make segmentation non-trivial. Requires morphological analyzers or statistical models.

Morphology

• Introduction: Study of the internal structure of words and how they are formed from morphemes (smallest meaningful units: roots, prefixes, suffixes).

  • Example: "unhappily" = un- (prefix) + happy (root) + -ly (suffix).

• Morphology of Indian Languages: Often highly inflectional and agglutinative. A single word can encode multiple grammatical categories (gender, number, case, tense).

  • Example (Sanskrit/Hindi): "rāma-ne" = rāma (root) + -ne (ergative case marker).

• Relationship with Finite-State Automata (FSA): Morphological analysis/generation can be efficiently modeled using FSA or Finite-State Transducers (FST). Lexicon and morphological rules are encoded as states and transitions.

Spelling Correction & Normalization

• Challenges:

  • Non-word errors: Result in strings not in dictionary (e.g., "fone").

  • Real-word errors: Result in valid dictionary words but incorrect in context (e.g., "Their going home").

  • Context dependency: Correcting "write" vs. "right" requires context.

• Minimum Edit Distance (Levenshtein Distance): Minimum number of edit operations (insert, delete, substitute, transpose) to transform string A into string B.

  • Algorithm: Dynamic programming.

  • Let $D(i,j)$ be distance between first $i$ chars of string A and first $j$ chars of string B.

$$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)} \\ D(i-2,j-2) + 1 & \text{(transposition, if } A_i=B_{j-1} \text{ and } A_{i-1}=B_j) \end{cases}$$

\boxed{D(0,j)=j, \quad D(i,0)=i}

• Phonological Rules: Rules that describe how sounds (phonemes) change in specific contexts. Significant for phonetic spelling correction (e.g., "fone" → "phone" based on /f/ and /ph/ similarity).

Regular Expressions (Regex)

• Role: Powerful tool for pattern matching and text extraction based on character sequences.

• Key Patterns:

  • . : Any single character.

  • \d : Digit ([0-9]), \w : Word character ([a-zA-Z0-9_]), \s : Whitespace.

  • * : 0 or more, + : 1 or more, ? : 0 or 1.

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

  • [...] : Character set, [^...] : Negated set.

  • | : OR, () : Grouping.

• Use Cases: Tokenization (splitting on punctuation), extracting email/phone numbers, identifying capitalization patterns, simple pattern-based tagging.

Corpora (Language Resources)

• Introduction: Structured collections of written or spoken text used for linguistic analysis and training NLP models.

• Significance of Corpora Analysis:

  • Provides empirical evidence of language use.

  • Enables calculation of statistics (word frequencies, collocations).

  • Essential for training and evaluating statistical NLP models (n-grams, parsers, taggers).

  • Helps in lexicography (dictionary making) and studying language variation.

• Treebanks:

  • Construction: A corpus where each sentence is annotated with its syntactic structure (parse tree). Requires skilled linguists and strict annotation guidelines (e.g., Penn Treebank format). Process: Sentence selection → Parsing → Manual/automatic annotation → Validation.

  • Role: The gold standard for training and evaluating statistical parsers. Provides data to learn Probabilistic CFG (PCFG) rule probabilities and dependency relations.

[!TIP] Exam Focus: Minimum Edit Distance algorithm and Treebank construction/role are very high-yield. Be ready to write the DP recurrence for edit distance and list treebank construction steps.

III. LANGUAGE MODELING

N-gram Models

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

• Bigram Probability Calculation:

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

*Example:* $$\displaystyle P(\text{NLP}|\text{love}) = \frac{\text{Count("love NLP")}}{\text{Count("love")}} $$

• Perplexity: A measure of how well a probability model predicts a sample. Lower perplexity = better model. For a test corpus $$\displaystyle W = w_1 w_2 ... w_T $$:

$$PP(W) = \sqrt[T]{ \frac{1}{P(w_1 w_2 ... w_T)} }$$

\boxed{PP(W) = 2^{-\frac{1}{T} \log_2 P(W)}}

Where $$\displaystyle P(W) = \prod_{i=1}^T P(w_i | w_{i-n+1} ... w_{i-1}) $$.

Smoothing Techniques

• Necessity (Zero Probability Problem): In n-gram models, many n-grams in test data may not appear in training corpus, leading to $$\displaystyle P=0 $$ and $$\displaystyle PP=\infty $$. Smoothing redistributes probability mass to unseen events.

• Laplace (Add-One) Smoothing: Add 1 to every count.

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

where $V$ = vocabulary size.

• Other Methods:

  • Good-Turing: Reallocate probability mass based on frequency of frequency counts.

  • Backoff: Use lower-order n-gram if higher-order n-gram count is zero (e.g., use bigram if trigram unseen).

  • Interpolation: Linearly combine probabilities from different n-gram orders (e.g., $$\displaystyle \lambda_1 P_{bigram} + \lambda_2 P_{unigram} $$).

Probabilistic Models: HMMs

• Hidden Markov Model (HMM): A model for sequential data with hidden states and observable emissions.

  • Components:

    1. Set of hidden states $$\displaystyle S = \{s_1, ..., s_N\} $$ (e.g., POS tags).

    2. Set of observations $$\displaystyle O = \{o_1, ..., o_M\} $$ (e.g., words).

    3. Transition probabilities $$\displaystyle A = \{a_{ij}\} = P(q_t = s_j | q_{t-1} = s_i) $$.

    4. Emission probabilities $$\displaystyle B = \{b_j(o)\} = P(o_t = o | q_t = s_j) $$.

    5. Initial state distribution $\pi$.

  • Application in Tagging: States = POS tags, Observations = words. Goal: Find most likely state sequence (tag sequence) for a given word sequence using Viterbi algorithm.

[!TIP] Exam Focus: Perplexity formula and Laplace smoothing are extremely frequent. Understand the intuition behind smoothing. HMMs are core for POS tagging.

IV. SYNTACTIC ANALYSIS (PARSING)

Grammar Formalisms

• Context-Free Grammar (CFG): A formal grammar defined by a 4-tuple $$\displaystyle G = (N, \Sigma, R, S) $$.

  • $N$: Set of non-terminal symbols (syntactic categories: S, NP, VP).

  • $\Sigma$: Set of terminal symbols (words).

  • $R$: Set of production rules (e.g., $$\displaystyle S \rightarrow NP\ VP $$).

  • $S$: Start symbol.

  • How it captures structure: Rules define how phrases are recursively built from smaller phrases.

• Probabilistic CFG (PCFG): Extends CFG by assigning a probability to each rule $$\displaystyle A \rightarrow \beta $$: $$\displaystyle P(A \rightarrow \beta) $$. The probability of a parse tree is the product of rule probabilities used.

• Dependency Grammar: Represents sentence structure as a directed graph where:

  • Nodes = words (lexical units).

  • Edges = dependency relations (e.g., nsubj, dobj, amod) from a head word to its dependent.

  • Principle: Every word (except the root) has exactly one head. Captures head-modifier relationships directly.

Parsing Algorithms & Concepts

• Syntactic Parsing: Process of analyzing a string of symbols (sentence) according to a grammar to produce a parse tree (constituency) or dependency graph (dependency) representing its syntactic structure.

• Ambiguity in Parse Trees:

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

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

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

    • Interpretation 2: I saw the man who had a telescope. ([S [NP I [VP saw [NP the man [PP with the telescope]]]]])

• Probabilistic CYK Algorithm: Extension of the Cocke-Kasami-Younger (CYK) algorithm for CFGs in Chomsky Normal Form (CNF). It fills a parse table with probabilities for each constituent spanning a substring, allowing selection of the most probable parse.

• Synthetic vs. Statistical Parsers:

  • Synthetic (Rule-Based): Use hand-crafted grammatical rules. Precise but brittle, poor coverage.

  • Statistical: Learn probabilities from treebanks. Robust, handle noise, but require large annotated data.

Finite-State Automata (FSA)

• Role in Morphological Analysis: FSA/FST are used to recognize valid word forms and analyze them into morphemes.

  • States represent morphological positions.

  • Transitions are labeled with morphemes or surface forms.

  • A path through the automaton from start to accept state corresponds to a valid morphological analysis.

[!TIP] Exam Focus: CFG components, structural ambiguity with example, and dependency grammar principles are very frequent. Be ready to draw simple parse trees for ambiguous sentences.

V. PART-OF-SPEECH (POS) TAGGING

• Task: Assign a part-of-speech tag (noun, verb, adjective, etc.) to each word in a sentence.

• Tagset: A predefined list of tags (e.g., Penn Treebank tagset: NN, VB, DT). Choice of tagset affects complexity and granularity.

Tagging Approaches

[!TIP] Exam Focus: Compare/contrast all four tagging approaches. TBL process (start state, rule learning, application) and HMM formulation for tagging are 7-mark favorites.

VI. SEMANTIC ANALYSIS & WORD SENSE

Word Sense Disambiguation (WSD)

• Concept: Task of determining which sense (meaning) of a word is used in a given sentence.

• Importance: Crucial for machine translation, information retrieval, and text understanding.

• Methods:

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

  2. Dictionary-Based (Knowledge-Based): Use computational lexicon (e.g., WordNet). Lesk Algorithm: Compare dictionary definition (gloss) of each sense with the context words of the target sentence. Select sense with highest overlap.

  3. Thesaurus-Based: Use thesaurus (e.g., WordNet) to find synsets (synonym sets). Use selectional preferences (e.g., verb eat prefers Food objects) or structural similarity between context and sense definitions.

  4. Bootstrapping Methods: Start with a small set of seed examples for a sense. Use a classifier to find more examples, then retrain iteratively. Useful when labeled data is scarce.

Semantic Representation & Composition

• 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" = meaning("red") ⊓ meaning("car") (intersection of properties).

  • Role: Enables systematic understanding of novel sentences from known words and grammar.

• First-Order Logic (FOL) as Representation: A formal language for representing semantic meaning.

  • Basic Elements: Constants (John), Predicates (Loves(John, Mary)), Variables (x), Quantifiers (∀, ∃), Connectives (∧, ∨, ¬, →).

  • Quantifiers with Example:

    • Universal Quantifier (∀): "All students read books."

$$\forall x (Student(x) \rightarrow \exists y (Book(y) \land Reads(x,y)))$$

    *   **Existential Quantifier (∃):** "Some student reads a book."

$$\exists x (Student(x) \land \exists y (Book(y) \land Reads(x,y)))$$

Discourse & Reference Resolution

• Anaphora Resolution: Identifying what a pronoun (he, she, it, they) or anaphoric expression refers to (its antecedent) in the preceding discourse.

  • Example: "Mary slipped. She fell." → "She" refers to "Mary".

• Named Entity Resolution (NER): Identifying and classifying named entities (persons, organizations, locations, dates) in text and linking them to unique identifiers in a knowledge base (e.g., Wikipedia page).

  • Example: "Apple" in "Apple released iPhone" → Organization (not Fruit).

• Key Difference: Anaphora resolves pronouns to prior mentions. NER identifies and classifies named mentions themselves.

[!TIP] Exam Focus: WSD methods (especially Lesk algorithm and bootstrapping) and quantifiers in FOL are common. Clearly distinguish anaphora resolution from NER.

VII. ADVANCED TOPICS & APPLICATIONS

Speech Recognition

• How it Works (Basic Pipeline):

  1. Acoustic Signal Processing: Convert analog sound to digital features (MFCCs).

  2. Acoustic Model: Maps acoustic features to phonemes (HMMs, DNNs).

  3. Language Model: Provides word sequence probabilities (n-grams, neural LMs) to resolve acoustic ambiguity.

  4. Decoder: Searches for the most likely word sequence given acoustic and language model scores.

• Role of NLP: Language models (n-grams, RNNs, Transformers) are crucial for predicting coherent word sequences, dramatically improving accuracy over pure acoustic matching.

Machine Translation (MT): Transfer Model

• Transfer Model: A rule-based/interlingua approach with three phases:

  1. Analysis: Source sentence → Source Language Representation (syntactic/semantic structure).

  2. Transfer: Source Representation → Target Language Representation (using bilingual dictionary and transfer rules).

  3. Generation: Target Representation → Target Language Sentence (using target language grammar).

• Limitation: Requires extensive manual rules for each language pair. Largely superseded by statistical (SMT) and neural (NMT) models.

Specialized Applications & Evaluation (Peripheral)

Note: Topics from the "AI in Healthcare" paper (Nov 2023) are not core NLP but appeared in the exam set. They are applications of general AI/ML.

• Medical Image Segmentation: Using CNNs/U-Nets to isolate structures (tumors, organs) in scans.

• Prognostic Models: Predict future health outcomes (e.g., survival time). Nelson-Aalen Estimator: Non-parametric estimator of the cumulative hazard function.

• Conditional Average Treatment Effect (CATE): Estimates the effect of a treatment (e.g., drug) on an outcome for individuals with specific characteristics.

• EHR Optimization: NLP used to extract information from unstructured clinical notes.

• Evaluation Metrics (General ML): Accuracy, Precision, Recall, F1-Score, AUC-ROC, Brier Score (for probabilities).

Commercial Uses of NLP (Recap & Expand)

1. Smart Grammar/Processors: Grammarly, Microsoft Editor (spelling/grammar/style correction).

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

3. Chatbots & Virtual Assistants: Customer service (Zendesk), personal assistants (Siri, Alexa).

4. Sentiment Analysis: Brand monitoring, market research (Brandwatch, Sprout Social).

5. Machine Translation: Real-time translation tools (Google Translate, DeepL).

6. Text Summarization: News digests (Google News), meeting summarization (Otter.ai).

[!TIP] Exam Focus: Speech recognition pipeline (highlight NLP's role) and Transfer Model phases are moderate frequency. Commercial uses are very high frequency—be ready to explain 3-4 in detail with real-world examples. Healthcare topics are peripheral but may appear as "applications of AI"—know basic definitions (CATE, Nelson-Aalen).