Natural Language processing

(NLP)
Javad Salimi Sartakhti

1
 Evaluation Method
• Active Class Participation (2 point)
• Midterm Exam (6 points)
• Final Exam (7 points)
• Seminar, Project, and Assignments (7 points)

2
 Contact Information
• [Link]@[Link]
• Salimi@[Link]
• Tel: 09373395815 (also in Telegram, Watsapp, Eita, Bale)

3
 Reference
SPEECH AND LANGUAGE PROCESSING
An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition
by Daniel Jurafsky and James H. Martin
Second Edition (2008)
Publisher: McGraw Hill

[Link]

4
 Why NLP?
• Natural languages
• English
• Persian
• German
• French
• ...
• Formal languages
• Java
• Python
• LaTeX
• ...
• Descriptive languages
• Biology: DNA
• Chemistry: chemical formulas
• ...

5
 Natural Language
• A vocabulary is a set consisting of a number of words (w_i).
• A text consists of a sequence of words belonging to a vocabulary.
• A language consists of a set of possible texts.

6
 Natural Language
• Examples of Vocabularies
• English
• the
• and
• eat
• you
• book
• ...

7
 Natural Language Processing
• Applications
• Text Technologies
• Speech Technologies
• Techniques

8
NLP Applications

9
Spell and Grammar Checking

10
11
Applications for spelling correction
Word processing Phones

Web search

12
Text Categorization
• Assigning each text to a category

13
Text Categorization

14
Information Retrieval
• Finding relevant information to the user’s query

15
Information Retrieval

16
Summarization

17
18
Information Extraction

Extracting the important items of a text and structuring them

19
20
Question Answering
• Answering natural language questions asked by the user

21
22
Machine Translation
• Translating a text from one language to another language

23
Machine Translation

24
Sentiment Analysis
• Identifying positive and negative opinions stated in a text

25
Sentiment Analysis

26
Optical Character Recognition
• Recognizing printed or handwritten texts and converting them to
computer-readable texts

27
Word Prediction
• Predicting the next word that is highly probable to be typed by the
user

28
Speech Technologies

29
Speech Recognition
• Recognizing a spoken language and transforming it into a text

30
Speech Synthesis
• Producing a spoken language from a text

31
Spoken Dialogue Systems

32
 Applications’ Levels
• Easy (mostly solved)
• Spell and grammar checking
• Spam detection
• Word prediction
• Intermediate (good progress)
• Information retrieval
• Sentiment analysis
• Information extraction
• Difficult (still hard)
• Machine translation
• Question answering
• Summarization
• Dialog system

33
NLP Techniques

34
Part Of Speech Tagging

‫مقوله نحوی‬

35
 ‫‪Parsing‬‬

‫کاربرد در ترجمه و پرسش و پاسخ و ‪...‬‬

‫‪36‬‬
Named Entity Recognition

37
Word Sense Disambiguation

1.I went fishing for some sea bass.

[Link] bass line of the song is too weak

38
‫‪Semantic Role Labeling‬‬

‫باید بدنیال نقش مفهومی جمالت باشیم‬

‫‪39‬‬
Content
• Introduction
• Linguistics Levels and NLP Challenges
• Mathematical Foundations
• Language Modeling
• Machine Learning Overview→ NN, Deep Learning, …
• Part-of-Speech Tagging

40
Linguistic Knowledge/ Level
• Phonetics and Phonology
• Morphology
• Syntax
• Semantics
• Pragmatics
• Discourse

41
Phonetics and Phonology
• The study of linguistic sounds and their relations to words

42
Morphology
• The study of internal structures of words and how they can be
modified
• Parsing complex words into their components

43
Syntax
• The study of the structural relationships between words in a sentence

‫در سطح جمله و تعیین ارتباط اجزا‬

44
Semantics
• The study of the meaning of words, and how these combine to form
the meanings of sentences
• Realizing lexical relations among words ‫در سطح جمله و تعیین روابط معنایی‬

45
Pragmatics
• The study of how language is used to accomplish goals, and the
influence of context on meaning
• Understanding the aspects of a language which depends on situation
and world knowledge

‫جزء سطوح خیلی پیچیده است‬

46
Discourse
• The study of linguistic units larger than a single utterance
• Co-reference

‫محدود به ضمیر نیست‬

47
Challenges

48
49
Phonetics and Phonology

• Computers can recognize speech

• Computers can wreck a nice peach

50
Morphology

!‫نشستند؟‬

51
Syntax

52
Syntax

53
Semantics
• The astronomer loves the star.

• Movie Star (Celebrity)

• Sky Star

54
Semantics
• Every man loves a woman.

55
Pragmatics
• Can you give me the salt?

• Would you please give me the salt?

• Do you have the ability to give me the salt?

56
Discourse
• Bob understands that you like your father, but he ...

57
Ambiguity
I made her duck
‫؟‬
I cooked duck for her (to eat)
I cooked duck belonging to her
I created a toy duck which she owns
I created a vehicle which she owns
I caused her to quickly lower her head or body
I waved my magic wand and turned her into a duck

58
Ambiguity
I made her duck
• duck - morphologically and syntactically ambiguous
• noun
• verb
• duck - semantically ambiguous
• waterfowl
• vehicle moving on the water
• her - syntactically ambiguous
• possessive
• dative
• make - semantically ambiguous
• cook
• create
• make - syntactically ambiguous
• Takes a direct object and a verb (5)
• Transitive - takes a direct object (2)
• Di-transitive - takes two objects (6)
59
Mathematical Foundations
• Zipf’s Law

• Probability Theory

60
 Zipf’s Analysis
• Count the frequency of all the words in a corpus
• Sort the words by frequency
• Rank: position of a word in the sorted list

61
Word Frequency

62
Word Frequency

63
 Zipf’s Law
• The frequency of any word is inversely proportional to its rank in the
frequency table
• Given a corpus of natural language utterances, the most frequent
word will occur approximately
• twice as often as the second most frequent word,
• three times as often as the third most frequent word,
• ...
Rank of a word times its frequency is approximately a constant
• Rank · Freq ≈ c
• c ≈ 0.1 for English

64
Zipf’s Law
• Zipf’s Law is not very accurate for very frequent and very infrequent
words

65
Probability of a Word

66
Probability of a Sequence of Words

67
Conditional Probability P(A|B)
• Sometimes we have partial knowledge about the outcome of an
experiment
• Conditional (or Posterior) Probability
• Suppose we know that event B is true
• The probability that A is true given the knowledge about B is
expressed by

68
Conditional Probability

69
Statistical Independence

70
Bayes theorem

71
Bayes Decomposition

72
Random Variables
• A random variable (RV) X is a variable whose possible values are
numerical outcomes of a random phenomenon.
• Types of random variables:
• Discrete
• Continuous

73
Expectation value

74
Variance

75
Language Modeling

76
Language modeling

77
Applications

78
Applications

79
Applications

80
Applications

81
Corpus
• Probabilities are based on counting things
• Counting of thing in natural language is based on a corpus (plural: corpora)
• A computer-readable collection of text or speech
• The Brown Corpus
• A million-word collection of samples
• 500 written texts from different genres
• (newspaper, fiction, non-fiction, academic, ...)
• Assembled at Brown University in 1963-1964
• The Switchboard Corpus
• A collection of 240 hours of telephony conversations
• 3 million words in 2430 conversations averaging 6 minutes each
• Collected in early 1990s

82
Corpus
• Text Corpora
• The Brown Corpus
• Corpus of Contemporary American English
• The British National Corpus
• The International Corpus of English
• The Google N-gram Corpus

83
Word Occurrence
• A language consist of a set of V words (Vocabulary)
• A text is a sequence of the words from the vocabulary
• A word can occur several times in a text
• Word Token: each occurrence of words in text
• Word Type: each unique occurrence of words in the text

84
Word Occurrence

85
Language Modeling

86
Conditional Probability-Bayes Decomposition

87
 Practical Issues

•We do everything in log space

•Avoid underflow
•(also adding is faster than multiplying)

log(p1 ´ p2 ´ p3 ´ p4 ) = log p1 + log p2 + log p3 + log p4

88
‫‪Markov Assumption‬‬

‫تاریخچه خیلی دور بکار نمی‬

‫آید‬

‫‪89‬‬
N-gram Model

Where Bigram? Where Trigram?

90
Maximum Likelihood

91
Maximum Likelihood
P(saw|

92
Maximum Likelihood

93
 More examples:
Berkeley Restaurant Project sentences

• can you tell me about any good Cantonese restaurants close by

mid priced thai food is what i’m looking for
• tell me about chez pansies
• can you give me a listing of the kinds of food that are available
• i’m looking for a good place to eat breakfast
• when is caffe venezia open during the day

94
 Raw bigram counts
• Out of 9222 sentences

95
Raw bigram probabilities
• Normalize by unigrams:

• Result:

96
 Google N-Gram Release

97
Language Modeling Toolkits
• SRILM
• [Link]
•KenLM
• [Link]
•NLTK
•OpenNLP
•Hazm
98
Smoothing

100
Zero Probability

101
 Laplace Smoothing
• Add one to all counts

102
Laplace Smoothing

103
 Interpolation and Back-off Smoothing
• Back-off Smoothing
• Use a background probability

104
Interpolation and Back-off Smoothing
• Interpolation

105
 background probability
• Lower levels of n-gram can be used as background probability
• trigram →bigram → unigram → zerogram → (1/V )

106
background probability
• Interpolation
• trigram →bigram → unigram → zerogram (1/V )

107
 Advanced Smoothing
• Bayesian Smoothing with Dirichlet Prior
• Absolute Discounting
• Kneser-Ney Smoothing

108
Bayesian Smoothing with Dirichlet Prior

109
Absolute Discounting

110
Absolute Discounting

111
Kneser-Ney Smoothing

112
Kneser-Ney Smoothing

113
Kneser-Ney Smoothing

114
Language Model Evaluation

115
 Entropy
• Entropy measures the amount of information in a RV
• Amount of information contained in a message (after removing all possible
redundancy)
• number of bits that the message has after compression
‫آنتروپی در تئوری اطالعات (که توسط کلود شانون معرفی‬
‫شد) نشاندهنده میزان عدم قطعیت یا میزان اطالعات‬
،‫ به زبان ساده‬.‫مورد انتظار در یک منبع داده است‬
‫آنتروپی میزان غیرقابل پیشبینی بودن یک متغیر‬
.‫تصادفی را اندازهگیری میکند‬

• Note: if you want the “unit” of the entropy to be “bit”, you have to use the log to the
basis 2
116
 Entropy
• Reporting the result of rolling an 8-sided die:

• The average length of the message needed to transmit an outcome of

that variable using the optimal code

117
Example
• Vocabulary with two words:
• V = a; b

118
Example
• Vocabulary of W words wi with uniform distribution p(wi) = 1/W

119
Joint Entropy
• The joint entropy of 2 RV X; Y is the amount of the information
needed on average to specify both their values

120
Chain Rule

121
Mutual Information
• I(X; Y) is the mutual information between X and Y .
• The reduction of uncertainty of one RV due to knowing about the
other, or the amount of information one RV contains about the other

122
Mutual Information

123
 Shannon Game
• Shannon’s Experiment to Calculate the Entropy of English

Th-r- -s -nly -n- w-y t- f-ll -n th- v-w-ls -n th-s s-nt-nc

There is only one way to fill in the vowels in this sentence

124
Entropy of a Language: Shannon’s Approach
• Show somebody the beginning of a text
• Ask him/her to guess the next letter
• Count the number of trials

125
 Entropy and Linguistics
• Entropy is measure of uncertainty. The more we know about something the lower
the entropy
• If a language model captures more of the structure of the language, then the
entropy should be lower
• We can use entropy as a measure of the quality of our models

126
 Perplexity
• Definition: Perplexity is a measurement of how well a probability
distribution or probability model predicts a sample.

• The perplexity of a discrete probability distribution p is defined as:

127
 Perplexity
• In natural language processing, perplexity is a way of evaluating
language models.
• A language model is a probability distribution over entire sentences
or texts

128
 Branching Factor
• Branching factor is the number of possible words that can be used in
each position of a text
• Maximum branching factor for each language is V

• Ali eats an …….

Desk, Glass, apple, banana, umbrella, orange, mobile

A good language model should be able to:

minimize this number
give a higher probability to the words that occur in real texts

129
Perplexity for a sentence

130
 Perplexity
• Maximum branching factor for each language is |V|

131
Perplexity

132
 Evaluation
• The evaluation must give an indication of how well the learner will do
when it is asked to make new predictions for data it has not already
seen.
• Dividing the corpus into two parts:

• Building a language model from the training set

• Estimating the probability of the test set
• Calculate the perplexity of the test set
133
 Parameter Tuning and Cross-validation
• Dividing the corpus into three parts train, dev, test
• Building a language model from the training set
• Calculating the perplexity of the development set with different
parameter values
• Choosing the best parameter value and use it to estimate the
probability of the test set
• Calculating the perplexity of the test set

134