Title: Theory / Important / CS / Algo / NLP
On every note of this deck, unless a note says otherwise:
Chapter: 2

Name: Eliza
Definition: Simulation of Rogerian psychotherapist by a bot
Page: 2

Name: chatbots
Definition: programs created to interact with user
Page: 2
Context: NLP

Name: text normalization
Definition: Editing a text in order to make it more conveniant to work with
Page: 2
Example: Tokenization
Example2: Lemmatization

Name: Tokenization
Definition: Separating a text into words
Page: 2
Example: I am fan of "New York"
Applied to: I'm fan of New York

Name: Lemmatization
Definition: the task of determining
that two words have the same root, despite their surface differences
Page: 3
Example: Sing sang sung

Name: Stemming
Definition: Stripping suffixes from end of the word to lemmatize it
Page: 3

Name: Sentence segmentation
Definition: breaking up a text into individual sentences, using cues like
periods or exclamation points
Page: 3

Page: 3
Chapter: 2
Name: Edit distance
Definition: Number of edition to transform a text into another one
Metric: yes

Name: Editions
Definition: Insertion/Deletion
Page: 3
Context: Edit distance
Definition2: Substitution
Conjdef: Either

Name: Regexp
Definition: Omitted
Page: 3
Section: 1

Name: Range
Definition: A set of consecutive character
Page: 4
Context: Regexp
Denoted by: x-z

Name: Anchors
Definition: Indicate that the regexp in a particular place in the string.
Page: 4
Context: Regexp
Example: $ ^
Example2: \b

Name: Corpus (Corpora)
Definition: A computer-readable
collection of text or speech
Page: 11
Context: NLP

Name: Utterance
Definition: A spoken correlate of a sentence
Page: 11
Context: NLP
Example: I do uh main- mainly business data processing

Name: Disfluency
Page: 11
Context: NLP
Example: Filler
Example2: Fragment

Name: Filler
Definition: Sounds that are not related to words.
Page: 11
Context: NLP
Example: uh... um...
Name2: Filled pause

Name: Fragment
Definition: A prefix of a word, interupted by the speech process
Page: 11
Context: NLP
Example: main- for mainly

Name: Lemma
Definition: the same stem,
Page: 12
Context: NLP
Definition2: the same major part-of-speech,
Conjdef: having
Definition3: and the same word sense
DefType: a set of lexical forms

Name: A word-form
Definition: the full inflected or derived form of the word
Page: 12
Context: NLP

Name: Type of C
Definition: The number of distinct word in C
Page: 12
Context: C a corpus of text
Notation: [$]\abs{V}[/$]

Name: Tokens of C
Definition: The number of word occurring in C
Page: 12
Context: C a corpus of text
Notation: \(N\)

Name: Herdan's law
Definition: [$]\abs{V}=kN^\beta[/$] with \(0<\beta<1\) depending on genra and corpus size
Page: 12
Variables: C a corpus of text
Context: Corpus of text
Name2: Heap's law

Name: Boldface form
Page: 12
Context: NLP Dictionnary
Name2: Entry

Name: African American Vernacular English
Page: 13
Section: 3
Context: Linguistic
Abbreviation: AAVE

Name: Standard American English
Page: 13
Section: 3
Context: Linguistic
Abbreviation: SAE

Name: Code switching
Definition: Using multiple language in a single sentence
Page: 13
Section: 3
Context: Linguistic

Name: Named entity detection
Definition: the task of detecting names, dates, and
organizations
Page: 16
Section: 4
Context: Linguistic

Name: A clitic
Definition: A part of a word that can’t stand on its own, and can only occur when it is attached to another word.
Page: 16
Section: 4
Context: Linguistic
Example: 're n't
Example2: j' l'
Applied to: English
Applied to2: French

Name: Penn Treebank tokenization standard
Definition: A Tokenization standard
Page: 16
Section: 4
Context: Linguistic

Name: Hanzi
Definition: A chinese character
Page: 16
Section: 4
Context: Linguistic

Name: Morpheme
Definition: A single/minimal unit of meaning
Page: 16, 17
Section: 4
Context: Linguistic
Example: un likely est
Applied to: Unlikeliest

Name: Word segmentation
Definition: Separating a text in a sequence of words
Page: 17
Section: 4.2

Name: A training corpus
Definition: A corpus used to prepare a model
Page: 18
Section: 4.2

Name: A test corpus
Definition: A corpus used to check whether a model is correct
Page: 18
Section: 4.2

Page: 18
Implementation: Take as vocabulary the set of letters.
Replace the most common pair of successive elements, and replace all pairs (a,b) by a new vocabulary ab.
Do it a fixed number of time, as parametrized in the algorithm.
Section: 4.2
Chapter: 2
Name: Byte-pair encoding
Abbreviation: BPE
Intuition: All words will appear multiple time, be detected, and so be in the vocabulary. E.g. "[l,o,w,e,r]" may be replaced by "[low, er]"

Page: 20
Implementation: Given a vocabulary V and a string S
Create a list of elements of vocabulary, whose concatenation is S. Find the longest word in V which is a prefix of S, remove this string from S start and iterate until S is empty.
Section: 4.3
Chapter: 2
Name: Maximum matching algorithm
Abbreviation: MaxMatch

Question: What's the downside of case folding
Answer: we lose the difference between "us" and "US"
Page: 21
Chapter: 2
Section: 4.4

Name: Morphology
Definition: the study of
the way words are built up from morphene
Page: 21
Section: 4.4
Context: Linguistic

Name: Stem
Definition: the central morpheme of a word
Page: 21
Section: 4.4
Context: Linguistic

Name: Porter stemming
Definition: Applying rewriting rule such as Ing → ε, and ational → ate until a fixpoint is reached.
Page: 22
Section: 4.4
Context: Linguistic

Name: Levenshtein distance
Definition: The edit distance where edition, deletion and addition all have a cost of one
Page: 23
Section: 5

Page: 23
Implementation: Let \(D[i,j]\) the cost to transform \(input[1..i]\) into \(output[1..j]\)
For i being 0, it's j's insertions
For j being 0, it's i's deletions
Otherwise it's the minimal of:
* \(D[i-1, j]\) + cost of deletion
* \(D[i, j-1]\) + cost of insertion
* \(D[i-1,j-1]\) if input[i]=output[j] or \(D[i-1,j-1]\) + replacement cost otherwise
Section: 5.1
Chapter: 2
Variables: input
output
strings
Name: Dynamic programming for computing minimum edit distance between two strings