CL HC 2 - 04/05/21 - Introductie, Edit Distance
Deel 1: Introductie
Doel en inhoud
- Methoden en technieken rond taal en spraak die van belang zijn voor het ontwikkelen van
dergelijke applicaties. Hypothesen en kansen spelen daarbij een belangrijke rol
- In het practicum worden deze technieken in de praktijk gebracht
Computational linguistics & AI
- The idea of computers that process human language is as old as the idea of computers
themselves
- AI: the ability to achieve human-level performance in cognitive tasks, su cient to fool an
interrogator: laatste betekent dat je kan overtuigen dat je een mens bent -> heel belangrijk
- Turing test (1950): je slaagt voor de test als je als interrogator niet weet of er een mens of
machine antwoord geeft
- Natural Language Processing was considered a major factor in achieving AI
ELIZA
Dialog voerder: concept is heel simpel
1. Read a collection of templates
2. Greet the user
3. Conduct a series of exchanges
1. Reading a line of input and breaking it into words
2. Matching the input against a template
3. Creating a response
Template: systeem gaat op zoek naar een bepaald stukje tekst, en geeft een bepaalde variabele
terug, vaak meerdere omdat het systeem meestal niet hetzelfde antwoord geeft op twee keer
dezelfde vraag -> om realistischer over te komen.
- Voorbeeld: als je vraagt ‘Are you …?’, krijg je terug ‘Would you prefer if I were not …?’
- Dus op ‘Are you', reactie met ‘I were’
Het systeem probeert zijn gebreken te verbergen, met bijvoorbeeld: ‘We were discussing you, not
me!’ Of ‘Have you asked anyone else?’. Het probeert het gesprek los te voeren van het gesprek
over hoe de machine werkt.
Met het woordje ‘how’ kan het systeem niet heel veel. Dus dan komen er omslachtige en vage
antwoorden uit.
Templates
- Templates match part of a user’s sentence
- Example: User: ‘Men are all alike.’ -> Eliza: ’In what way?’ -> template is alike, response =
‘How?’, ’In what way?’ en nog 2 andere opties
- Watson & language: understanding questions posed in everyday language, hele ingewikkelde
architectuur en toegang tot enorme informatie data bases: DeepQA
Deel 2: Edit Distance
Kwanti ceren in hoeverre een woord lijkt op het getypte: tellen hoeveel acties je
nodig hebt om het woord te krijgen wat je bedoelde. Je gebruikt insertie,
deletion of substitutie, en transpositie (twee letters omgedraaid, wordt niet gebruikt
in het algoritme). Vraag is of substitutie 1 of 2 stappen duurt. Basisidee: in stapjes
kwanti ceren hoe je van het ene woord naar het andere komt: algoritme gebruiken.
- Je wil zo e ciënt mogelijk werken.
- To be able to compute the edit distance of 2 words at all, we need to ensure there is a
nite number of steps.
- To calculate: gerichte cyclische graaf, set of nodes and arrows (arcs).
Page 1 of 29
fi fifi ffi ffi
, - Horizontal arcs correspond to deletions, vertical arcs correspond
to insertions and diagonal arcs correspond to substitutions (a
letter can be substituted for itself)
- Vraag die je jezelf gaat stellen: je kijkt wat de kortste route is naar
het einddoel.
- VB: calculate how far away fry is from fyre. In other
words: the minimum edit distance = minimum
number of operations it would take to convert
one word into another.
- Kan op meerdere manieren, meerdere routes beschikbaar.
Horizontaal het getypte woord uitzetten, en verticaal het
gewenste woord.
In de cel helemaal rechts boven heb je niks, linksonder heb je
‘fyrefry’ (het maximale).
- The graph is acyclic = for any given node, it is impossible to
return to that node by following the arcs
- Uitrekenen: alle 3 de handelingen kosten 1, en substitutie met
hetzelfde karakter is 0.
E ciënte manier om tot de juiste oplossing te komen:
dynamic programming = a program designed to make use of
results earlier: tussenkosten gebruiken. En overal in de cellen
invullen. Dikgedrukt is het minimale pad; minimale kosten is
dus 2 in dit geval.
Page 2 of 29
ffi
, CL HC 3 - 06/05/21 - N-grams
N-grams
- Sequenties van n woorden. Je kan een zin opdelen in n-grams
- Unigrammen zijn de individuele woorden, bigrammen zijn combinaties van 2 woorden,
trilrammen zijn combinaties van 3 woorden
- Aantal mogelijke n-grams neemt zeer sterk toe met lengte
- Unigram < bigram < trigram < quadrigram …
- Het aantal n-grams is van belang bij de keuze
- Bij V = {a, b, c} zijn de unigrams (3): a, b, c, de bigrams (3*3=9): ab, ac, ba, bc, ca, cb, aa, bb,
cc, de trigrams (3*3*3=27): aaa, aab, aac, baa, bab, … en de quadrigrams (3*3*3*3=81)
- Als je de n heel groot maakt ontstaat er een gat tussen het aantal n-grams die je kan maken en
het aantal dat je daadwerkelijk ziet
Google Books Ngram Viewer
- Meten van cultural trends uit alle boeken geanalyseerd door Google. Je kan zeggen hoe
populair iets was in de geschiedenis, kijkend naar hoe vaak de n-grams voorkomen in teksten.
- Bijvoorbeeld: AI begon vanaf 1965 op te komen, dus je ziet vanaf dan een trend, vanaf 1985
komt machine learning op
- Wat het systeem doet is niets anders dan tellen/turven
- Het nut van voorspelling: ook op je telefoon zijn woordsuggesties hierop gebaseerd
Taalmodel
- Hoe kom je tot de volgende waarschijnlijkheid? Testcorpus moet wel vergelijkbaar zijn met het
volgende woord. Kansberekenen: hoe waarschijnlijk is het dat een bepaald woord volgt? Het
statistisch model dat dat kan noemen we een taalmodel.
- P(independent|serve as the): count(serve as the independent)/count(serve as the)
- Meten: 794/1830 = 0.43 kans dat ‘independent’ volgt na ‘serve as the’
- Alle mogelijke opties tellen op tot 1, namelijk 100%
- Voorbeeld: bigrams ab, ab en ac. P(y|x) = P(b|a) = C(ab)/C(a) = 2/3. P(c|a) = 1/3. Samen 1.
Bigram kansen: deel aantal geteld door totale aantal mogelijkheden. De
waarschijnlijkheid van een zin kan je berekenen door de zin op te delen
in bigrammen, en de kansen te vermenigvuldigen.
Dus bv als bigrammen met ‘i’ als eerste woord 2533 keer voorkomen en
het bigram ‘i want’ 827 keer: bigram kans = 827/2533 = 0.33
Al zijn ze ruw, N-gram waarschijnlijkheden beschrijven interessante taal
en cultuur feiten. Staat los van grammatica. Tellen van data.
Shannon’s Method
- Het toekennen van waarschijnlijkheid aan een zin is aardig maar niet heel verhelderend. Je kan
nieuwe zinnen maken.
- Kies een willekeurig biagram, op basis van de kans erop, kies vervolgens een willekeurig
bigram waarvan het eerste woord het zelfde is als het laatste van het eerste bigram, en zo
verder tot je een zin kan vormen.
- Als je een grote data base hebt van Obama’s speeches kan je dus een nieuwe speech vormen
zoals hij het ook zou doen (grote kans lig). Of nieuwe teksten van Shakespeare.
- Quadiagrammen beschrijven het meest: wat er gegenereerd wordt ziet er Shakespeareaans uit
omdat het bijna Shakespeare is; hoe groter, hoe beter (want steeds meer citaten van hem)
Evaluatie
- Hoe weten we dat onze modellen goed zijn?
- Shannon’s procedure geeft een intuïtie
- Trainen, testen en evalueren
- Standaard methode: train de parameters van het model op een trainings set en kijk hoe het
model zich gedraagt voor nieuwe gegevens (test set afkomstig van de bron)
- Maar kost veel tijd. Een snellere methode is perplexiteit gebruiken. Geeft weer hoeveel
opvolgers elk woord gemiddeld heeft. Een perfect model is een model dat altijd weet welke
woorden volgen > in de realiteit niet haalbaar, maar hier zou geen onzekerheid in zitten. Andere
Page 3 of 29
Deel 1: Introductie
Doel en inhoud
- Methoden en technieken rond taal en spraak die van belang zijn voor het ontwikkelen van
dergelijke applicaties. Hypothesen en kansen spelen daarbij een belangrijke rol
- In het practicum worden deze technieken in de praktijk gebracht
Computational linguistics & AI
- The idea of computers that process human language is as old as the idea of computers
themselves
- AI: the ability to achieve human-level performance in cognitive tasks, su cient to fool an
interrogator: laatste betekent dat je kan overtuigen dat je een mens bent -> heel belangrijk
- Turing test (1950): je slaagt voor de test als je als interrogator niet weet of er een mens of
machine antwoord geeft
- Natural Language Processing was considered a major factor in achieving AI
ELIZA
Dialog voerder: concept is heel simpel
1. Read a collection of templates
2. Greet the user
3. Conduct a series of exchanges
1. Reading a line of input and breaking it into words
2. Matching the input against a template
3. Creating a response
Template: systeem gaat op zoek naar een bepaald stukje tekst, en geeft een bepaalde variabele
terug, vaak meerdere omdat het systeem meestal niet hetzelfde antwoord geeft op twee keer
dezelfde vraag -> om realistischer over te komen.
- Voorbeeld: als je vraagt ‘Are you …?’, krijg je terug ‘Would you prefer if I were not …?’
- Dus op ‘Are you', reactie met ‘I were’
Het systeem probeert zijn gebreken te verbergen, met bijvoorbeeld: ‘We were discussing you, not
me!’ Of ‘Have you asked anyone else?’. Het probeert het gesprek los te voeren van het gesprek
over hoe de machine werkt.
Met het woordje ‘how’ kan het systeem niet heel veel. Dus dan komen er omslachtige en vage
antwoorden uit.
Templates
- Templates match part of a user’s sentence
- Example: User: ‘Men are all alike.’ -> Eliza: ’In what way?’ -> template is alike, response =
‘How?’, ’In what way?’ en nog 2 andere opties
- Watson & language: understanding questions posed in everyday language, hele ingewikkelde
architectuur en toegang tot enorme informatie data bases: DeepQA
Deel 2: Edit Distance
Kwanti ceren in hoeverre een woord lijkt op het getypte: tellen hoeveel acties je
nodig hebt om het woord te krijgen wat je bedoelde. Je gebruikt insertie,
deletion of substitutie, en transpositie (twee letters omgedraaid, wordt niet gebruikt
in het algoritme). Vraag is of substitutie 1 of 2 stappen duurt. Basisidee: in stapjes
kwanti ceren hoe je van het ene woord naar het andere komt: algoritme gebruiken.
- Je wil zo e ciënt mogelijk werken.
- To be able to compute the edit distance of 2 words at all, we need to ensure there is a
nite number of steps.
- To calculate: gerichte cyclische graaf, set of nodes and arrows (arcs).
Page 1 of 29
fi fifi ffi ffi
, - Horizontal arcs correspond to deletions, vertical arcs correspond
to insertions and diagonal arcs correspond to substitutions (a
letter can be substituted for itself)
- Vraag die je jezelf gaat stellen: je kijkt wat de kortste route is naar
het einddoel.
- VB: calculate how far away fry is from fyre. In other
words: the minimum edit distance = minimum
number of operations it would take to convert
one word into another.
- Kan op meerdere manieren, meerdere routes beschikbaar.
Horizontaal het getypte woord uitzetten, en verticaal het
gewenste woord.
In de cel helemaal rechts boven heb je niks, linksonder heb je
‘fyrefry’ (het maximale).
- The graph is acyclic = for any given node, it is impossible to
return to that node by following the arcs
- Uitrekenen: alle 3 de handelingen kosten 1, en substitutie met
hetzelfde karakter is 0.
E ciënte manier om tot de juiste oplossing te komen:
dynamic programming = a program designed to make use of
results earlier: tussenkosten gebruiken. En overal in de cellen
invullen. Dikgedrukt is het minimale pad; minimale kosten is
dus 2 in dit geval.
Page 2 of 29
ffi
, CL HC 3 - 06/05/21 - N-grams
N-grams
- Sequenties van n woorden. Je kan een zin opdelen in n-grams
- Unigrammen zijn de individuele woorden, bigrammen zijn combinaties van 2 woorden,
trilrammen zijn combinaties van 3 woorden
- Aantal mogelijke n-grams neemt zeer sterk toe met lengte
- Unigram < bigram < trigram < quadrigram …
- Het aantal n-grams is van belang bij de keuze
- Bij V = {a, b, c} zijn de unigrams (3): a, b, c, de bigrams (3*3=9): ab, ac, ba, bc, ca, cb, aa, bb,
cc, de trigrams (3*3*3=27): aaa, aab, aac, baa, bab, … en de quadrigrams (3*3*3*3=81)
- Als je de n heel groot maakt ontstaat er een gat tussen het aantal n-grams die je kan maken en
het aantal dat je daadwerkelijk ziet
Google Books Ngram Viewer
- Meten van cultural trends uit alle boeken geanalyseerd door Google. Je kan zeggen hoe
populair iets was in de geschiedenis, kijkend naar hoe vaak de n-grams voorkomen in teksten.
- Bijvoorbeeld: AI begon vanaf 1965 op te komen, dus je ziet vanaf dan een trend, vanaf 1985
komt machine learning op
- Wat het systeem doet is niets anders dan tellen/turven
- Het nut van voorspelling: ook op je telefoon zijn woordsuggesties hierop gebaseerd
Taalmodel
- Hoe kom je tot de volgende waarschijnlijkheid? Testcorpus moet wel vergelijkbaar zijn met het
volgende woord. Kansberekenen: hoe waarschijnlijk is het dat een bepaald woord volgt? Het
statistisch model dat dat kan noemen we een taalmodel.
- P(independent|serve as the): count(serve as the independent)/count(serve as the)
- Meten: 794/1830 = 0.43 kans dat ‘independent’ volgt na ‘serve as the’
- Alle mogelijke opties tellen op tot 1, namelijk 100%
- Voorbeeld: bigrams ab, ab en ac. P(y|x) = P(b|a) = C(ab)/C(a) = 2/3. P(c|a) = 1/3. Samen 1.
Bigram kansen: deel aantal geteld door totale aantal mogelijkheden. De
waarschijnlijkheid van een zin kan je berekenen door de zin op te delen
in bigrammen, en de kansen te vermenigvuldigen.
Dus bv als bigrammen met ‘i’ als eerste woord 2533 keer voorkomen en
het bigram ‘i want’ 827 keer: bigram kans = 827/2533 = 0.33
Al zijn ze ruw, N-gram waarschijnlijkheden beschrijven interessante taal
en cultuur feiten. Staat los van grammatica. Tellen van data.
Shannon’s Method
- Het toekennen van waarschijnlijkheid aan een zin is aardig maar niet heel verhelderend. Je kan
nieuwe zinnen maken.
- Kies een willekeurig biagram, op basis van de kans erop, kies vervolgens een willekeurig
bigram waarvan het eerste woord het zelfde is als het laatste van het eerste bigram, en zo
verder tot je een zin kan vormen.
- Als je een grote data base hebt van Obama’s speeches kan je dus een nieuwe speech vormen
zoals hij het ook zou doen (grote kans lig). Of nieuwe teksten van Shakespeare.
- Quadiagrammen beschrijven het meest: wat er gegenereerd wordt ziet er Shakespeareaans uit
omdat het bijna Shakespeare is; hoe groter, hoe beter (want steeds meer citaten van hem)
Evaluatie
- Hoe weten we dat onze modellen goed zijn?
- Shannon’s procedure geeft een intuïtie
- Trainen, testen en evalueren
- Standaard methode: train de parameters van het model op een trainings set en kijk hoe het
model zich gedraagt voor nieuwe gegevens (test set afkomstig van de bron)
- Maar kost veel tijd. Een snellere methode is perplexiteit gebruiken. Geeft weer hoeveel
opvolgers elk woord gemiddeld heeft. Een perfect model is een model dat altijd weet welke
woorden volgen > in de realiteit niet haalbaar, maar hier zou geen onzekerheid in zitten. Andere
Page 3 of 29
