Natural Language Text Processing

Notes
Chapter 1
Introduction:
Generic Natural Language Processing (NLP) system [CO1]
NLP is the field that enables computers to understand and respond to human language. It is
crucial for applications like email filtering (e.g., spam detection). NLP has evolved from
traditional rule-based systems to using machine learning and deep learning techniques,
especially from the 1980s onward. Natural language processing (NLP) is a branch of artificial
intelligence that helps computers understand, interpret and manipulate human language.

Natural Language Processing, usually shortened as NLP, is a branch of artificial intelligence

that deals with the interaction between computers and humans using the natural language.

The ultimate objective of NLP is to read, decipher, understand, and make sense of the human
languages in a manner that is valuable. It is an interdisciplinary subfield
of linguistics, computer science, and artificial intelligence concerned with the interactions
between computers and human language.

Text Analytics and NLP

Text analytics focuses on extracting meaningful insights from text data, which may not
always be human language. In contrast, NLP includes both text and speech recognition. The
two branches of NLP are: -
Natural Language Understanding (NLU): Comprehension of spoken or written language by
machines.
Natural Language Generation (NLG): Machines producing human-understandable text.
Stages in NLP, [CO1]
To converse with human a program must understand the syntax(grammar), semantics (word
meaning) and morphology (word level analysis), and pragmatics(conversation).
 Natural Language Text Processing
Notes
Chapter 1

There are certain phases in which Natural language processing is performed.

1. Morphological Analysis

It deals with morphemes which are the smallest units of meaning in a word. It is important
for understanding structure of words and their parts by identifying free morphemes
(independent words like "cat") and bound morphemes (like prefixes or suffixes e.g. "un-" or
"-ing").
Key tasks in morphological analysis:
1. Stemming: Reducing words to their root form like "running" to "run".
2. Lemmatization: Converting words to their base or dictionary form considering the
context like "better" becomes "good".
Importance of Morphological Analysis
1. Understanding Word Structure: It helps in breaking the composition of complex
words.
2. Improving Accuracy: It enhances accuracy of tasks such as part-of-speech tagging,
syntactic parsing and machine translation.
By identifying and analysing morphemes system can identify text correctly at the most basic
level which helps in more advanced NLP applications.

2. Syntactic Analysis (Parsing)

Syntax is the foundation of language, it’s how words and phrases come together to form
meaningful sentences. Syntactic analysis (or parsing) lets NLP systems understand sentence
structure and relationships between words rather than analyzing them in isolation.

This ensures that AI-powered chatbots, smart IVR systems, and voice assistants interpret user
queries correctly.

When NLP performs syntactic analysis, it:

 Identifies sentence structure: Breaks a sentence into subject, predicate, objects,

clauses, etc.
 Determines relationships between words: Determines which words depend on or
modify others.
 Checks for grammatical correctness: Ensures the sentence follows valid language
rules.
 Natural Language Text Processing
Notes
Chapter 1
Syntactic analysis is important for chatbots and virtual assistants to improve customer
experience with smart IVR. When a customer says, “I need help to reset my password”, the
system uses syntactic analysis to recognize:

 “I” as the subject

 “need help” as the action
 “resetting my password” as the specific request

This structured understanding helps the AI respond appropriately, directing users to the right
solution without confusion or misinterpretation.

3. Semantic Analysis
Semantic Analysis focuses on understanding meaning behind words and sentences. It ensures
that the text is not only grammatically correct but also logically coherent and contextually
relevant. It aims to understand dictionary definitions of words and their usage in context and
also find whether the arrangement of words in a sentence makes logical sense.

Key Tasks in Semantic Analysis

1. Named Entity Recognition (NER): It identifies and classifies entities such as names of
people, locations, organizations, dates and more. These entities provide important
meaning in the text and help in understanding the context. For example in the sentence
"Tesla announced its new electric vehicle in California," NER would identify "Tesla" as
an organization and "California" as a location.
2. Word Sense Disambiguation (WSD): Many words have multiple meanings depending
on the context in which they are used. It identifies the correct meaning of a word based on
its surrounding text. For example word "bank" can refer to a financial institution or the
side of a river. It uses context to identify which meaning applies in a given sentence
which ensures that interpretation is accurate.

Example of Semantic Analysis

"Apple eats a John." while grammatically correct this sentence doesn’t make sense
semantically because an apple cannot "eat" a person. Semantic analysis ensures that the
meaning is logically sound and contextually appropriate. It is important for various NLP
applications including machine translation, information retrieval and question answering.

4. Discourse Integration
It is the process of understanding how individual sentences or segments of text connect and
relate to each other within a broader context. This phase ensures that the meaning of a text is
consistent and coherent across multiple sentences or paragraphs. It is important for
understanding long or complex texts where meaning focuses on previous statements.
example In the text, “Jack is a bright student. He spends most of the time in the library.”
Here, discourse assigns “he” to refer to “Jack”.
It is important for NLP applications like machine translation, Chabot’s and text
summarization. It ensures that meaning remains same across sentences which helps machines
to understand context. This enables accurate and natural responses in applications like
conversational AI and document translation.
 Natural Language Text Processing
Notes
Chapter 1
5. Pragmatic Analysis
The final stage of NLP, Pragmatics interprets the given text using information from the
previous steps. Given a sentence, “Turn off the lights” is an order or request to switch off the
lights.

Ambiguity in Natural language, [CO1]

Input is ambiguous if there are multiple alternative Ambiguous linguistic structures that can
be built for it situation where a word or a sentence may have more than one meaning.
Ambiguity in Natural Language Processing (NLP) happens because human language can
have multiple meanings. Computers sometimes confuse to understand exactly what we mean
unlike humans, who can use intuition and background knowledge to infer meaning,
computers rely on precise algorithms and statistical patterns.
The sentence "The chicken is ready to eat" is ambiguous because it can be interpreted in two
different ways:
1. The chicken is cooked and ready to be eaten.
2. The chicken is hungry and ready to eat food.
This dual meaning arises from the structure of the sentence, which does not clarify the
subject's role (the eater or the one being eaten). Resolving such ambiguities is essential for
accurate NLP applications like Chabot’s, translation, and sentiment analysis.
There are different types of ambiguities
 Lexical
 Syntactical
 Semantic
 Discourse Ambiguity
 Pragmatic Ambiguity

1. Lexical Ambiguity

Lexical ambiguity occurs when a single word has multiple meanings, making it unclear
which meaning is intended in a particular context. This is a common challenge in language.
For example, the word "bat" can have two different meanings. It could refer to a flying
mammal; like the kind you might see at night. Alternatively, "bat" could also refer to a piece
of sports equipment used in games like baseball or cricket.
For computers, determining the correct meaning of such a word requires looking at the
surrounding context to decide which interpretation makes sense.

2. Syntactic Ambiguity

Syntactic ambiguity occurs when the structure or grammar of a sentence allows for more than
one interpretation. This happens because the sentence can be understood in different ways
depending on how it is put together.
For example, take the sentence, “The boy kicked the ball in his jeans.” This sentence can
be interpreted in two different ways: one possibility is that the boy was wearing jeans and he
 Natural Language Text Processing
Notes
Chapter 1
kicked the ball while he was wearing them. Another possibility is that the ball was inside the
boy’s jeans, and he kicked the ball out of his jeans.
A computer or NLP system must carefully analyse the structure to figure out which
interpretation is correct, based on the context.

3. Semantic Ambiguity

Semantic ambiguity occurs when a sentence has more than one possible meaning because of
how the words are combined. This type of ambiguity makes it unclear what the sentence is
truly trying to say.
For example, take the sentence, “Visiting relatives can be annoying.” This sentence could
be understood in two different ways. One meaning could be that relatives who are visiting
you are annoying, implying that the relatives themselves cause annoyance. Another meaning
could be that the act of visiting relatives is what is annoying, suggesting that the experience
of going to see relatives is unpleasant.
The confusion comes from how the words "visiting relatives" can be interpreted: is it about
the relatives who are visiting, or is it about the action of visiting? In cases like this, semantic
ambiguity makes it hard to immediately understand the exact meaning of the sentence, and
the context is needed to clarify it.

4. Referential Ambiguity/ Anaphoric Ambiguity

Referential ambiguity occurs when a pronoun (like "he," "she," "it," or "they") or a phrase is
unclear about what or who it is referring to. This type of ambiguity happens when the
sentence doesn’t provide enough information to determine which person, object, or idea the
pronoun is referring to.
For example, consider the sentence, “Alice told Jane that she would win the prize.” In this
case, it’s unclear whether the pronoun "she" refers to Alice or Jane. Both could be possible
interpretations, and without further context, we can’t be sure. If the sentence was about a
competition, "she" could be referring to Alice, meaning Alice is telling Jane that she would
win the prize. However, it could also mean that Alice is telling Jane that Jane would win the
prize.

5. Pragmatic Ambiguity

Pragmatic ambiguity occurs when the meaning of a sentence depends on the speaker’s
intent, tone, or the situation in which it is said. This type of ambiguity is common in
everyday conversations, and it can be tricky for computers to understand because it often
requires knowing the broader context.
For example, consider the sentence, “Can you open the window?” In one situation, it could
be understood as a literal question asking if the person is physically able to open the
window. However, in another context, it could be a polite request, where the speaker is
asking the listener to open the window, even though they’re not directly giving an order.
The meaning changes based on the tone of voice or social context, which is something that is
difficult for NLP systems to capture without understanding the surrounding situation
 Natural Language Text Processing
Notes
Chapter 1

Challenges of NLP, [CO1]

Applications of NLP Machine Translation, Sentiment Analysis etc. [CO1]

1. Sentiment analysis
· Sentiment analysis, also referred to as opinion mining, is an approach to natural language
processing (NLP) that identifies the emotional tone behind a body of text.
· This is a popular way for organizations to determine and categorize opinions about a
product, service or idea.
· Sentiment analysis systems help organizations gather insights into real-time customer
sentiment, customer experience and brand reputation.
· Generally, these tools use text analytics to analyze online sources such as emails, blog
posts, online reviews, news articles, survey responses, case studies, web chats, tweets, forums
and comments.
· Sentiment analysis uses machine learning models to perform text analysis of human
language. The metrics used are designed to detect whether the overall sentiment of a piece of
text is positive, negative or neutral.
[Link] Translation
Machine translation, sometimes referred to by the abbreviation MT, is a sub-field of
computational linguistics that investigates the use of software to translate text or speech from
one language to another.
On a basic level, MT performs mechanical substitution of words in one language for words in
another, but that alone rarely produces a good translation because recognition of whole
phrases and their closest counterparts in the target language is needed.
Not all words in one language have equivalent words in another language, and many words
have more than one meaning.
Solving this problem with corpus statistical and neural techniques is a rapidly growing field
that is leading to better translations, handling differences in linguistic typology, translation of
idioms, and the isolation of anomalies.
Corpus: A collection of written texts, especially the entire works of a particular author.
3. Text Extraction
· There are several natural language processing techniques that can be used to extract
information from text or unstructured data.
· These techniques can be used to extract information such as entity names, locations,
quantities, and more.
 Natural Language Text Processing
Notes
Chapter 1
· With the help of natural language processing, computers can make sense of the vast amount
of unstructured text data that is generated every day, and humans can reap the benefits of
having this information readily available.
· Industries such as healthcare, finance, and e-commerce are already using natural language
processing techniques to extract information and improve business processes.
· As the machine learning technology continues to develop, we will only see more and more
information extraction use cases covered.
4. Text Classification
Unstructured text is everywhere, such as emails, chat conversations, websites, and social
media. Nevertheless, it’s hard to extract value from this data unless it’s organized in a certain
way.
Text classification also known as text tagging or text categorization is the process of
categorizing text into organized groups. By using Natural Language Processing (NLP), text
classifiers can automatically analyze text and then assign a set of pre-defined tags or
categories based on its content.
Text classification is becoming an increasingly important part of businesses as it allows to
easily get insights from data and automate business processes.
5. Speech Recognition
· Speech recognition is an interdisciplinary subfield of computer science and computational
linguistics that develops methodologies and technologies that enable the recognition and
translation of spoken language into text by computers.
· It is also known as automatic speech recognition (ASR), computer speech recognition or
speech to text (STT).
· It incorporates knowledge and research in the computer science, linguistics and computer
engineering fields. The reverse process is speech synthesis. 3 Speech recognition use cases Ø
A wide number of industries are utilizing different applications of speech technology today,
helping businesses and consumers save time and even lives.
Some examples include:
Ø Automotive: Speech recognizers improves driver safety by enabling voice-activated
navigation systems and search capabilities in car radios.
Ø Technology: Virtual agents are increasingly becoming integrated within our daily lives,
particularly on our mobile devices. We use voice commands to access them through our
smartphones, such as through Google Assistant or Apple’s Siri, for tasks, such as voice
search, or through our speakers, via Amazon’s Alexa or Microsoft’s Cortana, to play music.
They’ll only continue to integrate into the everyday products that we use, fueling the
“Internet of Things” movement.
Ø Healthcare: Doctors and nurses leverage dictation applications to capture and log patient
diagnoses and treatment notes.
 Natural Language Text Processing
Notes
Chapter 1
Ø Sales: Speech recognition technology has a couple of applications in sales. It can help a
call centre transcribe thousands of phone calls between customers and agents to identify
common call patterns and issues.
AI Chabot’s can also talk to people via a webpage, answering common queries and solving
basic requests without needing to wait for a contact centre agent to be available. In both
instances speech recognition systems help reduce time to resolution for consumer issues.
6. Chatbot
· Chabot’s are computer programs that conduct automatic conversations with people. They
are mainly used in customer service for information acquisition. As the name implies, these
are bots designed with the purpose of chatting and are also simply referred to as “bots.”
· You’ll come across Chabot’s on business websites or messengers that give pre-scripted
replies to your questions. As the entire process is automated, bots can provide quick
assistance 24/7 without human intervention.

7. Email Filter
Ø One of the most fundamental and essential applications of NLP online is email filtering. It
began with spam filters, which identified specific words or phrases that indicate a spam
message. But, like early NLP adaptations, filtering has been improved.
Ø Gmail's email categorization is one of the more common, newer implementations of NLP.
Based on the contents of emails, the algorithm determines whether they belong in one of
three categories (main, social, or promotional).
Ø This maintains your inbox manageable for all Gmail users, with critical, relevant emails
you want to see and reply to fast.
8. Search Autocorrect and Autocomplete
· When you type 2-3 letters into Google to search for anything, it displays a list of probable
search keywords. Alternatively, if you search for anything with mistakes, it corrects them for
you while still returning relevant results. Isn't it incredible? 4
· Everyone uses Google search autocorrect autocomplete on a regular basis but seldom gives
it any thought. It's a fantastic illustration of how natural language processing is touching
millions of people across the world, including you and me.
· Both, search autocomplete and autocorrect make it much easier to locate accurate results.

Text Processing [CO1]

Natural Language Processing (NLP) has advanced significantly and now plays an important
role in multiple real-world applications like Chabot’s, search engines and sentiment analysis.
An early step in any NLP workflow is text pre-processing, which prepares raw textual data
for further analysis and modelling.
 Natural Language Text Processing
Notes
Chapter 1
Text processing involves cleaning and preparing raw text data for further analysis or model
training. Proper text pre-processing can significantly impact the performance and accuracy of
NLP models.

Importance of Text Pre-processing

Raw text data is usually noisy and unstructured, containing various inconsistencies such as
typos, slang, abbreviations and irrelevant information. Pre-processing helps in:
Improving Data Quality: Removing noise and irrelevant information ensures that the data
fed into the model is clean and consistent.
Enhancing Model Performance: Well-pre-processed text can lead to better feature
extraction, improving the performance of NLP models.
Reducing Complexity: Simplifying the text data can reduce the computational complexity
and make the models more efficient.
Text Pre-processing

1. Text Cleaning:
This is the first step where we remove unwanted things from the text. We get rid of HTML
tags if the text is from the web, remove special characters like punctuation and numbers, and
change all text to lowercase to make it uniform.

2. Tokenization:
In this step, we break the text into smaller parts called tokens. Tokens can be individual
words or sentences. There are two types: word tokenization (splitting into words) as well as
sentence tokenization (splitting into sentences).

3. Stop Word Removal:

Stop words are common words that don't add much meaning, like "and," "the," and "is." We
remove these words to make the data smaller and help models work better.

4. Stemming and Lemmatization:

These NLP preprocessing techniques reduce words to their basic forms. Stemming cuts off
 Natural Language Text Processing
Notes
Chapter 1
the ends of words (like "running" to "run"). Lemmatization considers the meaning and
context (like "better" to "good").

5. Part-of-Speech Tagging:
This step labels each word with its part of speech, such as noun or verb. It helps us
understand the grammar of the text better.

6. Named Entity Recognition (NER):

NER identifies important names in the text, like people, places, and organizations. This helps
extract useful information from the text.

7. Vectorization:
Finally, we convert the cleaned and tokenized text into numbers that machine learning
algorithms can use. Common methods include Bag of Words (BoW), which creates a matrix
of words, and Term Frequency–Inverse Document Frequency (TF-IDF), which highlights
important words in the text.

Stemming Vs Lemmatization:

[Link] Stemming Lemmatization

Stemming is faster because it chops Lemmatization is slower as compared
1 words without knowing the context of the word to stemming but it knows the context of
in given sentences. the word before proceeding.
2 It is a rule-based approach. It is a dictionary-based approach.
3 Accuracy is less. Accuracy is more as compared to Stemming.
When we convert any word into root-form Lemmatization always gives the
4 then stemming may create the non- dictionary meaning word while converting
existence meaning of a word. into root-form.
Lemmatization would be recommended when
Stemming is preferred when the meaning of
the meaning of the word is important for
the word is not important for analysis.
5 analysis.
Example: Spam Detection
Example: Question Answer
For Example: For Example:
6
“Studies” => “Studi” “Studies” => “Study”
 Natural Language Text Processing
Notes
Chapter 1
Language Model:
A language model is a machine learning LM model that predicts upcoming words. More
formally, a language model assigns a probability to each possible next word, or equivalently
gives a probability distribution over possible next words. Language models can also assign a
probability to an entire sentence. Thus an LM could tell us that the following sequence has a
much higher probability of appearing in a text:
all of a sudden I notice three guys standing on the sidewalk
than does this same set of words in a different order:
on guys all I of notice sidewalk three a sudden standing the
Understanding N-grams:
Definition:
N-grams are contiguous sequences of ’n’ items, typically words in the context of NLP. These
items can be characters, words, or even syllables, depending on the granularity desired. The
value of ’n’ determines the order of the N-gram.
Examples:
Unigrams (1-grams): Single words, e.g., “cat,” “dog.”
Bigrams (2-grams): Pairs of consecutive words, e.g., “natural language,” “deep learning.”
Trigrams (3-grams): Triplets of consecutive words, e.g., “machine learning model,” “data
science approach.”
4-grams, 5-grams, etc.: Sequences of four, five, or more consecutive words.

N-gram language model,

Let’s begin with the task of computing P(w|h), the probability of a word w given some
history h. Suppose the history h is “The water of Walden Pond is so beautifully” and we want
to know the probability that the next word is blue:
P(blue|The water of Walden Pond is so beautifully)

Why Language Models Are Needed

LMs help choose more likely word sequences in:

 Natural Language Text Processing
Notes
Chapter 1
 Machine Translation
Example:
P(high winds tonight)>P(large winds tonight)
 Spell Correction
P(about fifteen minutes from)>P(about fifteen minuets from)
 Speech Recognition
P(I saw a van)≫P(eyes awe of an)
 OCR & Handwriting Recognition – predicting unclear words from context
 Typing Suggestions / Context-sensitive spelling
P(College is closed...)>P(Collage is closed...)

Goal of Ngram Language Model

To compute the probability of a sentence or sequence of words occurring together:
P(W) = P (w1, w2, w3, w4, w5…wn) Joint Probability
Related task: probability of an upcoming word:
P (w5|w1, w2, w3, w4) Conditional Probability
A model that computes either of these:
P(W) or P (wn|w1, w2…wn-1) is called a language model

How N-gram Language Models Work

An n-gram language model uses n-grams to estimate how likely a given sequence of words is.
The core idea is the Markov assumption: the probability of each word depends only on the
preceding n-1 words, not the entire history. In other words, n-gram models approximate
language by looking at a sliding window of n words.
One way to estimate this probability is directly from relative frequency counts: take a very
large corpus, count the number of times we see The water of Walden Pond is so beautifully,
and count the number of times this is followed by blue. This would be answering the question
“Out of the times we saw the history h, how many times was it followed by the word w”, as
follows:

Problem of estimating probabilities directly from counts

With a large enough corpus, such as the web, we can compute these counts and estimate the
probability from above equation. While this method works fine in many cases, but in most
cases, it turns out that even the web isn’t big enough to give us good estimates. This is
because language is creative; new sentences are created all the time, and we won’t always be
able to count entire sentences. Even simple extensions of the example sentence may have
counts of zero on the web (such as “Walden Pond’s water is so transparent that the”; well,
used to have counts of zero)
 Natural Language Text Processing
Notes
Chapter 1

Probabilistic Language Modeling

Probabilistic language modeling represents how likely a sequence of words is using
probability theory.

There are two main objectives:

(1) Joint Probability of a Sentence
We compute the probability of a full sentence consisting of a sequence of words:
P(W) = P(w1, w2, w3, …, wn)
This tells us how likely an entire sentence is to occur.
(2) Conditional Probability of the Next Word
We compute the probability of a word given the words that come before it:
P(wn | w1, w2, …, w(n−1))
This is used for prediction tasks such as typing suggestions, speech recognition, and text
generation.
A model that computes either joint probability or conditional probability is called a Language
Model (LM).

Chain Rule of Probability

Language modeling uses the Chain Rule to break the probability of a sentence into smaller
conditional probabilities.
Basic identity:
P(B | A) = P(A, B) / P(A)
⇒ P(A, B) = P(A) P(B | A)
For multiple variables:
P(A, B, C, D) = P(A) P(B | A) P(C | A, B) P(D | A, B, C)
General Chain Rule:
P(x1, x2, x3, …, xn) = P(x1) P(x2 | x1) P(x3 | x1, x2) … P(xn | x1, …, x(n−1))
Example
For the sentence: “its water is so transparent”
P(its water is so transparent) =
P(its) × P(water | its) × P(is | its water) ×
P(so | its water is) × P(transparent | its water is so)
Thus, the probability of a sentence is the product of probabilities of each word given all
previous words.

N-Gram Model
Using the full chain rule is impractical because each word depends on all previous words.
Definition
An n-gram is a sequence of n words.
Bigram (2-gram): two-word sequence (e.g., “turn your”)
Trigram (3-gram): three-word sequence (e.g., “turn your homework”)
Core Idea
Instead of using the entire history, we approximate using only the last few words.
For a bigram model:
P(wn | w1, w2, …, w(n−1)) ≈ P(wn | w(n−1))
Example approximation:
 Natural Language Text Processing
Notes
Chapter 1
P(the | Walden Pond’s water is so transparent that)
≈ P(the | that)

Markov Assumption
This simplification is called the Markov Assumption.

OR

Statement: The probability of a word depends only on a limited number of previous words,
not the entire history.
In a bigram model:
P(wn | w1, …, w(n−1)) ≈ P(wn | w(n−1))
This reduces complexity and makes language modeling computationally feasible.

In Terms of Probability calculation

In other words, we approximate each component in the product

Estimating N-Gram Probabilities

Probabilities are estimated from counts in a corpus using Maximum Likelihood Estimation
(MLE).

Maximum Likelihood Estimation for NGrams

 Natural Language Text Processing
Notes
Chapter 1

Challenges:
Extremely large number of possible sentences
Not all sequences appear in the corpus
Many valid word combinations have zero counts
Language is creative; new sentences are always formed
This problem is known as data sparsity.

Bigram Sentence Probability

Example sentence with boundaries:
I want english food
Its probability under a bigram model is:
P(I | Start) × P(want | I) × P(english | want) × P(food | english) × P( End| food)

Ngram Model Numerical Example

 Natural Language Text Processing
Notes
Chapter 1

Numerical 1: Consider the following corpus

<s> I am Sam </s>
<s> Sam I am </s>
<s> I do not like green eggs and ham </s>
Calculate the Probability for all Bigrams.

Answer:
P (I | <s>) = 2/3 = .67
P(</s> | Sam) = 1/2 = 0.5
P (Sam | <s>) = 1/3 = .33
P (Sam | am) = 1/2 = .5
P (am | I) = 2/3 = .67
P (do | I) = 1/3 = .33

Numerical 2: Estimating Bi-gram probabilities

Question:
What is the most probable next word predicted by the model for the following word
sequence? Consider the following Corpus

<s> I am Henry </s>

<s> I like college </s>
<s> Do Henry like college </s>
<s> Henry I am </s>
<s> Do I like Henry </s>
<s> Do I like college </s>
<s> I do like Henry </s>

Word Frequencies
<s> 7
</s> 7
I 6
am 2
Henry 5
like 5
college 3
do 4

1) <s> Do?
 Natural Language Text Processing
Notes
Chapter 1
Next word prediction probability
wi−1=do

Formula:

P(</s> | do) = 0/4

P (I | do) = 2/4
P (am | do) =0/4
P (Henry | do) = 1/4
P (like | do) = 1/4
P (college | do) = 0/4
P (do | do) = 0/4

2) <s> I like Henry?

Next word prediction probability

wi−1=Henry

Formula:

P(</s> | Henry) = 3/5

P (I | Henry) = 1/5
P (am | Henry) = 0
P (Henry | Henry) = 0
P (like | Henry) = 1/5
P (college | Henry) = 0
P (do | Henry) = 0

</s> is more probable

Numerical 3:
 Natural Language Text Processing
Notes
Chapter 1
For the following corpus C₁ of 3 sentences, what is the total count of unique bigrams for
which the likelihood will be estimated? Assume we do not perform any pre-processing, and
we are using the corpus as given.

 Alice went to the cafe

 Bob was waiting for Alice
 Alice and Bob went to the museum

a. 15
b. 16
c. 17
d. 18

Why Do We Use Log Probabilities in N-gram Language Models?

In an N-gram language model, the probability of a sentence is computed as a product of many

conditional probabilities:

Since each probability is less than 1, multiplying many of them creates several practical
problems. Log probabilities solve these issues.

Problems with Using Raw Probabilities

1. Numerical Underflow

 Conditional probabilities are small numbers (e.g., 0.1, 0.01, 0.001).

 Multiplying many small numbers of results in extremely tiny values.
 Computers may round these values to 0 due to limited floating-point precision.
 This makes different sentences appear equally improbable.

2. Computational Inefficiency

 Sentence probability requires many multiplications.

 Multiplication is computationally more expensive than addition.
 Large-scale NLP systems perform millions of such calculations.

3. Difficulty in Comparison

 Exact probability values are not important; we only need to compare which sentence
is more probable.
 Raw probabilities become too small to compare reliably.

4. Mathematical Complexity
 Natural Language Text Processing
Notes
Chapter 1
 Many machine learning objectives (e.g., cross-entropy, perplexity, maximum
likelihood) involve products of probabilities.
 Products are harder to differentiate and optimize than sums.

5. Loss of Numerical Precision

 Floating-point systems have limited precision.

 Repeated multiplication increases rounding errors.

Solution: Using Log Probabilities

We apply the logarithm to convert products into sums:

log⁡(ab)=log⁡a+log⁡b

So, sentence probability becomes:

Evaluating Language Models: Training, Test Sets, and Perplexity [CO3]

1. Extrinsic and Intrinsic Evaluation

Extrinsic Evaluation

 Evaluates a language model by embedding it in a real application.

 Measures how much the overall application improves.
 Example applications include speech recognition and machine translation.
 It is the only way to know whether improvements in a language model actually help a
task.
 This type of evaluation is expensive because it requires running complete NLP
systems.

Evaluating language model

Intrinsic Evaluation

 Measures the quality of a language model independently of any application.

 Provides a fast way to compare language models.
 Perplexity is the standard intrinsic evaluation metric.
 Used for both n-gram models and large neural language models.

Evaluating Models Using Probability

 Natural Language Text Processing
Notes
Chapter 1
 A better language model assigns a higher probability to the test set.
 Higher probability means better prediction of word sequences.
 Models are compared by how well they predict unseen test data.
 Probability must be computed only on data not seen during training.

Perplexity

Definition

 Perplexity is the inverse probability of the test set.

 It is normalized by the number of words or tokens.
 It measures how surprised a model is by the test data.
 Lower perplexity indicates a better language model.

Evaluating language model

For a test set W=w1, w2, wn:

Perplexity Formula

Using the chain rule:

Perplexity for Different n-gram Models

Unigram Model

Bigram Model

Interpretation of Perplexity
 Natural Language Text Processing
Notes
Chapter 1
 Lower perplexity means the model predicts words better.
 Higher probability → lower perplexity.
 Perplexity values are only comparable when models use the same vocabulary.
 A reduction in perplexity does not always guarantee better task performance.
 End-to-end evaluation is still important.

Perplexity as Weighted Average Branching Factor

 Branching factor = number of possible next words.

 Perplexity represents a weighted average branching factor.
 If word probabilities are uniform, perplexity equals branching factor.
 If some words are more probable, perplexity becomes smaller.
 This shows how predictability reduces perplexity.

Perplexity as Weighted Average Branching Factor

It turns out that perplexity can also be thought of as the weighted average branch ing factor of a
language. The branching factor of a language is the number of possible next words that can follow
any word. For example consider a mini artificial language that is deterministic (no probabilities), any
word can follow any word, and whose vocabulary consists of only three colors:

L ={red,blue,green}

The branching factor of this language is 3. Now let's make a probabilistic version of the same LM,
let’s call it A, where each word follows each other with equal probability 1 3 (it was trained on a
training set with equal counts for the 3 colours), and a test set T = “red red red red blue”. Let’s first
convince ourselves that if we compute the perplexity of this artificial colour language on this test set
(or any such test set) we indeed get 3. By Eq. 3.15, the perplexity of A on T is:

But now suppose red was very likely in the training set of a different LM B, and so B has the following
probabilities: P(red) =0.8 P(green)=0.1 P(blue)=0.1

We should expect the perplexity of the same test set red red red red blue for language model
Btobelowersince mostof the time the next color will be red, which is very predictable, i.e. has a high
probability. So the probability of the test set will be higher, and since perplexity is inversely related
to probability, the perplexity will be lower. Thus, although the branching factor is still 3, the
perplexity or weighted branching factor is smaller:

Advanced: Perplexity's Relation to Entropy [CO3]

 Natural Language Text Processing
Notes
Chapter 1
Basic Smoothing, Advanced Smoothing Models.

Problem with Maximum Likelihood Estimates (MLE)

 Any finite training corpus will miss some valid English word sequences.
 Some n-grams may never occur in training data but appear in the test set.
 Example: the words ruby and slippers appear in training data, but the phrase ruby
slippers does not.
 Such unseen n-grams are called zeros (zero-probability n-grams).

Why Zero-Probability n-grams Are a Problem

 Zero-probability sequences cause underestimation of probabilities for valid word

sequences.
 This reduces the performance of applications using the language model.
 If any word in the test set has probability 0, the probability of the entire test set
becomes 0.
 Perplexity is based on the inverse probability of the test set.
 If the test set probability is 0, perplexity cannot be computed because division by zero
is not possible.
 Natural Language Text Processing
Notes
Chapter 1

Edit distance - Dynamic Programming Approach

We often need a way to compare how similar two words or strings are in tasks like automatic
speech recognition or machine translation, where we want to know how similar the sequence
of words is to some reference sequence of words.
Edit distance gives us a way to quantify these intuitions about string similarity. More
formally, the minimum edit distance between two strings is defined as the minimum number
of editing operations (operations like insertion, deletion, substitution) needed to transform
one string into another.
For example, the gap between intention and execution, is 5 (delete an i, substitute e for n,
substitute x for t, insert c, substitute u for n). It’s much easier to see this by looking at the
most important visualization for string distances, an alignment between the two strings,
shown in Fig. Below. Representing the minimum edit distance between two strings as an
alignment. The final row gives the operation list for converting the top string into the bottom
string: d for deletion, s for substitution, i for insertion.

Given two sequences, an alignment is a correspondence between substrings of the two

sequences. Thus, we say I aligns with the empty string, N with E, and so on. Beneath the
aligned strings is another representation; a series of symbols expressing an operation list for
converting the top string into the bottom string: d for deletion, s for substitution, i for
insertion.
We can also assign a particular cost or weight to each of these operations. The Levenshtein
distance between two sequences is the simplest weighting factor in which each of the three
operations has a cost of 1 (Levenshtein, 1966)—we assume that the substitution of a letter for
itself, for example, t for t, has zero cost. The Lev enshtein distance between intention and
execution is 5.
Levenshtein also proposed an alternative version of his metric in which each insertion or
deletion has a cost of 1 and substitutions are not allowed. (This is equivalent to allowing
substitution, but giving each substitution a cost of 2 since any substitution can be represented
by one insertion and one deletion).
Using this version, the Levenshtein distance between intention and execution is 8.
 Natural Language Text Processing
Notes
Chapter 1

The Minimum Edit Distance Algorithm

How do we find the minimum edit distance?
We can think of this as a search task, in which we are searching for the shortest path—a
sequence of edits—from one string to another.

The space of all possible edits is enormous, so we can’t search naively.

However, lots of distinct edit paths will end up in the same state (string), so rather than
recomputing all those paths, we could just remember the shortest path to a state each time we
saw it. We can do this by using dynamic programming.
The intuition of a dynamic programming problem is that a large problem can be solved by
properly combining the solutions to various subproblems. Consider the shortest path of
transformed words that represents the minimum edit distance between the strings intention
and execution shown in Fig below

The minimum edit distance algorithm

It an example of the class of dynamic programming algorithms. The various costs can either
be fixed (e.g., ∀x,ins-cost(x) = 1) or can be specific to the letter (to model the fact that some
letters are more likely to be in serted than others). We assume that there is no cost for
substituting a letter for itself (i.e., sub-cost(x,x) = 0)
 Natural Language Text Processing
Notes
Chapter 1

Applying the above algorithm to Calculate the Minimum Edit Distance between
intention and execution

Alignment
Knowing the minimum edit distance is useful for algorithms like find ing potential spelling
error corrections.
But the edit distance algorithm is important in another way; with a small change, it can also
provide the minimum cost align ment between two strings.
Aligning two strings is useful throughout speech and language processing. In speech
recognition, minimum edit distance alignment is used to compute the word error rate
 Natural Language Text Processing
Notes
Chapter 1
Alignment plays a role in ma chine translation, in which sentences in a parallel corpus (a
corpus with a text in two languages) need to be matched to each other.

Figure above also shows the intuition of how to compute this alignment path. The
computation proceeds in two steps.
Step 1: we augment the minimum edit distance algorithm to store back pointers in each cell.
The back pointer from a cell point to the previous cell (or cells) that we came from in
entering the current cell. We’ve shown a schematic of these back pointers in Fig. above.
Some cells have multiple back pointers because the minimum extension could have come
from multiple previous cells.
Step 2: we perform a backtrace. In a backtrace, we start from the last cell (at the final row and
column) and follow the pointers back through the dynamic programming matrix. Each
complete path between the final cell and the initial cell is a minimum distance alignment.