Natural Language Processing (IT-802 (B)) - Unit 1 Short Notes

UNIT 1: FOUNDATIONS & CORE TASKS OF NATURAL LANGUAGE PROCESSING

1.0 Introduction to Natural Language Processing (NLP)

Definition:

Natural Language Processing (NLP) is a subfield of artificial intelligence and computational linguistics concerned with the computational understanding, manipulation, and generation of human language by machines.

Rationale & Necessity:

• Volume of Text Data: Explosion of digital text (social media, web, documents).

• Human-Computer Interaction: Enable intuitive communication with systems via natural language.

• Information Overload: Automate extraction, summarization, and retrieval of relevant information.

• Accessibility: Tools for translation, text-to-speech, aiding differently-abled users.

Broad Classification of NLP Applications:

Commercial & Industrial Uses:

• Customer Support: Chatbots, automated ticket routing.

• Business Intelligence: Analyzing customer feedback, market trends.

• Healthcare: Clinical note analysis, patient triage.

• Finance: News sentiment for trading, fraud detection in documents.

• Legal: Contract analysis, e-discovery.

[!TIP] Exam Focus: Be prepared to define NLP and list at least 4 applications with brief examples. Highlight the need by connecting to data explosion and HCI.

2.0 Text Pre-processing and Normalization

Tokenization:

• Concept: Segmenting text into basic units (tokens: words, numbers, punctuation).

• Challenges:

  • Punctuation handling (e.g., "U.S.A." vs "U.S. ,").

  • Contractions ("don't" → "do" "n't" or "don't").

  • Language-specific delimiters (e.g., hyphens, slashes).

  • Emojis, URLs, hashtags in social media text.

• Algorithms: Rule-based (regex), machine learning-based.

Word Segmentation vs. Tokenization:

Sentence Segmentation:

• Techniques: Rule-based (detecting sentence terminators like ., !, ? with exceptions like "Mr.", "Dr."), machine learning (classifiers using features like capitalization, next token).

• Importance: Fundamental for downstream tasks (parsing, summarization, machine translation).

Normalization:

Stop-word Removal:

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

• Language-Specific: Stop-word lists are language-dependent; must be curated carefully (e.g., "not" is a stop-word in English but crucial for sentiment).

Spell Checking & Correction:

• Core Concept: Identify and correct non-dictionary words.

• Minimum Edit Distance (Levenshtein Distance): Minimum number of single-character edits (insertions, deletions, substitutions) to change one string into another.

  • Formula (Recursive):

$$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 characters match, else `1`.

• Algorithms: Dynamic programming (to compute edit distance), noisy channel model for candidate generation and ranking.

[!TIP] Common Pitfall: Confusing stemming (heuristic, fast) with lemmatization (vocabulary-based, accurate). Know the Porter Stemmer steps (iterative suffix stripping).

3.0 Corpora in NLP

Definition: A corpus (plural: corpora) is a structured, machine-readable collection of natural language text (and sometimes speech), used for linguistic analysis and NLP system development.

Types of Corpora:

Significance of Corpus Analysis:

• Empirical Foundation: Provides data for training and evaluating statistical models.

• Linguistic Discovery: Reveals language usage patterns, frequencies, collocations.

• Benchmarking: Standard corpora allow fair comparison of different NLP systems.

• Resource Development: Essential for building language models, dictionaries, and taggers for low-resource languages.

Corpus Creation & Annotation:

• Guidelines: Must be clear, consistent, and cover edge cases. Inter-annotator agreement (e.g., Cohen's Kappa) is measured to ensure quality.

• Process: Text collection → sampling → annotation (manual/semi-auto) → quality control → format conversion.

Well-Known Corpora:

• Penn Treebank: English newswire text with POS tags and syntactic parse trees (using Penn Treebank POS Tagset).

• Brown Corpus: First major electronic corpus (1M words, 1960s American English, genre-balanced).

• Indian Language Corpora: IL-POS (Indian Language POS Tagset), Hindi Dependency Treebank, EMILLE (monolingual/multilingual for 14 Indian languages).

Evaluation Using Corpora:

• Standard splits: Training, Development (Dev), Test sets.

• Test set must be held-out (never used in training/tuning) for unbiased performance estimation.

[!TIP] Exam Focus: Know the difference between parallel and annotated corpora. Be ready to name at least 2 corpora and their annotation types. Mention challenges in creating corpora for Indian languages (orthographic variation, script issues, annotation scarcity).

4.0 Morphology and Finite State Automata

Morphology:

• Definition: Study of the internal structure of words and how they are formed from smaller meaningful units called morphemes.

• Key Processes:

  • Inflection: Modifying a word to express grammatical categories (tense, number, case). Example: walk → walked (past tense).

  • Derivation: Creating a new word (often changing part-of-speech) by adding affixes. Example: happy → unhappiness.

  • Compounding: Combining two or more free morphemes. Example: "bookstore".

Morphology of Indian Languages (Specific Challenges):

• Agglutination: Words formed by stringing together morphemes (each with a clear grammatical function). Example (Hindi): "राम-ने" (Ram-ERG), "किताबें" (book-PL).

• Sandhi/Samasa: Phonological changes at morpheme boundaries (e.g., vowel coalescence, consonant doubling). Example (Sanskrit/Hindi): "राम+अयुक्त" → "रामायुक्त".

• Rich Inflection: Verbs and nouns have extensive paradigms (e.g., 13+ case endings in Sanskrit, 3 genders + 2 numbers in Hindi).

• Script & Orthography: Multiple scripts (Devanagari, Tamil, etc.), conjunct consonants, lack of standard romanization.

Finite State Automata (FSA) & Transducers (FST):

• FSA: Abstract machine with states and transitions, accepting/rejecting strings. Used for recognition (e.g., is this word valid?).

• FST: Extends FSA; maps input string to output string. Used for generation/analysis (e.g., lemma → inflected form).

• Relationship with Morphology:

  • Morphological rules (e.g., "add -ed for past tense") can be encoded as FST arcs.

  • Lexicon (list of stems/roots) forms the initial states.

  • Composition of FSTs: Complex morphology can be built by combining simpler FSTs (for prefix, suffix, sandhi rules).

• Designing FSA for Morphological Parsing:

  1. Define states for each morpheme/affix position.

  2. Transitions labeled with input symbols (characters/morphemes).

  3. Accepting states correspond to valid word forms.

• Finite-State Morphology for Indian Languages:

  • Handles agglutination via cascade of transducers (root → suffix1 → suffix2...).

  • Models sandhi rules as context-sensitive rewrite rules on FST arcs.

  • Tools: Foma, HFST (Helsinki Finite-State Toolkit) used to build morphological analyzers for Hindi, Bengali, etc.

[!TIP] Key Insight: FSTs provide a compact, efficient representation of morphological knowledge. For agglutinative languages, FSTs avoid combinatorial explosion of surface forms.

5.0 Part-of-Speech (POS) Tagging

Definition & Purpose:

• Assigning a syntactic/semantic category tag (e.g., Noun, Verb, Adjective) to each word in a sentence.

• Purpose: Disambiguate word senses, provide features for parsing, improve IR, serve as input to higher-level NLP tasks.

Tagset Standards:

• Penn Treebank Tagset: 45 tags (e.g., NN singular noun, VBZ 3rd person verb, JJ adjective). Widely used for English.

• Indian Language Tagsets: IL-POS tagset (based on EAGLES guidelines) with ~30 tags, adapted for Indian language features (e.g., separate tags for case markers, compound verbs).

Tagging Approaches:

Evaluation Metrics:

• Tagging Accuracy: $$\displaystyle \frac{\text{Number of correctly tagged words}}{\text{Total words}} \times 100\% $$.

• Error Rate: $1 - \text{Accuracy}$.

[!TIP] Brill Tagger Example: Rule: IF previous tag = 'VBD' AND current word = 'ing' THEN change current tag to 'VBG'. Start with most frequent tag for each word, apply rules iteratively.

6.0 Syntactic Analysis (Parsing)

Definition & Goals:

• Analyze sentence structure to determine constituency (phrase structure) or dependency relationships.

• Goals: Resolve ambiguity, extract meaning representations, provide syntax for downstream tasks (e.g., machine translation).

Parser Types:

Key Parsing Algorithms:

• CYK (Cocke-Younger-Kasami): Bottom-up, $$\displaystyle O(n^3) $$ time, requires grammar in Chomsky Normal Form (CNF) (rules: $$\displaystyle A \rightarrow BC $$ or $$\displaystyle A \rightarrow a $$).

• Earley Parser: Top-down with bottom-up filtering, $$\displaystyle O(n^3) $$ worst-case, $$\displaystyle O(n^2) $$ for unambiguous, $O(n)$ for deterministic. Handles any CFG.

Evaluation of Parsers:

• Precision, Recall, F1-Score: On constituents (for phrase-structure) or dependency arcs.

• Labeled vs. Unlabeled: Considering vs. ignoring syntactic labels.

• Bracketing Scores (PARSEVAL): Precision/recall over labeled brackets.

Challenges:

• Free Text: Ambiguity (structural, lexical), ill-formed sentences, domain variation.

• Indian Languages: Free word order (due to case marking), rich morphology leading to sparse data, lack of large treebanks, complex agreement patterns.

[!TIP] Distinguish: Synthetic parsers use hand-crafted rules; statistical parsers learn probabilities from annotated corpora (treebanks). CYK is for PCFG in CNF; Earley is more general.

7.0 Semantic Analysis

Need for Semantic Analysis:

• Syntax alone is insufficient for full understanding. Semantics captures meaning.

• Enables tasks like question answering, textual entailment, semantic search.

Lexical Semantics:

• Word Sense Disambiguation (WSD): Determining the correct sense of an ambiguous word in context.

  • Knowledge-Based: Use dictionaries/thesauri (WordNet) and selectional restrictions (e.g., "drink" prefers liquid objects).

  • Supervised: Train classifier on sense-annotated data (e.g., using Lesk algorithm—overlap in dictionary definitions).

  • Unsupervised: Word Sense Induction (cluster contexts), bootstrapping (start with seed examples).

• Semantic Roles & FrameNet:

  • FrameNet: Lexical resource where frames (conceptual scenarios) define frame elements (semantic roles like Agent, Patient, Instrument).

  • Example: [John]Agent [broke]Target [the window]Patient.

  • Roles are frame-specific (e.g., Buyer, Seller in Commerce_buy frame).

Bootstrapping Methods for Semantic Analysis:

• Self-Training: Use a model trained on limited labeled data to label unlabeled data, then retrain on combined set.

• Co-Training: Train two classifiers on disjoint feature sets; let each label unlabeled data for the other.

• Seed Examples: Start with small set of known examples (e.g., specific person names for NER), extract patterns, find more examples, iterate.

Distributional Semantics & Word Embeddings (Brief):

• Hypothesis: "You shall know a word by the company it keeps" (Firth).

• Idea: Represent words as vectors based on co-occurrence statistics in large corpora.

• Models: Word2Vec (Skip-gram, CBOW), GloVe, fastText.

• Use: Capture semantic similarity, analogies, serve as input features for NLP tasks.

[!TIP] WSD Example: "Bank" in "river bank" (location) vs. "bank account" (financial institution). Lesk algorithm compares context words with dictionary definitions of each sense.

8.0 Discourse Analysis & Coreference Resolution

Anaphora Resolution:

• Definition: Resolving referring expressions to their antecedents.

• Types:

  • Pronominal: "She" → "Mary".

  • Definite Noun Phrase: "The company" → previously mentioned company.

• Algorithms & Heuristics:

  • Hobbs Algorithm: Syntax-based, shallow parsing. Search syntax tree left-to-right, depth-first for the nearest NP satisfying constraints (number, gender, semantic compatibility).

  • Centering Theory: Track forward-looking centers (discourse entities) in utterance; prefer antecedents with high centering score (subjecthood, recency).

  • Machine Learning: Use features: distance, gender/number agreement, string match, semantic class.

Named Entity Recognition (NER) & Resolution:

• NER: Identifying and classifying named entities (PERSON, ORGANIZATION, LOCATION, DATE, etc.) in text.

  • Techniques: Rule-based (gazetteers, patterns), Machine Learning (CRF, BiLSTM-CRF), Transformers (BERT-based).

• Resolution (Linking): Disambiguating detected entities to knowledge base entries (e.g., "Apple" → company vs. fruit).

  • Techniques: Contextual similarity, entity linking systems (e.g., using Wikipedia/DBpedia).

Difference: Anaphora vs. Named Entity Resolution

[!TIP] Key Distinction: Anaphora is intra-document, coreferential (same entity). NER resolution is entity linking to KB (may be cross-doc, disambiguation across entities with same name).

9.0 Special Topics in NLP

Phonological Rules:

• Significance: Describe systematic sound changes in a language. Crucial for:

  • Speech Processing: Grapheme-to-phoneme (G2P) conversion for TTS.

  • Morphology: Modeling pronunciation of inflected forms.

  • ASR: Building pronunciation dictionaries.

• Types: Assimilation (e.g., "in" + "possible" → "impossible"), deletion, insertion, metathesis.

Bayesian Methods in Pronunciation Modeling:

• Application: Predicting pronunciation of out-of-vocabulary (OOV) words or names.

• Naïve Bayes Approach:

  • Model: $$\displaystyle P(\text{phoneme sequence} \mid \text{grapheme sequence}) \propto P(\text{grapheme sequence} \mid \text{phoneme sequence}) P(\text{phoneme sequence}) $$.

  • Use letter-to-sound rules as features, trained on pronunciation dictionary.

  • Bayesian inference allows incorporation of prior linguistic knowledge (e.g., common phonotactics).

Overview of Models & Algorithms in NLP (Connecting Tasks):

[!TIP] Bayesian Pronunciation: Think of it as a noisy channel model: source (phonemes) → noisy channel (grapheme rules) → observed (spelling). Bayes' theorem finds most likely source given observation.

10.0 Summary & Integration

NLP Pipeline Interconnection:

Raw Text

    ↓

Tokenization → Sentence Segmentation

    ↓

Normalization (case, stemming) → Stop-word Removal

    ↓

POS Tagging (provides tags/features)

    ↓

Syntactic Parsing (constituent/dependency structure)

    ↓

Semantic Analysis (WSD, role labeling)

    ↓

Discourse Analysis (coreference, coherence)

    ↓

Application-Specific Tasks (Summarization, QA, MT)

Challenges for Indian Languages:

1. Morphological Richness: Agglutination, sandhi → complex tokenization, data sparsity.

2. Resource Scarcity: Limited annotated corpora, treebanks, lexicons compared to English.

3. Script Diversity: Multiple scripts, encoding issues, lack of standardization.

4. Code-Mixing: Frequent mixing with English (Hinglish, Tanglish) → non-standard orthography.

5. Free Word Order: Dependency parsing harder; features like case marking become crucial.

6. Lack of Capitalization: No case information for NER, proper noun detection.

Current Trends & Future Directions:

• Pre-trained Language Models (PLMs): BERT, GPT, mBERT, XLM-R for cross-lingual transfer, low-resource languages.

• Multimodal NLP: Integrating text with vision, speech.

• Explainable AI (XAI): Interpretable models for NLP decisions.

• Low-Resource NLP: Cross-lingual transfer, data augmentation, few-shot learning for Indian languages.

• Ethical NLP: Bias detection/mitigation, fairness in NLP systems.

[!TIP] Integration Point: Always relate lower-level tasks (tokenization) to higher-level ones (parsing). For Indian languages, emphasize how morphology impacts every downstream step.