PCP3165:
Natural Language Processing
Text Normalization
Session Objectives
• Learning different text preprocessing techniques using
text normalization.
2 v 1.2
Session Outcomes
• At the end of this session, participants will be able to
– Apply text normalization techniques to preprocess the given text
3 v 1.2
Agenda
• Token Vs Vocabulary
• Issues in tokenization
• Word tokenization
– Max matching algorithm
– Issues
• Case folding
• Lemmatization
• Stemming
• Porter stemmer
• Sentence segmentation
4 v 1.2
Text Normalization
• Every NLP task needs to do some form of text
normalization. Not terribly glamorous but
critical to further processing
– Determining a relevant vocabulary
– Segmenting/tokenizing words in running text
– Normalizing word formats
– Segmenting sentences in running text
5 v 1.2
5
How many words?
“They lay back on the San Francisco grass and looked at the stars
and their…”
• Type: an element of the vocabulary
• Token: an instance of that type in running text
• How many words are there in this sentence?
– 15 tokens (or maybe 14)
– 13 types (or 12)
6 v 1.2
6
Vocabulary
• First, what’s our vocabulary?
– What words are needed for a particular application? All of English?
A subset?
– How many will there be?
– How do we determine the right list?
– Is it finite?
– Etc.
7 v 1.2
7
How many words?
N = number of tokens
V = vocabulary = set of types
|V| is the size of the vocabulary
Tokens = N Types = |V|
Switchboard phone 2.4 million 20 thousand
conversations
Shakespeare 884,000 31 thousand
Google N-grams 1 trillion 13 million
8 v 1.2
8
Simple Tokenization in UNIX
• Given a text file, output all the word types and their
associated frequencies in that text corpus
– Inspired by Ken Church’s UNIX for Poets.
• Unix has many commands to deal with basic text
processing operations
– Original Unix designers cared a lot about text processing
– Most of which are line oriented
9 v 1.2
9
The first step: tokenizing
• So let’s do some dumb tokenization and get each
token on a line by itself.
tr -sc ’A-Za-z’ ’\n’ < [Link] | head
THE
SONNETS
by
William
Shakespeare
From
fairest
creatures
We
...
10 v 1.2
10
The second step: sorting
tr -sc ’A-Za-z’ ’\n’ < [Link] | sort |
head
A
A
A
A
A
A
A
A
A
...
11 v 1.2
11
Then some counting
• Merging upper and lower case
tr ‘A-Z’ ‘a-z’ < [Link] | tr –sc ‘A-Za-z’ ‘\n’
• Sorting the counts
tr ‘A-Z’ ‘a-z’ < [Link] | tr –sc ‘A-Za-z’ ‘\n’
| sort | uniq –c | sort –n –r
23243 the
22225 i
18618 and
16339
15687
to
of
What happened here?
12780 a
12163 you
10839 my
10005 in
8954 d
12 v 1.2
12
Issues in Tokenization
• Finland’s capital → Finland Finlands Finland’s ?
• what’re, I’m, isn’t → What are, I am, is not
• Hewlett-Packard → Hewlett Packard ?
• state-of-the-art → state of the art ?
• Lowercase → lower-case lowercase lower case ?
• San Francisco → one token or two?
• m.p.g., PhD. → ??
13 v 1.2
13
Tokenization: language issues
• French
– L'ensemble → one token or two?
• L ? L’ ? Le ?
• German noun compounds are not segmented
– Lebensversicherungsgesellschaftsangestellter
– ‘life insurance company employee’
– German information retrieval needs compound splitter
14 v 1.2
14
Tokenization: language issues
• Chinese has no spaces between words
– 莎拉波娃现在居住在美国东南部的佛罗里达。
– 莎拉波娃 现在 居住 在 美国 东南部 的 佛罗里达
– Sharapova now lives in US southeastern Florida
• Japanese allows multiple alphabets intermingled
フォーチュン500社は情報不足のため時間あた$500K(約6,000万円)
Katakana Hiragana Kanji Romaji
15 v 1.2
15
Word Tokenization in Chinese
• Also called Word Segmentation
• Chinese words are composed of characters
– Characters are generally 1 syllable and 1 morpheme.
– Average word is 2.4 characters long.
• Standard baseline segmentation algorithm:
– Maximum Matching (also called Greedy)
16 v 1.2
16
Maximum Matching
Word Segmentation Algorithm
Given a wordlist of Chinese, and a string
1) Start a pointer at the beginning of the string
2) Find the longest word in dictionary that matches the
string starting at pointer
3) Move the pointer over the word in string
4) Go to 2
17 v 1.2
17
18 v 1.2
18
Max-match English Example
• Thecatinthehat the cat in the hat
• Thetabledownthere the table down there
theta bled own there
• Doesn’t generally work in English!
• But works astonishingly well in Chinese
– 莎拉波娃现在居住在美国东南部的佛罗里达。
– 莎拉波娃 现在 居住 在 美国 东南部 的 佛罗里达
• Modern probabilistic segmentation algorithms even better
19 v 1.2
19
Maximum Matching
themartian
20 v 1.2
20
Testing, Improvement and Evaluation
• There are two tasks:
– Make sure that you have implemented MaxMatch
correctly
• Testing
– Figure out a way to improve performance on this task
• This means you need a way to detect improvement
21 v 1.2
21
Testing
• Given a particular dictionary and a correct
implementation there is a “right” answer that
MaxMatch should come up with. So for
“themartian” that might be
– them art i an
• That’s the “right” answer even though its clearly
not the right answer…
22 v 1.2
22
Improvement and Evaluation
• So given a test set of outputs like
– them art i an
• How do we know if things are getting better?
• What do we need to know to say things are
getting better?
23 v 1.2
23
Reference Answers
• We need to know what the “right” answer is.
Here “right” means the answer we would expect
a human to produce. In this case “the martian”.
So we have
– them art i an
– the martian
• And a whole bunch of examples like this, some
right, some wrong
• How do we assess how well we’re doing?
24 v 1.2
24
Evaluation
• Strict accuracy
– Given a test set, how many things are right and how
many are wrong?
• Too pessimistic
– Might get you fired
• Not fine-grained enough
– May not show you are making progress when you are
in fact making progress
25 v 1.2
25
Progress?
• Start with
– them art I an
– the martian
• Move to
– The mart I an
– The martian
• They’re both still wrong. So does it make sense
to say one is better?
26 v 1.2
26
Case folding
• Applications like web search: reduce all letters to
lower case
– Since users tend to use lower case
• For sentiment analysis, MT, Information
extraction
– Case is helpful (US versus us; IRE vs. ire)
27 v 1.2
27
Lemmatization
• Reduce inflections or variant forms to base form
– am, are, is → be
– car, cars, car's, cars' → car
• the boy's cars are different colors → the boy car
be different color
• Lemmatization: have to find correct dictionary
headword form
28 v 1.2
28
Stemming
• Reduce terms to their stems
• Stemming is crude chopping of affixes
– language dependent
– e.g., automate(s), automatic, automation all
reduced to automat.
for example compressed for exampl compress and
and compression are both compress ar both accept
accepted as equivalent to as equival to compress
compress.
29 v 1.2
29
Porter’s Algorithm
Step 1a Step 2 (for long stems)
sses → ss caresses → caress ational→ ate relational→ relate
ies → i ponies → poni izer→ ize digitizer → digitize
ss → ss caress → caress ator→ ate operator → operate
s → ø cats → cat
Step 1b Step 3 (for longer stems)
(*v*)ing → ø walking → walk al → ø revival → reviv
sing → sing able → ø adjustable → adjust
(*v*)ed → ø plastered → plaster ate → ø activate → activ
30 v 1.2
30
Complex Morphology
• Some languages requires complex morpheme
segmentation
– Turkish
– Uygarlastiramadiklarimizdanmissinizcasina
– `(behaving) as if you are among those whom we could
not civilize’
– Uygar `civilized’ + las `become’
+ tir `cause’ + ama `not able’
+ dik `past’ + lar ‘plural’
+ imiz ‘p1pl’ + dan ‘abl’
+ mis ‘past’ + siniz ‘2pl’ + casina ‘as if’
31 v 1.2
31
Sentence Segmentation
• In English, punctuation is used to mark sentence
boundaries
– !, ? are relatively unambiguous
– Period “.” is quite ambiguous
– Abbreviations like Inc. or Dr.
– Numbers like .02% or 4.3
• Machine learning approach
– Build a binary classifier
– Looks at each possible EOS punctuation and decides
EndOfSentence/NotEndOfSentence
32 v 1.2
32
Decision Tree Example
33 v 1.2
33
More sophisticated decision tree features
• Case of word with “.”: Upper, Lower, Cap,
Number
• Case of word after “.”: Upper, Lower, Cap,
Number
• Numeric features
– Length of word with “.”
– Probability(word with “.” occurs at end-of-s)
– Probability(word after “.” occurs at beginning-of-s)
34 v 1.2
34
Decision Trees and other classifiers
• We can think of the questions in a decision tree
as features that could be exploited by any kind
of classifier
– Logistic regression
– SVM
– Neural Nets
– etc.
35 v 1.2
35
Summary
• Token Vs Vocabulary
• Issues in tokenization
• Word tokenization
– Max matching algorithm
– Issues
• Case folding
• Lemmatization
• Stemming
• Porter stemmer
• Sentence segmentation
36 v 1.2
Se pte mber 13, 2017
Check your understanding
Natural language processing (NLP) is a branch of artificial intelligence that
helps computers understand, interpret and manipulate human language.
NLP draws from many disciplines, including computer science and
computational linguistics, in its pursuit to fill the gap between human
communication and computer understanding.
• Apply text normalization and find the vocabulary.
37 v 1.2