NATURAL LANGUAGE PROCESSING

7th Semester CSE (R-19)

 Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

Subject Code Name of the Subject L T P C

NATURAL LANGUAGE PROCESSING 3 0 0 3

Course Educational Objectives
CEO 1 To analyze the leading trends and systems in natural language processing.

CEO 2 Make them understand the concepts of morphology, syntax, semantics and
pragmatics of the language and that they are able to give the appropriate
examples that will illustrate the above mentioned concepts.
CEO3 To recognize the significance of pragmatics for natural language understanding.
CEO4 Enable students to be capable to describe the application based on natural
language processing and to show the points of syntactic, semantic and pragmatic
processing.
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 2
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

Course Outcomes: Upon successful completion of this course, students should be able to:

CO1 Understand approaches to syntax and semantics in NLP.

Understand approaches to discourse, generation, dialogue and summarization
CO2
within NLP.
CO3 Understand current methods for statistical approaches to machine translation.
Understand machine learning techniques used in NLP, including the probabilistic
CO4
context-free grammars and unsupervised methods, as applied within NLP.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 3

 Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

SYLLABUS
UNIT:1 (10 Hours)
Introduction to Natural Language Processing: Need for processing natural languages, issues
and processing complexities in NLP, Brief history of NLP application development, Overview
of phases of natural language processing; Language Modeling: Various types of languages
and its modeling, Grammar based language models, Government and binding, Lexical
functional grammar for handling natural languages, Statistical modelling, n gram model.
UNIT:2 (12 Hours)
Word Level Analysis: Regular expressions, Finite state automata Morphological parsing,
Human morphological parsing, Spelling error detection and correction, Words and word
classes, Part of speech tagging, Rule-based tagger, Stochastic tagger, Unknown words.
Syntactic Analysis: Context free grammar, Phrase and sentence level constructions, Parsing:
Top-down parsing, Bottom-up parsing, A basic top-down parser, The Earley parser, The CYK
Parser, Probabilistic parsing: Estimating rule probabilities, Parsing PCFGs, Problems with PCFG.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 4

 Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

SYLLABUS
UNIT:3 (10 Hours)
Semantic Analysis: Meaning representation, Characteristics of meaning representation languages, Meaning
structure of languages, Syntax-driven semantic analysis, Semantic grammars, Lexical Semantics, Relations among
lexemes and their senses, WordNet, Internal structure of words, Ambiguity, Word sense disambiguation,
Selectional restriction-based disambiguation, Robust word sense disambiguation, Information retrieval, Other
Information retrieval tasks. Discourse Analysis: Context-based word sense disambiguation approaches,
Knowledge sources in WSD, WSD evaluation discourse context and world knowledge
UNIT:4 (10 Hours)
Natural Language Generation: Architecture of language generators, Surface realization, Discourse planning,
Template-based, phrase-based and feature-based natural language generation, Knowledge-based approaches.
Machine Translation: Machine translation system, Issues, Language similarities and differences, The transfer
metaphor, The interlingua idea: using meaning, Machine translation approaches: Direct machine translation, Rule-
based machine translation: Transfer-based and interlingua based, Statistical and example-based machine
translation, Semantic or knowledge based machine translation systems.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 5

 Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

Text Books:
1. Speech and Language Processing: An introduction to language processing, computational linguistics, and
speech recognition, D. Jurafsky and J. H. Martin, 2003, Pearson Education.
2. Natural language Processing and Information Retrieval, T. Siddiqui and U. S. Tiwary, 2008, Oxford University
Press.

Reference Books:
1. Natural Language Understanding, J. Allen, 2nd edition, 2008, Pearson Education.
2. Natural Language Processing- A Pananian Perspective, A. Bharathi, V. Chaitanya and R. Sangal, 1995, PHI
Learning.
3. Foundations of Statistical Natural Language Processing, Christopher D. Manning and Hinrich Schütze, 1999,
MIT Press.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 6

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

OUTLINE

Introduction to NLP
Origins
Language and Knowledge

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 7

 Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

INTRODUCTION

Language is the primary means of communication used by humans which we use to express
the greater part of our ideas and emotions
Natural Language Processing (NLP) is concerned with the development of computational
models of aspects of human language processing.
To develop automated tools for language processing
To Gain a better understanding of human communication
The two major approaches to NLP are
•Rationalist: assumes the existence of some lang. faculty in human brain
•Empiricist: Existence of some general organization principle such as pattern recognition, generalization
and association.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 8

 Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

INTRODUCTION

Natural Language Processing (NLP) includes both understanding (interpretation) and

generation (production)

Computational linguistics is concerned with the study of language using computational

models of linguistic phenomena. It deals with the application of linguistic theories and
computational techniques for NLP.

Computational models may be broadly categorized into:

Knowledge driven: often expressed as a set handcrafted grammar rules
Data driven: usually employ some machine learning techniques to learn syntactic patterns.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 9

 Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

LANGUAGE AND KNOWLEDGE (PHASES OF NLP)

Language, being a medium of expression, is the outer form of the content it expresses. As
computers are not able to understand the natural language methods are developed to map
its content in a formal language.
Level 1 – Speech sound (Phonetics & Phonology)
Level 2 – Words & their forms (Morphology, Lexicon)
Level 3 – Structure of sentences (Syntax, Parsing)
Level 4 – Meaning of sentences (Semantics)
Level 5 – Connected sentence processing in a larger body of text (Discourse)
Level 6 – Meaning in context & for a purpose (Pragmatics)

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 10

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

LANGUAGE AND KNOWLEDGE (PHASES OF NLP)

Lexical analysis: involves analysis of words.(word level processing).

Morphological knowledge is required i.e structure and formation of words from basic units
morphemes.
The rules for forming words from morphemes are language specific

Dog - Dog(s), Dog(ged), Lady – Lad(ies)

Should we store all forms of words in the lexicon?

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 11

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

LANGUAGE AND KNOWLEDGE (PHASES OF NLP)

Syntactic analysis: considers a sequence of words as a unit(sentence).
Decomposes a sentence into its constituents(words) and identifies how they related to each other.
Captures grammaticality and non-grammaticality of sentences by looking at constraints like word
order, number and case agreements.

✘ ✔
Went the I market to I went to the market
She are going to the market She is going to the market

Semantic analysis: associated with the meaning of the language.

Sometimes some valid sentences may be meaningless.
e.g: colorless green ideas sleep furiously.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 12

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

LANGUAGE AND KNOWLEDGE (PHASES OF NLP)

A word can have a number of possible meanings associated with it, some times its
context specific
e.g: kabir and Ayan are maried
Kabir and suhana are maried
In the above example we need pragmatic knowledge besides syntax and semantics

A still higher level of analysis is discourse analysis. Discourse-level processing attempts to

interpret the structure and meaning of even larger units, e.g., at the paragraph and
document level, in terms of words, phrases, clusters, and sentences.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 13

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

LANGUAGE AND KNOWLEDGE (PHASES OF NLP)

pragmatic knowledge may be needed for resolving anaphoric references. For example,
• The district administration refused to give the trade union permission for the
meeting because they feared violence.(1.2a)
• The district administration refused to give the trade union permission for the
meeting because they oppose government.(1.2b)
The highest level of processing is pragmatic analysis, which deals with the purposeful
use of sentences in situations. It requires knowledge of the world, i.e., knowledge that
extends beyond the contents of the text.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 14

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

CHALLENGES OF NLP

There are a number of factors that make NLP difficult. These relate to the problems of
representation and interpretation.
• It is almost impossible to embody all sources of knowledge that humans use to process
language. Even if this were done, it is not possible to write procedures that imitate
language processing as done by humans.
• perhaps the greatest source of difficulty in natural language is identifying its
semantics. (Our viewpoint is that words alone do not make a sentence. Instead, it is the
words as well as their syntactic and semantic relation that give meaning to a sentence.)

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 15

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

CHALLENGES OF NLP
• Idioms, metaphor, and ellipses add more complexity to identify the meaning of the
written text. As an example, consider the sentence:
“The old man finally kicked the bucket”.
The meaning of this sentence has nothing to do with the words ‘kick' and ‘bucket'
appearing in it.
• Quantifier-scoping is another problem. The scope of quantifiers (the, each, etc.) is
often not clear and poses problem in automatic processing.
• The first level of ambiguity arises at the word level. Without much effort, we can
identify words that have multiple meanings associated with them, e.g., bank, can, bat,
and still.
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 16
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

CHALLENGES OF NLP
• A word may be ambiguous in its part-of-speech or it may be ambiguous in its
meaning. The word ‘can' is ambiguous in its part-of-speech whereas the word 'bat' is
ambiguous in its meaning.
• Deciding whether 'can' is a noun or a verb is solved by 'part-of-speech tagging'
whereas identifying whether a particular use of bank' corresponds to 'financial
institution' sense or 'river bank sense is solved by 'word sense disambiguation'.
• A sentence may be ambiguous even if the words are not, for example, the sentence:
"Stolen rifle found by tree”. None of the words in this sentence is ambiguous but the
sentence is. This is an example of structural ambiguity.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 17

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

NLP APPLICATIONS

• Machine translation is the first application area of NLP. It involves the

complete linguistic analysis of a natural language sentence, and linguistic
generation of an output sentence. It is one of the most comprehensive and
most challenging tasks in the area (AI-complete). However, the recent
dramatic progress in the field of NLP has found interesting applications in
information retrieval, information extraction, text summarization, etc.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 18

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

NLP APPLICATIONS

The applications utilizing NLP include the following.

• Machine Translation: This refers to automatic translation of text from one human
language to another. In order to carry out this translation, it is necessary to have an
understanding of words and phrases, grammars of the two languages involved,
semantics of the languages, and world knowledge.
• Speech Recognition: This is the process of mapping acoustic speech signals to a set of
words. The difficulties arise due to wide variations in the pronunciation of words,
homonym (e.g. dear and deer) and acoustic ambiguities (e.g., in the rest and interest).

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 19

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

NLP APPLICATIONS

• Speech Synthesis: Speech synthesis refers to automatic production of

speech (utterance of natural language sentences). Such systems can read
out your mails on telephone, or even read out a storybook for you. In
order to generate utterances, text has to be processed. So, NIP remains
an important component of any speech synthesis system.
• Natural Language Interfaces to Databases: Natural language interfaces
allow querying a structured database using natural language sentences.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 20

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

NLP APPLICATIONS

• Information Retrieval: This is concerned with identifying documents

relevant to a user's query. NLP techniques have found useful applications
in information retrieval. Indexing (stop word elimination, stemming, phrase
extraction, etc.), word sense disambiguation, query modification, and
knowledge bases have also been used in IR system to enhance
performance.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 21

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

NLP APPLICATIONS

• Information Extraction: An information extraction system captures and

outputs factual information contained within a document. Similar to an
information retrieval system, it responds to a user's information need.
However, unlike in an IR system, the information need is not expressed as
a keyword query. Instead it is specified as pre-defined database
schemas or templates. Whereas an IR system identifies a subset of
documents in a large repository of text database.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 22

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

NLP APPLICATIONS
• Question Answering: Given a question and a set of documents, a question
answering system attempts to find the precise answer, or at least the
precise portion of text in which the answer appears. This is unlike an IR
system, which returns whole document that seems relevant to the user's
query.
 A question answering system is different from an information extraction system in
that the content that is to be extracted is unknown.
 In general, a question answering system benefits from having an information
extraction system to identify entities in the text.
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 23
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

NLP APPLICATIONS

 A question answering system requires more NLP than an information

retrieval system or an information extraction system. It requires not
only precise analysis of questions and portions of texts but also
semantic as well as background knowledge to answer certain type of
questions.
• Text Summarization: This deals with the creation of summaries of
documents and involves syntactic, semantic, and discourse level
processing of text.
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 24
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

LANGUAGE AND GRAMMAR

 Automatic processing of language requires the rules and exceptions

of a language to be explained to the computer. Grammar defines
language. It consists of a set of rules that allows us to parse and
generate sentences in a language. Thus, it provides the means to
specify natural language.
 The main hurdle in language specification comes from the constantly
changing nature of natural languages and the presence
of a large number of hard-to-specify exceptions.
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 25
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

LANGUAGE AND GRAMMAR

 Several efforts have been made to provide such specifications, which has led to
the development of a number of grammars. Main among them are
• Transformational grammar (Chomsky1957)
• Lexical functional grammar (Kaplan and Bresnan 1982)
• Government and Binding (Chomsky 1981)
• Generalized phrase structure grammar
• Dependency grammar
• Paninian grammar
• and Tree-adjoining grammar (Joshi 1985).
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 26
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

LANGUAGE AND GRAMMAR

Chomsky argued that phrase structure
grammars are not adequate to specify
natural language. He proposed a
complex system of transformational
grammar in his book on Syntactic
Structures (1957), in which he suggested
that each sentence in a language has
two levels of representation, namely, a
deep structure and a surface structure
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 27
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

LANGUAGE AND GRAMMAR

Chomsky argued that an utterance is the surface representation of a'deeper structure
representing its meaning. The deep structure can be transformed in a number of ways
to yield many different surface-level representations. Sentences with different
surface-level representations having the same meaning, share a common deep-level
representation.
Transformational grammar has three components:
1. Phrase structure grammar
2. Transformational rules
3. Morphophonemic rules These rules match each sentence representation to a
string of phonemes.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 28

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

LANGUAGE AND GRAMMAR

Phrase structure grammar consists of rules that generate natural language sentences
and assign a structural description to them. As an example, consider the following set
of rules:
S -> NP + VP
VP -› V + NP
NP -> Det + Noun
V -› Aux + Verb
Det -> the, a, an, ...
Verb -> catch, write, eat,….
Noun -> police, snatcher, ...
Aux -› will, is, can, ...

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 29

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

LANGUAGE AND GRAMMAR

The structure assigned by the grammar is a constituent structure analysis of the

sentence. The second component of transformational grammar is a set of
transformation rules, which transform one phrase-maker (underlying) into another
phrase-marker (derived). These rules are applied on the terminal string generated by
phrase structure rules.
The rule relating active and passive sentences (as given by Chomsky) is
NP1 - Aux - V - NP2 -> NP2 - Aux + be + en - V - by + NP1
This rule says that an underlying input having the structure NP-Aux-V-NP can be
transformed to NP - Aux + be + en - V - by + NP.
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 30
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

LANGUAGE AND GRAMMAR

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 31

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

LANGUAGE MODELLING
A model is a description of some complex entity or process. A language model is thus
a description of language. Indeed, natural language is a complex entity and in order
to process it through a computer-based program, we need to build a representation
(model) of it. This is known as language modelling.
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 (ill-formed) one, whereas a probabilistic language model attempts to identify a sentence
based on a probability measure, usually a maximum likelihood estimate. These two viewpoints have led
to the following categorization of language modelling approaches.
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 32
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

LANGUAGE MODELLING

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.).
• For example, 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.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 33

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

LANGUAGE MODELLING

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.
 Statistical language modelling is one of the fundamental tasks in many NLP applications, including
speech recognition, spelling correction, handwriting recognition, and machine translation.
 It has now found applications in information retrieval, text summarization, and question answering
also.
 A number of statistical language models have been proposed in literature. The most popular of
these are the n-gram models.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 34

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

VARIOUS GRAMMAR-BASED LANGUAGE MODELS

Generative Grammars:
 In 1957, in his book on Syntactic Structures, Noam Chomsky wrote that we can generate sentences
in a language if we know a collection of words and rules in that language.
 If we have a complete set of rules that can generate all possible sentences in a language, those
rules provide a model of that language. Of course, we are talking only about the syntactical
structure of language here. Language is a relation between the sound (or the written text) and its
meaning.
 Thus, any model of a language should also deal with the meaning of its sentences.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 35

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

VARIOUS GRAMMAR-BASED LANGUAGE MODELS

Hierarchical Grammar:
 Chomsky (1956) described classes of grammars in a hierarchical manner, where
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). Although this relationship has been given for
classes of formal grammars, it can be extended to describe grammars at various
levels, such as in a class-sub class (embedded relationship.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 36

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

GOVERNMENT AND BINDING (GB)

Transformational grammars assume two levels of existence of sentences-one at the

surface level and the other at the deep root level this should not be confused with the
meaning level).
Government and binding (GB) theories have renamed them as s-level and d-level,
and identified two more levels of representation (parallel to each other) called
phonetic form and logical form.
The GB envisages that if we define rules for structural units 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.
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 37
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

GOVERNMENT AND BINDING (GB)

Components of GB
Government and binding (GB) comprises 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 as well
as at s-structure level.
This can move constituents at any place if it does not violate the constraints put by
several theories and principles. Hence, in its simplest from GB can be represented by

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 38

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

GOVERNMENT AND BINDING (GB)

Components of GB
Government and binding (GB) comprises 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 as well as at s-structure
level.
This can move constituents at any place if it does
not violate the constraints put by several theories
and principles. Hence, in its simplest from GB can
be represented by
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 39
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

GOVERNMENT AND BINDING (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 α.
The GB considers all three levels of representations (d-, s-, and LF as syntactic, and LF
is also related to meaning or semantic-interpretive mechanisms. However, GB applies
the same Move α transformation to map d-levels to s-levels or s-levels to LF level.
Example: Consider the sentence: Two countries are visited by most travelers.
Its two possible logical forms are:
LFI: [ Two countries are visited by [most travellers]]
IF2: Applying Move a, [ Most travelers, [ two countries are visited by ]]
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 40
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

GOVERNMENT AND BINDING (GB)

In LF1, the interpretation is that most travelers visit the same two countries (say, India
and China).
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.
One of the important concepts in GB is that of constraints. It is the part of the
grammar which prohibits certain combinations and movements; otherwise Move α can
move anything to any possible position. Thus, GB is basically the formulation of theories or
principles which create constraints to disallow the construction of ill-formed sentences.
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 41
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

GOVERNMENT AND BINDING (GB)

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 42

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

GOVERNMENT AND BINDING (GB)

Theory: The 𝑋 theory (pronounced X-bar theory) is one of the central concepts in
GB. Instead of defining several phrase structures and the sentence structure with separate
sets of rules, theory defines them both as maximal projections of some head. In this
manner, the entities defined become language independent.
Thus, 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, and can be represented as head X of their corresponding phrases (where
X = (N, V, A, P). Not only that, even the sentence structure (S', which is projection of
sentence) can be regarded as the maximal projection of inflection (INFL).
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 43
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

GOVERNMENT AND BINDING (GB)

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 44

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

GOVERNMENT AND BINDING (GB)

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 45

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

GOVERNMENT AND BINDING (GB)

The sentence is considered to be

the head of INFL and the projection
of sentence is denoted by S, which
has the specifier as complementizer
(COMP),

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 46

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

GOVERNMENT AND BINDING (GB)

Projection Principle
The projection principle, a basic notion in GB, places a constraint on the three
syntactic representations and their mapping from one to the other.
The principle states that representations at all syntactic levels (i.e., d-level, s-
level, and LF level) are projections from the lexicon. Thus, lexical properties
of categorical structure (sub categorization), must be observed at each level.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 47

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

GOVERNMENT AND BINDING (GB)

(θ)
GB puts another restriction on the lexical heads through which it assigns 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 e-
roles and they are mentioned in the lexicon, say for example the verb 'eat' can take
arguments with θ-roles '(Agent, Theme)'.
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 48
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

GOVERNMENT AND BINDING (GB)

 Agent is a special type of role which can be assigned by a head to outside arguments
(external arguments) whereas other roles are assigned within its domain (internal
arguments).
 'Mukesh ate food', the verb 'eat' assigns the 'Agent' role to 'Mukesh' (outside VP) and
"Theme' (or 'patient') role to 'food'. As roles are assigned based on the syntactic
positions of the arguments, it is important that there should be a match between the
number of roles and number of arguments as depicted by θ-criterion.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 49

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

GOVERNMENT AND BINDING (GB)

 Theta-Criterion states that 'each argument bears one and only one θ-role, and each θ-
role is assigned to one and only one argument' (Sells1985). Thus, each argument will
have a unique θ-role and cannot be moved to a position where it may acquire another
θ-role.
 In GB. d-structure is conceived as some kind of 'pure' representation of arguments and
hence, θ-roles are assigned at d-level only, whereas theta-criterion is applied at all the
three levels

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 50

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

GOVERNMENT AND BINDING (GB)

 C-command: C-command defines the scope of maximal projection. It is a

basic mechanism through which many constraints are defined on Move α .
 If any word or phrase (say α or ) falls within the scope of and is
determined by a maximal projection, we say that it is dominated by the
maximal projection. Now, if there are two structures α and related in
such a way that 'every maximal projection dominating α dominates ', we
say that α C-commands , and this is the necessary and sufficient condition
(iff) for C-command.
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 51
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

GOVERNMENT AND BINDING (GB)

Government:
α governs iff:
α C-commands
α is an X (head, e.g., noun, verb, preposition, adjective, and inflection), and
every maximal projection dominating dominates α.
Thus no maximal projection can intervene between the governor and
governee. In GB literature, this has been stated as: 'Maximal projections are
barriers to government.'
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 52
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

GOVERNMENT AND BINDING (GB)

Binding Theory:
Binding is defined by Sells (1985) as follows:
α binds iff
α C-commands , and
α and are co-indexed
In sentence [e, INFL kill Mukesh]
[Mukesh, was killed (by e)]
Mukesh was killed.
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 53
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

GOVERNMENT AND BINDING (GB)

Bounding and Control Theory:

The long distance movement for complement clause can be explained by bounding theory
if NP and S are taken to be bounding nodes. The theory says that the application of Move
α may not cross more than one bounding node. The theory of control involves syntax,
semantics, and pragmatics.
Case Theory and Case Filter: In GB, case theory deals with the distribution of NPs and
mentions that each NP (with the possible exception of a few empty categories) must be
assigned a case. In English, we have the nominative, objective, genitive, etc., cases, which
are assigned to NPs at particular positions.
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 54
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

GOVERNMENT AND BINDING (GB)

Case Filter: An NP is ungrammatical if it has phonetic content or if it is an argument (with

the exception of big 'PRO') and is not case-marked.
Phonetic content here, refers to some physical realization, as opposed to empty
categories. Thus, case filters restrict the movement of NP at a position which has no case
assignment. It works in a manner similar to that of the θ-criterion. Case Theory and Case
Filter:
(a) What, do you think that Mukesh ate e,?
(b) What, do you think Mukesh ate e,?

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 55

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

LEXICAL FUNCTIONAL GRAMMAR (LFG) MODEL

Unlike GB, LFG represents sentences at two syntactic levels: constituent structure (c-
structure) and functional structure (f-structure).
The LFG is a formalism that is both computationally and linguistically motivated and
provides precise algorithms for linguistic issues it can handle.
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 help
define the given structure of a sentence and some of the long distance dependencies,
which is difficult in transformational grammars.
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 56
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

LEXICAL FUNCTIONAL GRAMMAR (LFG) MODEL

C-structure and f-structure in LFG:

The c-structure is derived from the usual phrase and sentence structure
syntax, as in CFG. However, as the grammatical-functional role cannot be
derived directly from phrase and sentence structure, functional specifications
are annotated on the nodes of c-structure, which when applied on sentences,
results in f-structure.
Hence, f-structure is the final product which encodes the information obtained
from phrase and sentence structure rules and functional specifications.
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 57
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

LEXICAL FUNCTIONAL GRAMMAR (LFG) MODEL

Let us consider an example.

She saw stars in the sky.
CFG rules to handle this sentence are:
Where
S -› NP VP
S: sentence P: preposition
VP -> V {NP} {NP} PP* {S'} S': clause V: verb
N:noun Comp: complement
PP -> P NP
{ }: optional
NP -> Det N {PP} *: Phrase can appear any number of
times including blank.
S' -> Comp S
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 58
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

LEXICAL FUNCTIONAL GRAMMAR (LFG) MODEL

When annotated with functional specifications, the rules become:

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 59

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

LEXICAL FUNCTIONAL GRAMMAR (LFG) MODEL

 Here, Î (up arrow) refers to the f-structure of the mother node that is on the left hand
side of the rule. The V (down arrow) symbol refers to the f-structure of the node under
which it is denoted.
 in Rule 1, ( subj = V ) indicates that the f-structure of the first NP goes to the f-
structure of the subject of the sentence, while ( = )indicates that the f-structure of the
VP node gods directly to the f-structure of the sentence VP.
 Similarly, in Rule 2, the f-structure of VP is defined by the lexical item V, the two
optional NPs, any number of PPs, and the optional clause(S’).

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 60

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

LEXICAL FUNCTIONAL GRAMMAR (LFG) MODEL

Let us see first the lexical entries of various words in the sentence.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 61

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

LEXICAL FUNCTIONAL GRAMMAR (LFG) MODEL

This will lead to the c-structure

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 62

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

LEXICAL FUNCTIONAL GRAMMAR (LFG) MODEL

Finally, the f-structure is the set of

attribute-value pairs, represented
as:

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 63

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

LEXICAL FUNCTIONAL GRAMMAR (LFG) MODEL

 It is interesting to note that the final f-structure is obtained through the

unification of various f-structures for subject, object, verb, complement, etc.
 This unification is based on the functional specifications of the verb, which
predicts the overall sentence structure.
 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.
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 64
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

LEXICAL FUNCTIONAL GRAMMAR (LFG) MODEL

 LFG imposes three conditions on f-structure (Sells 1985).

 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.
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 65
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

LEXICAL FUNCTIONAL GRAMMAR (LFG) MODEL

 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 < ( Î Subj( Î Obi) >’ contains an
object as its governable function, a sentence like: 'He saw' will be
incomplete.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 66

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

LEXICAL FUNCTIONAL GRAMMAR (LFG) MODEL

 Coherence: Coherence 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.'

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 67

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

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. A number of statistical language models have been proposed in
literature. The dominant approach in statistical language modelling is the n-gram model.

n-gram Model: As discussed earlier, 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 chain rule as follows:

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 68

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

STATISTICAL LANGUAGE MODEL

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

= P(w1) P(w2 / w1) P(w3 / w1 w2) P(w4 / w1 w2 w3) ...P(wn/ w1 w2... Wn-1 )
=
where hi is history of word wi defined as
w1 w2... wi-1

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

probability of a word, given the sequence of words preceding it.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 69

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

STATISTICAL LANGUAGE MODEL

 An n-gram model simplifies the task by approximating the probability of a word

given all the previous words by the conditional probability given previous n-1 words
only.

𝑖 = wi-n+1,..., wi-1)
Thus, an n-gram model calculates by modelling language as Markov model
of order n-1, i.e., by looking at previous n-1 words only.
 A model that limits the history to the previous one word only, is termed a bi-gram (n
= 1) model. Likewise, a model that conditions the probability of a word to the
previous two words, is called a tri-gram (n = 2) model.
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 70
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

STATISTICAL LANGUAGE MODEL

 Using bi-gram and tri-gram estimate, the probability of a sentence can be
calculated as:

P(S) = −1

P(S) = wi/[Link]-1)
As an example, the bi-gram approximation of P(east/The Arabian knights are fairy
tales of the is: P(east/the)
whereas a tri-gram approximation is P(east/of the).
A special word (pseudo word) <s> is introduced to mark the beginning of the sentence in bi-gram
estimation. The probability of the first word in a sentence is conditioned on <s>. Similarly, in tri-gram
estimation, we introduce two pseudo-words <s1> and <s2>.
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 71
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

STATISTICAL LANGUAGE MODEL

 Now, we discuss how to estimate these probabilities. This is done by training the n-
gram model on the training corpus. We estimate n-gram parameters using the
maximum likelihood estimation (MLE) technique, i.e., using relative frequencies. We
count a particular n-gram in the training corpus and divide it by the sum of all n-
grams that share the same prefix.
 he sum of all n-grams that share first n-1 words is equal to the count of the common
prefix wi- n+1 ..., wi-1.

P(wi- n+1 ..., wi-1) = C (wi- n+1 ..., wi-1 , wi ) / (wi- n+1 ..., wi-1)

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 72

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

STATISTICAL LANGUAGE 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
Bi-gram model:
P(the/<s>) = 0.67 P(Arabian/the) = 0.4 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
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 73
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

STATISTICAL LANGUAGE MODEL

Test sentence(s):
The Arabian knights are the fairy tales of the east.
P(The/<s>) x P(Arabian/the) × P(Knights/Arabian) × P(are/knights)X P(the/are) ×
P(fairy/ the) × P(tales/fairy) × P(of/tales) × P(the/of)× P(east/the)
= 0.67 × 0.5 × 1.0 x 1.0 x 0.5 x 0.2 × 1.0 × 1.0 × 1.0 x 0.2
= 0.0067
As each probability is necessarily less than 1, multiplying the probabilities might cause
a numerical underflow, particularly in long sentences. To avoid this, calculations are
made in log space, where a calculation corresponds to adding log of individual
probabilities and taking antilog of the sum.
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 74
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

STATISTICAL LANGUAGE MODEL

 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.
 This is because of the assumption that the probability of occurrence of a word
depends only on the preceding word (or preceding n-1 words), which is not true in
general.
 A number of smoothing techniques have been developed to handle the data
sparseness problem, the simplest of these being add-one smoothing.
Smoothing in general refers to the task of re-evaluating zero-probability or low-
probability n-grams and assigning them non-zero values.
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 75
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

STATISTICAL LANGUAGE MODEL

Add-one Smoothing:
 This is the simplest smoothing technique. It adds a value of one to each n-gram
frequency before normalizing them into probabilities.
 In general, add-one smoothing is not considered a good smoothing technique. It
assigns the same probability to all missing n-grams, even though some of them could
be more intuitively appealing than others.
 Another problem with this technique is that 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.
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 76
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

STATISTICAL LANGUAGE MODEL

Good-Turing Smoothing:
Good-Turing smoothing (Good 1953) adjusts the frequency f of an-gram using the
count of n-grams having a frequency of occurrence f+[Link] converts the frequency of an
n-gram from f to f* using the following expression:

+ 1/
where n, is the number of n-grams that occur exactly f times in the training corpus. As
an example, consider that the number of n-grams that occur 4 times is 25,108 and the
number of -grams that occur 5 times is 20,542. Then, the smoothed count for 5 will
be20542
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 77
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

STATISTICAL LANGUAGE MODEL

Caching Technique:
Another improvement over basic n-gram model is caching. 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 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.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 78

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

WORD LEVEL ANALYSIS

Character Classes:

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 79

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

WORD LEVEL ANALYSIS

Character Classes:

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 80

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

WORD LEVEL ANALYSIS

Finite Automata:
A finite automaton has the following properties:
1. A finite set of states, one of which is designated the initial or start state, and one or
more of which are designated as the final states.
2. A finite alphabet set,∑, consisting of input symbols.
3. A finite set of transitions that specify for each state and each symbol of the input
alphabet, the state to which it next goes.
A finite automaton can be deterministic or non-deterministic. In a non-deterministic
automaton, more than one transition out of a state is possible for the same input
symbol.
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 81
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

WORD LEVEL ANALYSIS

Morphological Parsing:
Morphology is a sub-discipline of linguistics. It studies word structure and the formation
of words from smaller units (morphemes). The goal of morphological parsing is to
discover the morphemes that build a given word.
For example, the word 'bread' consists of a single morpheme and 'eggs' consist of two: the morpheme egg
and the morpheme -s.

There are two broad classes of morphemes: stems and affixes. The stem is the main
morpheme, i.e., the morpheme that contains the central meaning. Affixes modify the
meaning given by the stem.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 82

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

WORD LEVEL ANALYSIS

Affixes are divided into prefix, suffix, infix, and circumfix.
 Prefixes are morphemes which appear before a stem
 suffixes are morphemes applied to the end of the stem.
 Circumfixes are morphemes that may be applied to either end of the stem while
infixes are morphemes that appear inside a stem.
Prefixes and suffixes are quite common in Urdu, Hindi, and English.

For example, the Urdu word (bewaqt), meaning un-timely, is composed of the stem, waqt
and the prefix, be-,

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 83

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

WORD LEVEL ANALYSIS

There are three main ways of word formation: inflection, derivation, and compounding.
 In inflection, a root word is combined with a grammatical morpheme to yield a word
of the same class as the original stem.
 Derivation combines a word stem with a grammatical morpheme to yield a word
belonging to a different class.
e.g., formation of the noun 'computation' from the verb 'compute. The formation of a noun from a verb or
adjective is called nominalization.

 Compounding is the process of merging two or more words to form a new word.
For example, personal computer, desktop, overlook.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 84

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

WORD LEVEL ANALYSIS

Parsing, in general, means taking an input and producing some sort of structures for it.
In NLP, this structure might be morphological, syntactic, semantic, or pragmatic.
A morphological parser uses following information sources:
1. Lexicon: A lexicon lists stems and affixes together with basic information about
them.
2. Morphotactic: There exists certain ordering among the morphemes that constitute a
word. They cannot be arranged arbitrarily.
For example, rest-less-ness is a valid word in English but not rest-ness-less.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 85

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

WORD LEVEL ANALYSIS

3. Orthographic rules: These are spelling rules that specify the changes that occur when
two given morphemes combine.
For example the y -> ier spelling rule changes 'easy to 'easier and not to 'easyer.

 Morphological analysis can be avoided if an exhaustive lexicon is available that

lists features for all the word-forms of all the roots. Given a word, we simply consult
the lexicon to get its feature values.
For example, suppose an exhaustive lexicon for Hindi contains the following entries for the Hindi root-
word ghodhaa:

Ghodaa, Ghodi, Ghodon, Ghode ..

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 86

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

WORD LEVEL ANALYSIS

This approach has several limitations.

 First, it puts a heavy demand on memory. We have to list every form of the word,
which results in a large number of, often redundant, entries in the lexicon.
 Second, an exhaustive lexicon fails to show the relationship between different roots
having similar word-forms. That means the approach fails to capture linguistic
generalization, which is essential to develop a system capable of understanding
unknown words.
 Third, for morphologically complex languages, like Turkish, the number of possible
word-forms may be theoretically infinite.
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 87
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

WORD LEVEL ANALYSIS

The simplest morphological systems are stemmers that collapse morphological

variations of a given word (word-forms) to one lemma or stem. They do not require a
lexicon.
Stemming algorithms work in two steps:
(i) Suffix removal: This step removes predefined endings from words.
(ii) Recoding: This step adds predefined endings to the output of the first step.
e.g:
ier -> y (e.g., earlier -› early) ational -> ate
ing -> є (e.g., playing -> play)
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 88
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

WORD LEVEL ANALYSIS

 It is difficult to use stemming with morphologically rich [Link] in English,

stemmers are not perfect. Krovitz (1993) pointed out errors of omissions and
commissions in the Porter algorithm, such as transformation of the word:
• ‘organization' into 'organ’
• 'noise' into’ noisy.
 Another problem with Porter's algorithm is that it reduces only suffixes; prefixes and
compounds are not reduced.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 89

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

WORD LEVEL ANALYSIS

 It is difficult to use stemming with morphologically rich [Link] in English,

stemmers are not perfect. Krovitz (1993) pointed out errors of omissions and
commissions in the Porter algorithm, such as transformation of the word:
• ‘organization' into 'organ’
• 'noise' into’ noisy.
 Another problem with Porter's algorithm is that it reduces only suffixes; prefixes and
compounds are not reduced.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 90

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

WORD LEVEL ANALYSIS

A more efficient two-level morphological model, first proposed by Koskenniemi (1983),

can be used for highly inflected languages. In this model, a word is represented as a
correspondence between its lexical level form and its surface level form. The surface
level represents the actual spelling of the word while the lexical level represents the
concatenation of its constituent morphemes. Morphological parsing is viewed as a
mapping from the surface level into morpheme and feature sequences on
the lexical level.
For example, the surface form 'playing' is represented in the lexical form as play + V + PP

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 91

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

WORD LEVEL ANALYSIS

To get from the surface form of a word to its morphological analysis, we proceed in
two steps as:

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 92

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

WORD LEVEL ANALYSIS

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 93

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

SPELLING ERROR DETECTION AND CORRECTION

In computer-based information systems, errors of typing and spelling constitute a very

common source of variation between strings. These errors have been widely
investigated. All investigations agree that single character omission, insertion,
substitution, and reversal are the most common typing mistakes.
In an early investigation, Damearu (1964) reported that over 80% of the typing errors were single-error
misspellings:
(1) substitution of a single letter,
(2) omission of a single letter,
(3) insertion of a single letter, and
(4) transposition of two adjacent letters.
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 94
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

SPELLING ERROR DETECTION AND CORRECTION

Unlike typing errors, spelling errors are mainly phonetic, where the misspell word is
pronounced in the same way as the correct word. Phonetic errors are harder to set
right because they distort the word by more than a single insertion, deletion, or
substitution. Phonetic variations are common in transliteration.
Spelling errors belong to one of two distinct categories: non-word errors and real word
errors.
• When an error results in a word that does not appear in a given lexicon or is not a valid
orthographic word form, it is termed a non-word error.
• A real-word error results in actual words of the language. It occurs due to typographical mistakes or
spelling errors e.g: piece - peace or meat - meet
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 95
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

SPELLING ERROR DETECTION AND CORRECTION

Real-word errors may cause local syntactic errors, global syntactic errors, semantic
errors, or errors at discourse or pragmatic levels. It becomes impossible to decide that
a word is wrong without some contextual information.
Spelling correction consists of detecting and correcting errors. Error detection is the
process of finding misspelled words and error correction is the process of suggesting
correct words to a misspelled one.
These sub-problems are addressed in two ways:
1. Isolated-error detection and correction : each word is checked separately
2. Context-dependent error detection and correction

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 96

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

SPELLING ERROR DETECTION AND CORRECTION

There are a number of problems associated with this simple strategy.
• The strategy requires the existence of a lexicon containing all correct words. Such
a lexicon would take a long time to compile and occupy a lot of space.
• Some languages are highly productive. It is impossible to list all the correct words
of such languages.
• This strategy fails when spelling error produces a word that belongs to the
lexicon, e.g., when 'theses' is written in place of these'. Such an error is called a
real-word error.
• The larger the lexicon, the more likely it is that an error goes undetected, because
the chance of a word being found is greater in a large lexicon.
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 97
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

SPELLING ERROR DETECTION AND CORRECTION

Context dependent error detection and correction methods, utilize the context of a
word to detect and correct errors. This requires grammatical analysis and is thus more
complex and language dependent. Even in context dependent methods, the list of
candidate words must first be obtained using an isolated-word method before making
a selection depending on the context.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 98

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

SPELLING ERROR DETECTION AND CORRECTION

The spelling correction algorithm has been broadly categorized byKukich (1992) as
follows:
Minimum edit distance: The minimum edit distance between two strings is the minimum
number of operations (insertions, deletions, or substitutions) required to transform one
string into another. Spelling correction algorithms based on minimum edit distance are
the most studied algorithms.
Similarity key techniques: The basic idea in a similarity key technique is to change a
given string into a key such that similar strings will change into the same key.
n-gram based techniques: The n-grams can be used for both non-word and real-word
error detection because in the English alphabet, certain bi-grams and tri-grams of
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 99
letters never occur ‹ or rarely do so; for example the tri-gram gst and the bi-gram gd.
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

SPELLING ERROR DETECTION AND CORRECTION

n-gram based techniques:
 The n-grams can be used for both non-word and real-word error detection because
in the English alphabet, certain bi-grams and tri-grams of letters never occur or
rarely do so; for example the tri-gram qst and the bi-gram qd. This information can
be used to handle non word error. Strings that contain these unusual n-grams can be
identified as possible spelling errors.
 n-gram techniques usually require a large corpus or dictionary as training data, so
that an gram table of possible combinations of letters can be compiled. In case of
real-word error detection, we calculate the likelihood of one character following
another and use this information to find possible correct word candidates.
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 100
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

SPELLING ERROR DETECTION AND CORRECTION

Neural nets: These have the ability to do associative recall based on incomplete and
noisy data. They can be trained to adapt to specific spelling error patterns. The
drawback of neural nets is that they are computationally expensive.
Rule-based techniques: In a rule based technique, a set of rules (heuristics) derived
from knowledge of a common spelling error pattern is used to transform misspelled
words into valid words. For example, if it is known that many errors occur from the
letters ue being typed as eu, then we may write a rule that represents this.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 101

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

MINIMUM EDIT DISTANCE

The minimum edit distance is the number of insertions, deletions, and substitutions
required to change one string into another (Wagner and Fischer 1974). When we talk
about distance between two strings, we are talking of the minimum edit distance.
For example:
 The minimum edit distance between tutor' and tumor is 2.
 We substitute 'm' for t and insert ‘U' before r.
 No smaller edit sequence can be found for this conversion. Therefore, the minimum
edit distance is 2.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 102

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

MINIMUM EDIT DISTANCE

Edit distance can be viewed as a string alignment problem. By aligning two strings, we
can measure the degree to which they match. There may more than one possible
alignment between two strings.
For example:
t u t o _ r
t u m o u r
A dash in the upper string indicates insertion. A substitution occurs when the two
alignment symbols do not match (shown in bold). We can associate a weight or cost
with each operation.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 103

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

MINIMUM EDIT DISTANCE

Another possible alignment for this sequences is:

t u t _ o _ r
t u _ m o u r
The dynamic programming algorithm for minimum edit distance is implemented by
creating an edit distance matrix. This matrix has one row for each symbol in the source
string and one column for each matrix in the target string.
The (i, j)th cell in this matrix represents the distance between the first i character of the
source and the first j character of the target string. Each cell can be computed as a
simple function of its surrounding cells.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 104

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

MINIMUM EDIT DISTANCE

Thus, by starting at the beginning of the matrix, it is possible to fill each entry
iteratively. The value in each cell is computed in terms of three possible paths.
dist [i - 1, jl + insert_cost
Dist [I , j] = dist|i - 1, j - 1] + subst_cost [sourcei, targetj ]
dist [i, j-1] + delete _cost
The substitution will be 0 if the ith character in the source matches with jth character in
the target.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 105

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

MINIMUM EDIT DISTANCE

t u t o _ r
t u m o u r

# T U M O U R
# 0 1 2 3 4 5 6
T 1 0 1 2 3 4 5
U 2 1 0 1 2 3 4
T 3 2 1 1 2 3 4
O 4 3 2 2 1 2 3
R 5 4 3 3 2 2 2

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 106

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

MINIMUM EDIT DISTANCE

Compute the minimum distance between paecflu and peaceful

# P E A C E F U L
#
P
A
E
C
F
L
U

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 107

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

WORDS AND WORD CLASSES

Words are classified into categories called part-of-speech. These are sometimes called
word classes or lexical categories. These lexical categories are usually defined by their
syntactic and morphological behaviours.
The most common lexical categories are nouns and verbs. Other lexical categories
include adjectives, adverbs, prepositions, and conjunctions.
Word classes are further categorized as open and closed word classes.
• Open word classes constantly acquire new members while closed word classes do not (or only
infrequently do so).
• Nouns, verbs (except auxiliary verbs), adjectives, adverbs, and interjections are open word classes.
Prepositions, auxiliary verbs, delimiters, conjunction, and particles are closed word classes.
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 108
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

WORDS AND WORD CLASSES

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 109

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

PART-OF-SPEECH TAGGING
Part-of-speech tagging is the process of assigning a part-of-speech (such as a noun,
verb, pronoun, preposition, adverb, and adjective), to each word in a sentence.
• The input to a tagging algorithm is the sequence of words of a natural language
sentence and specified tag sets (a finite list of part-of-speech tags).
• The output is a single best part-of-speech tag for each word.
Many words may belong to more than one lexical category. For example, the English
word ‘book' can be a noun as in 'I am reading a good book' or a verb as in 'The police
booked the snatcher’
The same is true for other languages. For example, the Hindi word ‘sona' may mean
'gold' (noun) or 'sleep' (verb).
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 110
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

PART-OF-SPEECH TAGGING
The collection of tags used by a particular tagger is called a tag set. Most part-of-
speech tag sets make use of the same basic categories, i.e., noun, verb, adjective, and
prepositions. However, tag sets differ in how they define categories and how finely
they divide words into categories.
Zuha eats an apple daily.
Aman ate an apple yesterday.
They have eaten all the apples in the basket.
I like to eat guavas.

The word eat has a distinct grammatical form in each of these four sentences. Eat is the
base form, ate its past tense, and the form eats requires a third person singular
subject.
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 111
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

PART-OF-SPEECH TAGGING
Similarly, eaten is the past participle form and cannot occur in another grammatical
context. It is required after have or has. Thus, the following sentences are
ungrammatical:
I like to eats guava.
They eaten all the apples.

Eat VB
Ate VBD
Eaten VBN
Eats VBP

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 112

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

PART-OF-SPEECH TAGGING
Part-of-speech tagging is an early stage of text processing in many NLP applications
including speech synthesis, machine translation, information retrieval, and information
extraction.
Part-of-speech tagging methods fall under the three general categories.
Rule-based (linguistic)
• Stochastic (data-driven)
• Hybrid
Rule-based taggers use hand-coded rules to assign tags to words. These rules use a
lexicon to obtain a list of candidate tags and then use rules to discard incorrect tags.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 113

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

PART-OF-SPEECH TAGGING

Stochastic taggers have data-driven approaches in which frequency-based information

is automatically derived from corpus and used to tag words. Stochastic taggers
disambiguate words based on the probability that a word occurs with a particular tag.
The simplest scheme is to assign the most frequent tag to each word.

Hybrid taggers combine features of both these approaches. Like rule. based systems,
they use rules to specify tags. Like stochastic systems, they use machine-learning to
induce rules from a tagged training corpus automatically.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 114

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

PART-OF-SPEECH TAGGING
Rule-based Tagger
Most rule-based taggers have a two-stage architecture.
• The first stage is simply a dictionary look-up procedure, which returns a set of
potential tags (parts-of-speech) and appropriate syntactic features for each word.
• The second stage uses a set of hand-coded rules to discard contextually illegitimate
tags to get a single part-of-speech for each word.
For example, consider the noun-verb ambiguity in the following sentence:
The show must go on.
The potential tags for the word show in this sentence is (VB, NN]. We resolve this ambiguity by using the
rule: IF preceding word is determiner THEN eliminate VB tag.
This rule simply disallows verbs after a determiner.
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 115
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

PART-OF-SPEECH TAGGING
• Rule-based taggers usually require supervised training. Instead, rules can be induced automatically.

• To induce rules untagged text is run through a tagger. The output is then manually corrected. The

corrected text is then submitted to the tagger, which learns correction rules by comparing the two sets

of data. This process may be repeated several times.

• Speed is an advantage of the rule-based tagger, and unlike stochastic taggers, they are

deterministic.

• One of the arguments against them is the skill and effort required in writing disambiguation rules.

• Another disadvantage of the rule-based tagger is that it is usable for only one language. Using it for

another one requires a rewrite of most of the program;

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 116
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

PART-OF-SPEECH TAGGING
Stochastic Tagger
• The standard stochastic tagger applies the simplifying assumption that the
probability of a chain of symbols can be approximated in terms of its parts or n-
grams. The simplest n-gram model is the unigram model, which assigns the most
likely tag (part-of-speech) to each token.
• The unigram model needs to be trained using a tagged training corpus before it can
be used to tag data. The most likely statistics are gathered over the corpus and
used for tagging.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 117

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

PART-OF-SPEECH TAGGING
The context used by the unigram tagger is the text of the word itself. For example, it
will assign the tag J for each occurrence of fast, since fast is used as an adjective more
frequently than it is used as a noun, verb, or adverb. This results in incorrect tagging in
each of the following sentences:
She had a fast.
Muslims fast during Ramadan.
Those who were injured in the accident need to be helped fast.
In the first sentence, fast is used as a noun. In the second, it is a verb, and in the third,
an adverb.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 118

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

PART-OF-SPEECH TAGGING
• Stochastic models have the advantage of being accurate and language
independent.
• Most stochastic taggers have an accuracy of 96-97%. The accuracy seems to be
quite high but it should be noted that this is measured as a percentage of words. An
accuracy of 96% means that for a sentence containing 20 words, the error rate per
sentence will be 1-0.9620 = 56%. This corresponds to approximately one word per
sentence.
• One of the drawbacks of stochastic taggers is that they require a manually tagged
corpus for training.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 119

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

PART-OF-SPEECH TAGGING

• A tagger trained on a hand-coded corpus performs better than one trained on an

unannotated text. In order to achieve good performance a tagged corpus is
required.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 120

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

PART-OF-SPEECH TAGGING

Hybrid Taggers:
• Hybrid approaches to tagging combine the features of both the rule-based and
stochastic approaches. They use rules to assign tags to words. Like the stochastic
taggers, this is a machine learning technique and rules are automatically induced
from the data.
• Transformation-based learning (TBL) of tags, also known as Brill tagging, is an
example of hybrid approach. TBL is a machine learning method introduced by E.
Brill (in1995).

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 121

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

PART-OF-SPEECH TAGGING
• The initial state annotator uses the lexicon to assign the most likely tag to each word
as the start state.
• An ordered set of transformation rules are applied sequentially. The rule that results
in the most improved tagging is selected.
• A manually tagged corpus is used as reference for truth.
• The process is iterated until some stopping criterion is reached, such as when no
significant information is achieved over the previous iteration.
• At each iteration, the transformation that results in the highest score is selected.
• New text can then be annotated by first assigning the most frequent tag and then
applying the ranked list of learned transformations in order.
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 122
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

PART-OF-SPEECH TAGGING

• INPUT: Tagged corpus and lexicon (with most frequent information)

• Step 1: Label every word with most likely tag (from dictionary)
• Step 2: Check every possible transformation and select one which most improves
tagging.
• Step 3: Re-tag corpus applying the rules.
• Repeat 2-3 Until some stopping criterion is reached.
• RESULT: Ranked sequence of transformation rules

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 123

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

PART-OF-SPEECH TAGGING

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 124

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

PART-OF-SPEECH TAGGING

Example: Assume that in a corpus, fish is most likely to be a noun.

• P(NN/fish) = 0.91
• P(VB/fish) = 0.09
Now consider the following two sentences and their initial tags.
• I/PRP like/VB to/TO eat/VB fish/NNP.
• I/PRP like/VB to/TO fish/NNP.
As the most likely tag for fish is NNP, the tagger assigns this tag to the word in both
sentences.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 125

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

PART-OF-SPEECH TAGGING

In the second case, it is a mistake.

After initial tagging when the transformation rules are applied, the tagger learns a
rule that applies exactly to this mis-tagging of fish:
• Change NNP to VB if the previous tag is TO.
As the contextual condition is satisfied, this rule will change fish/NN to fish/VB:
• like/VB to/TO fish/NN -> like/VB to/TO fish/VB

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 126

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

PART-OF-SPEECH TAGGING

In the second case, it is a mistake.

After initial tagging when the transformation rules are applied, the tagger learns a
rule that applies exactly to this mis-tagging of fish:
• Change NNP to VB if the previous tag is TO.
As the contextual condition is satisfied, this rule will change fish/NN to fish/VB:
• like/VB to/TO fish/NN -> like/VB to/TO fish/VB
The algorithm can be made more efficient by indexing the words in a training corpus
using potential transformation.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 127

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

PART-OF-SPEECH TAGGING
Unknown Words:
Unknown words are words that do not appear in dictionary or a training corpus. They
create a problem during tagging.
There are several potential solutions to this problem.
• One is to assign the most frequent tag (which occurs with most word types in the
training corpus) to the unknown word.
• Another solution is to assume that the unknown words can be of any part-of-
speech and initialize them by assigning them open class tags.
Then proceed to disambiguate them using the probabilities of those tags.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 128

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

PART-OF-SPEECH TAGGING

• We can also use morphological information, such as affixes, to guess the possible
tag of an unknown word.
• In this approach, the unknown word is assigned a tag based on the probability of
the words belonging to a specific part-of-speech in the training corpus having the
same suffix or prefix.
• A similar approach is used in Brill's tagger.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 129

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

SYNTACTIC ANALYSIS
 The word 'syntax' refers to the grammatical arrangement of words in a sentence and their
relationship with each other. The objective of syntactic analysis is to find the syntactic structure of the
sentence.
 This structure is usually depicted as a tree. Nodes in the tree represent the phrases and leaves
correspond to the words. The root of the tree is the whole sentence. Identifying the syntactic structure
is useful in determining the meaning of the sentence. The identification is done using a process known
as parsing.
 Two important ideas in natural language are those of constituency and word order.
• Constituency is about how words are grouped together and how we know that they are really
grouping together.
• Word order is about how, within a constituent, words are ordered with respect to one another,
and also how constituents are ordered with respect to one another.
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 130
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

SYNTACTIC ANALYSIS
A widely used mathematical system for modelling constituent structure in natural
language is context-free grammar (CFG) also known as phrase structure grammar.
The CFG is basically a positional grammar and is not suitable for Indian languages,
which are free word order languages.
CONTEXT-FREE GRAMMAR
A CFG (also called phrase-structure grammar)consists of four components:
1. A set of non-terminal symbols, N
2. A set of terminal symbols, T
3. A designated start symbol, S, that is one of the symbols from N.
4. A set of productions, P, of the form: [A→α]

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 131

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

SYNTACTIC ANALYSIS
where A € N and α is a string consisting of terminal and non-terminal symbols. The rule
A → α says that constituent A can be rewritten as α. This is also called the phrase
structure rule. It specifies which elements (or constituents) can occur in a phrase and in
what order.
For example, the rule S → NP VP states that S consists of NP followed by VP, i.e., a sentence consists of a
noun phrase followed by a verb phrase.

A language is usually defined through the concept of derivation. The basic operation is
that of rewriting a symbol appearing on the left hand side of production by its right
hand side.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 132

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

SYNTACTIC ANALYSIS

The symbol S can be rewritten as

NP VP using Rule 1, then using
rules R2 and R4, NP and VP are
rewritten as N and V NP
respectively. NP is then rewritten
as Det N (R3). Finally, using rules
R6 and R7, we get the sentence:
Hena reads a book.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 133

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

CONSTITUENTS (PHRASES)
The fundamental idea of syntax is that words group together to form constituents
(often termed phrases), each of which acts as a single unit. They combine with other
constituents to form larger constituents, and eventually, a sentence.
For example, the noun phrase, The bird, can combine with the verb phrase, flies, to form the sentence, “The
bird flies”.

Phrase Level Constructions:

a fundamental notion in natural language is that certain groups of words behave as
constituents. These constituents are identified by their ability to occur in similar contexts

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 134

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

CONSTITUENTS (PHRASES)
One of the simplest ways to decide whether a group of words is a phrase, is to see if it
can be substituted with some other group of words without changing the meaning.
If such a substitution is possible then the set of words forms a phrase.
Hena reads a book.
Hena reads a storybook.
Those girls read a book.
She reads a comic book.

We can easily identify the constituents that can be replaced for each other in these
sentences. These are Hena, she, and Those girls and a book, a storybook, and a comic
book.
Elements that can substitute each other in certain syntactic positions are said to be
members of one paradigm.
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 135
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

CONSTITUENTS (PHRASES)

 Phrase types are named after

their head, which is the lexical
category that determines the
properties of the phrase. Thus,
if the head is a noun, the phrase
is called a noun phrase, if the
head is a verb, the phrase is
called a verb phrase, and so on.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 136

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

CONSTITUENTS (PHRASES)

 Noun Phrase: A noun phrase is a phrase whose head is a noun or a pronoun,

optionally accompanied by a set of modifiers. It can function as subject, object, or
complement.
• The modifiers of a noun phrase can be determiners or adjective phrases.
• The obligatory constituent of a noun phrase is the noun head- all other
constituents are optional.
• These structures can be represented using the phrase structure rule.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 137

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

CONSTITUENTS (PHRASES)

NP → Pronoun
NP → Det Noun
NP → Noun
NP → Ad; Noun
NP → Det Adj Noun
We can combine all these rules in a single phrase structure rule as follows:
NP → (Det) (Adj) Noun │Pronoun
The constituents in parentheses are optional.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 138

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

CONSTITUENTS (PHRASES)
NP → Pronoun
NP → Det Noun
NP → Noun
NP → Ad; Noun
NP → Det Adj Noun
We can combine all these rules in a single phrase structure rule as follows:
NP → (Det) (Adj) Noun │Pronoun
The constituents in parentheses are optional.
This rule states that a noun phrase consists of a noun, possibly preceded by a determiner and an
adjective (in that order). This rule does not cover all possible NPs.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 139

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

CONSTITUENTS (PHRASES)
After incorporating PP and AP in the phrase structure rule, we get the following:
NP → (Det) (AP) Noun (PP)
The following are a few examples of noun phrases:
They (1)
The foggy morning (2)
Chilled water (3)
A beautiful lake in Kashmir (4)
Cold banana shake (5)
The phrase (1) consists only of a pronoun; (2) consists of a determiner, an adjective (foggy) that stands for
an entire adjective phrase, and a noun; (3) comprises an adjective phrase and a noun; (4) consists of a
determiner (the), an adjective phrase (beautiful), a noun (lake), and a prepositional phrase (in Kashmir);
and (5) consists of an adjective followed by a sequence of nouns. A noun sequence is termed as nominal.
None of the phrase structure rules discussed so far are able to handle nominals.
9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 140
Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

CONSTITUENTS (PHRASES)
So, we modify our rules to cover this situation.
NP → (Det) (AP) Nom (PP)
Nom → Noun | Noun Nom

A noun phrase can act as a subject, an object, or a predicate. The following sentences
demonstrate each of these uses.
The foggy damped weather disturbed the match. (1)
I would like a nice cold banana shake. (2)
Kula botanical garden is a beautiful location. (3)

In (1), the noun phrase acts as a subject. In (2), it acts as an object, and in (3), it is a
predicate.

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 141

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

CONSTITUENTS (PHRASES)
Verb Phrase: Analogous to the noun phrase is the verb phrase, which is headed by a
verb. There is a fairly wide range of phrases that can modify a verb.
This makes verb phrases a bit more complex. The verb phrase organizes various
elements of the sentence that depend syntactically on the verb.
The following are some examples of verb phrases:
Khushbu slept. (1.1)
The boy kicked the ball. (1.2)
Khushbu slept in the garden. (1.3)
The boy gave the girl a book. (1.4)
The boy gave the girl a book with blue cover. (1.5)

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 142

Lecture – 1 Prepared by Prof. Ranjeet Panigrahi Natural Language Processing

CONSTITUENTS (PHRASES)
As you can see from these examples:
a verb phrase can have a verb [VP → Verb in (1.1)];
a verb followed by an NP (VP → Verb NP in (1.2)];
a verb followed by a PP [VP → Verb PP in (1.3)];
a verb followed by two NPs [VP → Verb NP NP in (1.4)];
a verb followed by two NPs and a PP [VP → Verb NP NP PP in (1.5)].
In general, the number of NPs in a VP is limited to two, whereas it is possible to add
more than two PPs.
VP → Verb (NP) (NP) (PP)*

9/11/2023 DEPARTMENT OF CSE, GIET UNIVERSITY, GUNUPUR 143