Class notes
Lecture Notes NLP - alles
- Course
- Institution
All NLP lectures summarized. There was no book for this course, so this is all exam material
[Show more]
Seller
Follow
donjaschipper
Content preview
Lecture notes Natural Language ProcessingLecture 1
Why is language special?
- Language emerged in homo sapiens between 30.000–100.000 yrs ago
o Other intelligent species have communication, but language is uniquely human
o Human language conveys an unbounded number of meanings
- Every child can learn any of ~6000 languages that exist today during “critical period”
o Learning “mother tongue” takes no effort at all, compared to second language (SL)
- Transmission of knowledge; writing systems invented ~5.000 yrs ago
Important tools for NLP
- Finite-state automata (FSA)
o An abstract machine that can process sequences of symbols
o Consists of states and transitions
o Reads sequences of symbols, one at a time
o An automaton accepts a sequence of symbols if and only if it stops in one of the
predefined final states after processing the entire sequence
o A finite-state automaton is a five-tuple ⟨ Σ, S , q o , F , δ ⟩ where:
Σ is a set of symbols – alphabet
S is a finite set of states
q 0 is the initial state
F ⊆ S is the set of final states
δ is the transition function
- Regular languages
o If Σ is an alphabet, then:
The empty set Ø (= { }) and {ε} are regular languages (ε is the empty string)
The set {x} is a regular language for every x ∈ Σ
If A and B are regular languages, then so is their union A U B
If A and B are regular languages, then so is their concatenation A • B
If A is a regular language, then so is A* (“Kleene closure”) where
¿ i
A =U i ≥ 0 A and A0 = {ε}, A1 = A, Ai = A • ... • A
Nothing else is a regular language
If A is a regular language, then so is its complement ∑ ¿¿
If A and B are regular languages, then so is their intersection A ∩ B
- Regular expressions
, o Can be used to represent regular languages, or (equivalently) finite-state automata
o A regex is a sequence of characters that defines a search pattern
o Cheat sheet: slide 40/41
Lecture 2
- Phonology - study of phonemes, the basic units of speech sounds, and
phonotactics
- Morphology – study words and the parts from which words are composed,
i.e., morphemes
- Pragmatics – studies the difference between literal and implied meaning.
E.g., “I feel like pizza today.”
FSAs can be used for testing if strings belong to a language or not (classification).
However, many natural language processing tasks require converting one string to another:
For these tasks we need rewrite systems – transducers (FST)
- If a transducer has to look ahead an unbounded distance in
order to correctly generate the output on the first decision –
nondeterministic.
- Unlike FSA, nondeterministic FST cannot always be converted
to a deterministic equivalent!
- A finite-state transducer FST is an FSA that can produce
output strings:
o FST → ⟨ Σ ,O , S , q0 , F , δ ⟩
Σ is a set of input symbols (alphabet)
O is the set of output symbols
S is a set of states
q 0 is the initial state
F ⊆ S is the set of final states
δ is a function form ( Σ ∪ { ε } ) × S into P¿
Example transition rule
o ⟨ ⟨ a , q 0 ⟩ , ⟨ q1 , b ⟩ ⟩
o when reading symbol a in state q0, go into state q1 and write
b
Applications of FST in NLP
1. Tokenization
2. Stemming
3. Lemmatization
4. Morphological processing
- Tokenization
, o Turning a string, document or text into tokens (smaller chunks), e.g., sentences,
words, characters, or subwords. Sometimes also called “segmentation”
o Important first step in preprocessing of text for more complex applications (every
state-of-the-art NLP system uses tokenization to prepare input)
o Rules for tokenization can be created with regex + FST
o Sentence tokenization often based on punctuation.
Does not always work as intended: “Wow!”, said Alice. “Wow! / “, said Alice.
o In English, words are often separated from each other by blanks (whitespace).
But whitespace is not always sufficient for word tokenization: New York ->
New / York, but you want them together.
o Very hard for languages that for example do not have whitespaces like Thai,
Japanese, etc.
o Non-alphabetic languages use logograms (a.k.a. characters, glyphs) that correspond
to words or morphemes
Use a weighted FST
Each path has an
associated cost
Find the path that
minimizes overall cost
Costs can be learned
from data (annotated
corpora)
o Deciding problem: given a model and a
sequence of observations, what is the most likely state sequence in the model that
produces these observations?
Viterbi algorithm provides a method for finding the most optimal path in the
least number of steps
Always choose the shortest path to get somewhere (prune a path if it
has a higher cost than another path that is at the same time but with
a lower cost)
- Inflectional Morphology
o The morphology of a language defines how words are built up from smaller parts.
Morphemes are the smallest units that have some meaning in a language
o There are many productive patterns in language (but also many exceptions). It is
much more efficient in NLP to store these rules than all word forms. Rules are then
used to derive one form from another, or to decompose unknown words.
o Morphological rules are useful if we want to decompose words into subword units (in
for example the stem of the word -> stemming).
- Stemming
o cats = cat + s, walking = walk + ing
o Widely used - Porter algorithm
Based on a series of cascaded rewrite rules implemented as an FST:
ATIONAL→ATE (e.g., relational → relate)
ING→ if and only if stem contains vowel (e.g., motoring → motor, but
not bring → br)
Lexicon-free (no dictionary or vocabulary needs to be used)
- Lemmatization
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller donjaschipper. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $6.18. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
82388 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now