Scribd
Upload
7 views37 pages

Finite State Transducers: Mausam

The document discusses finite state transducers (FSTs) and their applications in morphological parsing and tokenization. It explains key concepts such as lexemes, lemmas, stems, and roots, and highlights the practical uses of morphological analysis in various applications like spelling correction and part-of-speech tagging. Additionally, it covers the Porter Stemmer algorithm and its implementation in natural language processing tasks.

Uploaded by

Jiru Alemayehu
Copyright
© All Rights Reserved
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
7 views37 pages

Finite State Transducers: Mausam

The document discusses finite state transducers (FSTs) and their applications in morphological parsing and tokenization. It explains key concepts such as lexemes, lemmas, stems, and roots, and highlights the practical uses of morphological analysis in various applications like spelling correction and part-of-speech tagging. Additionally, it covers the Porter Stemmer algorithm and its implementation in natural language processing tasks.

Uploaded by

Jiru Alemayehu
Copyright
© All Rights Reserved
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

Finite State Transducers

Morphological Parsing & Tokenization

Mausam

(Based on slides by Jurafsky & Martin,


Julia Hockenmaier)
1/20/2023 2
1/20/2023 3
1/20/2023 4
1/20/2023 5
1/20/2023 6
1/20/2023 7
1/20/2023 8
Lexeme, Lemma, Stem, Root
• A lexeme is a unit of lexical meaning underlying a
set of words that are related through inflection
• A lemma is a word that stands at the head of a
definition in a dictionary.
• A root is the central (free) morpheme to which
other bound morphemes are added to form a word.
• A stem is the portion of strings that are common in
all the inflections of a word.
 reproduce, reproduces and reproducing are forms of the
same lexeme, for which
 reproduce is the lemma.
 reproduc is the stem.
 duce(?) is the root.
9
1/20/2023 10
1/20/2023 11
1/20/2023 12
1/20/2023 13
1/20/2023 14
1/20/2023 15
1/20/2023 16
1/20/2023 17
1/20/2023 18
19
20
21
22
23
24
25
26
27
Practical Uses
• This kind of parsing is normally called
morphological analysis
• Can be
• An important stand-alone component of an
application (spelling correction, information
retrieval, part-of-speech tagging,…)
• Or simply a link in a chain of processing
(machine translation, parsing,…)

28
FST-based Tokenization

1/20/2023 29
Porter Stemmer (1980)
• Common algorithm for stemming English

• Conventions + 5 phases of reductions


 phases applied sequentially
 each phase consists of a set of commands
 sample convention: Of the rules in a compound
command, select the one that applies to the
longest suffix.

30
Porter Stemmer (1980)
• Standard, very popular and usable stemmer (IR,
IE) – identify a word’s stem
• Sequence of cascaded rewrite rules, e.g.
 IZE  ε (e.g. unionize  union)
 CY  T (e.g. frequency  frequent)
 ING  ε , if stem contains vowel (motoring 
motor)
• Can be implemented as a lexicon-free FST
(many implementations available on the web)
• [Link]

31
Eliza

1/20/2023 34
Eliza FST

1/20/2023 35
RelNoun: Nominal Open IE

Constructions

36
Compound Noun Extraction
Baseline
• NIH Director Francis Collins

(Francis Collins, is the Director of, NIH)


• Challenges
 New York Banker Association ORG NAMES

 German Chancellor Angela Merkel DEMONYMS

COMPOUND
 Prime Minister Modi RELATIONAL NOUNS

 GM Vice Chairman Bob Lutz


37
Rule-Based System
• Classifies and filters orgs

• List of demonyms
 appropriate location conversion

• Bootstrap a list of relational noun prefixes


 vice, ex, health, …

38
Summing Up
• Regular expressions and FSAs can represent subsets
of natural language as well as regular languages
 Both representations may be difficult for humans to
use for any real subset of a language
 But quick, powerful and easy to use for small problems

• Finite state transducers and rules are common


ways to incorporate linguistic ideas in NLP for
small applications

• Particularly useful for no data setting


39

You might also like