Module 2

Morphological Analysis and POS Tagging

Sentence Segmentation – Language Specific issues – Text
Normalization – Stemming - Inflectional and Derivation
Morphology - Morphological Analysis and Generation using
finite state transducers - Introduction to POS Tagging, Hidden
Markov Models for POS Tagging - Viterbi Decoding for HMM
 Text Preprocessing
• Text preprocessing is an essential step in natural
language processing (NLP) that involves cleaning and
transforming unstructured text data to prepare it for
analysis. It includes tokenization, stemming,
lemmatization, stop-word removal, and part-of-speech
tagging.
 Text Preprocessing cont..
To prepare the text data for the model building, we perform
text preprocessing. It is the very first step of NLP projects.
Some of the preprocessing steps are:
• Removing punctuations like . , ! $( ) * % @
• Removing URLs
• Removing Stop words
• Lower casing
• Tokenization
• Stemming
• Lemmatization
A few basic rules first…
• Machine doesn’t understand characters, words or
sentences.
• Machines can only process numbers.
• Text data must be encoded as numbers for input
or output for any machine.
Why Text Encoding?
We cannot pass raw text into machines as input until and unless
we convert them into numbers, hence we need to perform text
encoding.

WHAT is text encoding?

Text encoding is a process to convert meaningful text into
number / vector representation so as to preserve the context
and relationship between words and sentences, such that a
machine can understand the pattern associated in any text and
can make out the context of sentences.
 Character Encoding
• Text in a computer or on the Web is composed of
characters. Characters represent letters of the alphabet,
punctuation, or other symbols.
• It is a system for representing characters as numerical
values, known as code points. These code points allow
computers to store and manipulate text, which can then be
displayed or used in other ways.
• Types
– ASCII
– Unicode
 ASCII
• ASCII (American Standard Code for Information
Interchange) is a character encoding standard that assigns
unique numbers to each letter, digit, and other symbol
used in written text. It is widely used, but it has some
limitations.
• ASCII has 128 code points, which means that it can
represent 128 characters and symbols. Some of these code
points represent instructions for the computer, while
others represent printable characters such as letters and
digits.
ASCII TABLE
 ASCII Example
• We can encode the string
“Language” as “4C 61 6E 67 75 61 67 65”
Limitations
• Not suited for any language that uses more than the
basic Latin alphabet.
• special symbols, like emojis or currency symbols that
are not included in ASCII cannot be represented
 Unicode
• Unicode is a character encoding standard developed in
the late 1980s and early 1990s
• One of the main motivations was the need to have a
single-character encoding standard that could be used
to represent text in any language
• Unicode uses a 16-bit encoding scheme, which allows
it to represent over 65,000 different characters.
 Unicode cont..
• It can encode and display text in a wide range of
languages, including those using scripts other than the
Latin alphabet (e.g. Chinese, Japanese, Arabic), as well
as special symbols like emojis and currency symbols.
• UTF(Unicode Transformation Format)-8 and UTF-16 are
the most commonly used encodings.
• UTF-8 uses one to four bytes for each code point. It is
very compatible with ASCII.
• UTF-16 uses one or two 16-bit code units per code
point.
• The basic TensorFlow [Link] type allows us to build
tensors of the byte string. Unicode strings are UTF-8 by
default.
Example of Unicode using Tensorflow
library
 Representation of Unicode
We can represent a Unicode string in Tensorflow in two
standards:
• string scalar — where the sequence of code points is
encoded using a known character encoding (such as
Unicode).
• int32 vector — where each position contains a single
code point.
 Segmentation/Tokenization

• Segmentation is the process of taking an

undifferentiated sequence of symbols and
segmenting it into chunks
• Sentence segmentation is the problem of
automatically finding the sentence boundaries in a
corpus
• Word segmentation is the problem of finding word
boundaries in a corpus
• In languages without word boundary markers, like
Chinese and Japanese has its own challenges

16
 Sentence Segmentation
• Sentence segmentation is the process of determining the
longer processing units consisting of one or more words.
This task involves identifying sentence boundaries between
words in different sentences.
• Since most written languages have punctuation marks
which occur at sentence boundaries, sentence
segmentation is frequently referred to as sentence
boundary detection, sentence boundary disambiguation,
or sentence boundary recognition. All these terms refer to
the same task: determining how a text should be divided
into sentences for further processing.
 Sentence Segmentation

• ! , ? – Unambiguous
• Period “. “ – ambiguous
– Sentence boundary
– Abbreviations like Inc. Or Dr.
– Numbers like .02% or 4.3
– Various libraries - NLTK, Spacy, Stanford CoreNLP
Sentence Segmentation
 Tokenization
• Tokenization is breaking the raw text into small chunks.
Tokenization breaks the raw text into words, sentences
called tokens. These tokens help in understanding the
context or developing the model for the NLP. The
tokenization helps in interpreting the meaning of the
text by analyzing the sequence of the words.
• For example, the text “It is raining” can be tokenized
into ‘It’, ‘is’, ‘raining’
 Tokenization cont..
• A tokenizer breaks unstructured data and natural
language text into chunks of information that can be
considered as discrete elements. The token
occurrences in a document can be used directly as a
vector representing that document.
• This immediately turns an unstructured string (text
document) into a numerical data structure suitable for
machine learning.
 Word Segmentation/ Word Tokenization

• Process of segmenting a string of characters into

words
I have a can opener; But I can’t open these
cans

No of Word Tokens:
No of Word Types:

Word Tokens: An occurrence of a word

Word Types: A different realization of a word/ An
entry in the dictionary

23
 How Many Words?

they lay back on the San Francisco grass and looked at the stars
and their

• How many?
– 15 tokens
– 13 types

24
 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.h., PhD. → ??

26
 Tokenization issues

Apostrophe
• French
– L'ensemble → one token or two?
• L ? L’ ? Le ?
• Want l’ensemble to match with un ensemble

• German noun compounds are not segmented

– Lebensversicherungsgesellschaftsangestellter
– ‘life insurance company employee’
– German information retrieval needs compound splitter

27
Word Tokenization in Sanskrit

28
 Tokenization: language issues

• Chinese and Japanese no spaces between words:

– 莎拉波娃现在居住在美国东南部的佛罗里达。
– 莎拉波娃 现在 居住 在 美国 东南部 的 佛
罗里达
– Sharapova now lives in US
southeastern Florida
フォーチュン500社は情報不足のため時間あた$500K(約6,000万円)
Katakana Hiragana Kanji Romaji
• Further complicated in Japanese, with multiple alphabets
intermingled
– Dates/amounts in multiple formats

29
 Tokenization issues in Biotext
• Periods
While most periods are end of sentence punctuation
marks, others mark an abbreviation such as in etc. or
Calif.
These abbreviation periods presumably should remain as
part of the word, and in some cases keeping them might
be important so that we can distinguish Wash., an
abbreviation for the state of Washington, from the
capitalized form of the verb wash.
 Tokenization issues in Biotext
• Commas
– 2,6-diaminohexanoic acid
– tricyclo([Link],7)decanone
• Hyphenation-Four kinds of hyphens(Different forms
representing the same word)
– “Syntactic:”
• Calcium-dependent
• Hsp-60
– Knocked-out gene:
• lush– flies
– Negation:
• -fever
– Electric charge:
• Cl-
 Text Normalization
• Text normalization in NLP (Natural Language Processing)
refers to the process of transforming text data into a
standardized and consistent format.
• This involves addressing variations in spelling, punctuation,
capitalization, and other linguistic elements to ensure
uniformity.
• The goal of text normalization is to enhance the efficiency
and accuracy of language processing tasks by reducing the
impact of irrelevant variations in the input text.
 EXAMPLE

Normalizing in this context means that similar words are

combined into a single, normalized form.
 Case folding/Case Normalization

• Applications like IR: reduce all letters to lower

case
– Since users tend to use lower case
– Possible exception: upper case in mid-sentence?
• e.g., General Motors
• Fed vs. fed Federal Reserves
• SAIL vs. sail Single Alternative Inspection Location
• For sentiment analysis, MT, Information
extraction
– Case is helpful (US versus us is important)

36
Text Normalization
 Text Normalization - Expanding contractions

• Expanding contractions: Contractions are words or

combinations of words that are shortened by dropping letters
and replacing them by an apostrophe, and removing them
contributes to text standardization.
• We will contracted as “we’ll”
 Text Normalization - Expanding contractions
• Create a
dictionary of
contractions with
their
corresponding
expansions:
 Text Normalization - Tokenize
• Tokenization is the process
of segmenting running text
into sentences and words.
In essence, it’s the task of
cutting a text into pieces
called tokens.
 Text Normalization – Remove punctuations
• Remove the various punctuations in the text
 Text Normalization – Stemming
• Stemming is the process of reducing the words to their
word stem or root form. The objective of stemming is to
reduce related words to the same stem even if the stem is
not a dictionary word.
• For example, connection, connected, connecting word
reduce to a common word “connect”.
Text Normalization – Stemming
 Text Normalization – Lemmatization
• Unlike stemming, lemmatization reduces words to their base word,
reducing the inflected words properly and ensuring that the root word
belongs to the language.
• It’s usually more sophisticated than stemming, since stemmers works
on an individual word without knowledge of the context.
• In lemmatization, a root word is called lemma. A lemma is the
canonical form, dictionary form, or citation form of a set of words.
Text Normalization – Lemmatization

Gone

Going Go

Went
 Text Normalization –
Stemming vs Lemmatization
 NOTE
• Stemming is a process that stems or removes last few
characters from a word, often leading to incorrect
meanings and spelling.
Eg: the word 'Caring' would return 'Car'
• Lemmatization considers the context and converts the
word to its meaningful base form, which is called
Lemma.
lemmatizing the word 'Caring' would return 'Care'
 Text Normalization – POS tagging
• POS tagging is the task of assigning each word in a sentence the part of speech
that it assumes in that sentence.
• The primary target of POS tagging is to identify the grammatical group of a given
word: whether it is a noun, pronoun, adjective, verb, adverbs, etc. based on the
context.
• POS tagging improves accuracy
Text normalization -Byte Pair Encoding

▪ Dynamically decide the level of tokens

▪ Character level
▪ Morpheme level
▪ Word level
▪ Phrase level
 Sentence Segmentation

▪Cues for segmenting a text into sentences

• are punctuation
▪ Periods “.”
▪ question marks “?”
▪ exclamation points “!”
▪Question marks and exclamation points are relatively
unambiguous markers of sentence boundaries.
▪Periods, on the other hand, are more ambiguous.
Segmentation
Algorithms
▪ Rule based
▪ Machine Learning Based
 Rule Based Approach
▪ In the Stanford CoreNLP toolkit sentence splitting is rule-
based
▪ Necessary rules for segmentation
▪ Text Book – Speech and Language
Processing Jurafsky- Section 2.4 ▪ On encountering punctuation (., !, or ?)
▪ which is not already grouped with other characters into a
token (such as for an abbreviation or number)
▪ optionally followed by additional final quotes or
brackets.
 Stemming
• Stemming is one of several text normalization
techniques that converts raw text data into a readable
format for natural language processing tasks.
• It is the process of reducing inflected form of a
word to one so-called “stem,” or root form.
• Stemming aims to improve text processing
in machine learning and information retrieval
systems.
 Stemming

• Reduce terms to their stems in information

retrieval
• Stemming is crude chopping of affixes
– language dependent
– e.g., automate(s), automatic, automation all
reduced to automat.
for exampl compress and
for example compressed compress ar both accept
and compression are both as equival to compress
accepted as equivalent to
compress.

57
Stemming
APPLICATION OF STEMMING
 Types of Stemming – Porter’s stemmer
• The Porter Stemmer is a stemming algorithm developed by
Martin Porter in 1980.
• It is a rule-based algorithm widely used in natural language
processing to reduce words to their base or root form.
• The primary purpose of stemming is to normalize words,
capturing their essential meaning and removing variations
such as different tenses or plural forms.
• The Porter Stemmer is particularly popular due to its
simplicity and effectiveness.
Porter Stemmer Algorithm
Porter Stemmer Definitions
 Measure of Word
V: Vowel
C: Consonant

VC VC VC VC

VC VC VC VC VCVC VC VC

For each VC combination measure M=1

Rules for removing a suffix
 The Porter Stemmer : Step 1b
• (m>0)EED →EE

Step 1 deals with plurals and past participles

Step 1 deals with plurals and past participles
The Porter Stemmer : Step 2
The Porter Stemmer : Step 2(Cleanup)

NOTE
The Porter Stemmer : Step 3
The Porter Stemmer : Step 4
The Porter Stemmer : Step 5(cleanup)

NOTE
 Snowball stemmer
• The Snowball Stemmer, compared to the Porter Stemmer,
is multi-lingual as it can handle non-English words.
• It supports various languages and is based on the
‘Snowball’ programming language, known for efficient
processing of small strings.
• The Snowball stemmer is way more aggressive than Porter
Stemmer and is also referred to as Porter2 Stemmer.
• Because of the improvements added when compared to
the Porter Stemmer, the Snowball stemmer is having
greater computational speed.
 Lovins Stemmer
• Lovins proposed this algorithm in 1968, which removes the
longest suffix from a word, then the word is recoded to
convert this stem into valid words.
• The Lovins algorithm is noticeably bigger than the Porter
algorithm, because of its very extensive endings list.
• But in one way that is used to advantage: it is faster.
• It needs just two major steps to remove a suffix, compared
with the eight of the Porter algorithm.
• Example: sitting -> sitt -> sit
 Dawson Stemmer
• The Dawson Stemmer is an extension of the Lovins
stemmer.
• In the Dawson Stemmer, suffixes are stored in the
reversed order indexed by their length and last letter.
 Krovetz Stemmer
• This stemming algorithm was proposed in 1993 by
Robert Krovetz. Here are the steps that the Krovetz
Stemmer follows:
• Convert the plural form of a word to its singular form.
• Convert the past tense of a word to its present tense
and remove the suffix ‘ing.’
• Example: ‘children’ -> ‘child’
 N-Gram Stemmer
• An n-gram is a set of n consecutive characters extracted
from a word in which similar words will have a high
proportion of n-grams in common.
• INTRODUCTIONS’ for n=2 becomes : *I, IN, NT, TR, RO,
OD, DU, UC, CT, TI, IO, ON, NS, S*
 Lancaster Stemmer
• The Lancaster stemmers are more aggressive and
dynamic compared to the other two stemmers.
• The stemmer is really faster, but the algorithm is really
confusing when dealing with small words.
• But they are not as efficient as Snowball Stemmers.
• The Lancaster stemmers save the rules externally and
basically uses an iterative algorithm
 Word categories
• A.k.a. parts of speech (POSs)
• Important and useful to identify words by their POS
– To distinguish homonyms eg: lead, watch
– To enable more general word searches
• POS familiar (?) from school and/or language learning
(noun, verb, adjective, etc.)
 Word categories
• Recall that we distinguished
– open-class categories (noun, verb, adjective, adverb)
– Closed-class categories (preposition, determiner, pronoun,
conjunction, …)
• While the big four are fairly clearcut, it is less obvious
exactly what and how many closed-class categories
there may be
 POS tagging
• Labelling words for POS can be done by dictionary lookup
and/or some sort of process
• Identifying POS can be seen as a prerequisite to parsing, and/or
a result of morphological analysis in its own right
• However, there are some differences:
– Parsers often work with the most simple set of word categories,
subcategorized by feature (or attribute-value) schemes
– Indeed the parsing procedure may contribute to the disambiguation of
homonyms
 POS tagging
• POS tagging, per se, aims to identify word-category information
somewhat independently of sentence structure …
• … and typically uses rather different means
• POS tags are generally shown as labels on words:
John/NPN saw/VB the/AT book/NCN on/PRP the/AT table/NN ./PNC
• We’ll return to tagging in detail, but first let’s mention …
 Chunking
• Like parsing except that it aims only to identify major
constituents
• And does not attempt to identify structure, neither
internal (within the chunk), nor external (between
chunks)
• Chunking will leave some parts of the text unanalysed
• Example:
[NP [NP G.K. Chesterton ], [NP [NP author ] of [NP [NP The Man ] who was [NP Thursday ] ] ] ]
 Chunking
• Chunks can be represented like tags or like parse trees
 Chunk parser
• A “chunk” is a continuous non-overlapping sequence of words
• Chunker finds such sequences, often using tagged text as input
• Chunk rules can be as simple as regular expressions
• Chunkers can allow embedding (recursive chunking), but
typically only to a shallow level
• Another example:
(S: (NP: I) saw (NP: the big dog) . )
 Sentence Segmentation – Language Specific issues – Text
Normalization – Stemming - Inflectional and Derivation
Morphology - Morphological Analysis and Generation using
finite state transducers - Introduction to POS Tagging, Hidden
Markov Models for POS Tagging - Viterbi Decoding for HMM

Inflectional and Derivation Morphology

Inflectional Morphology
 Inflectional Morphology
Regular and irregular inflection
 Derivation Morphology

Paint (Verb) -> Painter(Noun)

Derivation Morphology
 Derivation Morphology
Types of derivational affixes
Derivation Morphology
Class-changing affixes
 Derivation Morphology
Class-changing affixes - Nominalizers
 Derivation Morphology
Class-changing affixes - Verbalizers
 Derivation Morphology
Class-changing affixes - Adjectiviers
 Derivation Morphology
Class-changing affixes - Adverbializers
 Derivation Morphology
Class-maintaining affixes
 Derivation Morphology
Class-maintaining affixes – Noun patterns
 Derivation Morphology
Class-maintaining affixes – Verb patterns
 Derivation Morphology
Class-maintaining affixes – Adjective patterns
Finite State Automata
 INTRODUCTION
• FSA can be used to represent morphological lexicon
and recognition.
• The generally accepted approach to morphological
parsing is through the use of a finite state transducer
(FST), which inputs words and outputs their stem and
modifiers. The FST is initially created through
algorithmic parsing of some word source, such as a
dictionary.
• A language (a set of strings) that can be described by a
finite automaton is called a regular language.
• Formal languages are important to computer science (and
to many other fields). All programming languages, like
Java, C, and Python, are formal languages.
Regular Expressions and Finite State Automata
Finite State Automaton
Finite State Automaton
FSA

Input
String Output
“Accept”
Finite or
A utomaton
“ Reject”

1
1
0
Finite State Automaton
Formalization of FSA
Morphological Parsing
Morphological Parsing
Morphological Analysis
FSA for Morphology : Example
Merging Automata
Simple FSA for Nominal Inflection
Expanded FSA for few English Nouns

dog
dogs
cat
cats
goose
geese
Finite State Transducers
Recognition Vs Analysis
Finite State Transducers
Formal Definition of FST
 Formal Definition of FST

T defines the relation of the language

FSTs for NLP
FSTs for Morphological Parsing
FSTs for Morphological Parsing
FST’s and Orthographic rules
Intermediate Representation
FST for Orthographic Rules
Porter Stemmer
A simple ELIZA dialogue
 Parts of Speech: Nouns and Pronouns,
Words: Determiners and adjectives, verbs,
Phrase Structure.
THE PENN TREEBANK - POS TAGGING
Parts Of Speech(POS)
Adverb and
Adjective
 Phrase Structure Grammar
• Phrase structure grammar, also known as constituency
grammar, is a way of representing the syntactic structure
of natural language sentences using hierarchical trees.
• In natural language processing (NLP), phrase structure
grammar can be used to analyze, parse, and generate
natural language texts.
• A grammer
• Syntactic elements of a language defined using rewrite
rules
• Rewrite rules specify smaller constituents
• The cat killed the rat
Determiner Noun verb Determiner Noun

cat the killed the rat

Noun Determiner verb Determiner Noun
• The cat killed the rat
Determiner Noun verb Determiner Noun

Determiner + Noun
The cat killed the rat
Determiner Noun verb Determiner Noun
Noun phrase Noun phrase

NP->Determiner + Noun
 Types of Phrases
• Noun Phrase
• Verb Phrase
• Prepositional Phrase
• Adjective Phrase
• Adverb Phrase
 Types of Phrases
• Noun Phrase
 Types of Phrases
• Verb Phrase
 Types of Phrases
• Adjective Phrase

AdjP -> Deg + Adj + PP

quite happy with the result

Deg: Degree adverb(optional)

Adj: Adjective
PP : Preposition Phase(optional)
 Types of Phrases
• Adverb Phrase
AdvP - > Deg + Adv
 Types of Phrases
Prepositional Phrase
PP - > Deg + NP
Syntactic structure
Issues in POS tagging
Types of POS tagger
THE PENN TREEBANK- POS TAGGING
HIDDEN MARKOV MODEL
WITH POS TAGGING
MARKOV CHAIN
MARKOV CHAIN

HMM
 Transition Probability matrix
Rainy Sunny
Rainy 0.7 0.3
Sunny 0.4 0.6

Emission Probability matrix

Rainy Sunny
Walk 0.1 0.6
Shop 0.4 0.3
Clean 0.5 0.1
 Maximum likelihood estimate

MD-Modal Verb ("could," "will," "would," "shall," "should," "may," "might," and "must”)
Emission Probabilities
 HMM tagging as decoding
• For any model, such as an HMM, that contains
hidden variables, the task of determining the
hidden variables sequence corresponding to
the sequence of observations is called
decoding.
most probable tag sequence from a bigram tagger
Viterbi Decoding for HMM
Example - Viterbi Decoding Algorithm
SOLVED EXAMPLE HMM
 DO IT YOURSELF!
Assign the correct POS Tag using HMM-Viterbi alg
 Application of HMM
• Part-of-speech tagging: Using the word order and the POS tags of words
around it, HMMs can predict the part-of-speech tag for each word in a
sentence.
• Named Entity Recognition :Named entities in text, such as names of
people, places, or organizations, can be found using HMMs.
• HMMs can turn spoken language into text by simulating the probability
distribution of speech sounds given the words being spoken.
• HMMs can translate text from one language to another by simulating the
probability distribution of words in the target language given the words in
the source language.
• Language modelling: Using the previous words in a sequence as a guide,
HMMs can predict the following word. This can enhance the efficiency of
language processing tasks like text generation and spelling checking.