Module-I:

Introduction to Natural Language

Processing

Dr. Pamela Chaudhury

1
Outline

• Introduction to NLP
• Language modelling
• Word level Analysis: Use of FSA
• Spelling error detection
• POS Tagging
• Syntactic Analysis, parsing
• Semantic Analysis
• Information Retrieval system
• Machine Translation system
• Speech synthesis and recognition
• Other Applications

2
Books

• Speech and Language Processing – An introduction to Language

Processing, Computational Linguistics, and Speech Recognition, D.
Jurafsky and J. H. Martin, Pearson Education

• Natural language Processing and Information Retrieval, T. Siddiqui

and U. S. Tiwar, Oxford University Press

3
 Question Answering: IBM’s Watson

• Won Jeopardy on February 16, 2011!

WILLIAM WILKINSON’S
“AN ACCOUNT OF THE PRINCIPALITIES OF
WALLACHIA AND MOLDOVIA” Bram Stoker
INSPIRED THIS AUTHOR’S
MOST FAMOUS NOVEL

4
 Event: Curriculum meet
Information Extraction Date: Jan-16-2012
Start: 10:00am
End: 11:30am
Subject: curriculum meeting Where: Gates 159
Date: January 15, 2012
To: Dan Jurafsky

Hi Dan, we’ve now scheduled the curriculum meeting.

It will be in Gates 159 tomorrow from 10:00-11:30.
-Chris

Create new Calendar entry

5
Information Extraction & Sentiment Analysis

Attributes:
zoom
affordability
size and weight
flash
ease of use
Size and weight
• nice and compact to carry!
✓ • since the camera is small and light, I won't need to carry around those
✓ heavy, bulky professional cameras either!
• the camera feels flimsy, is plastic and very light in weight you have to be
✗ very delicate in the handling of this camera

6
 Machine Translation

• Helping human translators

• Fully automatic
Enter Source Text:

这 不过 是 一 个 时间 的 问题 .

Translation from Stanford’s Phrasal:

This is only a matter of time.

7
 Language Technology
making good progress
Sentiment analysis still really hard
Best roast chicken in Bhubaneswar!
mostly solved Question answering (QA)
The waiter ignored us for 20 minutes.
Q. How effective is ibuprofen in reducing
Spam detection Coreference resolution fever in patients with acute febrile illness?

Let’s go to Agra! ✓
✗
Carter told Mubarak he shouldn’t run again. Paraphrase
Buy Sreeram stock …
Word sense disambiguation XYZ acquired ABC yesterday
(WSD)
I need new batteries for my mouse. ABC has been taken over by XYZ
Part-of-speech (POS) tagging
ADJ ADJ NOUN VERB ADV Summarization
Colorless green ideas sleep furiously. Parsing The Dow Jones is up Economy is
I can see Alcatraz from the window! The S&P500 jumped good
Housing prices rose
Named entity recognition (NER) Machine translation (MT)
PERSON ORG LOC 第13届上海国际电影节开幕… Dialog Where is Citizen Kane playing in SF?
Einstein met with UN officials in Princeton
The 13th Shanghai International Film Festival…
Castro Theatre at 7:30. Do
Information extraction (IE) you want a ticket?
Party
You’re invited to our dinner May 27
party, Friday May 27 at 8:30 add

8
 Ambiguity makes NLP hard:

Teacher Strikes Idle Kids

Bank visits reduced in 2022
Juvenile Court to Try Shooting Defendant
Local High School Dropouts Cut in Half

9
 Why else is natural language
understanding difficult?
non-standard English segmentation issues idioms
Great job @justinbieber! Were
SOO PROUD of what youve dark horse
the New York-New Haven Railroad
accomplished! U taught us 2 get cold feet
the New York-New Haven Railroad
#neversaynever & you yourself lose face
should never give up either♥ throw in the towel

neologisms world knowledge tricky entity names

unfriend Mary and Sue are sisters. Where is A Bug’s Life playing …
Retweet Mary and Sue are mothers. Let It Be was recorded …
… a mutation on the for gene …

But that’s what makes it fun!

10
 Introduction
Natural Language:
• Language spoken and written by human for general purpose
communication
• Examples : Odia, Hindi, English, French, Chinese, ………,
etc

Natural Language Processing (NLP):

• Focuses on processing, understanding and generating natural
languages by machines.

11
 Overview of the NLP Field

Computer Science

Artificial Intelligence Linguistics

Create Intelligent Scientific study of

machines and robots natural languages
Natural Language Processing

 Designing intelligent machines that

understands and generates human
languages

12
 Need of Processing Human Languages
• To develop different Human-computer Interactive systems
through natural languages.

• Allows to communicate with machines through human

languages

• To design different information processing systems

• to work on digital documents/data represented in natural
languages

13
Applications of NLP

14
 Example: The Search Engines

• The Web made it possible to access a large amount of information

quickly

• Search engines provides the required information quickly at finger tip

15
 Applications of NLP

• Information Retrieval
• Machine Translation
• Text Summarization
• Information Extraction Other Applications:
• Question Answering • Dictionary word suggestion
• Text to Speech • Spelling error/ grammar
• Speech to Text correction
• Chat bots
• Sentiment analysis
• …..

16
 Applications of NLP Cont…

Information Retrieval (IR):

• Focuses on retrieving the documents from a large document repository
based on their relevance to a user’s query.

• The IR technology is used in online search engines, library information

retrieval, organizational data retrieval, etc

Information Extractions (IE):

• Refers to the automatic extraction of structured information from
unstructured sources.

• The IE technology can be used to retrieve specific text such as place,

organization, people, monetary values, etc from unstructured
documents and present them in the form of a structured report.

17
 Applications of NLP Cont…
Text Summarization:
• The goal of automatic summarization is to take an information source,
extract contents from it and provide the most important contents to the
user in a concise form as a summary.

• It has its applications in obtaining document summaries, storylines of

events, summarization of user-generated content, etc.

Question Answering:
• Concerns with building systems that can automatically answer
questions posed by users in a natural language.

• It has its applications in designing experts question answering systems

on different domains such as: medical, agricultural, legal, etc

18
 Applications of NLP Cont…
Text to Speech:
• A text-to-speech (TTS) system converts natural language text into
speech
• It has its applications in designing speech synthesizers, screen
readers, language learning apps, etc.

Speech to Text:
• Speech to text (STT) conversion is the process of converting spoken
words into written texts.
• This is also called speech recognition.
• It has its applications in designing text dictation systems, command
and control, audio document transcription, etc

19
 Advanced Applications

• Virtual Assistants:

• Apple- Siri

• Amazon- Alexa

• Microsoft- Cortana

• Google: Google Assistant

20
 2. A Brief History of NLP
Application Development
• 1950: Mathematical model of computation (Turing machine)
Turing machines, first described by Alan Turing in Turing 1936–7, are simple
abstract computational devices that help investigate the extent and limitations of
what can be computed. Turing’s ‘automatic machines’, were devised for the
computing of real numbers. Today, they are considered to be one of the foundational
models of computability and (theoretical) computer science

21
History

• 1957: Rule based syntactic structures (Chomsky’s Syntactic

Structures)

The rules of how to order words help the language parts make
sense. Sentences often start with a subject, followed by a predicate
(or just a verb in the simplest sentences) and contain an object or a
complement (or both), which shows, for example, what's being acted
upon.

22
History

1969: Conceptual dependency theory

• Conceptual dependency (or CD) is a theory of how to represent the

meaning of natural language sentences in a way that:
•First, facilitates for drawing inferences from the sentences.
•Second, it has been argued that the representation (CD) is
independent of the language in which the sentences were originally
stated

23
History

• 1970: Finite State Automata concepts

Finite automata is an abstract computing device. It is a mathematical model of a

system with discrete inputs, outputs, states and a set of transitions from state to
state that occurs on input symbols from the alphabet
• Up to 1980s: NLP systems based on complex sets of hand-
written rules

• 1980 onwards: NLP with machine learning algorithms

• 1990s: NLP systems based on Statistical models

• 2000 onwards: NLP systems applied with advanced machine

learning techniques

24
 Issues and Processing Complexities
1. Ambiguity:
• Natural languages are highly ambiguous
• Words in a natural language may have a number of different
meanings.

Examples:
• Bank (River bank/ Financial Institution),
• Bat( cricket bat/ species)

• For many NLP task, the proper sense of each ambiguous word
in a sentence must be determine to interpret correct meaning.

25
 Cont…

2. Language Variability:
• There are various ways to express meaning

• A large number of languages are available world wide

• most of the languages use different character set, structure and
grammar rules.

• It is difficult to design a language processing model that can capture

all language variability.

26
 Cont…
3. Difficult to incorporate human cognition over
machine:

• It is difficult to capture all required knowledge human use to

process natural languages

• People have no trouble understanding language as they have-

common sense knowledge, reasoning capacity and experience

• Computers have- no common sense knowledge and no

reasoning capacity

27
 How can a machine understand these
differences?
Examples:

 Decorate the cake with the kids.

 Throw out the cake with the kids.

 The man saw the girl with a telescope in a park.

 Stolen painting found by tree.

 The old man finally kicked the bucket.

28
 Issues in Processing Indian
Languages
1. Unlike English, Indic scripts have a nonlinear structure.

• Example:
Language Script
English English language
Hindi हिन्दी भाषा
Odia ଓଡ଼ିଆ ଭାଷା
Bengali: বাাংলা ভাষা

29
 Cont…
2. English uses SVO (Subject-Verb-Object) format while Indian
languages uses SOV (Subject-Object-Verb) format

Example:
English: pooja plays veena
(S) (V) (O)

Hindi: pooja veena Bajati hai

(S) (O) (V)

30
 Cont…

3. Indian languages have a free word order

• i.e. words can be moved freely within a sentence without

changing the meaning of the sentence

Example:
Usne khaanaa khaya
or
Usne khaaya Khanaa

31
 Cont…
4. Have rich set of morphological variants

• Example: variants of the word ‘horse’

Hindi:
ghodda, ghodde, ghoddi, ghoddon……

32
 Cont…
5. Extensive and productive use of complex predicates

Example:
हिन्दी
शब्द
सम्पर्
ू ण

33
 Cont…
6. Ambiguity:

Example:
सोना

34
 Language and Grammar

• Automatic processing of language requires the rules and

exceptions of a language to be explained to the computer.

• Grammar defines the language

• It consists of a set of rules that allows parse and generate

sentences in a language

35
2 Main Components of NLP

36
3. Phases of Natural Language
Processing

Lexical Analysis Word level

analysis

Phrase level analysis

Syntactic Analysis based on grammar rules

Sentence level analysis

Semantic Analysis focusing on meaning

Discourse Analysis Paragraph level

Pragmatic Analysis Real world

knowledge
37
 Lexical Analysis
• Analysis of words (most fundamental units of any natural language)

• Word level processing requires Morphological Knowledge

• i.e. knowledge about the structure and formation of words from basic
units (morphemes)

• A morpheme is the smallest meaningful unit in a language

Example:
• cat (1 morpheme)
• cats (2 morphemes: ‘cat’, ‘s’)

• Rules for forming words are language specific

38
 Syntactic Analysis
• Analysis of sequence of words as a unit(i.e. a sentence) and
find its structure.
• It involves decomposes a sentence in to its constituents (or
words) and identifies the relation between them
• Requires Syntactic Knowledge (how words are combined to
form large units and constructs imposed on them)

Example:
“she is going to the market” valid sentence
“she are going to the market” invalid sentence

39
 Semantic Analysis
• Concerned with creating meaningful representation of linguistic
inputs.

• Example: “colorless green ideas sleep furiously”

(Syntactically correct but semantically anomalous)

• Requires semantic knowledge

• What words mean
• How word meanings combined in sentences to form sentence
meanings

40
 Discourse Analysis
• Attempts to interpret structure and meaning of even larger units
• The meaning of any sentence depends upon the meaning of the
sentence just before it.
• Requires Discourse Knowledge
• Knowledge of how the meaning of a sentence is determined
by processing sentences

Example:
She forgot her book.
To understand to whom- ‘she’, ‘her’ refers, processing of
previous sentences are required

41
 Pragmatic Analysis
• The meaning of a sentence can’t be always derived based on the
meaning of its words. Multiple interpretations of a sentence can be
possible.
• Syntactic structure and compositional semantics fail to explain
these interpretations.
• Pragmatic analysis deals with the purposeful use of sentences in
situations.
• It requires real world knowledge along with language knowledge

Example:
Do u know who am I?
(different context of use can be
possible)

42
 Major Approaches of NLP

• Rationalist approach(Symbolic approach)

• Empiricist approach
 Rationalist Approach (Symbolic approach)
• Assumes existence of some language faculty in human brain

• Machines can be made to function like human brain by giving some

basic knowledge and reasoning mechanisms.

• Linguistic knowledge is explicitly encoded in rule or other forms of

representation
 Empiricist Approach

• No language faculty

• Believes in existence of some general organization principles:

• Pattern reorganization
• Generalization
• Association

• Learning of detailed structures can takes place through the

applications of these principles on sensory inputs available

• Focused on use of large amount of data and procedures involving

statistical manipulation
 Classification of Computational Models
Knowledge driven:
• Rely on explicitly coded linguistic knowledge expressed as a set of hand
crafted grammar rules
• Constrained by the lack of sufficient coverage of domain knowledge
(acquiring and encoding such knowledge is difficult)

Data driven:
• Assumes the existence of large amount of data and techniques to learn
syntactic pattern
• Requires less human effort
• Performance depends on quantity of data
• Adaptive to noisy data
4. Language Modeling

47
 4. Language Modeling
• Language: Primary mean of communication used by human

• Grammar: Set of rules to generate sentences in a language

• Provides the mean to specify natural language

• Automatic processing of language requires rules and exceptions of

a language to be explained to the computer

• Language Modeling: Representation or model to process natural

language through a computer based program

48
 Types of Language Modeling

• Uses the grammar of a language to create

its model
Grammar-based

Example: Transformational Grammar(TG)

2 types

Statistical modeling Creates a language model by training

it from a corpus

Example:
n-gram model
49
 Grammar-based Language Modeling
• Uses the grammar of a language to create its model

• Represent the syntactic structure of language

Example:
S -> NP+VP //S: Sentence, NP: Noun Phrase, VP: Verb Phrase
Neha was going to school.

• It utilizes, the structure of a sentence (NP, VP) and relationships between

these structures.

• Examples of grammar based models:

• Transformational Grammar (TG), Government and Binding (GB),
Lexical Functional Grammar (LFG), Paninian grammar 50
Transformational grammar

• As per Chomsky an utterance is the surface representation of a

deeper structure representing a meaning.

• Sentences with different surface level representations having the

same meaning share a common deep level representation.

51
 Transformational Grammar
(Chomsky 1957)
• Assumes 2 levels of existence of sentences:
• Surface level
• Deep root level Deep structure:
S
Example:
sub obj
S: pooja plays veena reln

pooja plays veena

Surface structure:
S S

NP VP NP VP

pooja plays veena veena is played by pooja

52
 Cont…

• Transformational grammar has three components:

1. Phrase structure grammar

2. Transformational rule

3. Morphophonemic rule

53
 1. Phrase Structure Grammar
• Consists of rules that generate natural language sentences

• Assigns a structural description of natural languages

Example:

Set of rules: S: sentence

S→NP+VP NP: Noun Phrase N: Noun
VP →V+NP
VP: Verb phrase V:Verb
NP →Det+N
Det: Determiner (the, a, an)

• Sentences generated using these rules are called grammatical

54
 2. Transformational Rule

• Used to transform one surface representation into another

• Applied on the terminal strings generated by the phrase structure rules

Example:
• converting active sentence into passive

Plays-> played

55
Consider the active sentence :
The police will catch the snatcher.
The application of phrase structure rules will assign the structure shown
below:

56
• The transformational rules will convert it into:
The + snatcher + will + be + en + catch + by + police

57
 3. Morphophonemic rule

• is the study of word formation – how words are built up from smaller pieces
• Match each sentence representation to a string of phonemes:

Example:Morphology
morpho-phonemic rule will convert:
catch +en →caught

58
 Limitations of Grammar-based Language
Models
• A large number of re-writable rules which are language specific

• Generation of a complete set of rules covering all languages is a

challenging task.

59
 Probabilistic Language Models

• Today’s goal: assign a probability to a sentence

• Machine Translation:
• P(high winds tonite) > P(large winds tonite)
• Spell Correction
Why? • The office is about fifteen minuets from my house
• P(about fifteen minutes from) > P(about fifteen minuets from)
• Speech Recognition
• P(I saw a van) >> P(eyes awe of an)
• + Summarization, question-answering, etc., etc.!!
 Statistical Language Models
 A statistical language model is a probability distribution P(s) over
all possible word sequence (or words, sentences, paragraph,
documents, etc).
 It creates a language model by training it from a corpus
 The goal of statistical language model is to estimate the probability
(likelihood) of a sentence.

Example:
n-gram model

 It has applications in-

 Speech recognition, machine translation, spelling correction,
Information retrieval, etc
61
 Probabilistic Language Modeling

• Goal: compute the probability of a sentence or

sequence of words:
P(W) = P(w1,w2,w3,w4,w5…wn)
• Related task: probability of an upcoming word:
P(w5|w1,w2,w3,w4)
• A model that computes either of these:
P(W) or P(wn|w1,w2…wn-1) is called a language model.
• Better: the grammar But language model or LM is standard
How to compute P(W)

• How to compute this joint probability:

• P(its, water, is, so, transparent, that)

• Intuition: let’s rely on the Chain Rule of Probability

 Reminder: The Chain Rule

• Recall the definition of conditional probabilities

Rewriting:

• More variables:
P(A,B,C,D) = P(A)P(B|A)P(C|A,B)P(D|A,B,C)
• The Chain Rule in General
P(x1,x2,x3,…,xn) = P(x1)P(x2|x1)P(x3|x1,x2)…P(xn|x1,…,xn-1)
The Chain Rule applied to compute joint
probability of words in sentence

P(w1w2 … wn ) = Õ P(wi | w1w2 … wi-1 )

i
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)
How to estimate these
probabilities
• Could we just count and divide?

P(the | its water is so transparent that) =

Count(its water is so transparent that the)
Count(its water is so transparent that)
• No! Too many possible sentences!
• We’ll never see enough data for estimating these
 Markov Assumption

•Simplifying assumption:
Andrei Markov
P(the | its water is so transparent that) » P(the | that)
•Or maybe

P(the | its water is so transparent that) » P(the | transparent that)

 Markov Assumption

P(w1w2 … wn ) » Õ P(wi | wi-k … wi-1 )

•In other words, we approximate
i each
component in the product

P(wi | w1w2 … wi-1) » P(wi | wi-k … wi-1)

 Cont…
 The probability (likelihood) of a sentence can be estimated by
decomposing sentence probability into a product of conditional
probabilities using the chain rule:

P(s) = P(w1, w2, w3,....., wn)

= P(w1). P(w2/w1). P(w3/w1w2)...... P(wn/w1w2…. wn-1)

= , where hi is history of word wi defined

as-
w1 w2 ....., wi-1
 In order to calculate sentence probability, the probability of each
word is needed to be calculated, given the sequence of words
preceding it.
 The n-gram model approximates the probability of a word given all
the previous words by the conditional probability given previous
69
n-1 words only.
 n-gram Model
 An n-gram model calculates P(wi/hi) by modeling language as
Markov model of order n-1.

 i.e. by looking at previous n-1 words only.

when n=1: uni-gram

n=2: Bi-gram
n=3: Tri-gram
n=4 : Four-gram
n=5: Five-gram
……

70
 Simplest case: Unigram model

P(w1w2 … wn ) » Õ P(w i )
i
Some automatically generated sentences from a unigram model

fifth, an, of, futures, the, an, incorporated, a,

a, the, inflation, most, dollars, quarter, in, is,
mass

thrift, did, eighty, said, hard, 'm, july, bullish

that, or, limited, the

 Uni-gram Model
• In a uni-gram model, the probability of each word depends on its
own probability in the document/ corpus

Example:
If total no. of words in a corpus= 1,000,00 and the word ‘the’
appears 69971 times.
using un-igram model,
P(the)= 69971/100000
= 0.69971
= 0.7

72
 Bigram model

Condition on the previous word:

P(wi | w1w2 … wi-1) » P(wi | wi-1)

texaco, rose, one, in, this, issue, is, pursuing, growth, in,
a, boiler, house, said, mr., gurria, mexico, 's, motion,
control, proposal, without, permission, from, five, hundred,
fifty, five, yen

outside, new, car, parking, lot, of, the, agreement, reached

this, would, be, a, record, november

 Bi-gram Model
 In a bi-gram model, the probability of each word depends on its
previous word only.

 Probability of a word wi can be calculated as-

Example-1:
Training Corpus:
<s> I am Sam </s>
<s> Sam I am </s>
<s> I do not like eggs </s>

Using bigram model:

74
 Example-2
Training set:
The Arabian Knights
These are the fairy tales of the east
The stories of the Arabian Knights are translated in many
languages

Find the probability of the test sentence given below considering a

bigram model

Test sentence:
The Arabian Knights are the fairy tales of the east

75
 Answer
Training set:
The Arabian Knights
These are the fairy tales of the east
The stories of the Arabian Knights are translated in many languages

Bigram probabilities of words in training set:

P(the/<s>)=2/3= 0.67 P(Arabian/the)=2/5= 0.4 P(Knights/ Arabian)=
2/2= 1.0

P(these/<s>=1/3= .33 P(are/these)=1/1=1.0 P(the/are)=1/2=0.5

P (fairy/the)=1/5=0.2 P(tales/fairy)= 1/1=1.0 P(of/tales)=1/1=1.0
P(the/of)=2/2=1.0 P(east/the)=1/5=0.2

P(stories/the)= 1/5=0.2 P(of/stories)= 1/1=0.1 P(are/Knights)= 1/2 =0.5

P(translated/are)=1/2=0.5 P(in/translated)= 1/1=1.0 P (many/in)=
1/1=1.0
P(language/many)=1/1=1.0
76
 Estimating Sentence Probability
P(The Arabian Knights are the fairy tales of the east)

=P(The/<s>) × P(Arabian/the) × P (Knights/ Arabian) × P(are/

Knights) × P( the/are) × P(fairy/the) × P(tales/fairy) × P(of/tales)
× P(the/of) × P(east/the)

= 0.67 × 0.4 × 1.0 × 0.5

× 0.5 × 0.2 × 1.0 × 1.0
× 1.0 × 0.2

= 0.00268

77
 Raw bigram counts
• Out of 9222 sentences
Raw bigram probabilities

• Normalize by unigrams:

• Result:
Bigram estimates of sentence probabilities

P(<s> I want english food </s>) =

P(I|<s>)
× P(want|I)
× P(english|want)
× P(food|english)
× P(</s>|food)
= .000031
 Tri-gram Model
 In a tri-gram model, the probability of each word depends on its
previous 2 word.

 For the word sequence-

w1, w2, w3,... wi-2 ,wi-1,wi .., wn
history

 Probability of a word wi can be calculated as:

Example:
The Arabian Knights
P (Knights/ the Arabian)
81
 Example
Find probability of the below given test sentence using a tri-gram model.
Training set:
The Arabian Knights
These are the fairy tales of the east
The stories of the Arabian Knights are translated in many languages

Test Sentence:
The Arabian Knights are the fairy tales of the east

Answer:
Trigram probabilities:
P(The/<s1><s2>) = 2/3= 0.666=0.67 P(Arabian/<s2>the)=1/2=0.5
P (Knights/ the Arabian)= 2/2=1.0 P(are/Arabian Knights)= ?
……// find the tri-gram probabilities of other sequences

82
 Estimating Sentence Probability
P(The Arabian Knights are the fairy tales of the east)
= P(<s1><s2>The Arabian Knights are the fairy tales of the east)

=P(The/<s1><s2>) × P(Arabian/<s2>the) × P (Knights/ the

Arabian)
× P(are/ Arabian Knights) × P( the/Knights are) × P(fairy/are the)
× P(tales/the fairy) × P(of/fairy tales) × P(the/tales of)
× P(east/of the)

= ?
// calculate the sentence probability

83
Practice Examples on n-gram Model

84
 Example-1
Consider the following frequency matrix and Find the likelihood
estimate of the below sentence using bigram model:

‘The Arabian Knights’

Term frequency word sequence Relative

frequency
<s> 3
<s> The 3
The 5
The Arabian 2
Arabian 2
Knights 2 Arabian Knights 2

85
 Answer

P(The Arabian Knights)

=P(the/<s>) . P(Arabian/ the) . P (Knights /Arabian)

= (3/3). (2/5) . (2/2)

= 0.4

86
 Example-2
For the below given training set find bi-gram probability of all terms
in training set and find the probability of the given test sentence .

Training set:
I am Sam
Sam I am
I am not Sam

Test sentence:
I am not Sam

87
 Answer
Bigram probabilities:
P(I/<s>)=2/3=0.67
P(am/I)=3/3=1.0
P(sam/am)=1/3=0.33
P(sam/<s>)=1/3=0.33
P(I/Sam)=1/3)=0.33
P(not/am)=1/3=0.33
P(sam/not)=1/1=1.0

P(I am not Sam)

= P(I/<s>). P(am/I). P(not/am) .P Sam/not)
= 0.67 x 1.0 x 0.33 x 1.0
= 0.2211

88
Homework Questions

89
 Example-3

Find the sentence probability using a tri-gram model on example-2

Answer: 0.2211

90
 Example-4

Using sentence S1, S2, S3 as training data, find the probability of S4

using a bigram model.

S1: The section of all the intelligent students

S2: The students
S3: The intelligent students of this college

S4: The section of all the intelligent students of this college

Answer: 0.0103

91
 Data Sparseness Problem in n-gram Model

• An n-gram that does not occur in the training set is assigned a zero
probability

• Smoothing techniques:

• Add-one smoothing (or Laplace smoothing): assigns a count of

1 to unseen n-grams

• Caching technique: assigns the probability of the most recent

sequence

92
 Add-one Smoothing

• Also called Laplace smoothing

• Pretend we saw each word one more time than we did
• Just add one to all the counts

• MLE estimate: c(wi-1, wi )

PMLE (wi | wi-1 ) =
c(wi-1 )
• Add-1 estimate:

c(wi-1, wi )+1
PAdd-1 (wi | wi-1 ) =
c(wi-1 )+V
Where, V=no. of words in the vocabulary

93
 N-gram models

• We can extend to trigrams, 4-grams, 5-grams

• In general this is an insufficient model of language
• because language has long-distance dependencies:
“The computer which I had just put into the machine room on
the fifth floor crashed.”

• But we can often get away with N-gram models