Tab 1

TITLE

SubTitle
Content.

SubTitle
Content.

SubTitle
Content.

SubTitle
Content.
NLP
NLP

NLP = linguistics + computer science (algorithms) + AI/ML​

​
Challenges in NLP
●​ Ambiguity: Words with multiple meanings.
●​ Context Understanding: Capturing long-range dependencies.
●​ World Knowledge: Lack of real-world reasoning.
●​ Multilinguality: Handling diverse languages.
●​ Data Scarcity: Limited labeled datasets.
●​ Bias: Inherited biases from training data.

Terms
●​ Corpus — A paragraph as our data; A large and structured set of texts used
for linguistic analysis and model training.
●​ Documents — Sentences as our data
●​ Vocabulary — Unique words present in the corpus
●​ Words — All words present in a corpus
Text Preprocessing
Text Preprocessing

Steps
Essential before converting text into numerical features:
1.​ Text Cleaning: We'll convert the text to lowercase, remove punctuation,
numbers, special characters and HTML tags.
2.​ Tokenization: Splitting the text into words.
3.​ Stop Words Removal: Removing common stop words from the tokens.
4.​ Stemming and Lemmatization: Reducing words to their base.
5.​ Handling Contractions: Expanding contractions in the text. (don’t to do not)
6.​ Handling Emojis and Emoticons: Converting emojis to their textual
representation.
7.​ Spell Check: Correcting spelling errors in the text.

Tokenization
●​ Tokenization is the process of breaking down a text into individual words or
tokens.
●​ These tokens are the building blocks for further analysis.
●​ 2 types:
○​ Word tokenizer - breaks corpus down into individual words
○​ Sentence tokenizer - breaks corpus down into individual sentences
●​ Example:
○​ Consider the sentence: “Natural Language Processing is amazing!”
○​ WordTokenization Result: [“Natural”,“Language”,“Processing”,“is”,
“amazing”, “!”]

○​ Consider the sentence: “Natural Language Processing is amazing! It

helps computers understand human language.”
○​ Sentence Tokenization Result :[“Natural Language Processing is
amazing!”, “It helps computers understand human language.”]

●​ Few more types:

○​ Character tokenization:
■​ Breaks a sentence into individual characters.
■​ Ex: Sentence: "Hi!" ; Tokens: ["H", "i", "!"]
○​ Subword Tokenization (used in modern NLP models like BERT, GPT):
■​ Splits rare or complex words into smaller, more common
sub-parts.
 ■​ Ex: Word: "unhappiness"; Tokens: ["un", "happi", "ness"]

Sentence Segmentation Challenges

Case Example Problem

Abbreviations "Dr.", "Mr.", "etc." Periods don’t always mark sentence ends.

Decimal "Price is $5.99." Period is part of a number, not sentence

Numbers boundary.

Ellipses "So... what now?" Multiple periods may confuse segmentation.

Quotations "He said, 'Let’s go.'” Sentence ends inside quotes, hard to detect.

Multiple Hindi-English mix Rules differ across languages, complicating

Languages boundary detection.

Stop Words
●​ Stop words are common words in a language (e.g., “the,” “is,” “and”) that
usually do not contribute significant meaning to text analysis.
●​ They are often removed during preprocessing in NLP tasks to reduce noise
and improve efficiency.
●​ Purpose of Removing Stop Words:
○​ To reduce the dimensionality of text data.
○​ To focus on meaningful words that contribute to understanding the
content.
○​ Speeds up algorithms by ignoring frequent but uninformative words.
●​ Process:
○​ Tokenization: Split the text into individual tokens (words or sub-words).
■​ Example: "The quick brown fox jumps over the lazy dog."
■​ Tokens: [“The”, “quick”, “brown”, “fox”, “jumps”, “over”, “the”,
“lazy”, “dog.”]
○​ Stop Word Removal: Filter out tokens that are considered stop words.
■​ Example after removal: [“quick”, “brown”, “fox”, “jumps”, ”over”
“lazy”, “dog.”]
●​ Examples of Stop Words: a, an, the, I, he, she, it, we, on, in, at, by, and, or, but,
is, am, are, was, were
●​ Important Notes:
 ○​ Stop word lists differ between libraries (e.g., NLTK, spaCy, Scikit-learn
each have their own list).
○​ Some tasks may retain stop words if they are important (e.g.,
sentiment analysis: “not happy” → removing “not” changes meaning).
○​ Stop words are language-dependent (English stop words differ from
Hindi, French, etc.).
●​ Applications where stop words are removed:
○​ Information retrieval (e.g., search engines).
○​ Text classification.
○​ Topic modeling.
●​ Applications where stop words are kept:
○​ Sentiment analysis.
○​ Question answering.
○​ Context-sensitive tasks.

Stemming
●​ Stemming is the process of reducing words to their root/base form (stem) by
stripping suffixes and prefixes.
●​ The stem may not always be a valid word in the language.
●​ Purpose:
○​ To group words with the same root meaning together.
○​ Reduces vocabulary size for NLP tasks.
○​ Improves efficiency in search, indexing, and text classification.
●​ Process:
○​ Example Input: "Running, runner, ran"
○​ After Stemming: [“run”, “runner”, “ran”]
●​ Examples of Stemming:
○​ CONNECT family:
■​ CONNECT
■​ CONNECTED
■​ CONNECTING
■​ CONNECTION
■​ CONNECTIONS
■​ → Stem: CONNECT
●​ Advantages:
○​ Reduces inflectional/derived forms to a single root.
○​ Helps in text normalization (standardizing words).
○​ Useful in Information Retrieval (IR) systems (search engines, indexing).
●​ Disadvantages:
 ○​ Over-stemming: Different words with different meanings reduced to
the same stem.
■​ Example: universe → univers, university → univers.
○​ Under-stemming: Words that should be grouped remain separate.
■​ Example: ran and run are not reduced to the same root in some
algorithms.
○​ The stem may not be a valid dictionary word (e.g., happi, histori).
●​ Applications:
○​ Search engines (to match “connect” with “connected”).
○​ Text mining and indexing.
○​ Topic modeling.

Lemmatization
●​ Lemmatization is the process of reducing words to their base/dictionary form
(lemma).
●​ Unlike stemming, the lemma is always a valid word.
●​ It uses morphological analysis + vocabulary/dictionary to return the correct
root form.
●​ Purpose:
○​ To normalize words into their proper dictionary headword.
○​ Ensures that all inflectional/variant forms are mapped to the same
lemma.
○​ Produces linguistically accurate results (better than stemming).
●​ Process:
○​ Example Input: "stepped, goes, loving, made, ate, went, eaten"
○​ Lemmatization Output: [“step”, “go”, “love”, “make”, “eat”, “go”, “eat”]
●​ Examples:
○​ am, are, is → be
○​ cars, car’s, cars’ → car
○​ Sentence: “the boy’s cars are different colors”
■​ After Lemmatization → “the boy car be different color”
●​ Techniques/Tools:
○​ WordNet Lemmatizer (NLTK).
○​ spaCy Lemmatizer (built-in with POS tagging).
●​ Advantages:
○​ Produces valid words (linguistically correct).
○​ Handles irregular words properly (ate → eat, went → go).
○​ Better accuracy for tasks requiring semantic meaning.
●​ Disadvantages:
○​ Computationally more expensive than stemming.
 ○​ Requires POS (Part-of-Speech) tagging for best accuracy.
○​ Slower for large text datasets.
●​ Applications:
○​ Sentiment analysis.
○​ Machine translation.
○​ Chatbots & search engines (accurate query matching).
○​ Any NLP task where meaning and grammar are important.

Stemming vs Lemmatization

Aspect Stemming Lemmatization

Definition Reduces words to their root Reduces words to their

form by chopping off base/dictionary form (lemma)
prefixes/suffixes (rule-based). using linguistic analysis.

Output Validity May produce non-dictionary Always produces valid words

words (e.g., history → histori, (e.g., history → history, happy →
happy → happi). happy).

Accuracy Less accurate, crude cutting of More accurate, linguistically

words. correct.

Speed Faster, lightweight. Slower, computationally

expensive.

Need for POS No need for POS tagging. Often requires POS tagging for
Tagging correctness.

Examples “studies, studying, studied” → “studies, studying, studied” →

“studi” “study”

Applications Quick text preprocessing, Tasks needing semantic

search indexing, IR systems. meaning: sentiment analysis,
machine translation, chatbots.

Text Normalization

Normalization: It is the process of transforming text into a standard,

consistent format for better processing and analysis.
Common Normalization Steps:

1.​ Lowercasing
○​ "NLP is FUN" → "nlp is fun"
2.​ Removing Punctuation
○​ "hello!" → "hello"
3.​ Removing Stopwords
○​ "I am happy" → "happy"
4.​ Stemming/Lemmatization
○​ "running", "ran" → "run"
5.​ Expanding Contractions
○​ "can't" → "cannot"
6.​ Handling Spelling Variations
○​ "color" ↔ "colour"

Why It’s Needed:

●​ Reduces variation in text

●​ Improves model accuracy
●​ Prepares data for further NLP tasks
 Popular NLP Libraries
Library Key Features Best Used For

WordNet Provides synonyms, antonyms, Lexical semantics,

hypernyms, hyponyms; word synonym/antonym lookup, word
relations relations

NLTK Tokenization, POS tagging, Educational projects,

stemming, corpora, parsers, learning/classic NLP tasks
simple models

spaCy Fast, accurate NLP pipelines; Industrial-grade NLP pipelines,

built-in tokenization, POS tagging, production use
NER
Hugging Face Large collection of pretrained Deep NLP tasks: text
(Transformers) transformer models (BERT, GPT, classification, summarization,
etc.); easy fine-tuning translation, Q&A

Stanford NLP Neural pipeline, support for Advanced academic research,

(CoreNLP / multiple languages, advanced multi-language NLP, NER
Stanza) NER, parsing
Text Representation
Text Representation

Need
●​ Text data is unstructured.
●​ Machine learning and deep learning models require numerical feature
vectors.
●​ Representation methods convert text into numbers while preserving
important information.

Bag-of-Words (BoW)
●​ Represents a document as a "bag" of its words, disregarding grammar and
word order.
●​ Only word counts matter.
●​ Steps:
○​ Build a vocabulary from the corpus (unique words).
○​ Represent each document as a vector of word counts.
●​ Example:
○​ Corpus = {“the dog barks”, “the cat meows”}
○​ Vocabulary = [“the”, “dog”, “barks”, “cat”, “meows”]
○​ Doc1: [1, 1, 1, 0, 0]
○​ Doc2: [1, 0, 0, 1, 1]
●​ Advantages:
○​ Simple, easy to implement.
○​ Works well for small datasets.
●​ Limitations:
○​ Ignore grammar and word order.
○​ Leads to sparse vectors (high dimensionality).
○​ Cannot capture word importance across documents.

TF-IDF (Term Frequency – Inverse Document Frequency)

●​ Enhances BoW by weighing words based on frequency in a document and
rarity across documents.
●​ Helps reduce the importance of common words (like the, is, and).
●​ Formula:
 ○​ TF(w, d) = (Number of times word w appears in document d) / (Total
words in document d)
○​ IDF(w) = log( (Total number of documents) / (Number of documents
containing w) )
○​ TF-IDF(w, d) = TF(w, d) × IDF(w)
●​ Example:
○​ If the word “cat” appears frequently in one document but rarely across
others, it will have a high TF-IDF score.
○​ If the word “the” appears in almost every document, it will have a low
TF-IDF score.
●​ Advantages:
○​ Captures importance of terms across documents.
○​ Reduces weight of common words.
○​ More informative than plain BoW.
●​ Limitations:
○​ Still ignores word order and semantics.
○​ Produces sparse vectors for large corpora.
Zipf’s Law
Zipf’s Law
●​ Zipf’s Law is an empirical law describing how word frequencies are
distributed in a language corpus.
●​ It states that the frequency of any word is inversely proportional to its rank
in the frequency table.

Mathematical Expression

f(r) ∝ 1/(r ** s)​)

Where:

●​ f(r) → Frequency of the word ranked at position r

●​ r → Rank of the word (most frequent = rank 1)
●​ s → A constant, typically close to 1 for natural languages

Interpretation

●​ The most frequent word (rank 1) appears twice as often as the 2nd most
frequent, three times as often as the 3rd, etc.
●​ When you plot log(rank) vs log(frequency) → you get an approximate
straight line with a negative slope, showing a power-law distribution.

Example

Word Rank (r) Frequency (f) f × r (≈ constant)

the 1 1000 1000

of 2 500 1000

and 3 333 ~999

language 10 100 ~1000

Why Important

Aspect Relevance

Stopword High-frequency words (like the, and, is) carry low semantic
Removal value → often removed.

Rare Word Very low-frequency words cause data sparsity → need

Handling smoothing or subword models.

Corpus A small fraction of vocabulary accounts for most text → helps in

Compression optimizing storage and computation.

Language Understanding long-tail word distributions improves

Modeling probabilistic models and vocabulary design.
Language Models
 Language Models
A Language Model assigns a probability to a sequence of words — helping predict
what word (or phrase) is likely to come next, or how likely a sentence is in a given
language.

Example
Given: "The cat sat on the"
Predicted: "mat"

Goals of Language Models

●​ Predict the next word in a sentence
●​ Estimate the likelihood of a full sentence
●​ Assist in various NLP tasks:
○​ Machine Translation
○​ Speech Recognition
○​ Autocomplete & Chatbots
○​ Spelling Correction

Types of NLP Language Models

Type Description Example Algorithm

Rule-based Uses fixed linguistic rules or CFG (Context-Free Grammar),

templates POS rules

Statistical Relies on word co-occurrence and N-gram models

probabilities

Neural Learns word dependencies using RNN, LSTM, BERT

neural networks

Transformer - Trained on large datasets, GPT, BERT, RoBERTa

based fine-tuned for tasks
Probabilistic Formulation

Using the Chain Rule of Probability:​

For a sentence W=w1,w2,…,wn​

​
This gives the overall probability of the sentence.
N-Gram Models
N-Gram Models
An N-Gram is a continuous sequence of N words used for approximating the chain
rule efficiently.
Since full context is impractical, we assume:

Types of N-Grams

Model Example Sentence:​ Approximation Used Interpretation

“I love NLP”

Unigram “I”, “love”, “NLP” P(wi​) Each word is

(N=1) independent

Bigram (“I love”), (“love NLP”) P(wi | wi−1​) Depends on

(N=2) previous word

Trigram (“I love NLP”) P(wi ​| wi−1​,wi−2​) Depends on

(N=3) previous 2 words

Example Calculation
For Bigram model on sentence: “I love NLP”

Applications
●​ Predictive text & autocomplete
●​ Machine translation
●​ Speech recognition
●​ Text generation
Formula and Numerical

​
​
Content.
Unstructured Data & Feature Selection
Unstructured Data & Feature Selection

Unstructured Data
●​ Data without a predefined model or schema (unlike relational databases or
CSVs).
●​ Often consists of free-form text, images, videos, or audio.
●​ In NLP, this mainly refers to textual data (emails, tweets, articles, reviews,
etc.).
●​ Examples:
○​ Social media posts (Twitter, Reddit, Instagram captions)
○​ Customer reviews and feedback
○​ News articles, research papers
○​ Chat transcripts or emails
○​ Web pages and scraped HTML content
●​ Key Challenges:
○​ No fixed structure: Data comes in variable formats (sentences,
symbols, emojis, HTML tags).
○​ High dimensionality: Large vocabulary size → huge feature space.
○​ Noisy content: Spelling errors, emojis, URLs, abbreviations.
○​ Mixed formats: May include multiple languages or encoding issues.
●​ Common Sources:
○​ Plain Text - .txt documents, logs
○​ PDFs - Reports, scanned content
○​ HTML/XML - Web pages, scraped data
○​ JSON - API data (social media, chatbots)
○​ DOCX - Word documents

Techniques for Handling Raw Text Data

●​ Tokenization: Splitting sentences into words or tokens.
●​ Named Entity Recognition (NER): Detects entities like names, dates,
organizations.
●​ Sentiment Analysis: Detects opinions, emotions (positive/negative/neutral).
●​ Part-of-Speech (POS) Tagging: Identifies grammatical roles (noun, verb,
adjective).
Machine Learning Applications on Text
●​ Text Classification: Categorizing documents (e.g., spam vs. not spam, topic
detection).
●​ Topic Modeling: Automatically discovering hidden topics (LDA, NMF).
●​ Pattern Recognition: Detecting recurring phrases or linguistic structures.
●​ Clustering: Grouping similar documents (K-Means, hierarchical clustering).

Role of Large Language Models (LLMs)

●​ Context Understanding: Capture relationships between distant words or
sentences.
●​ Complex Query Processing: Can answer specific questions from long
documents.
●​ Multi-format Output: Convert text into structured data (tables, summaries,
JSON).
●​ Domain Adaptation: Learn specialized vocabulary for industries (medical,
legal, finance).

Text Embeddings (Feature Representation)

Word Embeddings (Static)
●​ Represent each word as a dense vector capturing semantic meaning.
●​ Similar words → similar vector representations.
Popular Methods:
●​ Word2Vec:
○​ CBOW: Predict current word from context.
○​ Skip-Gram: Predict surrounding words from current word.

Feature CBOW (Continuous Skip-gram

Bag-of-Words)

Primary Goal Predicts the target Predicts the surrounding

(center) word from its context words from the
surrounding context target (center) word.
words.

Analogy "Fill-in-the-blank" "Word association"

 Input & Output Input: Multiple context Input: One target word.
words. Output: One target Output: Multiple context
word. words.

Training Speed Faster. It has a simpler Slower. It has a more

prediction task. complex prediction task.

Performance Generally performs better Can be less efficient for

with Frequent and is more efficient with very frequent words.
Words words that appear often.

Performance May not represent rare Excellent at learning

with Infrequent words as effectively representations for rare
Words because it averages the words and phrases.
context.

Quality of Good for capturing Often results in higher

Embeddings syntactic relationships quality semantic
(e.g., grammar). embeddings (captures
meaning).

Dataset Size Can work well with Benefits more from larger
smaller datasets. datasets to learn context
effectively.

●​ GloVe: Learns from global word co-occurrence statistics.

●​ FastText: Uses subword information, handles out-of-vocabulary (OOV) words
better.

Contextual Embeddings (Dynamic)

●​ The meaning of a word depends on the context in the sentence.
●​ Generated using transformer-based models.
Examples:
●​ BERT – Bidirectional understanding of context.
●​ RoBERTa – Optimized BERT version with more training.
●​ GPT – Predictive model for text generation.

Key Use: These embeddings enable context-aware NLP — vital for chatbots,
translation, summarization, etc.
Laplace Smoothing
Laplace Smoothing

Problem with N-Grams

●​ Data Sparsity: Many word sequences never occur in the training corpus.
●​ Zero Probability Issue:
○​ Example:
■​ Corpus: "the dog barks"
■​ Vocabulary: [the, dog, barks, cat]
■​ Compute P(cat | the) → "the cat" never occurred → probability = 0

Laplace (Add-One) Smoothing

●​ Goal: Prevent zero probabilities for unseen n-grams.

Insight:
●​ Even unseen valid phrases like "the cat" now get a small probability instead
of 0.
●​ This helps the model generalize better to unseen text.
SubTitle
Content.

SubTitle
Content.
Evaluation Metrics in NLP
Evaluation Metrics in NLP
Evaluation metrics quantify how well NLP models perform. Different tasks require
different metrics:
●​ Machine Translation / Text Generation: BLEU, ROUGE
●​ Language Modeling: Perplexity
●​ Text Classification / NER / Sentiment Analysis: Accuracy, Precision, Recall, F1
Score

BLEU (Bilingual Evaluation Understudy)

●​ Measures the quality of machine-translated or generated text by comparing
n-grams with human reference text.
●​ Focuses on precision of n-grams.
●​ Includes Brevity Penalty (BP) to penalize overly short candidates.

●​ Where:
○​ pi = precision for each n-gram
○​ wi = weight assigned to each n-gram (usually equal, sum = 1)
○​ BP = Brevity Penalty
Perplexity
●​ Measures how well a probabilistic language model predicts a sequence.
●​ Lower perplexity → better prediction.

●​ Interpretation:
○​ Perplexity = 1 → perfect prediction
○​ Perplexity = 10 → model considers 10 equally likely options at each step
Classification Metrics
●​ True Positive (TP): Correctly predicted positive
●​ True Negative (TN): Correctly predicted negative
●​ False Positive (FP): Incorrectly predicted positive
●​ False Negative (FN): Incorrectly predicted negative

Formulas

1.​ Accuracy: Accuracy = (TP + TN) / (TP + TN + FP + FN​)

2.​ Precision: Precision = TP / (TP + FP)
3.​ Recall (Sensitivity): Recall = TP / (TP + FN)
4.​ F1 Score: F1 = 2 * (Precision * Recall / Precision + Recall)
POS Tagging
POS Tagging
●​ The process of assigning each word in a sentence its grammatical category
— such as noun, verb, adjective, adverb, pronoun, preposition, etc.
●​ Example:
○​ Sentence: “The quick brown fox jumps over the lazy dog.”
○​ Tags:
■​ The → Determiner (DT)
■​ quick → Adjective (JJ)
■​ brown → Adjective (JJ)
■​ fox → Noun (NN)
■​ jumps → Verb (VBZ)
■​ over → Preposition (IN)
■​ the → Determiner (DT)
■​ lazy → Adjective (JJ)
■​ dog → Noun (NN)

Purpose
●​ Helps in understanding sentence structure and meaning
●​ Useful in parsing, NER, sentiment analysis, machine translation, etc.

Challenges / Ambiguity
●​ Same word can have multiple POS depending on context
○​ “Like” → Verb (“I like Lakshya”)
○​ “Like” → Preposition (“He looks like Lakshya”)
●​ Context and surrounding words decide the correct tag.

Approaches

Type Description

Rule-based Uses handcrafted linguistic rules and dictionaries

Statistical Uses probabilistic models to assign most likely tag based on context

Neural Uses deep learning (context-aware embeddings) for tagging

Ambiguity

Type of Description Example Explanation

Ambiguity Sentence

Lexical A single word can I can swim. / Pass “Can” is a verb in the
Ambiguity belong to multiple parts me the can. first case and a noun
of speech depending on in the second.
context.

Syntactic The structure of the They are flying Could mean “planes
Ambiguity sentence allows planes. that are flying”
multiple possible POS (noun phrase) or
taggings or “people who are
interpretations. flying planes” (verb
phrase).

Semantic Even if POS tags are He saw her duck. “Duck” could be a
Ambiguity clear, meaning can still noun (bird) or a
be ambiguous. verb(action).

SubTitle
Content.

SubTitle
Content.

SubTitle
Content.
Parameter Estimation in NLP
 Parameter Estimation in NLP
●​ In NLP, parameters are the numerical values a model uses to make
predictions or decisions.
●​ Example: In a language model, parameters represent probabilities of one
word following another.

Purpose
●​ Parameter Estimation → The process of determining optimal parameter
values that make the model accurately:
○​ Understand text
○​ Generate text
○​ Translate text

Importance
●​ The accuracy and fluency of an NLP model depend on how well parameters
are estimated.
●​ Better parameter estimation → More human-like understanding and
generation of language.

Main Techniques

Technique Concept How It Works Example / Formula

Maximum Finds parameters 1️⃣ Collect large text data. 2️⃣ P(w∣wprev​) =
Likelihood that maximize the Count how often each word Count(wprev​,w)​/
Estimation likelihood of or sequence occurs. 3️⃣ Count(wprev​)
(MLE) observing the Estimate probabilities using
given data. observed frequencies.

Bayesian Updates 1️⃣ Start with prior (initial P(θ∣data) =

Estimation probabilities by assumption about (P(data∣θ)⋅P(θ)​) / P(data)
combining prior parameters). ​
beliefs with 2️⃣ Collect text data. ​
observed data 3️⃣ Use Bayes’ Theorem to
compute posterior
 using Bayes’ distribution (updated
Theorem. belief).

Key Difference Between MLE and Bayesian

Aspect MLE Bayesian Estimation

Prior Knowledge Does not use prior beliefs Uses prior beliefs before data

Result Single best estimate (point Distribution over possible

estimate) parameters (posterior)

Flexibility Simpler, faster More robust, handles uncertainty

Use Case Large datasets Small or uncertain data scenarios

Example (MLE):
Suppose your corpus has:
Count("the dog") = 50
Count("the") = 100
Then,

Key Takeaways
●​ MLE → Relies purely on observed data.
●​ Bayesian Estimation → Combines prior beliefs + observed data.
●​ Both are foundational for training NLP models, especially language models
and probabilistic parsers.

SubTitle
Content.
SubTitle
Content.

SubTitle
Content.
Morphology
 Morphology
●​ Morphology is the branch of linguistics that studies the internal structure of
words and how they are formed from smaller meaning-bearing units called
morphemes.
●​ Example:
○​ unhappiness → un- (not) + happy (root) + -ness (makes it a noun)
○​ Morphology studies how these building blocks combine to create
meaning.

Morpheme
●​ Definition: Smallest unit of meaning in a language.
●​ Cannot be broken down further without losing meaning.
●​ Example:
○​ cats = cat (root) + -s (plural marker)

Affix
A morpheme attached to a root or stem to create a new word or alter grammatical
meaning.
Type Position Example Effect

Prefix Beginning of a word un- + happy → unhappy Changes meaning

Suffix End of a word happy + -ness → happiness Changes word form or class

Infix Middle of a word abso-freaking-lutely Rare in English; expressive emphasis

Types of Morphemes
Morphemes are divided into two main categories: Free and Bound.

Free Morphemes
Can stand alone as a complete word.
Two subtypes:
Subtype Description Examples
 Lexical Carry the core meaning of a run, book,
Morphemes sentence happy, table

Functional Provide grammatical the, and, she,

Morphemes structure and relations in, it

Bound Morphemes
Cannot stand alone. Must attach to a free morpheme.
Includes all affixes.
Two main types:
Subtype Function Effect Examples

Inflectional Add grammatical information Don’t change word -s (cats), -ed

Morphemes (tense, number, possession, class or core (walked), -ing
comparison) meaning (running), -er
(faster)

Derivational Create new words or alter part Often change word un- (unkind), -ness
Morphemes of speech class and meaning (happiness), -er
(teacher)

Inflectional vs Derivational Morphemes

Feature Inflectional Morpheme Derivational Morpheme

Purpose Adds grammatical info (tense, Creates a new word or meaning

number, etc.)

Changes Word ❌ No ✅ Often yes

Class?

Number in English Limited to 8 suffixes Unlimited (open set)

Position Always a suffix Prefix or suffix

Example book → books friend → friendly

Meaning Change Minimal (grammatical) Significant (semantic or

syntactic)
The 8 Inflectional Morphemes in English:
1.​ -s → plural (cat → cats)
2.​ -’s → possessive (girl → girl’s)
3.​ -s → 3rd person singular (run → runs)
4.​ -ed → past tense (walk → walked)
5.​ -en → past participle (eat → eaten)
6.​ -ing → present participle (run → running)
7.​ -er → comparative (fast → faster)
8.​ -est → superlative (fast → fastest)

Importance of Morphology in NLP:

●​ Improves tokenization and stemming accuracy
●​ Helps in POS tagging and lemmatization
●​ Aids in language translation and speech recognition
●​ Useful for morphological analysis in low-resource languages

SubTitle
Content.

SubTitle
Content.

SubTitle
Content.
Named Entity Recognition
Named Entity Recognition
●​ Named Entity Recognition (NER) is the process of identifying and classifying
key elements (named entities) in text into predefined categories such as:
●​ Person names
●​ Organizations
●​ Locations
●​ Dates, times, monetary values, percentages, etc.
●​ Example:
○​ Sentence: Apple was founded by Steve Jobs in California in 1976.
○​ NER Output:
■​ Apple → Organization
■​ Steve Jobs → Person
■​ California → Location
■​ 1976 → Date

Main Task
●​ Entity Detection: Identify which words or phrases are entities.
○​ e.g., detecting "Barack Obama" as one entity.
●​ Entity Classification: Assign a label to each detected entity.
○​ e.g., "Barack Obama" → Person.

Approaches

Approach Description Examples/Techniques

Rule-based Uses manually crafted rules and Example: Capitalized

(Linguistic) patterns (regular expressions, words after “Mr.” likely →
lexicons). Person

Statistical / Uses features from text (POS tags, HMM, CRF, MaxEnt
Machine capitalization, neighboring words) to models
Learning train models.

Deep Learns contextual patterns BiLSTM-CRF, BERT-based

Learning-based automatically using embeddings. NER
Challenges

Challenge Description

Ambiguity “Apple” can be a fruit or a company.

Context Dependence “Jordan” could be a person or a

country.

Abbreviations and “UN” vs “United Nations”

Variations

Multilingual Texts Same entity in different languages.

New Entities Constantly emerging names, brands, or

slang.

SubTitle
Content.

SubTitle
Content.

SubTitle
Content.

SubTitle
Content.
Tab 15
* Do everything that we did for MST, refer MST paper for questions practice. Numericals will be
mostly from same topics as asked in MST.
* Numerical from Parsing.
* Theory: MST topics + Hidden Markov, Markov model, Parsing, Machine translation, lesk
algorithm, WSD. Mainly all those sir taught or mentioned in class. Nothing out of that.

Same Important as We have in MTT(All) problems,theory and diverse problems. DFA,FSA,

Regular expression, Zipf law,etc Information Extraction, Markov and hidden Markov model
Parsing techniques, Types ,Context free Grammer, Problems based on parsing, SR parser chart
parser etc. word sense disambiguation, Lesk Algorithm in detail.
Machine Translation in detail, types etc.
Hidden Markov Models
Hidden Markov Models

Markov Chains
●​ Hidden Markov Models are based on Markov Chains.
●​ A Markov Chain is a probabilistic model that represents sequences of random
variables (states).
●​ Each state can take values from a finite set, such as:
○​ Words
○​ Part-of-Speech (POS) tags
○​ Symbols (e.g., weather: sunny, rainy)
●​ The model assigns probabilities to sequences of states.

Key Idea
●​ A Markov chain predicts the future state based only on the current state, not
the entire history.

Markov Assumption
The Markov Assumption states that:
●​ The probability of a state depends only on the immediately preceding state.

Formally:
This assumption simplifies computation by reducing dependency on long histories.

Markov Chain (Formal Definition)

A Markov chain is defined by the following components:

1.​ Set of states

○​ Q={q1,q2,...,qN}
2.​ Initial state distribution
○​ πi=P(q1=i)
3.​ Transition probabilities
○​ aij=P(qj∣qi)
○​ Probability of moving from state i to state j

Hidden Markov Models (HMM)

A Hidden Markov Model extends a Markov chain by introducing:
●​ Hidden states (e.g., POS tags)
●​ Observed outputs (e.g., words)

Example (NLP)
●​ Observed: words in a sentence
●​ Hidden: corresponding POS tags

Assumptions in HMM
1.​ State Transition Assumption
○​ The probability of the current state depends only on the previous state:

○​
2.​ Output Independence Assumption
○​ The probability of an observation depends only on the current state:
HMM Components

An HMM is defined by:

1.​ States (Q)

○​ Hidden states (e.g., noun, verb, adjective)
2.​ Observations (O)
○​ Visible outputs (e.g., words)
3.​ Initial state probabilities (π)
○​ Probability of starting in a particular state
4.​ Transition probabilities (A)
○​ aij=P(qj∣qi)
5.​ Emission probabilities (B)
○​ bi(o)=P(o∣qi)

Viterbi Algorithm
●​ The Viterbi Algorithm finds the most likely sequence of hidden states given a
sequence of observations.
●​ It is a dynamic programming algorithm.

Step 1: Initialization

●​ Define:
○​ States
○​ Initial probabilities (π)
○​ Transition probabilities (A)
○​ Emission probabilities (B)
Step 2: Initialize the Viterbi Matrix

●​ Create a matrix to store:

○​ The highest probability of reaching each state at each time step.

Step 3: Initialize the Backpointer Matrix

●​ Create a backpointer matrix to:

○​ Store the state that led to the maximum probability.

Step 4: Recursion

For each observation from time step 2 to T:

●​ For each state:

○​ Compute: Vt(j)=max⁡i(Vt−1(i)×aij)×bj(ot​)
●​ Store:
○​ Maximum probability in the Viterbi matrix
○​ Corresponding state in the backpointer matrix

Step 5: Termination

●​ Select the state with the highest probability in the last column of the Viterbi
matrix.

Step 6: Backtracking

●​ Starting from the final state:

○​ Trace back using the backpointer matrix
○​ Retrieve the most probable sequence of hidden states

Comparison between Markov Model (MM) and Hidden Markov Model (HMM)

Aspect Markov Model (MM) Hidden Markov Model (HMM)

Nature of states States are directly States are hidden (not directly
observable observable)

Observations State itself is the Observations are generated from

observation hidden states
Output No separate output Has an emission/output probability
generation model model

Probability P(stateᵢ | stateᵢ₋₁) P(stateᵢ | stateᵢ₋₁) and P(observationᵢ |

defined as stateᵢ)

Components Transition probabilities Transition + emission + initial

+ initial probabilities probabilities
only

Sequence Models sequence of Models sequence of observations via

modeling states hidden states

Complexity Simpler More complex

Training Easier Computationally intensive

Typical Simple state Forward, Backward, Viterbi,

algorithms transitions Baum-Welch

Handling Limited Handles uncertainty and noise well

uncertainty

Usage in NLP Rare Widely used

Example Weather transitions POS tagging, speech recognition

application

Example Sunny → Rainy → Noun → Verb → Noun producing

Cloudy words
Machine Translation (MT)
1. Introduction to Machine Translation
●​ Rapid growth in global communication and digital content has increased:
○​ Demand for translation services
○​ Interest in computerized translation technologies
●​ Machine Translation (MT) has existed since the late 1950s
●​ Initially considered largely experimental
●​ Industry observers now suggest MT is commercially viable
●​ First MT system was demonstrated in 1954

2. Definition of Machine Translation

Machine Translation (MT) is a subfield of Natural Language Processing
(NLP) that deals with the automatic translation of text or speech from
one natural language (source language) to another (target language)
using computers.

3. NLP and Machine Translation

Natural Language Processing (NLP)

●​ A sub-domain of Artificial Intelligence

●​ Concerned with developing programs that:
○​ Possess some capability of understanding natural language
○​ Achieve specific goals such as:
■​ Translation
■​ Summarization
■​ Question answering

4. Understanding in NLP
Definition
Understanding in NLP is defined as:

●​ A transformation from:
○​ Input text (human language)
○​ To an internal representation (vectors, trees, symbols)

Why Internal Representation?

It enables the system to:

●​ Reason
●​ Translate
●​ Perform further language processing

NLP understanding ≠ human understanding​

It means converting text into a machine-processable form.

5. Historical Perspective of MT
●​ One of the oldest dreams of:
○​ NLP
○​ Artificial Intelligence
○​ Computer Science
●​ Continuous research since 1954
●​ Accuracy and usability have steadily improved

6. Objectives of Machine Translation

●​ Reduce human effort in translation
●​ Enable cross-lingual communication
●​ Support global information exchange
●​ Assist multilingual applications:
○​ Web platforms
○​ Social media
○​ Education
○​ Business
 7. Why Machine Translation?
●​ Provides cheap and fast translation
●​ Enables universal access to:
○​ Online information
○​ Content written in different languages
●​ Overcomes language barriers
●​ Ultimate goal:​
Access to information regardless of the original language

8. Interest in Machine Translation

8.1 Commercial Interest

●​ Heavy commercial and government investment

●​ United States invested significantly in MT research
●​ MT is widely used on the web (search engines, translators)
●​ European Union spends over $1 billion annually on translation
●​ Growth of semi-automated translation systems:
○​ Human + machine collaboration
○​ Faster and cheaper translations

8.2 Academic Interest

●​ MT poses challenging research problems

●​ Requires knowledge from multiple NLP sub-areas:
○​ Lexical semantics
○​ Parsing (syntax)
○​ Statistical modeling
○​ Morphological analysis
○​ Language modeling
●​ Enables resource transfer:
○​ From resource-rich to low-resource languages

9. Problems / Issues in Machine Translation

Despite progress, MT faces many challenges.

9.1 Lexical Ambiguity (Word Meaning Problem)

●​ A word can have multiple meanings

●​ Meaning depends on context

Example:

●​ Bank → river bank / financial bank

9.2 Structural Ambiguity (Sentence Structure Problem)

●​ Same grammatical structure, different meanings

Example:

“I saw the man with a telescope.”

●​ Meaning 1: I used a telescope

●​ Meaning 2: The man had a telescope

9.3 Syntactic Irregularity

●​ Natural languages often break fixed grammar rules

●​ Different languages follow different structures

9.4 Word Order Differences

●​ Languages use different word orders

●​ Example:
○​ English: SVO
○​ Hindi: SOV
 9.5 Idioms and Expressions

●​ Literal translation often fails

Example:

●​ “kick the bucket” → cannot be translated word-for-word

9.6 Morphological Complexity

●​ Some languages have:

○​ Many word forms
○​ Prefixes and suffixes
○​ Gender, tense, number variations

Example:

●​ Eat → Eating → Ate → Eaten

●​ Languages like Hindi, Tamil, Arabic are morphologically rich

9.7 Cultural & World Knowledge Problem

●​ Some meanings require real-world and cultural knowledge

Example:

“He is as brave as a lion.”

●​ Lion symbolizes bravery, not literal comparison

9.8 Context Influence

●​ Meaning depends on:

○​ Surrounding words
○​ Sentence structure
○​ Real-world knowledge
 9.9 Classic Ambiguity Examples
○​ Time flies like an arrow.
○​ Fruit flies like an apple.

●​ “flies” → verb / noun

●​ “like” → preposition / verb
○​ Get the cat with the gloves.

9.10 Evaluation Difficulty

●​ Translation quality is:

○​ Subjective
○​ Hard to measure automatically

10. Levels of Machine Translation

1.​ Word-level – Direct word-to-word mapping
2.​ Syntactic level – Grammar and structure
3.​ Semantic level – Meaning-based translation
4.​ Pragmatic level – Context and world knowledge

11. Translation Technology: Types of MT

There are four major approaches:

1.​ Direct Machine Translation

2.​ Rule-Based Machine Translation (RBMT)
3.​ Knowledge-Based Machine Translation (KBMT)
4.​ Statistical Machine Translation (SMT)​
(+ Neural Machine Translation – modern)

12. Direct Machine Translation

 Definition

●​ Simplest MT approach
●​ Translates word-to-word using a bilingual dictionary

Architecture
○​ Source Text → Dictionary Lookup → Target Text

Features

●​ No deep grammar analysis

●​ Minimal preprocessing

Advantages

●​ Simple
●​ Fast

Disadvantages

●​ Poor translation quality

●​ Cannot handle ambiguity

13. Rule-Based Machine Translation (RBMT)

Definition

●​ Uses linguistic rules and bilingual dictionaries

Types

1.​ Transfer-Based MT
○​ Analysis → Transfer → Generation
2.​ Interlingua-Based MT
○​ Language-independent representation

Components

●​ Morphological analyzer
●​ Syntactic parser
●​ Transfer rules
●​ Generator

Advantages

●​ Better grammatical accuracy

●​ Interpretable logic

Disadvantages

●​ Very expensive
●​ Language-pair specific
●​ Difficult to scale

14. Knowledge-Based Machine Translation

(KBMT)
Definition

●​ Uses meaning, concepts, and real-world knowledge

●​ Translation is meaning-based, not structure-based

Components

●​ Knowledge base (ontology)

●​ Semantic parser
●​ Inference engine

Advantages

●​ Handles ambiguity better

●​ High-quality translation

Disadvantages

●​ Very complex
●​ Huge knowledge base required
●​ Expensive and slow
 15. Statistical Machine Translation (SMT)
Definition

●​ Uses statistics and probability from large bilingual corpora

Basic Principle

●​ Find target sentence T that maximizes:

P(T∣S)

Training Data

●​ Parallel corpus
●​ Monolingual target corpus

SMT Models

●​ Word-based
●​ Phrase-based
●​ Syntax-based

N-gram Based Translation

●​ N-grams (usually 3 words)

●​ Reduce ambiguity
●​ Improve accuracy and fluency

SMT Architecture

●​ Lexicon system
●​ Alignment system
●​ Language system
●​ Global search
 Advantages

●​ Data-driven
●​ Automatic learning
●​ Better fluency

Disadvantages

●​ Needs large datasets

●​ Struggles with rare words
●​ Hard to interpret

16. Neural Machine Translation (NMT)

●​ Uses deep learning
●​ Encoder–Decoder architecture
●​ Transformer models
●​ Produces very natural translations
●​ Current state-of-the-art

17. Comparison

Approach Pros Cons

Direct Simple, fast Poor quality

Rule-based Grammatically accurate Expensive, slow

Knowledge-based Meaning-aware Very complex

Statistical Data-driven Needs large data

Neural Natural output Compute-heavy

 18. Current MT Systems in Use
●​ Google Translate – Statistical MT
●​ SYSTRAN – Rule-based
●​ AltaVista Babel Fish – Uses SYSTRAN
●​ Language Weaver – Statistical MT
●​ Microsoft Translator – Statistical MT

19. Personal Speech-to-Speech Translators

●​ Emerging MT research area
●​ Real-time spoken translation

Process

1.​ Speech → Text

2.​ Text → Translation
3.​ Text → Speech

IBM Mastor
●​ Hybrid statistical + knowledge-based
●​ Focuses on meaning
●​ Suitable for mobile devices

20. Future of Machine Translation

●​ Continuous demand for better MT
●​ More research funding
●​ Growth in:
○​ Commercial systems
○​ Hybrid approaches
○​ Speech-based translators
●​ MT becoming:
○​ More accurate
○​ More natural
○​ More accessible
Context Free Grammar
Context-Free Grammars (CFGs)

1. Syntax
Definition

●​ Syntax refers to the rules describing how words connect to each other to
form phrases and sentences.
●​ It captures the implicit knowledge of language that:
○​ Native speakers acquire naturally by age 3–4
○​ Without explicit grammar instruction
●​ It is different from school grammar rules

Examples (Grammaticality vs Meaning)

●​ I saw you yesterday ✅ (grammatical & meaningful)

●​ colorless green ideas sleep furiously✅ (grammatical but meaningless)
●​ *that and after year last ❌(ungrammatical)

➡️ Syntax is about structure, not meaning.

2. Why Should We Care About Syntax?

Syntax is essential for many NLP applications:

●​ Grammar checkers
●​ Question answering
●​ Information extraction
●​ Machine translation

3. Context-Free Grammar (CFG)

Purpose
CFGs are used to:

●​ Capture constituency
●​ Capture ordering of words and phrases

Constituency

●​ How words group into units (phrases)

●​ How these units behave as a whole

Examples of constituents:

●​ Sentence (S)
●​ Noun Phrase (NP)
●​ Verb Phrase (VP)
●​ Prepositional Phrase (PP)

Ordering

●​ Rules governing the order of words and phrases

●​ Example:
○​ English: Det + Noun
○​ Hindi: Noun + Postposition

4. CFG Example
S -> NP VP
NP -> Det NOMINAL
NOMINAL -> Noun
VP -> Verb
Det -> a
Noun -> flight
Verb -> left

➡️ These rules specify how sentences are built.

5. Why “Context-Free”?
●​ Rules apply independent of surrounding context
●​ Example:

A -> B C

Means:

●​ An A can always be rewritten as B C

●​ Regardless of where A appears

“Context” here does NOT mean real-world or linguistic context.

6. Interpretation of CFG Rules

Example:

S -> NP VP

This rule:

●​ Defines units called S, NP, VP

●​ Says S consists of NP followed by VP
●​ Does NOT say:
○​ This is the only kind of sentence
○​ NPs or VPs can appear only here

7. Generativity of CFGs
CFG rules can be seen as:

●​ Analysis machines
●​ Synthesis machines

They can:
 ●​ Generate valid strings
●​ Reject invalid strings
●​ Assign tree structures (parse trees) to strings

8. Parsing
Definition

●​ Parsing is the process of:

○​ Taking a string and a grammar
○​ Producing one or more parse trees

9. Why CFGs (and not others)?

●​ Regular languages → too weak
●​ Context-sensitive grammars → too powerful
●​ CFGs → good balance for natural language

10. Sentence Types in English

Declarative
A plane left
S -> NP VP

Imperative
Leave!
S -> VP

Yes–No Questions
Did the plane leave?
S -> Aux NP VP

WH-Questions
When did the plane leave?
S -> WH Aux NP VP

11. Conjunction
Examples:

S -> S and S
NP -> NP and NP
VP -> VP and VP

General rule:

X -> X and X

Example:

John went to NY and Mary followed him

12. Recursion in CFGs

Definition

●​ A rule where the same non-terminal appears on both sides

Examples:

NP -> NP PP
VP -> VP PP

Why Recursion Matters

●​ Allows infinite sentence construction

Example growth:
 ●​ Flights from Denver
●​ Flights from Denver to Miami
●​ Flights from Denver to Miami in February
●​ Flights from Denver to Miami in February on a Friday
●​ …

➡️ This is what makes natural language expressive.

13. Key Insight (Very Important)

Rule:

VP -> V NP

●​ Only cares that the verb is followed by an NP

●​ Does NOT care about internal structure of NP

Valid NPs:

●​ flights from Denver

●​ flights from Denver to Miami in February
●​ flights … with lunch

14. Problems with CFGs

CFGs tend to overgenerate (allow invalid sentences).

Main issues:

1.​ Agreement
2.​ Subcategorization
3.​ Movement

Problem What Goes Wrong Why CFGs Fail

Agreement Number/person mismatch No feature tracking

Subcategorization Wrong verb arguments All verbs treated alike

Movement Long-distance dependencies Only local structure allowed

15. Agreement Problem

Examples:

This dog eats

Those dogs eat

Incorrect:

*This dogs
*Those dog
*This dog eat
*Those dogs eats

➡️ CFG rules alone cannot enforce number agreement.

16. Subcategorization
Definition

●​ Constraints a verb places on:

○​ Number of arguments
○​ Type of arguments

Examples:

●​ sneeze → no object
●​ find → NP
●​ give → NP NP
●​ help → NP PP
●​ prefer → TO-VP
●​ tell → S

Incorrect:
*John sneezed the book
*I prefer United has a flight
*Give with a flight

Why CFGs Fail Here

Rule:

VP -> V NP

Allows:

Sneezed the book

➡️ Grammatically valid but semantically invalid.

Solution:

●​ Use subcategorization frames to restrict arguments.

17. Movement Problem

Base sentence:

My travel agent booked the flight

Question:

Which flight do you want me to have the travel agent book?

Issue:

●​ Object of book is far from the verb

●​ Separated by multiple verbs

➡️ CFGs struggle to model long-distance dependencies.

18. Formal Definition of CFG

A CFG consists of:

1.​ N – set of non-terminal symbols

2.​ T – set of terminal symbols
3.​ P – set of production rules: A -> α
○​ Where:
i.​ A ∈ N
ii.​ α ∈ (N ∪ T)*
4.​ S – start symbol

19. Grammar Equivalence

Strong Equivalence

●​ Same strings
●​ Same phrase structure

Weak Equivalence

●​ Same strings
●​ Different phrase structures

20. Normal Form

Chomsky Normal Form (CNF)

Rules must be:

A -> B C
A -> a

Any grammar can be converted to a weakly equivalent CNF.

Example:

A -> B C D
becomes
A -> B X
X -> C D

21. Tree Structures (Concept)

You should be able to draw parse trees for:

●​ Dallas
●​ from Denver
●​ arriving in Washington
●​ I need to fly between Philadelphia and Atlanta

(Usually NP / PP / VP based trees in exams.)

Using & Augmenting Context-Free
Grammars (CFGs)
Using & Augmenting Context-Free
Grammars (CFGs)

1. Motivation for Context-Free Grammars

●​ CFGs are a simple and flexible formalism to describe syntactic structure
●​ Main goal:
○​ Recover the hidden structure of natural language sentences
●​ Despite weaknesses, CFGs are widely used because:
○​ Efficient parsing algorithms exist (e.g., CYK algorithm)
●​ Fixing CFG weaknesses:
○​ Possible, but
○​ Makes the grammar more complex and less elegant

2. Context-Free Grammar Overview

A CFG consists of:

1. Lexical items (Terminals)

●​ Atomic symbols (cannot be decomposed)

●​ Represent actual words
●​ Written in lowercase
●​ Example: police, put, around

2. Constituent types (Non-terminals)

●​ Abstract syntactic categories

●​ Can be decomposed into other constituents
●​ Written in uppercase
●​ Example: S, NP, VP, N

3. Production rules
 ●​ Define how constituents are decomposed
●​ Correspond to one-level branches in a parse tree

4. Start symbol

●​ A distinguished constituent (usually S)

●​ Root of a complete parse tree

2.1 Parse Example

Grammar
S -> NP VP
NP -> N
VP -> V NP PrP
PrP -> Pr N

N -> police | barricades | Chandigarh

V -> put
Pr -> around

Sentence

“police put barricades around Chandigarh”

Key Properties of the Parse Tree

●​ Leaves (fringe) = original sentence

●​ All leaves are lexical items
●​ All internal nodes are valid constituents
●​ Root is S
●​ Every branch matches a grammar rule

3. Shortcomings of Context-Free Grammars

Although CFGs look elegant, they have serious limitations.
3.1 Agreement Mismatch
Problem

Adding:

V -> puts

Allows:

❌ police puts barricades around upson

●​ police → 3rd person plural
●​ puts → 3rd person singular
●​ → Agreement mismatch

3.1.1 Possible Solution: Feature Encoding

●​ Encode person & number into categories

●​ Examples:
○​ V-1-s → first person singular verb
○​ V-3-p → third person plural verb
●​ Example rule:

S -> NP-1-s VP-1-s

Drawback

●​ Category proliferation
●​ Grammar size increases by a constant factor
●​ Manageable alone, but problematic with other issues

3.2 Case Mismatch

Problem
Add:

N-3-p -> they

Allows:

❌ police put they around upson

Correct sentence:

✅ police put them around upson

●​ they → nominative (subject)
●​ them → accusative (object)

3.2.1 Possible Solution

●​ Encode case into grammar categories

●​ Works in English (few pronouns)
●​ But:
○​ Other languages have many cases
○​ Also gender, noun classes, etc.

➡️ Leads to explosive category growth

3.3 Other Problems

3.3.1 Sub-categorization Error

Add rule:

VP -> V NP

Allows:

❌ police put barricades

But:

●​ Verb put requires:

○​ Object
○​ Location (PP)

Solution Attempt

●​ Encode verb argument structure:

V-1-s-1-NP-arg

Drawbacks

●​ More category proliferation

●​ Duplicates information:
○​ In tree structure
○​ In category names

3.3.2 Selectional Violation

Example:

❌ barricades put upson around police

●​ Syntactically valid
●​ Semantically nonsense

Why?

●​ Verb put requires:

○​ Animate subject
○​ Concrete object

Problem Severity

●​ No fixed, small feature set

●​ Semantic constraints explode category space
●​ Much harder than agreement or case
3.4 Beyond Category Proliferation: Long-Distance
Dependencies
Example (Wh-movement)

what did police put around upson?

●​ Dependency between:
○​ what (front)
○​ missing object position after put

Invalid sentences:

❌ where did police put around upson?

❌ what did police put barricades around upson?
●​
●​

Failed CFG Fix

Add:

VP -> V PrP

Allows:

❌ police put around upson

Trace Idea

Structure:

VP
V
NP (trace)
PrP

●​ NP is phonologically null
●​ Must be linked to WH-word
❌ CFG cannot enforce this linkage

4. Feature-Based CFGs with Unification Constraints

Motivation

Fix:

●​ Category proliferation
●​ Long-distance dependencies

Key Ideas

●​ Encode linguistic properties as features, not categories

●​ Use Attribute-Value Matrices (AVMs)
●​ Use unification constraints to enforce compatibility

Feature Example: Verb “notify”

Important Features

●​ CAT → category (V)

●​ ORTH → spelling
●​ HEAD → features passed upward
●​ SUBCAT → argument requirements
●​ RESTRICT → selectional restrictions
●​ AGREEMENT → person & number

Meaning

●​ Subject must be animate

●​ First argument:
○​ NP
○​ Animate
●​ No second argument
●​ Verb is 3rd person plural
Unification Constraints (Example)
Rule:

VP -> V NP

Constraints:

●​ VP inherits HEAD of V
●​ V expects NP as first argument
●​ V expects only one argument
●​ NP must be accusative

Why Important

●​ Avoids agreement, case, and sub-cat errors

●​ Maintains XP regularity
●​ No need for decorated categories

Unification Explained Simply

●​ Combine feature structures
●​ Must not conflict

Example:

●​ [PERSON 1] + [NUMBER singular] → ✅

●​ [PERSON 1] + [PERSON 3] → ❌

Long-Distance Dependencies with GAPINFO

●​ WH-phrase propagated via feature (e.g., GAPINFO)
●​ Enables:

✅ whom did police notify?

 ●​ Solves what CFGs cannot

5. Questions Summary
5.1 Tense Errors

●​ Adding tense rules causes sub-categorization errors

●​ Treating “will” as auxiliary reduces errors
●​ Still not perfect → needs features

5.2 Punctuation in Grammar

Key Insight

●​ Commas create lists

●​ Items in a list must have same constituent type

Example:

runs, bikes, and swims

Feature-Based Solution

●​ Treat lists like linked structures

●​ Use NEXT feature (like linked list)
●​ Enforce consistency via unification

⚠️ Still open research problem (mixed verb types)

5.3 Practicality of CFGs (Conceptual)

●​ Real language includes errors
●​ We must:
○​ Allow parsing of incorrect sentences
○​ Still recover meaningful structure
●​ Solution:
○​ Soft constraints
○​ Probabilistic or weighted grammars
○​ Feature-based relaxation
Word Sense Disambiguation (WSD)
Word Sense Disambiguation (WSD)
🔹 What is WSD?
Word Sense Disambiguation is the task of finding the correct meaning (sense) of
a word based on its context.

Many words have multiple meanings, and the computer must choose the right one.

🔹 Problem Definition (In Simple Terms)

WSD tries to find:

●​ The correct sense of

○​ a specific target word, or
○​ all words in a sentence (harder)

By using:

●​ A sense repository
○​ Dictionary / WordNet
●​ Or a thesaurus
○​ Contains synonyms, but no semantic relations

And using:

●​ The context in which the word appears

🔹 Example: Word “operation”

The word operation has many meanings:

Sense Meaning Example

Computer science A computing instruction millions of operations/sec

Military Army action military operation

Medical Surgery undergo an operation

Mathematics Calculation arithmetic operations

👉 Context tells us which meaning is correct

Approaches to WSD
1️⃣ Knowledge-Based Approaches
●​ Use WordNet, dictionaries, thesaurus
●​ Use:
○​ Grammar rules
○​ Hand-written rules
●​ No training data needed
●​ Slower and limited

📌 Example: Lesk Algorithm

2️⃣ Machine Learning-Based Approaches

●​ Learn from corpus (text data)
●​ Use:
○​ Tagged data (supervised)
○​ Untagged data (unsupervised)
●​ Use probability/statistics

📌 Example: Naive Bayes, HMMs, Neural models

3️⃣ Hybrid Approaches

 ●​ Combine:
○​ Corpus evidence
○​ WordNet semantic relations
●​ More practical and accurate

Selectional Preferences
🔹 Indian Linguistic Tradition
1️⃣ Aakaangksha (Desire)

Some words expect something.

Example:

I saw the boy with long hair.

●​ “saw” and “boy” expect an attachment

2️⃣ Yogyataa (Appropriateness)

Which attachment makes sense?

●​ “with long hair” fits boy

●​ Not “saw”

3️⃣ Sannidhi (Proximity)

If ambiguity still exists:

I saw the boy with a telescope.

●​ Telescope can attach to saw or boy

●​ Nearest word wins → boy
🔹 Modern Linguistic Theory (Selectional
Preferences)
Some words demand specific types of arguments.

Example: Give

●​ Agent → animate
●​ Object → physical thing
●​ Indirect object → recipient

I gave him the book ✔​

yesterday / in school → adjunct (extra info)

🔹 How Selectional Preferences Help WSD

Example: serve

Sentence Object Type Meaning

serves dinner edible food sense

serves sector region service/route sense

Context + argument type = correct sense

Overlap-Based Approaches
Use:

●​ Machine Readable Dictionary (MRD)

Idea:

●​ Compare:
○​ Sense definition words
○​ Context words
 ●​ The sense with maximum overlap wins

Lesk’s Algorithm (Very Important)

🔹 Core Idea
👉 The correct sense shares more words with the context.
Example:

On burning coal we get ash.

●​ Ash meanings:
○​ Tree
○​ Burnt residue ✔
○​ Verb

Words like burning, coal, residue overlap → Sense 2

🔹 Simplified Lesk
●​ Only compare:
○​ Sense definition of target word
○​ Words in the sentence
●​ Much faster

Walker’s Algorithm (Thesaurus Based)

●​ Each sense belongs to a topic/category
●​ Context words vote for a sense

Example: bank
Context words: money, interest, annum

Sense Score

Finance 3

Location 0

✔ Finance sense chosen

WSD vs Word Sense Discrimination

WSD WSDn

Uses dictionary senses No predefined senses

Supervised / Knowledge-based Unsupervised

Chooses a sense Discovers meanings

Why WSD is Hard for Computers

Humans use common sense​
Computers do not.

Example:

The bank was robbed​

The fisherman jumped off the bank

Same word, different meanings.

Heuristics in WSD
1️⃣ Most Frequent Sense
●​ Choose the most common meaning
●​ Surprisingly effective

2️⃣ One Sense per Discourse

●​ A word keeps same meaning in a document

Accuracy: ~70%

3️⃣ One Sense per Collocation

●​ Same word + same neighbor → same sense

Accuracy:

●​ ~97% (two senses)

●​ ~70% (WordNet granularity)

Semantic Similarity Approaches

🔹 Local Context
●​ Compare meaning similarity with nearby words

Example:

plant with flowers

●​ plant (factory) ❌
 ●​ plant (living thing) ✔

🔹 Global Context (Lexical Chains)

●​ Group semantically related words across text
●​ Words in same chain share meaning

Applications of WSD
●​ Machine Translation
○​ bill → pico / cuenta
●​ Information Retrieval
○​ cricket (sport / insect)
●​ Question Answering
●​ Knowledge Base creation

✅ Exam Tip
If asked:

●​ “Explain WSD” → give definition + approaches

●​ “Explain Lesk” → give overlap idea + example
●​ “Selectional preferences” → verb–argument constraints
Lesk Algorithm
LESK ALGORITHM 9 MARKER
Lesk’s Algorithm is a classic knowledge-based Word Sense Disambiguation (WSD)
technique proposed by Michael Lesk (1986).​
Its main goal is to determine the correct sense of an ambiguous word by comparing
dictionary definitions (glosses) with the context in which the word appears.

Idea Behind the Algorithm

The correct sense of a word is the one whose dictionary definition shares the maximum
number of common words (overlap) with the words in the given sentence or surrounding
context.

Working of Lesk’s Algorithm

1.​ Identify the ambiguous word in the sentence.​

2.​ Retrieve all possible senses of that word from a dictionary (e.g., WordNet).​

3.​ Extract the gloss (definition) of each sense.​

4.​ Compare the gloss words with the words in the sentence (context).​

5.​ Count the overlaps (common words) between each gloss and the context.​

6.​ Select the sense with the highest overlap as the correct meaning.​

Example

Sentence:

“I went to the bank to deposit money.”

Possible senses of bank:

●​ Bank (financial institution): an organization that accepts deposits of money​

 ●​ Bank (river edge): the land alongside a river​

Overlaps:

●​ Context words: deposit, money​

●​ Financial sense overlaps with deposit, money​

●​ River sense has no overlap​

✅ Correct sense: bank as a financial institution

Types of Lesk Algorithm

1.​ Original Lesk Algorithm​

○​ Uses only dictionary definitions.​

2.​ Simplified Lesk Algorithm​

○​ Compares gloss of the target word with the context only (most commonly used).​

3.​ Extended Lesk Algorithm​

○​ Also considers definitions of related words (synonyms, hypernyms, etc.).​

Advantages

●​ Simple and easy to understand​

●​ Does not require training data​

●​ Based purely on lexical knowledge​

Limitations
 ●​ Performance depends on quality of dictionary definitions​

●​ Overlap count may be very small​

●​ Fails when context and gloss use different words for the same concept​

Conclusion

Lesk’s Algorithm is an important baseline approach in Word Sense Disambiguation. Although

simple, it laid the foundation for more advanced knowledge-based and statistical WSD
techniques.
Parsing
 Parsing (NLP)
1. Introduction to Parsing
●​ Parsing is the process of analyzing the grammatical (syntactic) structure of a
sentence.
●​ A parser breaks a sentence into:
○​ Words
○​ Phrases (NP, VP, PP, etc.)
○​ Hierarchical structures (trees)
●​ Goal:
○​ Check whether a sentence is grammatically legal
○​ Construct its syntactic tree

Why Parsing is Important

Parsing is essential for:

●​ Machine Translation
●​ Information Extraction
●​ Question Answering
●​ Speech Recognition
●​ Dialogue Systems

2. POS Tagging vs Parsing

●​ POS Tagging
○​ Assigns part-of-speech to each word
○​ Resolves lexical ambiguity
○​ Example: book → noun or verb
●​ Parsing
○​ Determines sentence structure
○​ Resolves syntactic ambiguity
○​ Example: attachment of prepositional phrases
 3. Syntax
●​ Syntax refers to the rules governing:
○​ Word order
○​ Sentence structure
○​ Phrase formation
●​ Syntax defines how meaningful sentences are formed from words.

4. Core Language Components (Very Important)

Parsing depends on three main components:

4.1 Lexicon

●​ A vocabulary list containing words grouped by type.

Examples:

●​ Nouns: stench, breeze, glitter, nothing, wumpus, pit, pits, gold, east
●​ Verbs: is, see, smell, shoot, feel, stinks, go, grab, carry, kill
●​ Adjectives: right, left, east, south, back, smelly
●​ Adverbs: here, there, nearby, ahead
●​ Pronouns: me, you, it, she, y’all
●​ Names: John, Mary, Boston, UCB
●​ Articles: the, a, an
●​ Prepositions: to, in, on, near
●​ Conjunctions: and, or, but
●​ Digits: 0–9

4.2 Categorization

●​ Assigns part-of-speech tags to words.

Examples:

●​ Noun → pit, gold

●​ Verb → stinks, grab
●​ Adjective → smelly
 ●​ Adverb → nearby
●​ Pronoun → me, you
●​ Article → the, a
●​ Preposition → in, on
●​ Conjunction → and, or
●​ Digit → 1, 2, 3

4.3 Grammar Rules

●​ Grammar rules define valid sentence structures.

Example:

●​ Noun Phrase (NP) → Determiner + Adjective + Noun

Example phrase:

●​ The large cat

If a sentence does not match any grammar rule, the parser cannot parse it.

5. Parsing Process
●​ Parsing uses grammar rules to:
○​ Verify sentence legality
○​ Generate a syntactic tree

6. Relationship Between Words and Word Groups

Parsing identifies:

6.1 Constituency

●​ How words group together into phrases.

●​ Example:
 ○​ [The large cat] [eats] [the small rat]

6.2 Dependency

●​ How words depend on each other.

●​ Example:
○​ chases(cat, mouse)

Helps identify:

●​ Subject–Verb–Object
●​ Modifiers
●​ Attachments

7. Word Categories (Recap)

Words

●​ Nouns: dog, cat, grasshopper

●​ Verbs: chases, avoids, hunts
●​ Adjectives: quick, green
●​ Adverbs: slowly, quickly
●​ Pronouns: he, she, it
●​ Prepositions: in, on, at
●​ Conjunctions: and, but, or

8. Word Groups (Phrases)

Noun Phrase (NP)

●​ The quick brown fox

●​ A small bug

Verb Phrase (VP)

●​ chases the cat

●​ befriends the frog
 Prepositional Phrase (PP)

●​ in the garden
●​ on the leaf

Adjective Phrase (AdjP)

●​ very quick

Adverb Phrase (AdvP)

●​ very slowly

Conjunction Phrase (ConjP)

●​ and then
●​ but also

9. Syntactic Tree (Step-by-Step)

Sentence:​
The large cat eats the small rat

Hierarchy:

●​ Article + Adjective + Noun → NP

●​ Verb + NP → VP
●​ NP + VP → Sentence (S)

Final Tree:

●​ (S
●​ (NP (DT The) (JJ large) (NN cat))
●​ (VP (V eats)
●​ (NP (DT the) (JJ small) (NN rat))))
 10. Label Bracketing
●​ Linear representation of a syntactic tree.

Example:

●​ [S
●​ [NP [D the] [N dog]]
●​ [VP [V barked]]
●​ ]

11. Evaluation of Parsing

Metrics Used

●​ Precision = relevant retrieved / retrieved

●​ Recall = relevant retrieved / relevant
●​ F1 Score = 2PR / (P + R)

Example Result

●​ Labeled Precision = 42.9%

●​ Labeled Recall = 37.5%
●​ F1 Score = 40.0%

Uses gold standard brackets vs candidate brackets.

12. Types of Parsers

12.1 Dependency Parser

●​ Focus: word-to-word relations

●​ Output: dependency tree
●​ Example:
○​ chases(cat, mouse)
 12.2 Constituency Parser

●​ Focus: phrase structure

●​ Output: parse tree

12.3 Top-Down Parser

●​ Starts from sentence (S)

●​ Breaks into smaller units

12.4 Bottom-Up Parser

●​ Starts from words

●​ Builds larger phrases

13. Parsing Ambiguity

Definition

●​ A sentence has multiple valid parse trees.

Types of Ambiguity

Lexical Ambiguity

●​ A word has multiple meanings.

●​ Example:
○​ glasses → spectacles / drinking glasses

Structural Ambiguity

●​ Multiple sentence structures.

●​ Example:
○​ I saw the boy with the telescope

Explosive Nature of Ambiguity

(Number of parses grows exponentially)

 Sentence Parses

I saw the man with the telescope 2

I saw the man on the hill with the 5

telescope

Longer sentences 100+

Follows Catalan numbers.

14. Handling Ambiguity

●​ Probabilistic CFGs (PCFGs)
●​ Machine learning parsers
●​ Choose the most likely parse

15. Word Sense

Lexical ambiguity arises due to different word senses.

Word Sense Relations

Synonymy

●​ Same meaning
●​ buy / purchase

Antonymy

●​ Opposite meaning
●​ short / tall

Homonymy

●​ Same spelling, different meanings

●​ bank (river / financial)

Polysemy
 ●​ Related meanings
●​ bank (institution, building)

Hypernymy / Hyponymy

●​ car → Honda

16. WordNet 3.0

●​ Lexical database
●​ Hierarchical structure

Category Count

Nouns 117,798

Verbs 11,529

Adjectives 22,479

Adverbs 4,481

Example: multiple senses of bass (fish, voice, instrument).

17. Difficulties in Natural Language

Anaphora

●​ Pronoun reference
●​ Example: Mary threw a rock and broke it

Indexicality

●​ Context dependent
●​ Example: I am over here

Metonymy
 ●​ One entity refers to another
●​ Example: I read Shakespeare

Metaphor

●​ Non-literal usage
●​ Example: The process won’t die

18. Summary
●​ Core components:
○​ Lexicon
○​ Categorization
○​ Grammar Rules
●​ Parsing outputs:
○​ Syntactic Trees
○​ Label Bracketing
●​ Evaluation:
○​ Precision, Recall, F1
●​ Challenges:
○​ Ambiguity
○​ Word Sense
○​ Contextual interpretation
Difference between SR and Chart
Parsing
Shift-Reduce (SR) Parsing
What it is

Shift-Reduce parsing is a bottom-up parsing technique that:

●​ Shifts input symbols onto a stack

●​ Reduces symbols on the stack using grammar rules
●​ Continues until the start symbol is produced​

Used in LR, SLR, LALR parsers (common in compiler design).

How it works

●​ Uses a stack
●​ Reads input left to right
●​ Performs shift or reduce actions​

Example (SR Parsing)

Grammar:

E→E+E
E → id

Input:

id + id

Steps (simplified):

Stack Input Action

— id + id shift

id + id reduce (E → id)

E + id shift
 E+ id shift

E + id — reduce (E → id)

E+E — reduce (E → E + E)

✔ Input accepted

🔹 Characteristics
●​ Fast and efficient
●​ Requires unambiguous grammar
●​ Not suitable for ambiguous or natural language grammars​

2️⃣ Chart Parsing

What it is

Chart parsing is a dynamic programming parsing technique used mainly in

Natural Language Processing (NLP).

●​ Stores intermediate results in a chart

●​ Avoids recomputation
●​ Handles ambiguity efficiently​

Examples: Earley Parser, CYK Parser

🔹 How it works
●​ Maintains a chart (table/graph)
●​ Records all possible parses
●​ Uses operations like predict, scan, and complete

🔹 Example (Chart Parsing)

Grammar:
S → NP VP
NP → Det N | NP PP
VP → V NP
PP → P NP

Sentence:

I saw the boy with a telescope

Ambiguity handled:

●​ with a telescope modifies saw

●​ or modifies boy​

Chart parser stores both parses instead of failing.

✔ Multiple valid parse trees produced

🔹 Characteristics
●​ Handles ambiguous grammars
●​ Efficient for NLP
●​ More memory usage
●​ Slower than SR parsing​

3️⃣ Key Differences (Exam Table)

Feature Shift-Reduce Chart Parsing
Parsing

Parsing type Bottom-up Top-down +

Bottom-up

Main domain Compiler design NLP

Data structure Stack Chart (table/graph)

Handles ❌ No ✅ Yes
ambiguity

Grammar type Deterministic Context-free,

ambiguous

Efficiency Very fast Moderate

Example parsers LR, SLR, LALR Earley, CYK

Regular Expressions (Regex)
Regular Expressions (Regex)
Definition
●​ A Regular Expression (regex) is a sequence of characters that defines a
search pattern.
●​ Mainly used for:
○​ Pattern matching
○​ Search and replace operations
●​ Regex is a generalized way to match patterns in strings.
●​ Supported by almost all programming languages:
○​ C++, Java, Python, Perl, etc.

Why Regex is Important

●​ Used in:
○​ Text editors (Sublime, Notepad++, VS Code, Google Docs, MS Word)
○​ Google Analytics (URL matching)
○​ NLP tasks (tokenization, pattern detection)
○​ Input validation (email, phone number, PAN, URLs)

How to Write Regular Expressions

1.​ Learn special characters (., *, +, ?, etc.)
2.​ Choose a language/tool that supports regex
3.​ Write pattern using:
○​ Literal characters
○​ Special symbols
4.​ Apply regex using language-specific functions​
(e.g. [Link]() in Python)
Basic Regex Concepts & Symbols
Literal Characters
●​ Match exact characters.
●​ Example:
○​ cat → matches "cat"

Character Sets [ ]
●​ Match any one character from a set.
●​ Example:
○​ [0123456789] → matches any digit
○​ [abc] → matches a, b, or c

Repeaters
Asterisk (*)

●​ Matches 0 or more occurrences.

●​ Example:
○​ ab*c → ac, abc, abbc, abbbc, ...

Plus (+)

●​ Matches 1 or more occurrences.

●​ Example:
○​ ab+c → abc, abbc, ...

Curly Braces { }

●​ Control exact repetition count.

 ●​ {2} → exactly 2 times
●​ {min,} → at least min times ->ab{2,}c ->abbc, abbbc,------
●​ {min,max} → between min and max times

Wildcard (.)
●​ Matches any single character except newline.
●​ Example:
○​ .* → matches any character any number of times
○​ c.t

Matches:
●​ cat
●​ cut
●​ c@t
●​ C9t

Does NOT match:

●​ ct (missing a character)
●​ cart (extra character)​

Optional Character (?)

●​ Matches 0 or 1 occurrence.
●​ Example:
○​ docx? → matches doc or docx

Anchors (Positioning)
Caret (^)

●​ Match must start at beginning of string.

●​ Example:
 ○​ ^\d{3} → matches "901" in "901-333"

Dollar ($)

●​ Match must end at end of string.

●​ Example:
○​ -\d{3}$ → matches "-333" in "901-333"

Character Classes

Symb Meaning
ol

\s whitespace

\S non-whitespace

\d digit

\D non-digit

\w word character (letter,

digit, _)

\W non-word character

\b word boundary

Negated Character Set [^ ]

●​ [^abc] → matches any character except a, b, c

●​ h[^aeiou]t

Character Range

●​ [a-zA-Z] → matches uppercase and lowercase letters

Escape Character ( \ )
●​ Used to match special characters literally.
●​ Example:
○​ \+, \ ., \*
●​ Example:
○​ \d+[\+-x\*]\d+ → matches 2+2, 3*9

Grouping ( )
●​ Groups multiple symbols into one unit.
●​ Example:
○​ ([A-Z]\w+) → uppercase letter followed by word characters

Alternation ( | )
●​ Matches any one option.
●​ Example:
○​ th(e|is|at) → the, this, that

Backreference (\number)
●​ Refers to previously matched group.
●​ Example:
○​ ([a-z])\1 → matches "ee" in "Geek"

Comments in Regex
Inline Comment
 ●​ (?# comment )
●​ Example:
○​ \bA(?#comment)\w+\b

X-mode Comment

●​ Starts with # till end of line

●​ Example:
○​ (?x)\bA\w+\b # matches words starting with A

Important Regex Examples

Email Address Validation
\b[A-Za-z0-9._%+-]+@[A-Za-z0-9.-]+\ .[A-Z|a-z]{2,}\b

Explanation:

●​ \b → word boundary
●​ [A-Za-z0-9._%+-]+ → username
●​ @ → at symbol
●​ [A-Za-z0-9.-]+ → domain name
●​ \ . → dot
●​ [A-Za-z|a-z]{2,} → domain extension

Find URLs
\b(?:https?|ftp)://\S+

Explanation:

●​ (?: ) → non-capturing group

●​ https?|ftp → protocol
 ●​ :// → literal
●​ \S+ → non-whitespace characters

Find Hashtags
#(\w+)

●​ Matches hashtags like #NLP, #AI

Find Punctuation
[^\w\s]

●​ Matches characters that are not letters, digits, or spaces

Validate PAN Number

^[A-Z]{5}[0-9]{4}[A-Z]$

●​ 5 uppercase letters
●​ 4 digits
●​ 1 uppercase letter
Stemming (NLP)
Stemming (NLP)
Definition

●​ Stemming is the process of removing prefixes and suffixes from words to

reduce them to a root/base form (stem).
●​ It helps in text normalization, making text easier to process.

Purpose

●​ Improves effectiveness of text processing tasks

●​ Reduces vocabulary size
●​ Groups similar words together

Example

Root word: program

●​ programming → program
●​ programmer → program
●​ programs → program

Root word: like

●​ likes
●​ liked
●​ liking
●​ likely

Importance of Stemming
Used in:

●​ Text Classification
●​ Information Retrieval
●​ Text Summarization
●​ Sentiment Analysis
●​ Document Clustering
Advantages of Stemming
●​ Faster text processing
●​ Reduces redundancy
●​ Improves matching of related words

Limitations of Stemming
●​ Output stem may not be a real word
●​ Can affect readability
●​ Can produce incorrect roots

Types of Stemmers (NLTK)

1. Porter Stemmer

●​ Proposed in 1980
●​ Most popular and widely used
●​ Rule-based suffix stripping
●​ Works only for English
●​ Output stem may not be meaningful

Example Rule

●​ EED → EE
○​ agreed → agree

Advantages

●​ Simple and fast

●​ Low error rate

Limitations

●​ Produces non-real words (e.g., happily → happili)

2. Lovins Stemmer

●​ Proposed in 1968
●​ Removes longest possible suffix
●​ Then applies transformations

Example

●​ sitting → sitt → sit

Advantages

●​ Fast
●​ Handles irregular plurals (tooth → teeth)

Limitations

●​ Often fails to generate valid words

3. Krovetz Stemmer

●​ Proposed in 1993
●​ Light stemming approach
●​ Steps:
○​ Plural → singular
○​ Past → present
○​ Removes -ing

Example

●​ children → child

Advantages

●​ Produces meaningful stems

●​ Can be used as pre-stemmer

Limitations

●​ Inefficient for large documents

4. Xerox Stemmer

●​ Language-dependent
●​ Generates valid dictionary words

Examples

●​ children → child
●​ understood → understand
●​ best → good

Advantage

●​ Handles large datasets well

5. N-Gram Stemmer

●​ Breaks words into character sequences (n=2 or 3)

●​ Based on string similarity

Example (n=2)

●​ INTRODUCTIONS →​
I, IN, NT, TR, RO, OD, DU, UC, CT, TI, IO, ON, NS, S

Advantages

●​ Language independent

Limitations

●​ High memory usage

●​ Slow processing

6. Snowball Stemmer (Porter2)

●​ Improved version of Porter

●​ Supports multiple languages
●​ More aggressive and faster
Advantages

●​ Better performance
●​ Multilingual support

7. Lancaster Stemmer

●​ Very aggressive
●​ Extremely fast

Limitation

●​ Can distort small words badly

○​ wander → wand

8. Regex Stemmer

●​ Uses regular expressions

●​ Custom rule-based stemming

Advantage

●​ Highly customizable

Applications of Stemming
●​ Sentiment Analysis (reviews, feedback)
●​ Document Clustering
●​ Search Engines
●​ Information Retrieval
●​ Automatic Text Structuring

Disadvantages of Stemming
Over-Stemming
 ●​ Removes too much → loss of meaning
●​ Example:
○​ arguing → argu
○​ wander → wand (Lancaster)

Solution

●​ Choose correct stemmer

●​ Use lemmatization if needed

Under-Stemming

●​ Does not reduce related words enough

●​ Example:
○​ knavish → knavish
○​ knave → knave​
(Porter fails; Lovins → knav)
NLP Unit 3 PPT
1. What is a Grammar? (Phrase Structure Grammar)
A grammar is a set of rules that tells us:

●​ which words are allowed

●​ how words can be combined
●​ which sentences are valid

Example idea:

Grammar = rules of a language, just like rules of a game.

2. Lexical Categories (Parts of Speech)

These are types of words.

Examples:

●​ Nouns → dog, cat, wumpus

●​ Verbs → run, smell, chase
●​ Adjectives → smelly, dead
●​ Adverbs → quickly, nearby
●​ Prepositions → in, on, near
●​ Articles → the, a, an
●​ Conjunctions → and, but, or

These are the building blocks of sentences.

3. Syntactic Categories (Word Groups / Phrases)

Words group together to form phrases.

Examples:

●​ NP (Noun Phrase) → the smelly wumpus

●​ VP (Verb Phrase) → smells dead
●​ PP (Prepositional Phrase) → in the pit
So:

Words → Phrases → Sentence

4. Phrase Structure Rules (CFG Rules)

Rules tell how phrases are formed.

Examples:

●​ S → NP VP​
A sentence has a noun phrase and a verb phrase.
●​ VP → Verb NP​
A verb phrase can be a verb followed by a noun phrase.

Important point:​
👉 The rule does not care what is inside NP​
It only checks that an NP is present

5. Generative Capacity (Very Important Concept)

This tells how powerful a grammar is.

From weakest → strongest:

1.​ Regular Grammar

○​ Like Finite State Machines
○​ Can’t handle nested structures
○​ Example: a* b*
2.​ Context-Free Grammar (CFG)
○​ Used in NLP
○​ Can handle nesting
○​ Example: aⁿ bⁿ
3.​ Context-Sensitive Grammar
○​ More powerful
○​ Example: aⁿ bⁿ cⁿ
4.​ Recursively Enumerable Grammar
○​ As powerful as a Turing Machine
 ○​ No restrictions

6. Context-Free Grammar (CFG)

In CFG:

●​ Left side has only one non-terminal

Example:

NP → Article Noun
VP → Verb NP

CFGs are:

●​ Simple
●​ Efficient
●​ Widely used in NLP

But ❌ they have problems (explained later).

7. Probabilistic CFG (PCFG)

PCFG = CFG + probability

Each rule has a probability.

Example:

VP → Verb [0.7]
VP → V NP [0.3]

Meaning:

●​ 70% of the time, VP is just a verb

●​ 30% of the time, VP has a verb + object

👉 Helps choose the most likely parse when multiple parses exist.
8. Lexicon (Dictionary of Words)
Lexicon = list of all words with categories.

Two types:

Open Classes

●​ Nouns, verbs, adjectives, adverbs

●​ New words keep getting added
●​ Example: iPod, biodiesel

Closed Classes

●​ Articles, prepositions, pronouns

●​ Very few words
●​ Change slowly over centuries

9. Parse Tree (Very Important)

A parse tree shows:

●​ How a sentence is built

●​ Which words belong to which phrases

Example sentence:

Every wumpus smells

Tree (simple form):

S
/\
NP VP
| | |
Adjective Noun Verb
every wumpus smells
👉 A parse tree proves the sentence is valid.

10. Over-generation & Under-generation

Over-generation

Grammar allows wrong sentences

●​ “Me go Boston”

Under-generation

Grammar rejects correct sentences

●​ “I think the wumpus is smelly”

CFGs struggle to balance this.

11. Parsing (Syntactic Analysis)

Parsing = breaking sentence into structure.

Two methods:

Top-down Parsing

●​ Start from S
●​ Try to reach words

Bottom-up Parsing

●​ Start from words

●​ Build up to S

Problem:​
❌ Repeats work​
❌ Inefficient
12. Chart Parsing & Dynamic Programming
Solution:

●​ Store results
●​ Don’t recompute same phrase again

This makes parsing efficient.

13. CYK Algorithm

CYK is:

●​ Bottom-up parser
●​ Uses dynamic programming
●​ Requires grammar in Chomsky Normal Form (CNF)

CNF rules:

●​ A → BC
●​ A → a
●​ S → ε

CYK helps:

●​ Check if sentence is valid

●​ Find most probable parse

14. Parsing Ambiguity (Very Important)

A sentence can have multiple meanings.

Example:

I saw the man with the telescope.

Who has the telescope?

●​ Me?
 ●​ The man?

As sentence gets longer → parses explode.

This growth follows Catalan numbers.

👉 PCFGs help by choosing the most likely meaning.

Information Retrieval
Information Retrieval (IR) in NLP — Explained Clearly

Information Retrieval (IR) in Natural Language Processing (NLP) deals with

finding relevant documents or information from a large collection in response to a
user’s natural language query.

In simple words:

IR answers the question “Which documents are relevant to my query?”

1️⃣ What is Information Retrieval?

Information Retrieval is the process of:

●​ Accepting a user query (in natural language)

●​ Searching a large document collection
●​ Returning relevant documents, not exact answers​

Examples:

●​ Google search
●​ Searching papers on Google Scholar
●​ Searching emails in Gmail
●​ Searching product reviews on Amazon​

2️⃣ Key Components of IR in NLP

🔹 1. Document Collection
A large set of unstructured text documents​
Example: web pages, news articles, research papers

🔹 2. Query
User’s information need expressed in natural language​
Example:
"effects of climate change on agriculture"

🔹 3. Text Processing (NLP techniques)

Before retrieval, text is processed using NLP:

●​ Tokenization – splitting text into words​

●​ Stop-word removal – removing common words (the, is, of)​

●​ Stemming / Lemmatization – reducing words to base form​

●​ Normalization – lowercase, punctuation removal​

🔹 4. Indexing
Documents are converted into a searchable structure.

●​ Inverted Index:​
Maps terms → list of documents containing them​

Example:

climate → D1, D3, D7

agriculture → D2, D3

🔹 5. Retrieval Model
Determines how relevance is calculated.

Common models:

●​ Boolean Model – exact match using AND/OR/NOT​

●​ Vector Space Model (VSM) – uses TF-IDF and cosine similarity​

●​ Probabilistic Models – BM25​

 ●​ Neural IR Models – BERT-based retrievers​

🔹 6. Ranking
Documents are ranked by relevance score​
Most relevant documents appear first

3️⃣ Example of IR Process

Query:

"machine learning in healthcare"

Steps:

1.​ Tokenize → machine, learning, in, healthcare

2.​ Remove stop words -> remove in
3.​ Match terms in index
4.​ Compute similarity scores
5.​ Rank documents​

Output:

●​ Research paper on ML in medical diagnosis

●​ Article on AI in hospitals
●​ Blog on healthcare analytics​

4️⃣ Evaluation of IR Systems

To measure performance:

Metric Meaning
 Precision Relevant documents retrieved / total
retrieved

Recall Relevant documents retrieved / total

relevant

F-measure Harmonic mean of precision & recall

MAP Mean Average Precision

NDCG Ranking quality measure

5️⃣ Information Retrieval vs Information Extraction

Aspect Information Information
Retrieval Extraction

Output Documents Facts/entities

Example Google Search Named Entity

Recognition

Granularity Document-level Sentence/phrase-level

6️⃣ Applications of IR in NLP

●​ Search engines (Google, Bing)
●​ Question answering systems
●​ Recommendation systems
●​ Legal and medical document search
●​ Chatbots and virtual assistants
Tab 28
Language Modeling N-Grams

1. What are N-grams?

An N-gram is just a sequence of N words that appear together.

Examples:

●​ 1-gram (Unigram) → Medium

●​ 2-gram (Bigram) → Medium blog
●​ 3-gram (Trigram) → Write on Medium
●​ 4-gram → A Medium blog post

👉 So basically:
N-gram = “look at N words together”

2. What is the idea behind N-grams?

N-grams help us predict the next word using the previous words.

●​ In a bigram model, we predict the next word using 1 previous word

●​ In a trigram model, we predict the next word using 2 previous words

Example:

“Thank you so much for your ___”

Most humans immediately think “help”.​

N-gram models try to do the same thing using data.

3. Why do we need N-grams?

N-grams are used in many NLP applications:

✅ Auto-completion (Gmail suggestions)

✅ Spell checking
●​
●​
 ✅ Grammar checking
✅ Voice assistants
●​

✅ Predicting next word in a sentence

●​
●​

👉 They help computers guess what comes next in language.

4. How does the system know the next word?

Computers don’t guess like humans.​
They learn from large text data (corpus).

From training data, the system learns:

●​ Which words appear together

●​ How often they appear together

This gives us probabilities.

5. N-gram Probability (Bigram case)

In a bigram model, we calculate:

Meaning:

Probability of word w₁ coming after w₂

6. Training Example (Corpus)

Given sentences:

1.​ Thank you so much for your help

 2.​ I really appreciate your help
3.​ Excuse me, do you know what time it is
4.​ I’m really sorry for not inviting you
5.​ I really like your watch

7. Predicting after “really”

From the corpus:

●​ “really appreciate” → 1 time

●​ “really sorry” → 1 time
●​ “really like” → 1 time

Total occurrences of really = 3

Probability calculations:

👉 So when you type “I really”, the model:

●​ Has 3 equally likely choices
●​ Gets the correct one only 1 out of 3 times

8. Another Example
Input:

“Thank you for inviting ___”

From the corpus:

●​ Only one example exists → “inviting you”

So:

●​ The model confidently predicts “you”

👉 More data = better prediction.

9. Why use Trigram or 4-gram?

Bigram only looks at one previous word, which is limited.

Example:

●​ “set the temperature”

●​ “what’s the temperature”

Using trigrams:

●​ “set the” → likely followed by temperature

●​ “what’s the” → likely followed by temperature

Trigrams give more context, so predictions improve.