NATURAL LANGUAGE

PROCESSING (18AI641)
Dr. Pushpalatha K
Professor
Sahyadri College of Engineering & Management
Language Modelling
• A language model is a description of language.
• Language modelling can be viewed either as a problem of
grammar inference or a problem of probability estimation.
▪ A grammar-based language model attempts to distinguish a
grammatical sentence from a non-grammatical one,
▪ A probabilistic language model attempts to identify a sentence
based on a probability measure, usually a maximum likelihood
estimate.
• Two approaches:
▪ Grammar-based language model
▪ Statistical language modelling
Language Modelling contd..
• Grammar-based language model
▪ A grammar-based approach uses the grammar of a language to create its model.
▪ It attempts to represent the syntactic structure of language.
• Grammar consists of hand-coded rules defining the structure and ordering of
various constituents appearing in a linguistic unit (phrase, sentence, etc.).
▪ Eg: a sentence usually consists of noun phrase and a verb phrase.
▪ The grammar-based approach attempts to utilize this structure and also the relationships
between these structures.
• Statistical language modelling
▪ The statistical approach creates a language model by training it from a corpus.
▪ In order to capture regularities of a language, the training corpus needs to be
sufficiently large.
▪ It is one of the fundamental tasks in many NLP applications, including speech
recognition, spelling correction, handwriting recognition, machine translation,
information retrieval, text summarization, and question answering.
Various Grammar-based Language Models
• Generative Grammars
▪ Introduced by Noam Chomsky in 1957
▪ States that sentences can be generated in a language if
collection of words and rules are known.
▪ Only those sentences that can be generated as per the
rules are considered grammatical.
▪ The complete set of rules which generates all possible
sentences in a language, provides the model of that
language.
Various Grammar-based Language Models contd..
• Hierarchical Grammar
▪ described by Chomsky in 1956
▪ Classes of grammars are in a hierarchical manner
• The top layer contained the grammars represented by its sub
classes
• Type 0 (or unrestricted} grammar contains Type 1 (or context
sensitive grammar}, which in turn contains Type 2 (context-free
grammar} and that again contains Type 3 grammar (regular
grammar).
• This relationship can be extended to describe grammars at
various levels, such as in a class-sub class (embedded}
relationship.
Various Grammar-based Language Models contd..
• Government and Binding (GB)
▪ Is a syntactic framework within Generative Grammar developed by Noam
Chomsky in 1981.
▪ Transformational grammars assume two levels of existence of sentences one
at the surface level and the other at the deep root level
▪ Government and binding (GB) theories have renamed them as s-level and d-
level, and identified two more parallel levels of representation called
phonetic form (PF) and logical form (LF).
• PF is the interface with the Phonology where shapes, sounds, and groupings of
items are directly represented.
• LF is the interface with the Semantics.
Government and Binding (GB) contd..
▪ Transformational grammars have hundreds of
rewriting rules, which are generally language-specific
and also construct-specific.
• Generation of a complete set of coherent rules
may not be possible.
▪ The GB predicts that if rules for structural units can
be defined at the deep level, it will be possible to
generate any language with fewer rules.
• These deep-level structures are abstractions of
noun-phrase, verb-phrase, etc., and common to
all languages.
Government and Binding (GB) contd..
• Eg: Mahesh was killed
• In transformational grammar:

• In GB, s-structure d-structure

An inflectional ending
is a word part that is
added to the end of a
base word that
changes the number or
tense of a base word
Components of GB
• Government and binding (GB) comprise a set of theories that map the structures
from d-structure to s-structure and to logical form (LF) .
• A general transformational rule called Move α is applied at d-structure level and
s-structure level.
▪ This can move constituents at any place if it does not violate the constraints put by
several theories and principles.
• Simplest form of GB

• GB consists of 'a series of modules that contain constraints and principles' (Sells
1985) applied at various levels of its representations and the transformation rule,
Move α
Government and binding (GB) contd..
• The GB considers all three levels of representations (d-, s-, and LF) as
syntactic
▪ LF is also related to meaning or semantic-interpretive mechanisms.
• GB applies the same Move α, transformation to map d-levels to s-levels or
s-levels to LF level.
▪ LF level helps in quantifier scoping and also in handling various sentence
constructions such as passive or interrogative constructions.
• Consider the sentence: Two countries are visited by most travelers
▪ Its two possible logical forms are:
▪ LF1:[S Two countries are visited by [NP most travelers]]
▪ LF2: Applying Move α
[NP most travelers] [S Two countries are visited by ei].
▪ In LF1, the interpretation is that most travelers visit the same two countries.
▪ In LF2, when we move (most travelers] outside the scope of the sentence, the
interpretation can be that most travelers visit two countries, which may be different
for different travelers.
• GB is basically the formulation of theories or principles which
create constraints to disallow the construction of ill-formed
sentences
• The constraints of GB prohibits certain combinations and
movements.
▪ otherwise Move α can move anything to any possible
position.
• GB can specify that 'a constituent cannot be moved from
position X’
▪ where X can have value X1 in one language, X2 in another,
and so on
Organization of GB
X-Bar (X ) Theory
• In linguistics, X-bar theory is a model of phrase-structure grammar and a
theory of syntactic category formation
▪ It attempts to capture the structure of phrasal categories with a single
uniform structure called the X-bar schema, basing itself on the assumption
that any phrase in natural language is an XP (X phrase) that is headed by a
given syntactic category X.
• X-bar theory makes the claim that every single phrase in every single sentence
in the mental grammar of every single human language, has the same core
organization.
• X theory organizes the phase structures and the sentence structures as
maximal projections of some head
▪ According to x-bar theory, every phrase has a head.
• The head is the terminal node of the phrase
▪ Noun phrase (NP), verb phrase (VP), adjective phrase (AP) and
prepositional phrase(PP) are maximal projections of noun(N), verb (V),
adjective (A) and preposition (P) respectively.
• Represented as head X of their corresponding phrases , X={N,V,A,P}
• GB predicts projections at two levels • Specifier: determiners
▪ the, a, this
▪ projection of head at semi-phrasal level • Modifier: affect and enhance the
𝑋, meaning of a sentence.
▪ the second maximal projection at the ▪ I rode the earliest train
• Complement: something that
phrasal level (𝑋)ധ completes or perfects
• For sentences, ▪ Mary is a beautiful girl
• Argument : helps to complete
▪ the first level projection is denoted as S the meaning of a predicate
▪ the second level maximal projection is ▪ Jill likes Jack.
denoted by S'
 • representation • representation of • representation of • representation
of the NP the VP the AP of the PP
the food in a Ate the food in a Very proud of our In a dhabha
dhaba dhaba country PP
NP
VP AP

Det N
V PP Deg A
P NP
the PP
PP in a dhabha very A
N
V NP
in Det N
proud
of our country
in a dhabha ate The food
Food
a dhabha
[NPthe N[food] PP[ in a dhaba]]
• representation of the • Example
▪ John read a long book of
sentence
linguistics with a red cover
That she ate the food in
dhabha S

COMP S

NP VP
that INFL

she Ate the food

past
in dhabha
• Sub-categorization
▪ In linguistics, subcategorization denotes the ability/necessity for lexical items
(usually verbs) to require/allow the presence and types of the syntactic arguments
with which they co-occur.
▪ In GB, any maximal projection is used as the argument of a head and sub-
categorization is used as a filter to permit various heads to select a certain subset of
the range of maximal projections.
• the verb 'eat' can sub-categorize for NP which may result in a sentence 'ate
food’.
• the verb 'sleep' cannot be sub categorized because the sentence ‘slept the bed'
is not well formed.
▪ GB states that defining phrase structures as head projections and sub-categorization
helps ensure well-formed structures, even at the sentence level.
• Projection Principle
▪ The projection principle is a basic notion in GB.
▪ It places a constraint on the three syntactic representations and their mapping from
one to the other.
▪ It states that representations at all syntactic levels (i.e., d-level, s-level, and LF level)
are projections from the lexicon.
• Theta Theory-Theory) or The Theory of Thematic Relations
▪ In GB, sub-categorization places a restriction on syntactic categories which a head
can accept.
▪ Another restriction on the lexical heads is assignment of certain roles to its
arguments.
• These roles are pre-assigned and cannot be violated at any syntactical level as per
the projection principle.
• These role assignments are called theta-roles and are related to 'semantic-selection’.
• Theta-role and Theta-criterion
▪ There are certain thematic roles from which a head can select These are called Ɵ-
roles and they are mentioned in the lexicon
• Eg: the verb 'eat' can take arguments with θ- roles '(Agent, Theme)’
• Theta-Criterion
▪ It states that 'each argument bears one and only one θ - role, and each θ -role is
assigned to one and only one argument’
▪ Thus, each argument will have a unique θ -role and cannot be moved to a position
where it may acquire another θ -role.
▪ In GB, θ -roles are assigned at d-level only, where as theta-criterion is applied at all
the three levels.
Theta Roles
• Agent is a special type of role which can be assigned by a head to outside
arguments
▪ Agent is the thing that causes, or instigates, the action in a sentence.
▪ The one who intentionally initiates the action expressed by the predicate.
▪ Eg: The goalie caught the ball., The ball was caught by the goalie.
• Patient, or theme, is the thing affected by an action or the thing that
undergoes a change
▪ Eg: The basketball player bounced the ball
• Source designate the place from which, or person from whom, an action
originated
• Goal, or recipient, is the place toward which, or the person toward whom,
an action is directed
• Location designates the place at or in which an action takes place
Theta Roles example..
• John hit Greg.
agent theme
• Harry brought two fish from the store.
agent theme source
• The cookies were eaten in the kitchen by the baker.
theme location agent
• C command and Government
Lexical Functional Grammar (LFG) Model
• Lexical-Functional Grammar (LFG) is a model for the analysis of
language in which different types of linguistic information are
represented in separate dimensions, each with its own formalism.
▪ These dimensions are linked by mapping principles.
• LFG is a formalism for representing the native speaker’s syntactic
knowledge;
• LFG is a grammar framework in theoretical linguistics, a variety of
generative grammar;
• It has been designed to serve as a medium for expressing and
explaining important generalizations about the syntax of human
languages and thus to serve as a vehicle for independent linguistic
research
• LFG views language as being made up of multiple dimensions of structure.
▪ Each of these dimensions is represented as a distinct structure with its own rules, concepts, and form.
• LFG assigns 2 levels of syntactic description to every sentence of a language (primary structures)
▪ constituent structure or ‘c-structure’ and
▪ functional structure or ‘f-structure’.
• constituent structure (c-structure)
▪ derived from the usual phrase and sentence structure syntax
▪ encodes phrasal dominance and precedence relations, represented as a phrase structure tree.
▪ c-structure may vary substantially between languages.
• functional structure (f-structure).
▪ final product which encodes the information obtain d from phrase and sentence structure rules and
functional specifications.
▪ f-structure is a level of linguistic information that is relatively invariant between languages.
• It captures syntactic predicate–argument structure in terms of grammatical functions such as subject
and object
▪ An f-structure is a finite set of pairs of attributes and values
▪ F-structures are referred to as a projection from the c-structure because they are related to the c-
structure via a formal system of annotations
▪ The c-structure is built up on the basis of phrase structure rewrite rules.
• the S (sentence) is rewritten as an NP and a VP

• Above phrase structure rules in are annotated with functional equations.

▪ These equations provide the basis for computing the f-structure
(information about number, person, tense etc. is part of the lexical entries
of the nouns and the verb in the example.
▪ The up arrow refers to the f-structure of the mother node. i.e. VP in b
▪ the down arrow references the current node, i.e., V or NP in b
Sentence: A girl handed the baby a toy.
S

NP VP

Det N V NP NP

Det N Det N
A girl handed the baby a toy
• up arrow(↑) refers to the f-
structure of the mother node that
is on the left hand side of the rule.
• The down arrow(↓) symbol refers
to the f-structure of the node
under which it is denoted
• Eg:
• S → NP VP
( SUBJ) =  = 
NP says: My mother’s f-structure
has a SUBJ feature whose value
is my f-structure.
VP says: My mother’s f-structure
is my f-structure
f-structure: attributes
A feature value matrix: an unordered set of feature-value pair

Types of attributes:

NUM
PERS
Functional features
TENSE
…
Semantic feature PRED
SUBJ
OBJ
Grammatical relations ADJUNCT
COMP
…
f-structure:values

Types of values:

Value of the functional features: plu,

Atomic value
past, 3, fem
Semantic form value of PRED
f-structure value of grammatical relations

f-structures are reasonably invariant across languages

• c-structure
▪ Rules:
• S → NPVP
• VP → V {NP} {NP} pp* {S’}
• PP → P NP
• NP → Det N {PP}
• S' → Comp S
▪ where
S: sentence V: verb
P: preposition N: noun
S': clause Comp: complement
{} optional
*: Phrase can appear any number of times including blank.
▪ When annotated with functional specifications, the rules become:
She saw stars in the sky.
• The term 'lexical functional' is composed of two terms:
▪ the 'functional' part is derived from 'grammatical functions', such as
subject and object, or roles played by various arguments in a sentence.
▪ The 'lexical' part is derived from the fact that the lexical rules can be
formulated to define the given structure of a sentence and some of the
long distance dependencies, which is difficult in transformational
grammars
• LFG represents sentences at two syntactic levels
▪ constituent structure (c-structure)
• derived from the usual phrase and sentence structure syntax
▪ functional structure (f-structure).
• final product which encodes the information obtain d from phrase and
sentence structure rules and functional specifications
• She saw stars in the sky.
f-structure is the set of attribute-value
pairs, represented as
• LFG requires that all possible structures corresponding to passive constructs, dative constructs, etc.,
must be specified.
• If the given sentence does not match the specifications, it is said to be ill-formed.
• LFG imposes three conditions on f-structure
▪ Consistency In a given f-structure, a particular attribute may have at the most one value.
• Hence, while unifying two f-structures, if the attribute Num has value SG in one and PL in the other, it
will be rejected.
▪ Completeness: A function is called governable if it appears within the Pred value of some lexical form,
e.g., Subj, Obj, and Obj 2.
• Adjunct is not a governable function.
• When an f-structure and all its subsidiary f-structures contain all the functions that their predicates
govern, then and only then is the f-structure complete.
▪ For example, since the predicate 'see < (i Subj) (i Obj} >' contains an object as its governable function, a sentence
like 'He saw' will be incomplete.
▪ Coherence It maps the completeness property in the reverse direction.
• It requires that all governable functions of an f-structure, and all its subsidiary f-structures, must be
governed by their respective predicates. Hence, in the f-structure of a sentence, an object cannot be
• taken if its verb does not allow that object. Thus, it will reject the sentence, 'I laughed a book.’
• The completeness and coherence conditions are counterparts of Ѳ- criterion in GB theory.
• In LFG, the verb is converted to the participial form, but the sub-
categorization is changed directly. Consider the following example:
• Active: Tara ate the food.
• Passive: The food was eaten by Tara. Active: i Pred = 'eat <(i Subj} (i Obj}>'
Passive: i Pred = 'eat <(i Oblag} (i Subj} >'
• Here, [Link] represents oblique agent phrase. Similar rules can be applied
• in active and dative constructs for the verbs that accept two objects.
• Active: Tara gave a pen to Monika. Passive: Tara gave Monika a pen.
• Active: i Pred = 'give < (i Subj} (i Obh}(i Obj}>'
• Passive: i Pred = 'give < (i Subj} (i Obj} (i Oblg )>'
• Here, Oblgo stands for oblique goal phrase.
• Long Distance Dependencies and Coordination
• In GB, when a category moved, it creates an empty
category. In G, unbounded movement and coordination
is handled by the functional identity and by correlation
with the corresponding £-structure
• A noun phrase, as the term suggests, is a group of two or more words that functions like a
noun when put together
▪ a bird., the little boy., man of his word.
• Verb phrase is a group of words including a verb and its complements, objects, or other
modifiers that functions syntactically as a verb
▪ She will understand, The builders had arrived, The show is starting., Dana is coming to
participate in the program tomorrow.
• A prepositional phrase is a combination of a preposition, a modifier and its object.
▪ A prepositional phrase can be placed in the beginning, middle or end of a sentence based on
its role in that particular sentence.
▪ Prepositional phrases are just a part of the sentence it modifies and cannot stand alone.
• An adjective phrase, or adjectival phrase, is a group of words that include an adjective that
modifies (changes) a noun or pronoun
• An adjective phrase is a group of words headed by an adjective that describes a noun or a
pronoun.
▪ She speaks in a very slow voice., We never cycle in heavy rain. He had an incredibly loud
voice."
Paninian Framework
• Paninian grammar (PG) was written by Panini in 500 BC.
• Asian languages are SOV (Subject-Object-Verb) ordered and inflectionally
rich.
▪ The inflections provide important syntactic and semantic cues for language
analysis and understanding.
▪ The Paninian framework takes advantage of these features
• Some Important Features of Indian Languages
▪ morphologically rich language
▪ Relatively word order free
▪ Some languages like Sanskrit have the flexibility to allow word groups representing
subject, object, and verb to occur in any order.
• In Hindi, the position of subject and object can be changed
▪ Maan Bachche ko khanaa detii hai
▪ Mother child to food give
▪ Mother give food to the child.
▪ Bachche ko Maan khanaa detii hai
▪ Child to mother food give
▪ Mother gives food to the child
▪ The auxilary verbs follow the main verb
• khaa raha hai kartaa rahaa hal
• Eat-ing doing been has
• eating has been doing
▪ In Hindi, some verbs (main), e.g., give (dena), take (lena), also combine with
other verbs (main) to change the aspect and modality of the verbs.
• Usne khanaa khaayaa Usne khaanaa kha liyaa
▪ He (Subj) food ate He (Subj) food eat taken
▪ He ate food He ate food (completed the action
• Vo chala vo chal diya
He move given
▪ He moved He moved (started the action)
▪ In Indian languages, the nouns are followed by post-positions instead of
prepositions
Layered Representation in PG
• Paninian grammar framework is said to be syntactico-semantic, that is, one can
go from surface layer to deep semantics by passing through intermediate layers.
• It has 4 layers
▪ The surface level is the uttered or the written sentence
▪ Semantic level is what the person has in his mind
▪ PG specifies a mapping between the karaka level and the vibhakti level, and the vibhakti
level and the surface form.
• The vibhakti level is the level at which there are local word groups based on case endings,
preposition or postposition markers
▪ Vibhakti refers to word (noun, verb, or other) groups based either on case endings, or post-
positions, or compound verbs, or main and auxiliary verbs, etc.
▪ Word groups are formed based on various kinds of markers.
• These markers are language-specific, but all Indian languages can be represented at the. Vibhakti level
▪ Vibhakti for verbs includes the verb form and the auxiliary verbs
▪ The information about TAM (tense, aspect and modality) is given by the vibhakti for a verb.
• Karaka Level lies between this topmost level and vibhakti level
▪ At the karaka level, we have karaka relations and verb-verb relations etc.
▪ Karaka relations are syntactico-semantic (or semantico-syntactic) relations between the
verbs and other related constituents (typically nouns) in a sentence.
• Through these relations, the Karakas try to capture the information from the semantics of the texts.
▪ Thus, Karaka level processes the semantics of the language but represents it at the syntactic level.
• Hence, it acts as a bridge between semantic and syntactic analysis of a language.
▪ Paninian Grammar has its own way of defining Karaka relations
• These relations are based on the way the word groups participate in the activity denoted by the verb
group
▪ This is the level of semantics that is important syntactically and is reflected in the surface
form of the sentence.
Karaka Theory
• Karaka theory is the central theme of PG framework.
• Karaka relations are assigned based on the roles palyed by various
participants in the main activity.
▪ These roles are reflected in case markers and post position markers
▪ Reltions are similar to English but defined in different manner.
• the richness of the case endings found in Indian languages has been
used to its advantage.
• Karakas - direct participants in the action indicated by a verb root
▪ Karta (subject) - doer
▪ Karma (object) -locus of the result of the activity
▪ Karana (instrument)
▪ Sampradana (beneficiary/(recipient))
▪ Apadan(source/separation)
▪ Adhikaran (locationlocus).
Karakas explained..
• Maan bachchi ko aangan mein haath se rotii khilaatii hei
Mother child-to courtyard-in hand-by bread feed (s).
The mother feeds bread to the child by hand in the courtyard.
▪ maan' (mother) is the Karta
• Karta has generally 'ne' or ‘ ' case marker
▪ Rotii (bread) is karma
• karma has generally ‘ko' or ‘ ' case marker
▪ haath (hand) is karana
• karma has generally ‘dwara' or ‘ se' case marker
▪ bachchi (child) is ka Sampradana
• karma has generally ‘dwara' or ‘ se' case marker
• Maan ne thaali se khana uthakar bachthe ko diyaa
Mother-Karta plate from Apaadan food taking-up child-to gave.
The mother gave food to the child taking it up from the plate.
▪ thaali (plate) is Apadan
▪ aangan (courtyard) is Adhikaran
Issues In Paninian Grammar
• Computational implementation of PG
• Adaptation of PG to Indian, and other similar languages.
• PG is a multilayered implementation.
▪ The approach is named `Utsarga-Apvada’ (default-exception),
• where rules are arranged in multiple layers in such a way that each layer consists of rules
which are in exception to rules in the higher layer.
• Thus, as we go down the layer, more particular information is derived.
• Rules may be represented in the form of charts (such as Karaka chart and Lakshan chart).
▪ In cases of shared Karak relations many issues remain unresolved
▪ Another difficulty arises when mapping between the Vibhakti (case markers and
post-positions) and the semantic relation (with respect to verb) is not one to one.
• Two different Vibhakti can represent the same relation, or the same Vibhakti can represent
different relations in different contexts. T
• he strategy to disambiguate the various senses of words, or word groupings, are still the
challenging issues.
▪ As the system of rules is different in different languages, the framework requires
adaptations to tackle various applications in various languages.
STATISTICAL LANGUAGE MODEL
• A statistical language model is a probability distribution P(s) over all possible
word sequences (or any other linguistic unit like words, sentences, paragraphs,
documents, or spoken utterances).
▪ The dominant approach in statistical language modelling is the n-gram model.
• n-gram Model
▪ the goal of a statistical language model is to estimate the probability (likelihood) of a
sentence.
▪ This is achieved by decomposing sentence probability into a product of conditional
probabilities using the chain rule as follows:
• P(s)= P(w1, w2, w3,……….,wn)
• P(s)= P(w1) P(w2/w1) P(w3/w1 w2)…… P(wn/w1 w2 ……wn-1)
where hi, is history of word wi defined as wi w2 ,w i-I

▪ So, in order to calculate sentence probability, we need to calculate the probability of

a word, given the sequence of words preceding it
Example..
• Training corpus:
▪ <s> I am from Vellore </s>
▪ <s> I am a teacher </s>
▪ <s> students are good and are from various cities</s>
▪ <s> students from Vellore do engineering</s>
• Test data:
▪ <s> students are from Vellore </s>
• Steps
▪ Construct Unigram count matrix
▪ Construct Bigram count matrix
▪ Construct Bigram probability matrix
(normalized by unigram counts)
▪ P(<s> students are from Vellore </s>)
= P(students | <s>) * P(are | students) * P(from | are)
* P(Vellore | from) * P(</s> | Vellore)
= 1/4 * 1/2 * 1/2 * 2/3 * 1/2 = 0.0208
• As per the Bigram model, the test sentence can be
expanded as follows to estimate the bigram probability;
▪ P(<s> students are from Vellore </s>)
= P(students | <s>) * P(are | students) *
P(from | are) * P(Vellore | from) * P(</s> | Vellore)

count of sentence start (<s>) = 4,

count of string <s> students = 1

count of word students = 2,

count of string students are = 1
 count of word are = 2,
count of string are from = 1

count of word from = 3,

count of string from Vellore = 2

count of word Vellore = 2,

count of string Vellore </s> = 1

P(<s> students are from Vellore </s>)

= P(students | <s>) * P(are | students) * P(from | are)
* P(Vellore | from) * P(</s> | Vellore)
= 1/4 * 1/2 * 1/2 * 2/3 * 1/2 = 0.0208
• 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(s):
▪ The Arabian knights are the fairy tales of the east.
• Solution
▪ P(the/<s>= 0.67 P(Arabian/the) = 0.5 P(knights /Arabian) = 1.0
▪ P(are/these) =- 1.0 P(the/are) = 0.5 P(fairy/the) = 0.2
▪ P(tales/fairy) = 1.0 P(of/tales) = 1.0 P(the/of) = 1.0
▪ P(east/the) = 0.2 P(stories/the) = 0.2 P(of/stories) = 1.0
▪ P(are/knights) = 1.0 P(translated/are) = 0.5 P(in /translated) = 1.0 P(many/in) = 1.0
P(languages/many) = 1.0
▪ Test sentence:
• P(The/<s>) x P(Arabian/the) x P(Knights/Arabian) x P(are/knights) x P(the/are) x P(fairy/the) x
P(tales/fairy) x P(of/tales) x P(the/of) x P(east/the)
• 0.67 x 0.5x 1.0x 1.0 x 0.5 x 0.2 x 1.0 x 1.0 x 1.0 x 0.2 = 0.0067 -
• The n-gram model suffers from data sparseness problem.
▪ An n-gram that does not occur in the training data is
assigned zero probability, so that even a large corpus has
several zero entries in its bi-gram matrix.
▪ There are several long distance dependencies in natural
language sentences, which this model fails to capture.
▪ Smoothing techniques have been developed to handle
the data sparseness problem
Add-one Smoothing
• It adds a value of one to each n-gram frequency before normalizing them into
probabilities.
▪ Thus, the conditional probability becomes:

▪ where V is the vocabulary size, i.e., size of the set of all the words being considered.
• Issues:
▪ It assigns the same probability to all missing n-grams, even though some words are
more important.
▪ It shifts too much of the probability mass towards the unseen n-grams (n-grams with
0 probabilities) as there number is usually quite large
• Good-Turing smoothing considers the number of n-grams with a high frequency in
order to estimate the probability mass that needs to be assigned to missing or low-
frequency n-grams
Good—Turing Smoothing
• Good—Turing smoothing adjusts the frequency f of an gram using
the count of n-grams having a frequency of occurrence f+1.
• It converts the frequency of an n-gram from f to r using the
following expression

• where nf is the number of n-grams that occur exactly f times in the

training corpus.
• Eg:, consider that the number of n-grams that occur 4 times is
25,108 and the number of n-grams that occur 5 times is 20,542.
▪ Then, the smoothed count for 5 will be 20542/25108=4.09
Caching Technique
• The frequency of n-gram is not uniform across the text
segments or corpus.
• Certain words occur more frequently in certain segments (or
documents) and rarely in others.
• The basic n- gram model ignores this sort of variation of n-
gram frequency.
• The cache model combines the most recent n-gram frequency
with the standard n-gram model to improve its performance
locally.
• The underlying assumption here is that the recently discovered
words are more likely to be repeated.