0% found this document useful (0 votes)

2 views186 pages

Module 2

The presentation from St. Francis Institute of Technology covers Natural Language Processing (NLP) with a focus on word-level analysis, including concepts like tokenization, stemming, and lemmatization. It discusses English morphology, including inflectional and derivational morphology, as well as regular expressions and their application in text normalization. The content is intended for educational purposes and prohibits distribution or modification.

Uploaded by

jaskaurmukhtiar

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

2 views186 pages

Module 2

Uploaded by

jaskaurmukhtiar

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes.

Distribution and modifications of the content is prohibited.

Natural Language Processing

CSDC7013

Subject In-charge
Ms. Pradnya Sawant
Assistant Professor
Room No. 415
email: pradnyarane@[Link]

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 1
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Module 2
Word Level Analysis

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 2
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Contents
• Basic Terms: Tokenization, Stemming, Lemmatization
• Survey of English Morphology- Inflectional Morphology,
Derivational Morphology
• Regular expression with types
• Morphological Models: Dictionary lookup, finite state morphology
• Morphological parsing with FST (Finite State Transducer)
• Lexicon free FST, Porter Stemmer algorithm
• Grams and its variation: Bigram, Trigram; Simple (Unsmoothed)
N-grams
• N-gram Sensitivity to the Training Corpus; Unknown Words: Open
versus closed vocabulary tasks
• Evaluating N-grams: Perplexity; Smoothing: Laplace Smoothing,
Good-Turing Discounting
St. Francis Institute of Technology NLP
Department of Computer Engineering Ms. Pradnya Sawant 3
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Module 2
Lecture 1
• Basic Terms: Tokenization, Stemming,
Lemmatization
• Survey of English Morphology- Inflectional
Morphology, Derivational Morphology

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 4
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Tokenization
•One part of Text Normalization.
•Big quantity of text is divided into smaller parts called
tokens.
•Base step for stemming and lemmatization.
•Tokenization in Python
•Natural Language toolkit (NLTK)
• word tokenize : splitting a sentence into words.
• sentence tokenize : splitting a set of sentences into
individual sentences.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 5
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Tokenization of words
•word_tokenize() : split a sentence into words.
• Output can be converted to Data Frame for
applying ML Techniques.
•Assists further text cleaning steps such as
punctuation removal, numeric character removal
and so on.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 6
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Tokenization of Sentences
• sent_tokenize ()
• Sometimes it is needed to count average
words per sentence.
• Such output serves as an important feature
for ML.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 7
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Word Tokenization in English

• English words are often separated from each other

by whitespace
• But whitespace is not always sufﬁcient.
• Challenges:
• New York and rock ’n’ roll
• I’m to I am.
• Tokenize emotions :-) and hashtags
• Chinese, don’t have spaces between words

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 8
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Lemmatization

• Another part of text normalization

• The task of determining the root word.
E.g. sang, sung, and sings are forms of the verb
sing.
sing is the common lemma of these words a
lemmatizer maps from all of these to sing

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 9
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Lemmatization

• Lemmatization is essential for processing

morphologically complex languages like Arabic.
• Example : /‫ ضرب‬ḍaraba/ "he hit",
• /‫ ربَّ ض‬ḍarraba/ "he hit much" ,
• َّ‫ ب ِرض‬/ḍuriba/ "he was hit",
• /‫ضرب‬ḍarb/ "hitting", /‫ضارب‬ḍaarib/ "hitter"

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 10
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Stemming

• Another part of text normalization

• simpler version of lemmatization
• It mainly just strip sufﬁxes from the end
of the word.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 11
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Sentence Segmentation

•It involves breaking up a text into individual

sentences
Edit Distance
•Edit distance is a metric that measures how similar
two strings are based on the number of edits
(insertions, deletions, substitutions) it takes to change
one string into the other.
•Application : spelling corrections

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 12
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Example 1

• Given two strings str1 and str2 and below operations that
can performed on str1.
• Find minimum number of edits (operations) required to
convert ‘str1’ into ‘str2’.
• Insert
• Remove
• Replace
• All of the above operations are of equal cost.
• Example 1
• Input: str1 = "cat", str2 = "cut"
• Output: 1
• We can convert str1 into str2 by replacing 'a' with 'u'.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 13
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Example 2

Input: str1 = "sunday", str2 = "saturday“

How many operations?

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 14
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Example 2

Input: str1 = "sunday", str2 = "saturday"

Output: 3
Which are the operations?

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 15
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Example 2

Input: str1 = "sunday", str2 = "saturday"

Output: 3
Replace 'n' with 'r', insert t, insert a

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 16
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Morphology analysis
• Morphology is the study of the way words are built up from
smaller meaning-bearing MORPHEMES units, morphemes.
• A morpheme is often defined as the minimal meaning-bearing
unit in a language.
• Example the word fox consists of a single morpheme (the
morpheme fox) while the word cats consists of two: the
morpheme cat and the morpheme -s.
• There are two broad classes of STEMS morphemes:
stems and affixes.
• The stem is the “main” morpheme of the word, supplying the
main meaning, while the affixes add “additional” meanings of
various kinds.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 17
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

English Morphology

• Affixes are further divided into prefixes, suffixes, infixes, and

circumfixes.
• Prefixes precede the stem, suffixes follow the stem, circumfixes
do both(enlarged), and infixes are inserted inside the stem.
• For example, the word eats is composed of a stem eat and the
suffix -s. The word unbuckle is composed of a stem buckle and
the prefix un-.
• English doesn’t have any good examples of circumfixes and
infixes.
• A word can have more than one affix. For example, the word
rewrites has the prefix re-, the stem write, and the suffix -s.
• The word unbelievably has a stem (believe) plus three affixes
(un-, -able, and -ly).
St. Francis Institute of Technology NLP
Department of Computer Engineering Ms. Pradnya Sawant 18
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Inflectional Morphology
• Inflection is the combination of a word stem with a grammatical morpheme,
usually resulting in a word of the same class as the original stem.
• For example, English has the inflectional morpheme -s for marking the plural
on nouns, and the inflectional morpheme -ed for marking the past tense on
verbs.
• English nouns have only two kinds of inflection: an affix that marks plural
and an affix that marks possessive. For example, many (but not all) English
nouns can either SINGULAR appear in the bare stem or singular form, or
take a plural suffix.

The possessive suffix is realized by apostrophe + -s for regular singular

nouns (Rama’s) and plural nouns not ending in -s (children’s).

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 19
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Regular Verbs
These verbs are called regular because just by knowing the stem we
can predict the other forms by adding one of three predictable
endings and making some regular spelling changes.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 20
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Irregular verbs

The irregular verbs are those that have some more or less idiosyncratic
forms of inflection. Irregular verbs in English often have five different
forms, but can have as many as eight (e.g., the verb be) or as few as three
(e.g. cut or hit).

• The -ing participle is used in the progressive construction to mark present

or ongoing activity (It is raining), or
• when the verb is treated as a noun; this particular kind of nominal use of a
verb is called a gerund use: Fishing is fine if you live near water.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 21
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Derivational Morphology

● A very common kind of derivation in English is

the formation of new nouns, often from verbs
or adjectives. This process is called
nominalization.
● E.g. Computerization

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 22
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Derivational Morphology

● Examples of some particularly productive

English nominalizing sufﬁxes.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 23
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Derivational Morphology

Adjectives can also be derived from nouns and

verbs.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 24
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Derivational Morphology

● Derivation in English is more complex

because:
● It is generally less productive; even a (E.g. -
ation cannot be added to absolutely every
verb:*eatation or *spellation)
● There are subtle and complex meaning
differences among nominalizing sufﬁxes.
(ornament/agreement).

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 25
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Compounding
• Compounding is the combination of multiple word
stems together.
• For example the noun doghouse is the concatenation
of the morpheme dog with the morpheme house.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 26
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Cliticization
• Cliticization is the combination of a word stem with a
clitic.
• A clitic is a morpheme that acts syntactically like a word,
but is reduced in form and attached (phonologically and
sometimes orthographically) to another word.
• For example the English morphemes ’ve in the word
I’ve is a clitic.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 27
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Module 2
Lecture 2
•Regular Expressions with Types

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 28
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Regular Expression
•Used to specify strings extracted from a
document.
•Play an important role to a set of tasks
collectively called text normalization.
•Normalizing text means converting it to a
more convenient, standard form.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 29
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Regular Expressions

• It is an algebraic notation for characterizing a set of

strings.
• It is useful for searching in texts, when we have
• a pattern to search for and
• a corpus of texts to search through.
• A regular expression search function will search through the
corpus, returning all texts that match the pattern.
• The corpus can be a single document or a collection.
• A search can be designed to return :
• every match on a line, if there are more than one, or
• just the ﬁrst match.
• In the following examples we extract
• only the ﬁrst match.
• Regular expressions come in many variants.
St. Francis Institute of Technology NLP
Department of Computer Engineering Ms. Pradnya Sawant 30
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Basic Regular Expression Patterns

The simplest kind of RE is a sequence of simple characters.

E.g.
To search for woodchuck, we type /woodchuck/.
E.g.
The expression /Buttercup/ would return the line
“ I’m called little Buttercup.”
The search string can consist of :
a single character (like /!/) or
a sequence of characters(like/Buttercup/)

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 31
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Regular Expression
Regular expressions are case sensitive :
lower case /s/ is distinct from uppercase /S/
(/s/ matches a lower case s but not an uppercase S).
This means that the pattern /woodchucks/ will not match the
string Woodchucks.
This problem can be solved using square braces [ and ].
The string of characters inside the braces speciﬁes a disjunction
of characters to match.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 32
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Regular Expression
• RE : /[1234567890]/ specified any single digit.
• It is awkward to specify so.
• E.g.
• It is inconvenient to specify
/[ABCDEFGHIJKLMNOPQRSTUVWXYZ]/
• to mean “any capital letter”.
• When there is a well-defined sequence associated with a set of characters,
the brackets can be used with the dash (-) to specify any one character in a
range.
• E.g.
• /[2-5]/ specifies any one of the characters 2, 3, 4, or 5.
• /[b-g]/ specifies one of the characters b, c, d, e, f, or g.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 33
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Caret (ˆ)
• Caret ˆ can also be used to specify what a single character cannot
be.
• If the caret ˆ is the first symbol after the open square brace [,
the resulting pattern is negated.
• E.g. /[â]/ matches any single character (including special
characters) except a.
• This is only true when the caret is the first symbol after the open
square brace.
• If it occurs anywhere else, it stands for a caret.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 34
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Optional Elements
E.g. optional s in woodchuck and woodchucks?
Square brackets either allow “s or S”
They don’t allow us to say “s or nothing”.
For this we use the question mark /?/, which means “the
preceding character or nothing”.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 35
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Example

• Example Consider the language of certain sheep, which

consists of strings that look like the following:
• baa!
• baaa!
• baaaa!
• baaaaa!
This language consists of strings with a b, followed by at
least two a’s, followed by an exclamation point.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 36
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Kleene *
• It allows us to say things like “some number of a s” are based on
the asterisk or *, commonly called the Kleene *.
• Kleene * means “zero or more occurrences of the immediately
previous character or regular expression
• So /a*/ means “any string of zero or more a’s”.
• This will match
• a or aaaaaa
• Off Minor
• So the regular expression for matching one or more a is /aa*/,
meaning one a followed by zero or more as.
• More complex patterns can also be repeated.
• /[ab]*/ means “zero or more a’s or b’s” (not “zero or more right
square braces”).
• This will match strings like
• aaaa or ababab or bbbb
St. Francis Institute of Technology NLP
Department of Computer Engineering Ms. Pradnya Sawant 37
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Kleene +
• It’s annoying to have to write RE for digits twice
• E.g. ATM PIN: /[0-9] [0-9] [0-9] [0-9]/
• A shorter way to specify “at least one” of some character is
the Kleene +, which means “one or more occurrences of the
immediately preceding character or regular expression”.
• E.g. /[0-9]+/ is the normal way to specify “a sequence of
digits”.
• There are thus two ways to specify the sheep language:
/baaa*!/ or /baa+!/.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 38
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Wildcard Expression
One very important special character is the period (/./), a
wildcard expression that matches any single character (except a
carriage return).

Wildcard can be used together with Kleene * to mean “any

string of characters”.

E.g. Suppose we want to ﬁnd any line in which a particular word

appears twice.
RE : for word hello is
/hello.*hello/.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 39
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Anchors
• Anchors are special characters that anchor REs to particular
places in a string.
• Common anchors are the caret ˆ and the dollar sign $.
• caret ˆ
• The caret ˆ matches the start of a line.
• E.g. The pattern /ˆThe/ matches the word The only at the
start of a line.
• Thus, the caret ˆ has three uses:
• to match the start of a line e.g. /ˆThe/
• to indicate a negation inside of square brackets e.g. /[ˆa]/
• just to mean a caret. e.g. /[a^b]/

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 40
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Anchors
Dollar sign $
• The dollar sign $ matches the end of a line.
• The pattern _$ is a useful pattern for matching a space at
the end of a line.
• E.g. /ˆThe dog\.$/ matches a line that contains only the
phrase The dog. (Backslash here to mean “period” and not
the wildcard.)

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 41
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Anchors
There are also two other anchors:
• \b matches a word boundary, and \B matches a non-
boundary.
• Thus, /\bthe\b/ matches the word the but not the word
other.
• More technically, a “word” for the purposes of a regular
expression is deﬁned as any sequence of digits,
underscores, or letters; this is based on the deﬁnition of
“words” in programming languages.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 42
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Anchors
• For example,
• /\b99\b/ will match the string 99 in “There are 99 bottles of
water in the tray” (because 99 follows a space) but not 99
in “There are 299 bottles of water in the tray”(since 99
follows a number).
• But it will match 99 in $99 (since 99 follows a dollar sign
($), which is not a digit, underscore, or letter).

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 43
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Exercise

• Try to find regular expression for

identifying a 10 digit mobile number

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 44
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Exercise

Try to find regular expression for identifying

a 10 digit mobile number.

• [0-9][0-9][0-9][0-9][0-9][0-9][0-9][0-9][0-9][0-9] Not efficient

• [0-9]+ This matches any number of digits (≥1), not strictly 10.
• [0-9]{10}

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 45
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Disjunction Operator
• It is also called pipe symbol (|).
• E.g. /cat|dog/ implies cat or dog.
• To apply disjunction operator only to specific
patterns you should use parentheses.
• E.g. /gupp(y|ies)/ (disjunction is applied only to
suffix (y or ies ))

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 46
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Operator Precedence Hierarchy

• Patterns are greedy, expanding to cover as much of a string as

they can.
• To enforce non-greedy matching, use another meaning of the ?
qualifier.
• The operators *? and +? is a Kleene operators that matches as
little text as possible.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 47
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

More Operators

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 48
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Aliases for common sets of characters

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 49
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Regular expression operators for counting

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 50
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Some characters that need to be backslashed.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 51
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Regular Expression Substitution

and Capture Groups

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 52
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Substitutions
• An important use of regular expressions is in substitutions.
• The substitution operator is s/regexp1/pattern/.
E.g. s/colour/color/ Replaces every occurrence of colour with color.

• Suppose we want to put angle brackets around all integers in a

text:
• E.g. s/([0-9]+)/<\1>/

• Example
• the Xer they were, the Xer they will be
• RE: /the (.*)er they were, the \1er they will be/
• Match : the bigger they were, the bigger they will be.
(.*) → Captures anything before "er’’
\1 → Refers back to the same text captured earlier

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 53
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Capture group
• This uses parentheses to store a pattern in memory
• Every time a capture group is used (i.e., parentheses that
surround a pattern), the resulting match is stored in a numbered
register.
Example
• If you match two different sets of parentheses, \2 means
whatever matched the second capture group.
E.g. /the (.*)er they (.*), the \1er we \2/
• Input Sentence : the faster they ran
• After applying RE,
• Output Sentence: the faster they ran, the faster we ran.
Group 1 matched: fast Group 2 matched: ran

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 54
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Non-capturing Group
• Occasionally we may need to use parentheses for grouping, but
don’t want to capture the resulting pattern in a register.
• In that case, we use a non-capturing group.
• It is speciﬁed by putting the commands ?: after the open
parenthesis
• Format : (?: pattern ).
• E.g. RE: /(?:some|a few) (people|cats) like some \1/
• will match some cats like some cats but not some cats like
some a few.
• (?:some|a few) → Matches either "some" or "a few", without
capturing.
• (people|cats) → Captures either "people" or "cats" as group \1.
• \1 → Must match the same word captured by (people|cats).

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 55
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Lookahead assertions
• look ahead in the text see if some pattern
matches, but not advance the match cursor, so
that we can then deal with the pattern if it
occurs
• Format:(? syntax).
• The operator (?= pattern) is true if pattern
occurs
• The operator (?! pattern) only returns true if a
pattern does not match

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 56
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Module 2
Lecture 3
• Morphological Models: Dictionary lookup, finite
state morphology
• Deterministic FSA

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 57
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Morphological Models:Dictionary Lookup

• Dictionary is a data structure that directly
enables obtaining some precomputed results,
in our case it is word analysis.
• The data structure can be optimized for
efficient lookup and the results can be shared.
• Lookup operations are relatively simple.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 58
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Finite State Morphology using FSA

• RE is a convenient metalanguage for text
searching.
• RE is one way of describing a Finite State
Automaton (FSA).
• Any RE can be implemented by FSA (except
RE with memory).
• Symmetrically any FSA can be described by
RE.
• Both RE and FSA can be used to describe
Regular Language.
St. Francis Institute of Technology NLP
Department of Computer Engineering Ms. Pradnya Sawant 59
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Using FSA to Recognize Sheep Talk

Sheep language is any string from the following set:
baa!
baaa!
baaaa!
baaaaa!...

Find RE for this sheep language

Describe with the help of FSA

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 60
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

FSA For Sheep Language

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 61
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

State Transition Table

We can also represent an automaton with a state
transition table as below:

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 62
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

FSA
A finite automaton is defined by the following five
parameters:

For the sheeptalk automaton,

Q = {q0, q1, q2, q3, q4},
S = {a, b, !},
F = {q4}, and
𝞭 (q, i) is defined by the transition table.
St. Francis Institute of Technology NLP
Department of Computer Engineering Ms. Pradnya Sawant 63
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

D-RECOGNIZE
• It is an algorithm for recognizing a string
using a state-transition table
• The algorithm is called D-RECOGNIZE for
“deterministic recognizer”.
• A deterministic algorithm is one that has no
choice points; the algorithm always knows
what to do for any input.
• A deterministic automaton can be referred to
as a DFSA.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 64
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

D-RECOGNIZE
• The D-RECOGNIZE takes as input a tape and
an automaton. It returns accept if the string it
is pointing to on the tape is accepted by the
automaton, and reject otherwise.
• D-RECOGNIZE assumes it is already
pointing at the string to be checked, its task is
only finding a string in a corpus.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 65
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

D-RECOGNIZE

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 66
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

FSA For Sheep Language

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 67
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Fail State or Sink State

The algorithm will fail whenever there is no legal
transition for a given combination of state and input.
Fail State or Sink State: Any machine with empty
transitions is augmented with a fail state, so that there
is always somewhere to go from any state on any
possible input.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 68
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

FSA with fail state for sheep language

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 69
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Formal Languages
A formal language is a set of strings, each string
composed of symbols from a ﬁnite symbol-set called an
alphabet.
The alphabet for the sheep language is the set
Σ = {a, b, !}.
Given a model m, we can use L(m) to mean “the formal
language characterized by m.
The formal language for sheeptalk is
L(m) = {baa!, baaa!, baaaa!, baaaaa!, baaaaaa!, . . .}

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 70
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Formal Languages

• The usefulness of an automaton for deﬁning a

language is that it can express an inﬁnite set (such as
the one above) in a closed form.
• Formal languages are not the same as natural
languages.
• We often use a formal language to model part of a
natural language, such as parts of phonology,
morphology, or syntax.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 71
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Module 2
Lecture 4
• Non-deterministic FSA

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 72
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Non-Deterministic FSA

• Consider using this network as an automaton for

recognizing sheeptalk.
• When we get to state 2, if we see an a , we don’t
know whether to remain in state 2 or go on to state 3.
• Automata with decision points like this are called
non-deterministic FSAs (or NFSAs).

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 73
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Non-Deterministic FSA

• There is another common type of non-determinism,

caused by arcs that have no symbols on them (called ϵ-
transitions).

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 74
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Using an NFSA to Accept Strings

• If we want to identify string is an instance of

sheeptalk or not and if we use a nondeterministic
machine to recognize it, we might follow the wrong
arc and reject the correct instance.
• It occurs since there is more than one choice at
some point.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 75
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Problem of Non-Determinism
• There are three standard solutions to the problem of
non-determinism:
– Backup: Whenever we come to a choice point, we could
put a marker to mark where we were in the input, and
what state the automaton was in. Then if it turns out that
we took the wrong choice, we could back up and try
another path.
– Look-ahead: We could look ahead in the input to help us
decide which path to take.
– Parallelism: Whenever we come to a choice point, we
could look at every alternative path in parallel.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 76
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Backup Approach
• It suggests that we should make choices that might lead
to deadends, knowing that we can always return to the
unexplored alternatives.
• There are two keys to this approach:
– we need to remember all the alternatives for each
choice point, and
– we need to store sufﬁcient information about each
alternative so that we can return to it when necessary.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 77
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

State Transition Table

• There are two changes to the transition table that drives it.
1. To represent nodes that have outgoing ϵ-transitions, we add a new
ϵ-column to the transition table.
2. The second addition is needed to account for multiple transitions to
different nodes from the same input symbol. (Each cell entry consist
of a list of destination nodes rather than a single node)

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 78
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

ND Recognize
• It is an algorithm for using a NFSA to recognize an input
string.
• ND-RECOGNIZE uses the variable agenda to keep track
of all the currently unexplored choices generated during
the course of processing.
• Each choice (search state) is a tuple consisting of a node
(state) of the machine and a position on the tape.
• The variable current-search-state represents the branch
choice being currently explored.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 79
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 80
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Progress of ND RECOGNIZE

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 81
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Recognition as Search
• ND-RECOGNIZE accomplishes the task of
recognizing strings by systematically exploring all
the possible paths through a machine.
• If this exploration yields a path ending in an accept
state, it accepts the string, otherwise it rejects it.
• This systematic exploration is made possible by
the agenda mechanism
– on each iteration selects a partial path to explore and
– keeps track of any remaining unexplored partial paths.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 82
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

State-Space Search Algorithms

• Algorithms such as ND-RECOGNIZE, which

operate by systematically searching for solutions,
are known as state-space search algorithms.
• In such algorithms, the problem deﬁnition
creates a space of possible solutions; the goal is
to explore this space, returning an answer when
one is found or rejecting the input when the space
has been exhaustively explored.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 83
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

State-Space Search Algorithms

• In ND-RECOGNIZE, search states consist of pairings
of machine-states with positions on the input tape.
• The state-space consists of all the pairings of
machine-state and tape positions that are possible
given the machine in question.
• The goal of the search is to navigate through this
space from one state to another looking for a pairing
of an accept state with an end of tape position.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 84
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

State-Space Search Algorithms

• Effectiveness of the program depends on

– order in which the states in the space are
considered.
• A poor ordering of states may lead to the
examination of a large number of unfruitful states
before a successful solution is discovered.
• Unfortunately, it is typically not possible to tell a
good choice from a bad one.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 85
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

State-Space Search Algorithms

• The ordering of states in ND-RECOGNIZE is

unspeciﬁed.
• The unexplored states are added to the agenda as
they are created and the function NEXT returns
an unexplored state from the agenda when asked.
• How should the function NEXT be deﬁned?

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 86
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

State-Space Search : DFS

• Consider an ordering strategy where the states that are

considered next are the most recently created ones.
• Such a policy can be implemented by placing newly created
states at the front of the agenda and having NEXT return the
state at the front of the agenda when called.
• Thus the agenda is implemented by a stack.
• This is commonly referred to as a depth-ﬁrst search(DFS) or
Last In First Out (LIFO) strategy.
• Such a strategy dives into the search space following newly
developed leads as they are generated.
• It will only return to consider earlier options when progress
along a current lead has been blocked.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 87
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

State-Space Search: DFS

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 88
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

DFS : Drawback

• Under certain circumstances they can enter an

inﬁnite loop.
• This is possible either if the search space
happens to be set up in such a way that a search-
state can be accidentally re-visited, or if there are
an inﬁnite number of search states.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 89
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

BFS Strategy
• The second way to order the states in the search
space is to consider states in the Breadth-ﬁrst order
in which they are created.
• Such a policy can be implemented by placing
newly created states at the back of the agenda and
still have NEXT return the state at the front of the
agenda.
• Thus the agenda is implemented via a queue.
• This is commonly referred to as a breadth-ﬁrst
search(BFS) or First In First Out (FIFO) strategy.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 90
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

BFS

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 91
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

BFS - Drawback

• If the state-space is even moderately large, the

search may require an impractically large amount
of memory.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 92
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

State-Space Search Algorithms

• For small problems, either depth-first or breadth-
first search strategies may be adequate, although
depth-first is normally preferred for its more
efficient use of memory.
• For larger problems, more complex search
techniques such as dynamic programming must
be used.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 93
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Relating Deterministic and Non-

Deterministic Automata
• It may seem that allowing NFSAs to have non-
deterministic features like ϵ-transitions would make them
more powerful than DFSAs.
• In fact this is not the case; for any NFSA, there is an
exactly equivalent DFSA.
• In fact there is a simple algorithm for converting an
NFSA to an equivalent DFSA, although the number of
states in this equivalent deterministic automaton may be
much larger.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 94
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

NFSA to an equivalent DFSA

• The algorithm for converting a NFSA to a DFSA

is like this parallel algorithm; we build an
automaton that has a deterministic path for every
path our parallel recognizer might have followed
in the search space.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 95
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Module 2
Lecture 5
• Finite state morphological parsing
• Finite state transducers(FST)

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 96
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Finite-State Morphological Parsing

● Our goal will be to take input forms like those

in first columns and produce output forms like
those in second column shown below:

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 97
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Finite-State Morphological Parsing

● Morphological Features specify additional information about
the stem.
● For example the feature :
○ +N means that the word is a noun;
○ +Sg means it is singular,
○ +Pl that it is plural.

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 98
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Components needed to build a morphological

parser
● Lexicon: the list of stems and affixes, together with basic
information about them (whether a stem is a Noun stem or a
Verb stem, etc.).

● Morphotactics: the model of morpheme ordering that explains

which classes of morphemes can follow other classes of
morphemes inside a word.

● Orthographic rules: The spelling rules used to model the

changes that occur in a word, usually when two morphemes
combine (e.g., the y → ie )

St. Francis Institute of Technology NLP

Department of Computer Engineering Ms. Pradnya Sawant 99
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

A very simple finite-state model for English

nominal inflection

St. Francis Institute of Technology NLP 10

Department of Computer Engineering Ms. Pradnya Sawant 0
Example
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

FSA Above

● The lexicon also includes irregular noun forms that

don’t take -s, both singular irreg-sg-noun (goose,
mouse) and plural irreg-pl-noun (geese, mice).
● The FSA above assumes that the lexicon includes
regular nouns (reg-noun) that take the regular -s plural
(e.g., cat, dog, bag etc.).
● Here we ignored the fact that the plural of words like
fox have an inserted e: foxes.

St. Francis Institute of Technology NLP 10

A Model for English Verbal Inﬂection

St. Francis Institute of Technology NLP 10

Department of Computer Engineering Ms. Pradnya Sawant 3
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

FSA Above

● This lexicon has three stem classes :

○ (reg-verb-stem, irreg-verb-stem, and irreg-past-verb-form),
● Four more afﬁx classes
○ (-ed past, -ed participle, -ing participle, and third singular -s)

St. Francis Institute of Technology NLP 10

English Derivational Morphology

● English derivational morphology is

signiﬁcantly more complex than English
inﬂectional morphology, and so automata
for modeling English derivation tend to be
quite complex.

St. Francis Institute of Technology NLP 10

Morphotactic of English Adjectives

● FSA will recognize almost all the adjectives

Example: big, bigger, biggest,
happy, happier, happiest, happily
red, redder, reddest
unhappy, unhappier, unhappiest, unhappily
real, unreal, really
clear, clearer, clearest, clearly, unclear, unclearly
● It will also recognize ungrammatical forms like unbig, unfast,
oranger, or smally
St. Francis Institute of Technology NLP 10
Department of Computer Engineering Ms. Pradnya Sawant 6
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

FSA for English Nominal and Verbal Derivational

Morphology

St. Francis Institute of Technology NLP 10

FSA for Morphological Recognition

● We can now use these FSAs to determine
whether an input string of letters makes up a
legitimate English word or not. We do this by
expanding each arc (e.g., the reg-noun-stem
arc) with all the morphemes that make up the
set of reg-noun-stem.
● The resulting FSA can then be deﬁned at the
level of the individual letter.
● FSA will not give the lemma of the word.
Hence we use Finite State Transducers(FST) to
do the same.
St. Francis Institute of Technology NLP 10
Department of Computer Engineering Ms. Pradnya Sawant 8
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

FSA for Morphological Recognition

St. Francis Institute of Technology NLP 10

Finite-State Transducers
● FST is a type of ﬁnite automaton which maps between two sets
of symbols.
● In FST , each arc is labeled by an input and output string,
separated by a colon.
● An FST deﬁnes a relation between sets of strings.
● An FST is as a machine that reads one string and generates
another.

St. Francis Institute of Technology NLP 11

Department of Computer Engineering Ms. Pradnya Sawant 0
FST for finding lemma of the word
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Application of FST

● FST as recognizer: a transducer that takes a pair of

strings as input and outputs accept if the string-pair is
in the string-pair language, and reject if it is not.
● FST as generator: a machine that outputs pairs of
strings of the language. Thus the output is a yes or no,
and a pair of output strings.
● FST as translator: a machine that reads a string and
outputs another string
● FST as set relater: a machine that computes relations
between sets.

St. Francis Institute of Technology NLP 11

An FST can be formally deﬁned with 7 parameters:

St. Francis Institute of Technology NLP 11

Regular Relations
FSTs are closed under union operation. It has two additional
closure properties that turn out to be extremely useful:
● Inversion : The inversion of a transducer T (T−1) simply
switches the input and output labels. Thus if T maps from
the input alphabet I to the output alphabet O, T−1 maps
from O to I.
● Composition: If T1 is a transducer from I1 to O1 and T2 a
transducer from O1 to O2, then T1 ◦T2 maps from I1 to O2.

St. Francis Institute of Technology NLP 11

Module 2
Lecture 6
• Finite state transducers(FST)

St. Francis Institute of Technology NLP 11

Sequential Transducers and Determinism

● Transducers may be nondeterministic (a given

input may translate to many possible output
symbols).
● Thus using general FSTs requires the kinds of
search algorithms, making FSTs quite slow in the
general case.
● This suggests to convert a NDFST to a
deterministic one.
● Not all ﬁnite-state transducers can be
determinized.

St. Francis Institute of Technology NLP 11

Sequential Transducers
● Sequential transducers are a subtype of transducers
that are deterministic on their input.
● At any state of a sequential transducer, each given
symbol of the input alphabet Σ can label at most one
transition out of that state.

St. Francis Institute of Technology NLP 11

Sequential Transducers
● Sequential transducers can have epsilon symbols in
the output string, but not on the input.
● Sequential transducers are not necessarily sequential
on their output.
● Thus the inverse of a sequential transducer may not
be sequential.
• One generalization of sequential transducers is the
subsequential transducer SUBSEQUENTIAL which
generates an additional output string at the final states,
concatenating it onto the output produced so far.

St. Francis Institute of Technology NLP 11

Subsequential Transducers

● Both sequential and subsequential

transducers cannot handle ambiguity,
since they transduce each input string to
exactly one possible output string.
● Since ambiguity is a crucial property of
natural language, it will be useful to have
an extension of subsequential transducers
that can deal with ambiguity.

St. Francis Institute of Technology NLP 11

Subsequential Transducers
● One such generalization of subsequential transducers
is the p-subsequential transducer.
● A p-subsequential transducer allows p final output
strings to be associated with each final state.
● They can thus handle a finite amount of ambiguity,
which is useful for many NLP tasks.

An example of a 2-subsequential FST

St. Francis Institute of Technology NLP 12
Department of Computer Engineering Ms. Pradnya Sawant 0
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

FSTs for Morphological Parsing

● Given the input cats, for instance, we’d like to output
cat +N +Pl, telling us that cat is a plural noun.
● In FST morphology we represent a word as a
correspondence between a lexical level and surface
level
○ lexical level : represents a concatenation of
morphemes that make up a word
○ surface level : represents concatenation of letters
which make up the actual spelling of the word.

St. Francis Institute of Technology NLP 12

FSTs for Morphological Parsing

● It is convenient to view an FST as having 2 tapes.

● Upper or lexical tape, is composed of characters from
one alphabet Σ.
● Lower or surface tape, is composed of characters from
another alphabet ∆.

St. Francis Institute of Technology NLP 12

FSTs for Morphological Parsing

● When an FSA accepts a language stated over a
ﬁnite alphabet of single symbols, such as the
alphabet of our sheep language:
Σ = {b, a, !}
● an FST deﬁned this way accepts a language
stated over pairs of symbols, as in:
Σ′ = {a : a, b : b, ! : !, a : !, a : ϵ , ϵ : !}

St. Francis Institute of Technology NLP 12

FSTs for Morphological Parsing

● In two-level morphology, the pairs of symbols in Σ′
are also called feasible pairs.
● a : b implies symbol ‘a’ from one tape is mapped to
the symbol ‘b’ on the other tape.
● a : ϵ means that an a on the upper tape will correspond
to nothing on the lower tape.
● Since it’s most common for symbols to map to
themselves, like a : a default pairs, we just refer to
them by the single letter a.

St. Francis Institute of Technology NLP 12

FSTs for Morphological Parsing

● Now we will build an FST morphological
parser out of our earlier FSAs

St. Francis Institute of Technology NLP 12

FSTs for Morphological Parsing

● The symbol ˆ indicates a morpheme
boundary.
● The symbol # indicates a word boundary.
● The morphological features map to the
empty string ϵ or the boundary symbols
since there is no segment corresponding to
them on the output tape.

St. Francis Institute of Technology NLP 12

FSTs for Morphological Parsing

● Irregular plurals are dealt by allowing the lexicon to
also have two levels.
● E.g. geese maps to lexical goose, the new lexical entry
will be “g:g o:e o:e s:s e:e”.
● Thus the resulting transducer, will map plural nouns
into the stem plus the morphological marker +Pl, and
singular nouns into the stem plus the morphological
marker +Sg.

St. Francis Institute of Technology NLP 12

FSTs for Morphological Parsing

Thus a surface cats will map to cat +N +Pl. This can

be viewed in feasible-pair format as follows:
c:c a:a t:t +N:ϵ +Pl:ˆs#
St. Francis Institute of Technology NLP 12
Department of Computer Engineering Ms. Pradnya Sawant 8
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

FSTs for Morphological Parsing

● Since output symbols include boundary
markers and the lower labels do not correspond
exactly to the surface level, we refer to tapes
with boundary markers as intermediate tapes.

St. Francis Institute of Technology NLP 12

Transducers and Orthographic Rules

• Just concatenating the morphemes won’t work for
cases where there is a spelling change
• In English, we need to deal with the fact that English
often requires spelling changes at morpheme
boundaries by introducing spelling rules (or
orthographic rules).
• In general, rules can be implemented as a transducer

St. Francis Institute of Technology NLP 13

Department of Computer Engineering Ms. Pradnya Sawant 0
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Some spelling rules:

• These spelling changes can be considered taking as

input a simple concatenation of morphemes and
producing as output a slightly-modiﬁed (correctly-
spelled) concatenation of morphemes.

St. Francis Institute of Technology NLP 13

Schematic form of three levels

St. Francis Institute of Technology NLP 13

Example : E-insertion rule

• Here’s a formalization of the rule:

A rule of the form a →b/c_ d means “rewrite a as b

when it occurs between c and d”.
It means “insert an e after a morpheme-final x, s, or z,
and before the morpheme s”.

St. Francis Institute of Technology NLP 13

Transducer for the E-insertion rule

•q0 : default pair
•q1 : z ,s, or x
•q2 : z^ ,s^, or x^
•q3 : inserting e
•q4 : inserting s
•q0 : word boundary
and accept
•q5 : reject

St. Francis Institute of Technology NLP 13

Department of Computer Engineering Ms. Pradnya Sawant 4
Transducer for the E-insertion rule
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Module 2
Lecture 7
• Combining FST Lexicon and Rules
• Lexicon free FST : Porter Stemmer algorithm

St. Francis Institute of Technology NLP 13

Combining FST Lexicon and Rules

Architecture of a two-level morphology system

St. Francis Institute of Technology NLP 13

Architecture of a two-level morphology

system
The cascade has two transducers in series:
1. Transducer mapping from the lexical to the
intermediate levels
2. Collection of parallel transducers mapping from the
intermediate to the surface level.
The cascade can be run top down to generate a
string and bottom up to parse it.

St. Francis Institute of Technology NLP 13

A trace of the system accepting the mapping

from fox + N +Pl to foxes

St. Francis Institute of Technology NLP 13

Ambiguity
• Parsing can be slightly more complicated
than generation, because of the problem of
ambiguity.
• For example, foxes can also be a verb
• How are we to know which one is the
proper parse?
• Disambiguating will require some external
evidence such as the surrounding words.

St. Francis Institute of Technology NLP 14

Ambiguity
• Noun : I saw two foxes yesterday
• Verb : That trickster foxes me every time!.
• Barring such external evidence, the best our
transducer can do is just enumerate the possible
choices
• We can transduce foxˆs# into both
• fox +V +3SG
• fox +N +PL

St. Francis Institute of Technology NLP 14

Local Ambiguity
• Imagine parsing the input verb assess.
• After seeing ass, our E-insertion transducer may
propose that the e that follows is inserted by the
spelling rule
• It is not until we don’t see the # after asses, but
rather run into another s, that we realize we have
gone down an incorrect path.
• Because of this non-determinism, FST-parsing
algorithms need to incorporate some sort of
search algorithm.

St. Francis Institute of Technology NLP 14

Combining FST Lexicon and Rules

• Transducers in parallel can be combined by automaton
intersection.
• The automaton intersection algorithm just takes the Cartesian
product of the states i.e. for each state qi in machine 1 and state qj
in machine 2, we create a new state qi j . Then for any input
symbol a, if machine 1 would transition to state qn and machine 2
would transition to state qm, we transition to state qnm.
• This is done by intersection (∧) and composition (◦) process.

St. Francis Institute of Technology NLP 14

Lexicon-Free FSTs: The Porter Stemmer

• There are simpler algorithms that don’t

require the large on-line lexicon.
• These are used especially in Information
Retrieval (IR) tasks like web search.

St. Francis Institute of Technology NLP 14

Porter (1980) algorithm

• One of the most widely used such stemming

algorithms is the simple and efﬁcient Porter
(1980) algorithm,
• The algorithm contains a series of rules like these:
• ATIONAL → ATE (e.g., relational → relate)
• ING → ϵ if stem contains vowels (e.g.
motoring → motor)
• SSES → SS (e.g., grasses → grass)

St. Francis Institute of Technology NLP 14

Porter Algorithm Errors

St. Francis Institute of Technology NLP 14

Module 2
Lecture 7
• N-gram language model
• Bigram
• Trigram

St. Francis Institute of Technology NLP 14

N-grams

• This portion takes up the idea of word prediction.

• What word, for example, is likely to follow:
• Please turn your homework . . .
• a very likely word is in, or possibly over, but
probably not the.
• This idea of word prediction with probabilistic
models called N-gram models, which predict the
next word from the previous N−1 words.

St. Francis Institute of Technology NLP 14

Simple (Unsmoothed)N-grams
● Our goal is to compute the probability of a word w
given some history h : P(w|h)
● Suppose h is “its water is so transparent that” and we
want to know the probability :
P(the|its water is so transparent that)
● One way is to estimate it from relative frequency
counts.
● P(the|its water is so transparent that) =

St. Francis Institute of Technology NLP 14

Simple N-grams
• It turns out that even the web isn’t big enough to give us good
estimates.
• This is because language is creative : new sentences are created
all the time
• Even simple extensions of a sentence may have counts of zero
on the web.
“ Ram is a nice person”
• To compute the joint probability of an entire sequence of
words, there is lot to estimate!
• The intuition of the N-gram model is that instead of computing
the probability of a word given its entire history, we will
approximate history to last few words.

St. Francis Institute of Technology NLP 15

Bigram model
● The bigram model uses only the conditional probability of the
preceding word P(wn|wn−1).
● In other words, instead of computing P(the|water is so
transparent that) we approximate it with the probability
P(the|that)
● When we use a bigram model we make the following
approximation:
P(wn|wn−1)
● This assumption that depends only on the previous word is
called a Markov assumption.
● We can generalize the bigram to
○ trigram (which looks two words into the past)
○ N-gram (which looks N−1 words into the past).

St. Francis Institute of Technology NLP 15

N-gram
● The general equation for this N-gram approximation to the
conditional probability of the next word in a sequence is:

● Given the bigram assumption, we can compute the probability

of a complete word sequence as follows

St. Francis Institute of Technology NLP 15

How do we estimate these bigram or N-gram

probabilities?
● The simplest and most intuitive way is Maximum Likelihood
Estimation, or MLE.
● This is done by taking counts from a corpus, and normalizing
them so they lie between 0 and 1.
● To compute the count of the bigram C(xy) and normalize by the
sum of all the bigrams that share the same ﬁrst word x:

● We can simplify this equation, since the sum of all bigram

counts that start with a given word wn−1 must be equal to the
unigram count for that word wn−1 :

St. Francis Institute of Technology NLP 15

N-gram Computation
● For the general case of MLE N-gram parameter estimation:

● This estimates the N-gram probability by dividing observed

frequency of a sequence by observed frequency of a preﬁx.
● This ratio is called a relative frequency.

St. Francis Institute of Technology NLP 15

Example
● <s> marks beginning of the sentence
● </s> marks end of the sentence
<s> I am Sam </s>
<s> Sam I am </s>
<s> I do not like ham </s>
List and compute bi-gram probabilities for all symbols.

St. Francis Institute of Technology NLP 15

Example
<s> I am Sam </s>
<s> Sam I am</s>
<s> I do not like ham </s>
(<s> , I)
(I, am)
(am, Sam)
(Sam,</s>)
(<s> , Sam)
(Sam, I)
(am,</s>)
(I, do)
(do, not)
(not, like)
(like, ham)
(ham,</s>)
St. Francis Institute of Technology NLP 15
Department of Computer Engineering Ms. Pradnya Sawant 6
<s> I am Sam </s>
<s> Sam I am </s>
<s> I do not like ham </s>
P(<s> , I)=P(I | <s>)=2/3=1
P(I, am) =P(am | I)=2/3
P(am, Sam) =P(Sam | am)=1/2=1
P(Sam, </s>) =P(<\s> | Sam)=1/2
P(<s>,Sam)=P(Sam | <s>)=1/3
P(Sam, I)= P(I | Sam) =1/2
P(am, <\s>) P(<\s> | am)= 1/2
P(I, do)=P(do | I) =1/3
P(do, not)=P(not | do) = 1/1
P(not, like) =P(like | not)= 1/1
P(like, ham) = P(ham | like)= 1/1
P(ham,<\s>) =P(<\s> | ham)= 1/1
Problem
<s> She is honest <\s>
<s> She is friendly <\s>
<s> She has a friendly pet <\s>

List all the possible bigrams. Compute conditional

probabilities and predict the next word for the word
“friendly”
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Module 2
Lecture 8
• N-gram Sensitivity to the Training Corpus;
Unknown Words: Open versus closed vocabulary
tasks.
• Evaluating N-grams: Perplexity; Smoothing:
Laplace Smoothing, Good-Turing Discounting
St. Francis Institute of Technology NLP 16
Department of Computer Engineering Ms. Pradnya Sawant 0
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Training and Test Sets

● The probabilities of an N-gram model come
from the corpus it is trained on.
● In general, the parameters of a statistical
model are trained on some set of data called
training set and then we apply the models to
some new data in some task called test set
and see how well they work.

St. Francis Institute of Technology NLP 16

Training and Test Sets

● In addition to training and test sets, some-times we
need an extra source of data to augment the
training set. Such extra data is called a held-out
set.
● The held-out corpus is then used to set some
parameters.
● Then we would deﬁnitely need a fresh test set
which is truly unseen. In such cases, we call the
initial test set the development test set or, devset.
● In practice, we often just divide our data into 80%
training, 10% development, and10% test.

St. Francis Institute of Technology NLP 16

N-gram Sensitivity to Training Corpus

The N-gram model is very dependent on the
●
training corpus.
How should we deal with this problem
● Use a training corpus that looks like our test
corpus.
● E.g. To build N-grams for text prediction in SMS,
we need a training corpus of SMS data

St. Francis Institute of Technology NLP 16

Unknown Words
● The closed vocabulary task thus assumes
there are no unknown words.
● Generally, the number of unseen words
grows constantly.
● We call these unseen events : unknown
words, or out of vocabulary (OOV) words.
● The percentage of OOV words that appear
in the test set is called the OOV rate.

St. Francis Institute of Technology NLP 16

Open Vocabulary System

● An open vocabulary system is one model that deals with
unknown words in the test set by adding a pseudo-word
called <UNK>.
● We can train the probabilities of the unknown word model
<UNK> as follows:
1. Choose a vocabulary (word list) which is ﬁxed in advance.
2. Convert in the training set any word that is not in this set
(any OOV word) to the unknown word token <UNK> in a text
normalization step.
3. Estimate the probabilities for <UNK> from its counts just
like any other regular word in the training set.

St. Francis Institute of Technology NLP 16

Evaluating N-grams
● The best way to evaluate the performance of a language
model is to embed it in an application and measure the
total performance of the application. Such end-to-end
evaluation is called extrinsic evaluation also called in vivo
evaluation
● Unfortunately, end-to-end evaluation is often very
expensive; a large speech recognition test set, may takes
hours or even days.
● An intrinsic evaluation metric is one which measures the
quality of a model independent of any application.

St. Francis Institute of Technology NLP 16

Perplexity
● Perplexity is the most common intrinsic evaluation metric
for N-gram language models.
● The intuition of perplexity is that given two probabilistic
models, the better model is the one that has a tighter ﬁt
to the test data
● Perplexity ( PP for short) of a language model on a test set
is a function of the probability that the language model
assigns to that test set.
● For a test set W = w1w2 . . .wN, the perplexity is the
probability of the test set, normalized by the number of
words:

St. Francis Institute of Technology NLP 16

Perplexity
● We can use chain rule to expand the probability of W

● If we use a bigram model,

● Because of the inverse in the equation, the higher the

conditional probability of the word sequence, the lower the
perplexity.
● Thus minimizing perplexity is equivalent to maximizing
the test set probability according to the language model.
St. Francis Institute of Technology NLP 16
Department of Computer Engineering Ms. Pradnya Sawant 8
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Smoothing
● This is the problem of sparse data caused by the fact that
MLE was based on a set of training data.
● Some perfectly acceptable English word sequences are
bound to be missing from it.
● Thus we have a very large number of cases of putative
“zero probability N-grams”
● MLE method produces poor estimates when the counts are
non-zero but still small.
● Thus in order to evaluate our language models, we need to
modify the MLE method
● Assign some non-zero probability to any N-gram.

St. Francis Institute of Technology NLP 16

Department of Computer Engineering Ms. Pradnya Sawant 9
Problems with MLE
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Laplace Smoothing
● One simple way to do smoothing might be just to take our
matrix of bigram counts, before we normalize them into
probabilities, and add one to all the counts.
● This algorithm is called Laplace smoothing, or Laplace’s
Law.

St. Francis Institute of Technology NLP 17

Laplace Smoothing
● Let’s start with the application of Laplace smoothing to
unigram probabilities.
● Unsmoothed MLE probability of the word wi is its count ci
normalized by the total number of word tokens N:

St. Francis Institute of Technology NLP 17

Laplace Smoothing
● Laplace smoothing merely adds one to each count
● Since there are V words in the vocabulary,

● For bigrams,

St. Francis Institute of Technology NLP 17

Department of Computer Engineering Ms. Pradnya Sawant 3
Example using MLE
Example - Training set:
["I like coding", “Prakriti likes mathematics”, “She likes coding”].
Find the probability of “I like mathematics”.
• We insert a start token, <S> and end token, <\S> at the start and end
of a sentence respectively.
P(“I like mathematics”)
= P( I | <S>) * P( like | I) * P( mathematics | like) * P(<\S> |
mathematics)
= (count(<S>I) / count(<S>)) * (count(I like) / count(I)) * (count(like
mathematics) / count(like)) * (count(mathematics <\S>) / count(<\S>))
= (1/3) * (1/1) * (0/1) * (1/3)
=0
Using Laplace smoothing
["I like coding", “Prakriti likes mathematics”, “She likes coding”].
• Here, we simply add 1 to all the counts of words so that we never
incur 0 value.
PLaplace(wi | w(i-1)) = (count(wi w(i-1)) +1 ) / (count(w(i-1)) + V)
Where V= total words in the training set, 9 in our example.

So, P(“I like mathematics”)

= P( I | <S>)*P( like | I)*P( mathematics | like)*P(<\S> | mathematics)
= ((1+1) / (3+9)) * ((1+1) / (1+9)) * ((0+1) / (1+9)) * ((1+1) /
(3+9))
= 1 / 1800
Good-Turing Discounting

The Good-Turing intuition is to use the frequency of

singletons as a re-estimate of the frequency of zero-count
bigrams.
Good-Turing Discounting
Good-Turing Discounting
Good-Turing Discounting
Example
Example
Suppose we are fishing in a lake with 8 species (bass, carp,
catfish, eel, perch, salmon, trout, whitefish)
• we have seen 6 species with the following counts: 10 carp, 3
perch, 2 whitefish, 1 trout, 1 salmon, and 1 eel
• What is the probability that the next fish we catch will be a
new species, i.e., one that had a zero frequency in our
training set, i.e., in this case either a catfish or a bass?
• The MLE count c of bass or catfish is 0.
• Using Good Turing:
Example
Sample Questions

183
184
18. What is Laplace smoothing or add one smoothing
19. Explain spelling correction using N-gram.
20. Explain good Turing discounting

Exercise on steeming by porter stemmer, n-gram, k-gram, Laplace smoothing,

good turing, FSA, FST

185
The material in this presentation belongs to St. Francis Institute of Technology and is solely for educational purposes. Distribution and modifications of the content is prohibited.

Thank you …

St. Francis Institute of Technology NLP 18

Department of Computer Engineering Ms. Pradnya Sawant 6

Morphological Models in NLP Syllabus
No ratings yet
Morphological Models in NLP Syllabus
71 pages
Word Level Analysis and Morphology
No ratings yet
Word Level Analysis and Morphology
54 pages
Understanding Morphology in NLP
No ratings yet
Understanding Morphology in NLP
88 pages
Origins and Challenges of NLP
No ratings yet
Origins and Challenges of NLP
106 pages
NLP Morphology: Tokenization & Analysis
No ratings yet
NLP Morphology: Tokenization & Analysis
9 pages
NLP Tokenization and Morphology Guide
No ratings yet
NLP Tokenization and Morphology Guide
134 pages
Natural Language Processing Overview
No ratings yet
Natural Language Processing Overview
43 pages
Understanding Natural Language Processing
No ratings yet
Understanding Natural Language Processing
101 pages
Understanding Natural Language Processing
No ratings yet
Understanding Natural Language Processing
136 pages
Understanding Natural Language Processing
No ratings yet
Understanding Natural Language Processing
36 pages
Natural Language Processing
No ratings yet
Natural Language Processing
136 pages
WINSEM2024-25_CSE3015_ETH_AP2024254000308_2025-01-08_Reference-Material-I
No ratings yet
WINSEM2024-25_CSE3015_ETH_AP2024254000308_2025-01-08_Reference-Material-I
101 pages
Kuhlmann - Introduction To Computational Linguistics (Slides) (2015)
100% (1)
Kuhlmann - Introduction To Computational Linguistics (Slides) (2015)
66 pages
Understanding NLP: Word Structure & Challenges
No ratings yet
Understanding NLP: Word Structure & Challenges
56 pages
Understanding Finite State Transducers
No ratings yet
Understanding Finite State Transducers
12 pages
NLP Chapter2 - Word Level Analysis
No ratings yet
NLP Chapter2 - Word Level Analysis
198 pages
Understanding Word and Document Structure
No ratings yet
Understanding Word and Document Structure
52 pages
NLP Unit-1
No ratings yet
NLP Unit-1
135 pages
Lexical Representations in NLP
No ratings yet
Lexical Representations in NLP
36 pages
Lecture 2 - Words and Their Component
No ratings yet
Lecture 2 - Words and Their Component
20 pages
Morphological Analysis in NLP
No ratings yet
Morphological Analysis in NLP
103 pages
Advance Computer Technologies (Online)
No ratings yet
Advance Computer Technologies (Online)
22 pages
NLP Unit1 Notes
No ratings yet
NLP Unit1 Notes
14 pages
Morphological Parsing
No ratings yet
Morphological Parsing
59 pages
Understanding English Morphology and NLP
No ratings yet
Understanding English Morphology and NLP
12 pages
NLP_file
No ratings yet
NLP_file
30 pages
NLP Applications and Components Overview
No ratings yet
NLP Applications and Components Overview
19 pages
Introduction to Natural Language Processing
No ratings yet
Introduction to Natural Language Processing
19 pages
Understanding English Morphology Basics
No ratings yet
Understanding English Morphology Basics
5 pages
NLP Pipeline and Morphology Overview
No ratings yet
NLP Pipeline and Morphology Overview
21 pages
NLP Data Pre-Processing Techniques
No ratings yet
NLP Data Pre-Processing Techniques
43 pages
Text Preprocessing for Information Retrieval
100% (2)
Text Preprocessing for Information Retrieval
16 pages
NLP Text Preprocessing Techniques
No ratings yet
NLP Text Preprocessing Techniques
17 pages
Understanding Word Structure in NLP
No ratings yet
Understanding Word Structure in NLP
136 pages
Understanding Part-of-Speech Tagging
No ratings yet
Understanding Part-of-Speech Tagging
4 pages
Unit 2
No ratings yet
Unit 2
27 pages
Natural Language Processing Course Overview
No ratings yet
Natural Language Processing Course Overview
44 pages
M1.2 Morphology
No ratings yet
M1.2 Morphology
38 pages
NLP Word Structure Analysis Techniques
100% (1)
NLP Word Structure Analysis Techniques
19 pages
Text Processing Techniques in NLP
No ratings yet
Text Processing Techniques in NLP
5 pages
NLPP Lab Manual
No ratings yet
NLPP Lab Manual
30 pages
Unit V Notes
No ratings yet
Unit V Notes
44 pages
UNIT 2 Remaining
No ratings yet
UNIT 2 Remaining
6 pages
Morphological Analysis in NLP
No ratings yet
Morphological Analysis in NLP
47 pages
NLP Unit
No ratings yet
NLP Unit
49 pages
Unit 1 NLP
No ratings yet
Unit 1 NLP
23 pages
NLP Text Preprocessing Techniques
No ratings yet
NLP Text Preprocessing Techniques
27 pages
NLP1
No ratings yet
NLP1
17 pages
Morphology
No ratings yet
Morphology
90 pages
NLP Mid Exam Question Bank 2025-26
No ratings yet
NLP Mid Exam Question Bank 2025-26
54 pages
NLP Word Structure and Analysis Techniques
No ratings yet
NLP Word Structure and Analysis Techniques
250 pages
NLP 02 Text Preprocessing
No ratings yet
NLP 02 Text Preprocessing
31 pages
Text Preprocessing for NLP Explained
No ratings yet
Text Preprocessing for NLP Explained
36 pages
Total
No ratings yet
Total
165 pages
Importance of Morphological Analysis
No ratings yet
Importance of Morphological Analysis
5 pages
NLP Syntax Analysis and POS Tagging
No ratings yet
NLP Syntax Analysis and POS Tagging
186 pages
NLP Syntax and Semantics Overview
No ratings yet
NLP Syntax and Semantics Overview
48 pages
MESBL 401: CNC & 3D Printing Lab Manual
No ratings yet
MESBL 401: CNC & 3D Printing Lab Manual
16 pages
Question Classifier with Tf-Idf and ANN
No ratings yet
Question Classifier with Tf-Idf and ANN
9 pages
NLP Assignment Merged-3
No ratings yet
NLP Assignment Merged-3
20 pages
xPlore Error Management Guide
No ratings yet
xPlore Error Management Guide
390 pages
NLP Overview and Applications in AI
No ratings yet
NLP Overview and Applications in AI
50 pages
Understanding Natural Language Processing
No ratings yet
Understanding Natural Language Processing
2 pages
Introduction to Information Retrieval
No ratings yet
Introduction to Information Retrieval
132 pages
Essential Text Preprocessing Techniques
No ratings yet
Essential Text Preprocessing Techniques
6 pages
NLP Tokenization in English and Hindi
No ratings yet
NLP Tokenization in English and Hindi
57 pages
Meaning of Chesthanu in Hindi
No ratings yet
Meaning of Chesthanu in Hindi
60 pages
NLP Tokenization and Lemmatization Guide
No ratings yet
NLP Tokenization and Lemmatization Guide
38 pages
NLP Preprocessing Techniques for LLMs
No ratings yet
NLP Preprocessing Techniques for LLMs
9 pages
NLP Data Preprocessing Techniques
No ratings yet
NLP Data Preprocessing Techniques
35 pages
Unit 6 Natural Language Processing Questions Answers
No ratings yet
Unit 6 Natural Language Processing Questions Answers
34 pages
Understanding Lemmatization in NLP
No ratings yet
Understanding Lemmatization in NLP
20 pages
NLP - Week 2
No ratings yet
NLP - Week 2
34 pages
NLP Basics: Language Processing with Python
No ratings yet
NLP Basics: Language Processing with Python
121 pages
Understanding the Porter Stemmer
No ratings yet
Understanding the Porter Stemmer
23 pages
Class 10 NLP MCQs and Answers
No ratings yet
Class 10 NLP MCQs and Answers
15 pages
NLP Word Level Analysis: Morphology
No ratings yet
NLP Word Level Analysis: Morphology
82 pages
The Nuts and Bolts of Party Congress Research - Final Version
No ratings yet
The Nuts and Bolts of Party Congress Research - Final Version
23 pages
Understanding Natural Language Processing
No ratings yet
Understanding Natural Language Processing
3 pages
Issues in Intelligent Search Algorithms
No ratings yet
Issues in Intelligent Search Algorithms
8 pages
NLP Exp 2
No ratings yet
NLP Exp 2
3 pages
Understanding NLP: Key Concepts and Challenges
No ratings yet
Understanding NLP: Key Concepts and Challenges
24 pages
Introduction to Natural Language Processing
No ratings yet
Introduction to Natural Language Processing
60 pages
NLP Concepts and Applications for Class 10
No ratings yet
NLP Concepts and Applications for Class 10
9 pages
LexNLP: NLP for Legal Texts
No ratings yet
LexNLP: NLP for Legal Texts
7 pages
Text Preprocessing Steps in NLP
No ratings yet
Text Preprocessing Steps in NLP
8 pages
NLP Applications and Tasks Overview
No ratings yet
NLP Applications and Tasks Overview
57 pages