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

UNIT 2: NATURAL LANGUAGE PROCESSING - CORE CONCEPTS & TECHNIQUES

1. FOUNDATIONS & PREPROCESSING (High Frequency)

Introduction to NLP

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

• Need & Goals: Bridge the gap between human communication and computer understanding. Goals include machine translation, sentiment analysis, question answering, text summarization.

• Major Challenges:

  • Ambiguity: Lexical (word-level), syntactic (structure), semantic (meaning).

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

  • Inference & World Knowledge: Requires common sense and contextual understanding.

  • Non-standard Text: Typos, slang, informal language in social media.

  • Resource Scarcity: Lack of annotated data for many languages (especially Indian languages).

Text Preprocessing Pipeline

A sequential set of steps to convert raw text into a clean, analyzable format.

[!TIP] Exam Focus: Be ready to differentiate:

• Tokenization vs. Word Segmentation: Tokenization splits on whitespace/punctuation (for space-delimited languages like English). Word Segmentation is needed for languages without explicit word boundaries (e.g., Chinese, Thai), where the task is to find word boundaries in a continuous string.

• Stemming vs. Lemmatization: Stemming is faster, heuristic-based, may produce non-words. Lemmatization is slower, linguistically-aware, returns valid dictionary words (lemmas).

Regular Expressions (Regex) in NLP

• Role: Powerful tool for pattern matching, text extraction, and simple tokenization based on character patterns.

• Basic Patterns:

  • Character Classes: [a-z], [0-9], \w (word char), \s (whitespace).

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

  • Anchors: ^ (start), $ (end).

  • Groups & Capturing: (pattern) for grouping and extraction.

• Example: Extract email IDs: [\w\.-]+@[\w\.-]+\.\w+

Spelling Error Detection & Correction

• Challenges:

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

  • Real-word Errors: Result in valid dictionary words but wrong context (e.g., "I want to sea the movie" vs. "see").

• Approaches:

  • Dictionary-Based: Check if token is in dictionary. For correction, generate candidate corrections.

  • Probabilistic/Language Model-Based: Choose candidate with highest probability in context.

  • Minimum Edit Distance (Levenshtein Distance):

    • Definition: Minimum number of single-character operations (insert, delete, substitute, transpose) to change one string into another.

    • Algorithm: Dynamic Programming. Let D[i,j] be distance between first i chars of string A and first j chars of string B.

    • Recurrence Relation:

$$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)} \\ D[i-2,j-2] + 1 \quad \text{(transposition, if applicable)} \end{cases}$$

    *   **Application:** Generate candidate corrections by finding words within a small edit distance of the misspelled word.

2. LANGUAGE MODELING (Very High Frequency)

N-gram Models

• Concept: Assign a probability to a sequence of words $$\displaystyle P(w_1, w_2, ..., w_n) $$ using the chain rule:

$$P(w_1^n) = P(w_1) P(w_2|w_1) P(w_3|w_1^2) ... P(w_n|w_1^{n-1})$$

N-gram models **approximate** this by assuming a word depends only on the previous `n-1` words.

*   **Bigram (2-gram):** $$\displaystyle P(w_i | w_{i-1}) $$

*   **Trigram (3-gram):** $$\displaystyle P(w_i | w_{i-2}, w_{i-1}) $$

• Probability Estimation (Maximum Likelihood Estimation - MLE):

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

*   **Example:** "I want to eat pizza." Bigram: $$\displaystyle P(\text{eat}|\text{want}) = \frac{\text{count(``want eat'')}}{\text{count(``want'')}} $$

• Problem: Sparse Data – many n-grams never appear in training corpus, leading to zero probabilities.

Perplexity

• Definition: The inverse probability of a test set, normalized by the number of words. It measures how well a probability model predicts a sample. Lower perplexity = better model.

• Calculation for a test set of N words:

$$\text{Perplexity}(W) = P(w_1 w_2 ... w_N)^{-\frac{1}{N}} = \sqrt[N]{\frac{1}{P(w_1 w_2 ... w_N)}}$$

For a bigram model:

$$\text{PP}(W) = \exp\left(-\frac{1}{N} \sum_{i=1}^{N} \log P(w_i | w_{i-1})\right)$$

Smoothing Techniques (Critical)

• Why Smoothing? To assign non-zero probability to unseen n-grams and redistribute probability mass from seen to unseen events.

• Laplace (Add-One) Smoothing:

  • Method: Add 1 to every bigram count, and adjust denominator by adding V (vocabulary size).

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

*   **Example:** If `count(w_{i-1})=0`, probability becomes $$\displaystyle \frac{1}{V} $$ (uniform distribution).

• Other Methods (Conceptual):

  • Good-Turing: Use frequency of frequency counts. Re-estimate probability of k-times seen events as probability of (k+1)-times seen events.

  • Kneser-Ney: Lower-order models are interpolated with a discounted higher-order model. The lower-order probability is based on the number of contexts a word appears in (good for low-order n-grams).

  • Witten-Bell: Similar to Kneser-Ney, discounting based on number of unique words following a context.

[!TIP] Exam Focus: You must be able to calculate bigram probabilities with Laplace smoothing. Know the formula and apply it to a small corpus. Understand the intuition: smoothing reserves some probability for the unknown.

Evaluation Metrics

• Perplexity: Primary intrinsic evaluation metric for language models.

• Intrinsic vs. Extrinsic:

  • Intrinsic: Evaluate the model in isolation (e.g., perplexity, next-word prediction accuracy).

  • Extrinsic: Evaluate the model's impact on a downstream task (e.g., MT quality, speech recognition error rate).

3. MORPHOLOGY & FINITE STATE TECHNOLOGY

Morphology

• Introduction: Study of word formation and structure.

• Key Terms:

  • Morpheme: Smallest meaningful unit.

    • Stem/Base: Core meaning (e.g., "teach").

    • Affix: Added to stem (prefix, suffix, infix).

  • Inflection: Grammatical variants (e.g., teach, teaches, taught, teaching). Does not change part-of-speech or core meaning.

  • Derivation: Creates new word, often changing PoS (e.g., teach → teacher, teach → teachable).

• Morphology of Indian Languages:

  • Primarily agglutinative: words formed by concatenating morphemes (e.g., Telugu, Tamil, Kannada, Malayalam).

  • Rich inflection: Same root can have many surface forms based on gender, number, case, tense.

  • Script issues: Multiple scripts (Devanagari, Dravidian scripts), sometimes lack of standard Romanization.

  • Challenge for NLP: High number of possible word forms → sparsity; need for robust morphological analyzers/generators.

Finite State Automata (FSA) & Transducers (FST)

• Relationship: Morphological processes (inflection, derivation) can be elegantly modeled as finite-state transducers.

• FSA: Accepts/rejects strings (e.g., recognize valid word forms).

• FST: Maps an input string to an output string. Crucial for morphological parsing (surface form → stem + features) and generation (stem + features → surface form).

• Basic Concepts:

  • States: Represent stages of processing.

  • Transitions: Labeled with input/output symbols (for FST) or just input (for FSA).

  • Start State & Final/Accepting States.

• Example: A simple FST for English plural s:

  • Input: cat → Output: cat+s

  • Transitions: c:c, a:a, t:t, ε:+s (ε = empty string).

[!TIP] Diagram Idea: Sketch a simple FST with states q0 -> q1 -> q2 (final). Transitions: q0 -c/c-> q1 -a/a-> q2 -t/t-> q3 -ε/+s-> q4 (final).

4. PART-OF-SPEECH (POS) TAGGING (Very High Frequency)

Introduction

• Definition: The task of assigning a grammatical category (noun, verb, adjective, etc.) to each word in a sentence.

• Importance: Essential for syntactic parsing, semantic analysis, information extraction.

• Tag Sets: Standardized sets like Penn Treebank (45 tags: NN, VBZ, JJ, etc.). Indian languages have their own tag sets (e.g., IIIT-Hyderabad tag set).

Tagging Approaches

Hidden Markov Models (HMMs) for POS Tagging

• Components:

  • States: PoS tags.

  • Observations: Words.

  • Parameters:

    • Transition Probabilities: $$\displaystyle a_{ij} = P(t_i | t_j) $$ (probability of tag $$\displaystyle t_i $$ following tag $$\displaystyle t_j $$).

    • Emission Probabilities: $$\displaystyle b_i(o) = P(o | t_i) $$ (probability of word $o$ given tag $$\displaystyle t_i $$).

    • Initial Probabilities: $$\displaystyle \pi_i = P(t_i \text{ at start}) $$.

• Training (Supervised): From a tagged corpus (Treebank), compute MLE:

$$a_{ij} = \frac{\text{count}(t_j \rightarrow t_i)}{\text{count}(t_j)} \quad b_i(o) = \frac{\text{count}(t_i \rightarrow o)}{\text{count}(t_i)}$$

• Decoding (Finding Best Tag Sequence): Viterbi Algorithm (Dynamic Programming).

  • Goal: Find $$\displaystyle T^* = \arg\max_T P(T|W) \propto \arg\max_T P(W,T) $$.

  • Recurrence: For each position t and state s:

$$v_t(s) = \max_{s'} [v_{t-1}(s') \cdot a_{s',s}] \cdot b_s(w_t)$$

    Keep backpointer to trace best path.

*   **Complexity:** $$\displaystyle O(T^2 N) $$ where $T$ = number of tags, $N$ = sentence length.

[!TIP] Exam Focus: Be prepared to trace Viterbi on a small example (2-3 words, 2-3 tags). Know the recurrence formula and backpointer tracking.

5. SYNTAX & PARSING (Very High Frequency)

Grammar Formalisms

• Context-Free Grammars (CFGs):

  • Components: $$\displaystyle G = (N, \Sigma, R, S) $$

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

    • $\Sigma$: Set of terminals (words).

    • $R$: Set of productions (rules: $$\displaystyle NP \rightarrow Det\ N $$).

    • $S$: Start symbol.

  • How it Captures Structure: Generates phrase-structure trees (constituency).

  • Limitations: Cannot handle long-distance dependencies (e.g., "The cat that the dog chased was fast" – agreement between "cat" and "was").

• Dependency Grammar:

  • Principle: Words are connected by directed dependency relations (head → dependent). A sentence has a single root (main verb).

  • vs. Phrase-Structure: No phrasal nodes (NP, VP). Relations are syntactic functions (nsubj, obj, amod).

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

Parsing

• Goal: Given a sentence and a grammar, produce a valid parse tree (constituency or dependency).

• Parsing Algorithms:

  • CYK Algorithm (Cocke-Younger-Kasami):

    1. Input: CFG in Chomsky Normal Form (CNF) (productions: $$\displaystyle A \rightarrow B C $$ or $$\displaystyle A \rightarrow a $$).

    2. Dynamic Programming Table: Triangular chart C[i,j,A] = true if non-terminal A spans words from i to j.

    3. Recurrence: $$\displaystyle C[i,j,A] = \bigvee_{A \rightarrow BC} \bigvee_{k=i}^{j-1} (C[i,k,B] \land C[k+1,j,C]) $$

    4. Result: Parse exists if C[1,n,S] is true. To get tree(s), store backpointers.

  • Probabilistic CYK (PCYK): Extends CYK by storing the maximum probability of a constituent spanning i..j with label A:

$$P(i,j,A) = \max_{A\rightarrow BC, k} [P(i,k,B) \times P(k+1,j,C) \times P(A \rightarrow B C)]$$

    Backpointers store the rule and split point `k` that gave the max.

• Types of Parsers:

  • Synthetic/Rule-Based: Use hand-written grammar rules (e.g., early parsers). Often fail due to grammar size and ambiguity.

  • Statistical/Data-Driven: Learn probabilities from treebanks. Handle ambiguity by choosing the most probable parse (e.g., PCYK).

Treebanks

• What: Annotated corpus where each sentence is paired with its syntactic parse tree (constituency or dependency).

• Role:

  • Development: Primary resource for training statistical parsers (provides rules and probabilities).

  • Assessment: Standard test set for evaluating parser accuracy (e.g., Parseval metrics: labeled precision, recall, F1).

• Construction Process:

  1. Annotation: Human linguists annotate sentences (often using tools).

  2. Guidelines: Strict, consistent annotation manual (e.g., Penn Treebank guidelines).

  3. Quality Control: Adjudication of disagreements.

  4. Splitting: Train/Dev/Test sets.

Ambiguity in Parse Trees

• Structural/Attachment Ambiguity: A word/phrase can attach to different parts of the tree.

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

    • [I saw [the man [with the telescope]]] (instrumental: used telescope to see)

    • [I saw [the man] [with the telescope]] (modifier: the man had a telescope)

• Resolution: Probabilistic parsers use context (n-gram probabilities, lexical preferences) to assign probabilities to different structures and choose the most likely one.

6. SEMANTICS & WORD SENSE (High Frequency)

Word Sense Disambiguation (WSD)

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

• Why Hard: Polysemy (one word, many senses), lack of clear sense boundaries, context-dependence.

• Methods:

  • Supervised (Knowledge-Lean): Treat as classification task. Features: Collocations (words within ±k window), part-of-speech, syntactic dependencies. Requires labeled training data (e.g., SemCor corpus).

  • Dictionary-Based (Knowledge-Based): Use semantic network like WordNet.

    • Lesk Algorithm: Choose sense whose dictionary definition (gloss) has maximum overlap with the context words.

  • Thesaurus-Based: Assume similar words appear in similar contexts. Find distributional similarity between context and sense definitions from a large raw corpus (e.g., using vector space models).

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.

• Contribution: Allows building meaning for sentences from word meanings and syntactic structure. E.g., meaning of "red car" = red(car). Enables logical form representation for inference.

Semantic Analysis & Bootstrapping

• Need for Semantic Analysis: To understand meaning beyond syntax, for tasks like question answering, textual entailment, and knowledge base population.

• Bootstrapping Methods (Self-Training / Co-Training):

  • Problem: Labeled semantic data is scarce.

  • Idea: Start with a small seed set of high-confidence examples. Train an initial classifier. Use it to label more data. Iteratively add high-confidence new examples to training set.

  • Co-Training: Use two independent sets of features (e.g., syntax vs. lexical). Each classifier labels examples for the other.

7. APPLICATIONS & ADVANCED TOPICS (Medium Frequency)

Commercial Uses of NLP (Repeated)

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

• Machine Translation (MT): e.g., Google Translate. Uses phrase-based/neural MT.

• Sentiment Analysis: Determine opinion polarity (positive/negative) from reviews, social media.

• Chatbots & Virtual Assistants: Dialogue systems (e.g., Siri, Alexa).

• Text Classification: Spam filtering, topic labeling.

• Information Extraction (IE): Extract structured data (entities, relations) from unstructured text.

• Smart Compose/Text Prediction: Gmail's Smart Reply, keyboard suggestions.

Speech Recognition

• How it Works (Pipeline):

  1. Acoustic Model (AM): Maps audio signal to phonemes/units (HMMs, DNNs).

  2. Pronunciation Model: Maps phonemes to words (lexicon).

  3. Language Model (LM): Scores word sequences for plausibility (N-grams, neural LMs). NLP's key contribution – rescoring AM output to choose contextually correct words.

• Integration: LM helps disambiguate acoustically similar words (e.g., "recognize speech" vs. "wreck a nice beach").

Information Retrieval & Extraction

• Named Entity Recognition (NER): Identify and classify named entities (PERSON, ORGANIZATION, LOCATION, DATE) in text.

• Anaphora Resolution: Link pronouns (he, she, it, they) to their antecedents (the specific entity they refer to).

  • Differentiation:

    | Feature | Named Entity Recognition (NER) | Anaphora Resolution | | :--- | :--- | :--- | | Goal | Find what entities exist. | Find which entity a pronoun refers to. | | Output | Spans with labels: [PER John] | Link: he → John | | Dependency | Can be done without context. | Requires discourse context. |

Logic in NLP

• First-Order Logic (FOL): Formal language for representing knowledge and making inferences.

  • Symbols: Constants (John), Predicates (Loves(John, Mary)), Variables (x), Functions (Father(x)).

  • Quantifiers:

    • Universal (∀): "For all x, x is mortal." $\forall x\ \text{Mortal}(x)$

    • Existential (∃): "There exists a x such that x is happy." $\exists x\ \text{Happy}(x)$

• Use in NLP: Represent meaning of sentences in a formal, unambiguous way to enable logical inference (e.g., in question answering systems).

Phonological Rules & Pronunciation

• Significance: Describe how underlying phonemic representations are converted to surface phonetic forms (e.g., English plural /s/ → /z/ after voiced sounds).

• Bayesian Method for Pronunciation Modeling:

  • Goal: Model $P(\text{word} | \text{pronunciation})$ or $P(\text{pronunciation} | \text{word})$.

  • Bayes' Rule: $P(w|p) \propto P(p|w) P(w)$

  • Application: In speech recognition, generate possible pronunciations for a word (including variations) and score them using a model trained on pronunciation dictionaries and phonological rules.

[!TIP] Exam Focus: Be ready to differentiate NER vs. Anaphora Resolution (see table). Know basic FOL symbols and quantifiers. Connect phonological rules to speech recognition's pronunciation modeling.