Module -1

Introduction to NLP – Ambiguous nature of NLP - Morphological Analysis – Syntax Analysis–

Semantic Analysis –Pragmatic Analysis – Discourse Analysis -Introduction to real-life
applications of NLP – Introduction to corpora – Corpora Analysis.

[Link].R
Assistant Professor Senior grade
VIT Chennai

1
What is NLP?
Natural Language Processing (NLP)
•Natural language processing - to build machines that understand and respond
to text or voice data and respond with text or speech of their own in much the
same way humans do.

•NLP combines computational linguistics, rule-based modeling of human

language with statistical, machine learning, and deep learning models.
•The field of NLP is primarily concerned with getting computers to perform
useful and interesting tasks with human languages.
 Goals of NLP
• Scientific Goal
• Identify the computational machinery needed for an
agent to exhibit various forms of linguistic behavior.
• Engineering Goal
• Design, implement, and test systems that process
natural languages for practical applications.
 Forms of Natural Language

• The input/output of a NLP system can be:

– written text
– speech
• We will mostly concerned with written text (not speech).
• To process written text, we need:
– lexical, syntactic, semantic knowledge about the language
– discourse information, real world knowledge
• To process spoken language, we need everything required to process written text, plus the
challenges of speech recognition and speech synthesis.

4
 Components of NLP
• Natural Language Understanding
– Mapping the given input in the natural language into a useful representation.
– Different level of analysis required:
morphological analysis,
syntactic analysis,
semantic analysis,
discourse analysis, …
• Natural Language Generation
– Producing output in the natural language from some internal representation.
– Different level of synthesis required:
deep planning (what to say),
syntactic generation
• NL Understanding is much harder than NL Generation. But, still both of them are hard.

5
 Why NL Understanding is hard?
• Natural language is extremely rich in form and
structure, and very ambiguous.
– How to represent meaning,
– Which structures map to which meaning structures.
• One input can mean many different things.
Ambiguity can be at different levels.
– Lexical (word level) ambiguity -- different meanings of words
– Syntactic ambiguity -- different ways to parse the sentence
– Interpreting partial information -- how to interpret pronouns
– Contextual information -- context of the sentence may affect the
meaning of that sentence.
• Many input can mean the same thing.
• Interaction among components of the input is not
clear.
6
 Language Technologies

Goal: Deep Understanding Reality: Shallow Matching

Requires context, linguistic structure,
 Requires robustness and scale
meanings…
 Amazing successes, but
fundamental limitations
8
 Knowledge of Language
• Phonology – concerns how words are related to the sounds that realize them.

• Morphology – concerns how words are constructed from more basic meaning units
called morphemes. A morpheme is the primitive unit of meaning in a language.

• Syntax – concerns how can be put together to form correct sentences and determines
what structural role each word plays in the sentence and what phrases are subparts of
other phrases.

• Semantics – concerns what words mean and how these meaning combine in
sentences to form sentence meaning. The study of context-independent meaning.

9
 Knowledge of Language (cont.)
• Pragmatics – concerns how sentences are used in different situations and how use
affects the interpretation of the sentence.

• Discourse – concerns how the immediately preceding sentences affect the

interpretation of the next sentence. For example, interpreting pronouns and
interpreting the temporal aspects of the information.

• World Knowledge – includes general knowledge about the world. What each
language user must know about the other’s beliefs and goals.

10
11
12
13
14
15
16
 Ambiguity

I made her duck.

• How many different interpretations does this sentence have?

• What are the reasons for the ambiguity?
• The categories of knowledge of language can be thought of as ambiguity resolving
components.
• How can each ambiguous piece be resolved?
• Does speech input make the sentence even more ambiguous?
– Yes – deciding word boundaries

17
 Ambiguity (cont.)
• Some interpretations of : I made her duck.
1. I cooked duck for her.
2. I cooked duck belonging to her.
3. I created a toy duck which she owns.
4. I caused her to quickly lower her head or body.
5. I used magic and turned her into a duck.
• duck – morphologically and syntactically ambiguous:
noun or verb.
• her – syntactically ambiguous: dative or possessive.
• make – semantically ambiguous: cook or create.
• make – syntactically ambiguous:
– Transitive – takes a direct object. => 2
– Di-transitive – takes two objects. => 5
– Takes a direct object and a verb. => 4

18
 Ambiguity in a Turkish Sentence
• Some interpretations of: Adamı gördüm.
1. I saw the man.
2. I saw my island.
3. I visited my island.
4. I bribed the man.
• Morphological Ambiguity:
– ada-m-ı ada+P1SG+ACC
– adam-ı adam+ACC
• Semantic Ambiguity:
– gör to see
– gör to visit
– gör to bribe

19
20
21
22
23
 What is a corpus?
• The word corpus comes from Latin (“body”) and the plural is
corpora
• A corpus is a body of naturally occurring language
– …but rarely a random collection of text
– Corpora “are generally assembled with particular purposes in mind, and
are often assembled to be (informally speaking) representative of some
language or text type.” (Leech 1992)
• “A corpus is a collection of (1) machine-readable (2) authentic
texts (including transcripts of spoken data) which is (3) sampled
to be (4) representative of a particular language or language
variety.” (MXT 2006: 5)
 What is not a corpus?
• A list of words is not a corpus
– Building blocks of language
• A text archive is not a corpus
– A random collection of texts
• A collection of citations is not a corpus
– A short quotation which contains a word or phrase that is the reason for its selection
• A collection of quotations is not a corpus
– A short selection from a text chosen on internal criteria by human beings
• A text is not a corpus
– Intending to be read in different ways
• The Web is not a corpus
– Its dimensions unknown, constantly changing, not designed from a linguistic perspective

Sinclair (2005)
 What is a corpus for?

• A corpus is made for the study of language in a broad sense

– To test existing linguistic theory and hypotheses
– To generate and verify new linguistic hypotheses
– Beyond linguistics, to provide textual evidence in text-based
humanities and social sciences subjects
• The purpose is reflected in a well-designed corpus
 Why use corpora?
• Even expert speakers have only a partial knowledge of a language
– A corpus can be more comprehensive and balanced
• Even expert speakers tend to notice the unusual and think of what is possible
– A corpus can show us what is common and typical
• Even expert speakers cannot quantify their knowledge of language
– A corpus can readily give us accurate statistics
 Why use corpora?
• Even expert speakers cannot remember everything they know
– A corpus can store and recall all the information that has been stored in it
• Even experts speakers cannot make up natural examples
– A corpus can provide us with a vast number of examples in real communication
context
• Even expert speakers have prejudices and preferences and every language
has cultural connotations and underlying ideology
– A corpus can give you more objective evidence
 Why use corpora?
• Even expert speakers are not always available to be consulted
– A corpus can be made permanently accessible to all
• Even expert speakers cannot keep up with language change
– A constantly updated corpus can reflect even recent changes in the language
• Even expert speakers lack authority: they can be challenged by other expert
speakers
– A corpus can encompass the actual language use of many expert speakers
 Benefits of corpus data
• Corpus data is more reliable
– A corpus pools together linguistic intuitions of a range of language speakers, which
offsets the potential biases in intuitions of individual speakers
• Corpus data is more natural
– It is used in real communications instead of being invented specifically for linguistic
analysis
• Corpus data is contextualized
– Attested language use which has already occurred in real linguistic context
• Corpus data is quantitative
– Corpora can provide frequencies and statistics readily
• Corpus data can find differences that intuitions alone cannot perceive
– E.g. synonyms totally, absolutely, utterly, completely, entirely
 Empirical Laws

• Function words VS Content words

• Function words are closed class words

• Prepositions, Pronouns, auxiliary verbs, conjunctions, grammatical articles, and ect…

31
32
33
Type vs Tokens

34
35
36
37
38
39
40
41
Read the following sentences, and illustrate different types of ambiguity present in the
sentences.
a)The bank was crowded.
b)Visiting relatives can be annoying.
c)John said he would give a ride to Tom, but he didn’t show up.
d)The professor discussed the student's paper in the office.

42
Read the following sentences, and illustrate different types of ambiguity present in the
sentences.
a) The bank was crowded.  morphological ambiguity
b) Visiting relatives can be annoying.  syntactic ambiguity
c) John said he would give a ride to Tom, but he didn’t show up.  semantic ambiguity
d) The professor discussed the student's paper in the office.  syntactic ambiguity

43
44
45
46
47
 Applications
• Speech processing: get flight information or book a hotel over the
phone
• Information extraction: discover names of people and events they
participate in, from a document
• Machine translation: translate a document from one human language
into another
• Question answering: find answers to natural language questions in a
text collection or database
• Summarization: generate a short biography of Noam Chomsky from
one or more news articles
 Machine
Translation

People’s Daily, August 30,

2017

Trump Pope family watch a hundred years a year in the White House
balcony
 Machine
Translation

People’s Daily, August 30,

2017

Trump and his family watched a 100-year total solar eclipse on the
balcony of the White House
Speech Recognition
• Spoken Input
• Identify words and phonemes in speech
• Generate text for recognized word parts
• Concatenate text elements
• Perform spelling, grammar and context checking
• Output results
• Research question: How can speech recognition assist a deaf student
taking notes in class?
• VUST – Villanova University Speech Transcriber (
[Link]
Textual Analysis - Readability
• Text Input
• Analyze text & estimate “readability”
• Grade level of writing
• Consistency of writing
• Appropriateness for certain educ. level
• Output results
• Research question: How can computer analyze text and measure
readability?
• Opportunities for hands-on research
Plagiarism Detection
• Text Input
• Analyze text & locate “candidates”
• Find one or more passages that might be plagiarized
• Algorithm tries to do what a teacher does
• Search on Internet for candidate matches
• Output results
• Research question: What algorithms work like humans when finding
plagiarism?
• Experimental CS research
Intelligent Agents
• Example: ELIZA
• AIML: Artificial Intelligence Modeling Lang.
• Human types something
• Computer parses, “understands”, and generates response
• Response is viewed by human
• Research question: How can computers “understand” and “generate”
human writing?
• Also good area for experimentation
 Language processing
Task, Tools, and algorithms
Accurately determines the intended meaning of text or voice data.
Homonyms, homophones, sarcasm, idioms, metaphors, grammar and usage
exceptions, variations in sentence structure.
Basic text Processing
1. Tokenization- Tokenization breaks the raw text into words, sentences called
tokens.
2. Stemming- Stemming is a technique used to extract the base form of the words by
removing affixes from them.
3. Spelling Correction - error in the queries.
4. Normalization
5. Lemmatization -more formal way to find roots by analyzing a word’s morphology
using vocabulary from a dictionary.
6. Parts of speech tagging
Language Processing
• 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 – Meaning in context & for a purpose
(Pragmatics)
• Level 6 – Connected sentence processing in a larger
body of text (Discourse)

71
Examples of Levels
• L1 : sound
• L2 : Dog - Dog(s), Dog(ged)
Lady – Lad(ies)
Should we store all forms of words in the lexicon?
• L3 : Ram goes to market (right)
goes Ram to the market (wrong)
• L4 : translation from unstructured to structured
representation
go : (event)
agent : Ram
source : ?
destination : market
72
Example (Contd.)
• L5 : User situation & context
“Is that water?” – the action to be performed is
different in a chemistry lab and on a dining table.
• L6 : Backward & forward references –
• Coreference resolution
“The man went near the dog. It bit him.”
Often co reference & ambiguity go together as in –
“The dog went near the cat. It bit it.”

73
Noisy Channel Metaphor
Speech Text
Signal

Noisy

- I want food.

- It is cold today.

74
Natural Language Processing
Applications Core Technologies
• Machine Translation •Language modeling
•Information Retrieval •Part-of-speech tagging
•Question Answering •Syntactic parsing
•Dialogue Systems •Named-entity recognition
•Information Extraction •Word sense disambiguation
•Summarization •Semantic role labelling
•Sentiment Analysis •...
• ...
NLP lies at the intersection of
computational linguistics and machine
learning.
 Minimum Edit Distance

Natural Language Processing

 Definition of Minimum Edit
Distance
• Many NLP tasks are concerned with measuring how similar two strings are.

• Spell correction:
– The user typed “graffe”
– Which is closest? : graf grail giraffe
• the word giraffe, which differs by only one letter from graffe, seems intuitively to be
more similar than, say grail or graf,

• The minimum edit distance between two strings is defined as the minimum number of
editing operations (insertion, deletion, substitution) needed to transform one string into
another.
Minimum Edit Distance:
Alignment
• The minimum edit distance between intention and execution can be
visualized using their alignment.

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

two sequences.
 Minimum Edit
Distance

• If each operation has cost of 1 (Levenshtein Distance)

– Distance between them is 5

• If substitutions cost 2 (Generalized Levenshtein Distance)

– Distance between them is 8
Other uses of Edit Distance
in NLP
• Evaluating Machine Translation and speech
recognition
R Spokesman confirms senior government adviser was
shot
H Spokesman said the senior adviser was shot dead
S I D I

• Named Entity Extraction and Entity Coreference

– IBM Inc. announced today
– IBM profits
– Stanford President John Hennessy announced yesterday
– for Stanford University President John Hennessy
 The Minimum Edit
Distance Algorithm
• How do we find the minimum edit distance?
– We can think of this as a search task, in which we are searching for the shortest path—a
sequence of edits—from one string to another.

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

– Most of distinct edit paths ends up in the same state, so rather than
recomputing all those paths, we could just remember the shortest path to a
state each time we saw it.
– We can do this by using dynamic programming.
– Dynamic programming is the name for a class of algorithms that apply a
table-driven method to solve problems by combining solutions to sub-
problems.
 Minimum Edit Distance
between Two Strings
• For two strings
– the source string X of length n
– the target string Y of length m
• We define D(i,j) as the edit distance between X[1..i] and Y[1..j]
• i.e., the first i characters of X and the first j characters of Y
• The edit distance between X and Y is thus D(n,m)
 Dynamic Programming for Computing Minimum
Edit Distance
• We will compute D(n,m) bottom up, combining solutions to subproblems.
• Compute base cases first:
– D(i,0) = i
• a source substring of length i and an empty target string requires i deletes.
– D(0,j) = j
• a target substring of length j and an empty source string requires j inserts.
• Having computed D(i,j) for small i, j we then compute larger D(i,j) based on previously
computed smaller values.
• The value of D(i, j) is computed by taking the minimum of the three possible paths
through the matrix which arrive there:
 Dynamic Programming for
Computing Minimum Edit
• Distance
If we assume the version of Generalized Levenshtein distance in which the
insertions and deletions each have a cost of 1, and substitutions have a cost of
2 (except substitution of identical letters have zero cost), the computation for
D(i,j) becomes:
Minimum Edit Distance
Algorithm
Computation of Minimum Edit
Distance between intention
and execution
Computation of Minimum Edit
Distance between intention
and execution
deletion
insertion
substitution
Computation of Minimum Edit
Distance between intention
and execution
 Computing
Alignments
• Edit distance isn’t sufficient
– We often need to align each character of the two strings to each other
• We do this by keeping a “backtrace”
• Every time we enter a cell, remember where we came from
• When we reach the end,
– Trace back the path from the upper right corner to read off the alignment
MinEdit with
Backtrace

deletion
insertion
substitution
MinEdit with
Backtrace
Adding Backtrace to Minimum Edit Distance

• Base conditions: Termination:

D(i,0) = i D(0,j) = j D(N,M) is distance

• Recurrence Relation:
For each i = 1…M
For each j = 1…N
D(i-1,j) + 1 deletion
D(i,j)= min D(i,j-1) + 1 insertion
D(i-1,j-1) + 2; if X(i) ≠ Y(j) substitution
0; if X(i) = Y(j)
LEFT insertion
ptr(i,j)= deletion
DOWN substitution

DIAG
Performance of Minimum Edit
Distance Algorithm
• Time: O(nm)

• Space: O(nm)

• Backtrace: O(n+m)
References
• [Link]
ambiguities-in-natural-language-processing-179212a23b55