UNIT 3: NATURAL LANGUAGE PROCESSING

I. INTRODUCTION TO NATURAL LANGUAGE PROCESSING

Natural Language Processing (NLP) is a subfield of artificial intelligence and computational linguistics concerned with the interaction between computers and human (natural) languages. It enables computers to understand, interpret, manipulate, and generate human language in a valuable way.

Why NLP is Needed:

• Ambiguity: Natural language is inherently ambiguous at lexical, syntactic, and semantic levels (e.g., "I saw the man with the telescope").

• Variability: Infinite ways to express the same meaning; different word orders, synonyms, paraphrases.

• Implicit Knowledge: Relies on common sense, world knowledge, and context not explicitly stated.

• Evolution: Languages constantly evolve with new words, slang, and usages.

• Motivation: To bridge the communication gap between humans and machines, automate tasks involving text/speech, and extract insights from vast textual data.

Broad Classes of NLP Applications:

1. Information Retrieval & Extraction: Search engines, document summarization, entity extraction.

2. Machine Translation: Automatic translation between languages (e.g., Google Translate).

3. Sentiment Analysis & Opinion Mining: Determining sentiment (positive/negative/neutral) from text (e.g., product reviews).

4. Speech Recognition & Synthesis: Converting speech-to-text (e.g., Siri, Alexa) and text-to-speech.

5. Chatbots & Dialogue Systems: Automated customer service, virtual assistants.

6. Text Classification & Categorization: Spam detection, topic labeling, content moderation.

[!TIP] Exam Focus: Be prepared to define NLP clearly and list 4+ applications with real-world examples. Emphasize the challenges (ambiguity, variability) as the core reason for NLP's complexity.

II. TEXT PRE-PROCESSING

Purpose: To convert raw, unstructured text into a clean, normalized, and structured format suitable for computational analysis and modeling. It reduces noise and standardizes input.

Key Steps:

Tokenization vs. Word Segmentation:

• Tokenization: Primarily for languages with whitespace delimiters (English, Hindi in Devanagari). It separates punctuation and handles contractions.

• Word Segmentation: A more fundamental problem for languages like Chinese, Japanese, Thai where words are written consecutively. It's a sequence labeling or graph search problem.

• Key Difference: Tokenization assumes words are already separated by spaces; segmentation must discover word boundaries from a continuous character stream.

[!TIP] Exam Focus: A past question explicitly asks to differentiate tokenization and word segmentation. Use the table above and emphasize the script dependency (space-delimited vs. no-space scripts). For Indian languages like Tamil or Telugu, segmentation can be challenging despite spaces due to agglutination.

III. MORPHOLOGY

Morphology is the study of the internal structure of words and how they are formed from smaller meaningful units called morphemes (roots, prefixes, suffixes, inflections).

• Inflectional Morphology: Modifies a word for grammatical categories (tense, number, case) without changing core meaning (e.g., walk -> walked, cat -> cats).

• Derivational Morphology: Creates a new word with a new meaning/lexical category (e.g., happy -> unhappy, teach -> teacher).

Morphology of Indian Languages:

• Agglutinative: Words are formed by concatenating clear morphemes (e.g., Telugu, Kannada, Tamil). This leads to very long, complex word forms.

• Inflectional Richness: Verbs are heavily inflected for person, number, tense, aspect, mood.

• Script: Use of abugidas (e.g., Devanagari, Tamil) where consonant-vowel combinations form complex glyphs.

• Challenge: High out-of-vocabulary (OOV) rates for standard word-based models due to morphological richness.

Finite State Automata (FSA) in Morphology:

An FSA is a computational model (states and transitions) used to recognize and generate valid word forms of a language based on its morphological rules.

• Relationship: Morphological processes (like adding plural -s or past tense -ed) can be precisely modeled as state transitions in an FSA.

• Example: A simple FSA for English plural nouns: Start state -> (add -s) -> Final state (for "cat" -> "cats"). For "bus" -> "buses", a different transition handles the vowel insertion rule.

• Significance: FSAs provide an efficient, compact, and linguistically transparent way to handle morphology, crucial for spell-checking, morphological analysis, and as a front-end for NLP pipelines for morphologically rich languages.

[!TIP] Exam Focus: The DEC 2024 paper has a specific 7-mark question on the relationship between morphology and FSA. Draw a simple FSA diagram (using

DiagramCANVAS: Draw a 3-state FSA. State 1 (start) has an arrow labeled 'input: root' to State 2. State 2 has two arrows: one labeled '+s' to State 3 (final), another labeled '+es' to State 3.

) and explain how each transition corresponds to a morphological rule.

IV. CORPORA IN NLP

Corpora (singular: Corpus) are large, structured collections of written or spoken text used for linguistic analysis and training NLP models.

Types of Corpora:

• Monolingual: Text in a single language (e.g., British National Corpus).

• Parallel/Multilingual: Same text translated into multiple languages (e.g., Europarl). Essential for machine translation.

• Specialized: Domain-specific (medical, legal, financial texts).

• Annotated Corpora: Text enriched with linguistic labels (POS tags, parse trees, named entities).

• Speech Corpora: Audio recordings with transcriptions.

Significance of Corpus Analysis:

1. Empirical Foundation: Provides real-world data to study language patterns, frequencies, and distributions.

2. Model Training: The lifeblood of statistical and neural NLP models. Models learn patterns from annotated corpora.

3. Lexicography: Informs dictionary creation with actual usage examples.

4. Language Variation: Allows study of dialects, registers, and language change over time.

5. Evaluation: Standard annotated corpora (e.g., Penn Treebank) provide a benchmark to compare the performance of different NLP systems.

Corpus Design & Annotation Considerations:

• Representativeness: Should reflect the diversity of the language/domain.

• Size: Must be large enough to capture rare phenomena.

• Annotation Guidelines: Must be clear, consistent, and inter-annotator reliable (high agreement between human annotators).

• Annotation Levels: Word (POS), Phrase (chunking), Sentence (parse tree), Discourse (coreference), Semantic (WordNet senses).

• Ethics & Licensing: Copyright, privacy (for speech/personal text), and usage rights.

[!TIP] Exam Focus: For "significance," stress that modern NLP is data-driven. Without large, high-quality corpora, statistical/neural models cannot exist. Mention specific famous corpora (Penn Treebank, Wikipedia, Common Crawl).

V. PART-OF-SPEECH (POS) TAGGING

POS Tagging is the process of assigning a grammatical category (tag) to each word in a sentence based on its definition and context.

Example:

The/DT quick/JJ brown/JJ fox/NN jumps/VBZ over/IN the/DT lazy/JJ dog/NN ./.
(DT=Determiner, JJ=Adjective, NN=Noun, VBZ=Verb 3rd person singular, IN=Preposition)

Models for POS Tagging:

1. Rule-Based Taggers: Use hand-crafted linguistic rules (e.g., "if word ends in '-ing', tag as VBG"). Pros: Transparent, no training data needed. Cons: Hard to maintain, low accuracy (~77%).

2. Transformation-Based Tagging (TBL / Brill Tagger):

   • Starts with a simple baseline (e.g., assign most frequent tag to each word).

   • Learns a sequence of transformation rules from annotated training data.

   • Rule Format: (Trigger Condition) -> (Change Tag).

     • Example: (Previous Tag = NN) & (Current Word = 'are') -> Change Current Tag to VBZ.

   • Rules are ordered by score (net benefit: errors corrected - errors introduced).

   • Pros: More accurate than pure rule-based (~96-97%), rules are human-readable.

   • Cons: Rule ordering is critical; training can be slow.

3. Hidden Markov Models (HMM): A generative probabilistic model. Tags are hidden states, words are observations.

   • Uses: Transition Probabilities P(t_i | t_{i-1}) and Emission Probabilities P(w_i | t_i).

   • Finds the most likely tag sequence using the Viterbi algorithm.

4. Maximum Entropy (MaxEnt) Model for POS Tagging:

   • A discriminative probabilistic model. Directly models P(tag | features).

   • Features (φ): Local context features (previous/next words/tags, word suffixes, capitalization, etc.).

   • Model:

$$P(t \mid w, context) = \frac{1}{Z} \exp\left(\sum_{i} \lambda_i f_i(t, context)\right)$$

    where $$\displaystyle f_i $$ are binary feature functions, $$\displaystyle \lambda_i $$ are weights learned via **Maximum Entropy training** (often using GIS or L-BFGS), and $Z$ is a normalization constant.

*   **Pros:** Flexible feature design, often state-of-the-art accuracy. **Cons:** Requires careful feature engineering, training can be computationally intensive.

[!TIP] Exam Focus: The DEC 2024 paper asks specifically for Maximum Entropy Model. Be ready to write the formula, define features (give examples like "is current word capitalized?", "previous tag is DT?"), and contrast it with generative models (HMM). For TBL (a separate 4-mark question), explain the rule-learning cycle and give a concrete rule example.

VI. PARSING

Parsing (Syntactic Analysis) is the task of analyzing a sentence to determine its grammatical structure according to a grammar, typically producing a parse tree that shows hierarchical relationships (constituents).

Goals: Resolve syntactic ambiguity, provide structure for semantic interpretation, extract grammatical relations (subject, object).

Types of Parsers:

Comparison Summary: Synthetic parsers prioritize linguistic correctness and theory; statistical parsers prioritize empirical performance and coverage on real-world data. Modern state-of-the-art is neural statistical parsing (e.g., using neural networks to score parse trees).

[!TIP] Exam Focus: The DEC 2024 question asks to "differentiate synthetic and statistical parsers." Use the table structure above. Emphasize the trade-off: hand-crafted rules vs. data-driven probabilities.

VII. SEMANTIC ANALYSIS

Why Study Semantic Analysis?

To move beyond syntax to understand the literal meaning (semantics) of text and its intended meaning in context (pragmatics). It's crucial for:

• Question answering (understanding what is asked).

• Machine translation (choosing the right word sense).

• Textual entailment/contradiction detection.

• Information retrieval (matching query intent to document content).

Bootstrapping Methods for Semantic Analysis:

A semi-supervised learning approach to build semantic resources (like WordNet) or classifiers from very limited seed data.

1. Start with Seed: A small set of reliable seed examples (e.g., a list of words for a semantic category like "Sports").

2. Pattern Extraction: Use the seeds to find lexico-syntactic patterns in large corpora (e.g., "X and other sports" -> pattern X and other Y).

3. Pattern Application: Apply extracted patterns to find new, high-confidence candidates for the category.

4. Iteration: Add new candidates to the seed set and repeat steps 2-3, bootstraping the list to larger size.

5. Stopping: When no new high-quality candidates are found.

• Example: Hearst patterns for hyponymy: "X such as Y" -> Y is a hyponym of X.

Word Sense Disambiguation (WSD):

The task of identifying which sense (meaning) of a word is used in a sentence.

• Example: "The bank is steep" (river bank) vs. "I went to the bank" (financial institution).

• Approaches:

  • Knowledge-Based: Use external resources (WordNet, dictionaries). Lesk Algorithm: Compare dictionary definitions (glosses) of possible senses with the context words; choose sense with highest overlap.

  • Supervised: Treat as a classification problem. Train on sense-annotated corpora (e.g., SemCor). Features: surrounding words, POS, collocations.

  • Unsupervised/Word-Sense Induction: Cluster word occurrences based on context similarity to discover senses automatically.

[!TIP] Exam Focus: WSD is a separate 5-mark question. Be ready to define it, give a clear example, and list at least 3 approaches (Knowledge-based/Lesk, Supervised, Unsupervised). For Bootstrapping, explain the iterative seed-expansion cycle.

VIII. DISCOURSE AND PRAGMATICS

Anaphora Resolution:

• Concept: Identifying what a pronoun or referring expression (anaphor) refers to (its antecedent) in the preceding text or discourse.

• Methods:

  • Rule-Based: Use syntactic constraints (agreement in number/gender), binding theory, centering theory (focus on salient discourse entities).

  • Statistical/ML: Use features like distance, grammatical role (subject/object), lexical repetition, semantic compatibility.

• Example: "John told Mike that he was late." -> Resolve "he" to "John" or "Mike" using context.

Named Entity Resolution (NER) / Coreference Resolution:

• Concept: The task of clustering mentions of real-world entities (people, organizations, locations) in text that refer to the same entity.

• Methods: Similar to anaphora resolution but for proper nouns and noun phrases. Uses features like exact name match, alias lists, contextual similarity, semantic type consistency.

• Example: "Apple Inc., founded by Steve Jobs, announced the company's new iPhone." -> Cluster {"Apple Inc.", "the company"} to entity Apple_Inc..

Comparison: Anaphora Resolution vs. Named Entity Resolution

[!TIP] Exam Focus: The DEC 2024 paper has a direct question to differentiate these two. Use the table. Stress that NER/Coref is broader and document-level, while anaphora is often sentence-level and pronoun-focused.

IX. PHONOLOGICAL PROCESSING

Phonological Rules:

Rules that describe systematic, predictable changes in the pronunciation (phonemes) of words in a language's sound system.

• Role: Explain why a phoneme's actual pronunciation (allophone) differs from its underlying representation.

• Examples:

  • English Nasal Assimilation: /n/ becomes [m] before /p, b, m/ ("in" + "possible" -> [ɪmpɑsəbəl]).

  • Hindi Schwa Deletion: The inherent vowel 'अ' (schwa) is deleted in certain positions (e.g., "राम" is pronounced [raːm], not [raːəm]).

• Significance: Essential for Text-to-Speech (TTS) systems to generate correct pronunciation, and for Speech Recognition to model acoustic variations.

Minimum Edit Distance (Levenshtein Distance):

The minimum number of single-character edit operations (insertions, deletions, substitutions) required to transform one string into another.

• Calculation (Dynamic Programming): Build a matrix D[i,j] where D[i,j] is the edit distance between the 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)} \end{cases}$$

where `cost = 0` if `A[i] == B[j]`, else `1`.

• Applications: Spell checking, DNA sequence alignment, speech recognition (finding closest word in lexicon), plagiarism detection.

Bayesian Method of Pronunciation:

A probabilistic approach to model the mapping from orthography (spelling) to phonology (pronunciation).

• Goal: Find the most likely pronunciation sequence P for a given word W.

$$P^* = \arg\max_P P(P \mid W) = \arg\max_P \frac{P(W \mid P) P(P)}{P(W)}$$

Since `P(W)` is constant for a given `W`, we maximize: 

$$P^* = \arg\max_P P(W \mid P) P(P)$$

• Components:

  • P(P): Prior probability of a pronunciation sequence (from a phonotactic model of the language, e.g., a phoneme n-gram model).

  • P(W | P): Likelihood of observing the spelling given the pronunciation (a noisy channel model capturing spelling-to-sound rules and their probabilities).

• Use: Foundation for pronunciation modeling in TTS and grapheme-to-phoneme (G2P) conversion systems.

[!TIP] Exam Focus: Minimum Edit Distance is a 7-mark question. Be ready to compute it step-by-step for a small example (e.g., "kitten" -> "sitting"). For Bayesian pronunciation, write the core formula and explain the two components (Prior P(P), Likelihood P(W|P)). Phonological rules: give one concrete example from any language.

X. OVERARCHING MODELS AND ALGORITHMS IN NLP

Survey of Key Models & Algorithms:

Integration Across NLP Tasks:

Modern NLP systems are pipelines or end-to-end models:

1. Classic Pipeline: Raw Text -> Pre-processing -> Tokenization -> POS Tagging -> Parsing -> Semantic Analysis -> Application.

2. Modern End-to-End: Raw Text -> Pre-trained Transformer (e.g., BERT) -> Task-specific fine-tuning layer -> Output (e.g., sentiment, translation).

   • The transformer acts as a universal feature extractor that implicitly learns syntax, semantics, and some world knowledge during pre-training.

   • Integration: Lower-level tasks (POS, parsing) can be seen as intermediate objectives that help train better representations for higher-level tasks (semantic analysis, discourse).

[!TIP] Exam Focus: This is a 7-mark "survey" question. Do not dive deep into any one model. Instead, create a table like above with 5-6 key models, their type (generative/discriminative/neural), and 1-2 key applications. Conclude with the shift from pipeline to pre-trained transformer-based fine-tuning.