Welcome to

Natural Language Processing

Dr. M. Moshiul Hoque

CSE, CUET
 Evaluation
Sales Class
Participation
10%

Presentation
10%

Final
50% Midterm
20%

Proposal
10%
 Key Points
• What & why NLP?
• Steps involves in language processing:
Morphological, syntactic, semantic, pragmatic,
discourse integration
• Parsing: bottom up vs. top down
• Parser Implementation: ATN
• Why semantic is important?
• CFG/CSG/TGG
 Any Light at The End of The Tunnel?

• Yahoo, Google, Microsoft  Information Retrieval

• [Link], [Link] (Job finders)  Information Extraction +
Information Retrieval
• Systran powers Babelfish  Machine Translation
• Ask Jeeves  Question Answering
• Myspace, Facebook, Blogspot  Processing of User-Generated Content
• Tools for “business intelligence”
• All “Big Guys” have (several) strong NLP research labs:
– IBM, Microsoft, AT&T, Xerox, Sun, etc.
• Academia: research in an university environment
Natural Language Processing (NLP)
• Natural Language?
– Refers to the language spoken/written by people, e.g. English,
Japanese, Bengali, as opposed to artificial languages, like C++,
Java, LISP, Prolog, etc.
• Natural Language Processing
– Applications that deal with natural language in a way or another
– Computers use (analyze, understand, generate) natural language
– A somewhat applied field

 Computational Linguistics
– Doing linguistics on computers
– More on the linguistic side than NLP, but closely related
– More theoretical
 Why NLP?
• Language is meant for
communicating about
the world
– NLP offers insights into
language
• Language is the
medium of the web
• Help in communication
– With computers
Kismet: MIT Media Lab
– With other humans
(MT)
– HCI/HRI
 Why NLP?
• Classify text into categories
• Index and search large texts
Applications for • Automatic translation
processing large • Speech understanding
amounts of texts – Understand phone conversations
-require NLP
• Information extraction
expertise
– Extract useful information from resumes
• Automatic summarization
– Condense 1 book into 1 page
• Question answering
• Knowledge acquisition
• Text generations / dialogues
Why BLP (Bangla Language Processing)
• International Day of Mother Language [Feb.
01]
Widest possible distribution of Bangla
 Social/Political Importance

More than one language

 Commercial Importance

Highly paid job

 Scientific Importance

Computer science
 Philosophical Importance

Correct knowledge
interpretation
 NLP Involves ….
• Two tasks:
Processing written text
-Lexical
-Syntactic
-Semantic
-Pragmatic
Processing spoken language,
-Lexical, Syntactic, Semantic, Pragmatic+++
- Phonology
 NLP Involves ….
Natural Language Understanding (NLU): understanding & reasoning
while the input is NL
-Internal structure of the input NL
Natural Language Generation (NLG): generate other language

Natural Language Processing

NL Input Machine NL Output

Understanding Generation
 Linguistics and Language Processing

High-level

Low-level
 Steps in the NLP
• Morphological/Lexical Analysis: Individual words are
analyzed into their components
-non-word tokens such as punctuation are separated from
the words.
-Divide the text into paragraphs, sentences & words

• Syntactic Analysis: Linear sequences of words are

transformed into structures that show how the words
relate to each other.
-Boy the go to store (rejected due to violate the rules)
 Steps in the NLP
• Semantic Analysis: The structures created by the syntactic
analyzer are assigned meanings.
-Manush gass khai (syntactically correct but semantically not)

• Discourse integration: The meaning of an individual

sentence may depend on the sentences that precede it and
may influence the meanings of the sentences that follow it.
-you wanted it (it depends on the prior discourse context)

• Pragmatic Analysis: The structure representing what was

said is reinterpreted to determine what was actually meant.
-commonsense knowledge
-Do you know what is it? (request)
 Morphological Analysis
• Morphology is the analysis of words into
morphemes & conversely the synthesis of
words from morphemes
• Morphemes
-a smallest meaningful unit in the grammar
-a smallest linguistic unit that has semantic meaning
-a unit of language immediately below the ‘word level’
-a smallest part of a word that can carry a discrete meaning
 Morphological Analysis
Example:
The word “unbreakable” has 03 morphemes
1. un- a bound morpheme
2. -break- a free morpheme
3. -able- a bound morpheme
Also, un: prefix, able-suffix--affixes

How many morphemes?

“aagniporikhha” “unreliable”,
 Types of Morphemes
 Free Morphemes:
-can appear stand alone/free
town, dog
-with other lexemes
town hall, dog house
 Bound Morphemes
-appear only together with other morphemes to form a lexeme
un-: may be prefix/suffix
 Inflectional Morphemes
-modify a word’s tense, number, aspects etc
dog morpheme with plural marker
morpheme s becomes dogs
 Types of Morphemes
 Derivational Morphemes
-can be added to a word to derive another word
Addition of “-nees” to “happy”: “happiness”
 Root Morphemes
-primary lexical unit of a word. Roots can be either free or bound
morphemes
chatters has the inflectional root chatter but the lexical root chat
 Null Morphemes
-if is an invisible affix, also called zero morpheme represented as either
the figure zero (0), the empty set symbol , or its variant 
-Adding a null morpheme is called null affixation/null derivation/zero
derivation;
cat = cat + -0 = ROOT (“cat”) + singular
cats = cat + - s = ROOT (“cat”) + plural
 Syntactic Analysis
• Syntax
-Syntax is the structure of language.
-It is the grammatical arrangement of the words in a
sentence to show its relationship to one another in a
sentence
-Syntax is a finite set of rules that specify a language
-Rules: Phase Structure Rules
Context-Free or Context-Sensitive
-Syntax rules govern proper sentence structure
-Syntax is represented by Parse tree:
-a way to show the structure of a language
fragment or by a list
 Syntactic Analysis
He ate the pizza
PS Rules
Input String S NP VP
NP  PRO
NP  ART N
VP  V NP

Parser Lexicon V-ate

PRO-he
N-pizza
ART-the
Parse Tree
 Classification Phrases
• Sentence (S)
• Noun Phrase (NP): Noun/Pronoun as head
-Optionally accompanied by a set of modifiers
Determiners: article (the, a)
Adjectives (the red ball)
the black cat, a cat on the mat
• Verb Phrase (VP): verb as head
“eat cheese”, “jump up and down”
• Adjective Phrase (AP): adjective as head
full of toys, good boy
• Adverbial Phrase (AdvP): adverb as head
very carefully
• Prepositional Phrase (PP): preposition as head
in love, over the rainbow
 Classification Phrases
• Determiner Phrase (DP): determiner as head
a little dog, the little dogs
• In English, determiners are usually placed before
the noun as a noun modifier that includes:
-articles (the, a),
-demonstratives (this, that),
-numerals (two, five, etc.),
-possessives (my, their, etc.),
-quantifiers(some, many, etc.)
 PS Rules
• PS rules are a way to describe language syntax.
• Rules determine what goes into phrase & how its
constituents are ordered.
• They are used to break a sentence down to its
constituent parts namely phrasal categories & lexical
categories:
Phrasal category include: noun phrase, verb
phrase, prepositional phrase
Lexical category include: noun, verb,
adjective, adverb, others
 PS Rules
• PS rules are usually of the form A  B C
-meaning “constituent A is separated into sub-
constituents B & C
-Or simply “ A consists of B followed by C”
 S  NP VP Reads: S consists of an NP followed by a VP
-Means a sentence consists of a noun phrase followed by
a verb phrase
 NP  Det N1 Reads: NP consists of an Det followed by
N1
-Means a noun phrase consists of a determiner followed
by a noun
PS Rules and Tress for NP
 PS Rules
S NP VP Bill printed the red file
NP  (Det) (ADJS) N
S
NP  PRO
NP PN NP VP
ADJS  ADJ |ADJS
VP  V (NP) PN V NP
N  file|printer
printed
PN  Bill|Rahim|Bird Bill Det ADJS N
PRO  I|he|she ADJ
the file
Det  the|a|an
ADJ  short|long|want|red red
V  printed|created|want
 Parser
• A parser is a program, that accepts as input a sequence of
words in a natural language and breaks them up into parts
(nouns, verbs, & their attributes), to be managed by other
programming.
• Parsing can be defined as the act of analyzing the
grammatically an utterance according to some specific
grammar
• Parsing is the process to check, that a particular sequence of
words in sentence correspond to a language defined by its
grammar
• Parsing means show how we can get from the start symbol
of the grammar to the sentence of words using the
production rules
• The output of a parser is a parse tree/Structural
Representation (SR)
 Properties of a Parse Tree
• Parse tree is a way of representing the output of a
parser
 Each phrasal constituent found during parsing becomes
a branch node of the parse tree
 Every node corresponds either to an input word or to a
non-terminal
 Each level in the parse tree corresponds to the
application of one PS rule
 The words of the sentence become the leaves of the
parse tree
 There can be more than one parse tree for a single
sentence
 Conclusion
• Why NLP is important?
• Steps involves in
language processing
• Morphological analysis
• Syntactic analysis using
PS rules
• Structural
Representation (SR):
Parse tree
Topics Covers:
Artificial Intelligence: Rich & Knight
Artificial Intelligent & Expert System: Patterson