Natuurlijke-taalverwerking 1. Daniël de Kok

Natuurlijke-taalverwerking 1 Daniël de Kok

Natuurlijke-Taalverwerking

Het college Natuurlijke-taalverwerking is een inleiding in de computationele taalkunde en maakt deel uit van het curriculum van Informatiekunde en Kunstmatige Intelligentie. Aan de hand van enige toepassingen leggen we uit wat de belangrijkste onderzoeksvragen van de computationele taalkunde zijn. Vervolgens richten we ons het ontwikkelen van computationele grammatica’s en op het automatisch verwerken (ontleden) van natuurlijke taal met behulp van zulke grammatica’s.

Vandaag

I

Praktische zaken

I

College-overzicht

I

Wat is natuurlijke-taalverwerking?

I

Context-vrije grammatica’s

Overzicht

Praktisch

Natuurlijke-taalverwerking


Studiehandleiding

I I

I I

Zie http://www.let.rug.nl/~dekok/ntv/ Links naar de syllabus, aanvullende literatuur, college-aantekeningen, practicumopdrachten Practicum start komende week Beoordeling I I I I

I

Practicum (5 opdrachten, 50%) Tentamen (50%) Beide onderdelen moeten voldoende zijn Te laat ingeleverd is niet ingeleverd

Eregalerij

Praktisch

I

Hoorcolleges: Daniël de Kok ([email protected])

I

Practica: Jelmer van der Linde

I

Mail gerust voor praktische vragen, vragen over de opdrachten gelieve stellen tijdens de practica

I

Practica vinden plaats in 12 0119 op maandag 11-13.

Literatuur

I

Syllabus Natuurlijke-taalverwerking 1 (pdf, pdf, 2 blz/A4).

I

Learn Prolog Now! (Blackburn, Bos, Striegnitz), Chapters 7 and 8 (Definite Clause Grammars)

I

Chart Generation, Martin Kay, Proceedings of the 34th annual meeting on Association for Computational Linguistics

I

Statistical Methods and Linguistics, Steven Abney, In: Judith Klavans and Philip Resnik (eds.), The Balancing Act: Combining Symbolic and Statistical Approaches to Language. The MIT Press, Cambridge, MA. 1996

Optionele literatuur

I

Prolog and Natural Language Processing, Pereira en Shieber, 1988/2002

I

An Introduction to Unification-Based Approaches to Grammar, Shieber, 1986/1988/2003

Plagiaat

I

Tijdens de werkcolleges van dit vak is overleg met medestudenten toegestaan.

I

Maar: ingeleverde opdrachten moeten altijd en volledig eigen werk zijn.

I

Eigen inspanning is leerzamer.

I

Uiteraard wordt gebruik van standaardpredikaten in Prolog aangemoedigd!

Wat leer je dit college?

I

Hoe je een computergrammatica schrijft.

I

Hoe je met behulp van een grammatica zinnen kunt ontleden.

I

Hoe je met een grammaticale analyse feiten uit zinnen kunt extraheren.

I

Hoe je met een grammaticale analyse vragen kunt beantwoorden.

I

Hoe je met een grammatica zinnen kunt bouwen (genereren).

I

Hoe je een grammaticale analyse of gegenereerde zin kunt beoordelen.

College-overzicht

I

Week 1: Context-vrije grammatica’s

I

Week 2: Definite Clause Grammar (DCG)

I

Week 3: Unificatie-grammatica I

I

Week 4: Unificatie-grammatica II

I

Week 5: Automatisch Ontleden

I

Week 6: Parse selectie

I

Week 7: Generatie

Overzicht

Praktisch



Wat is natuurlijke-taalverwerking?

Het ontwikkelen van programma’s en toepassingen waarbij kennis van de structuur en de betekenis van natuurlijke taal een rol speelt.

Voorbeelden

I

spellingscontrole;

I

grammatica-correctie (identificeren en corrigeren van grammaticale fouten in tekst);

I

automatisch vertalen;

I

automatisch vragen beantwoorden;

I

automatisch e-mail beantwoorden;

I

informatie extractie;

I

zoeken

Spellingscontrole

Taalrader

Automatisch vragen beantwoorden

Automatisch vragen beantwoorden (2 voor 12)

I

Wie is de voorzitter van het Europese Parlement?

I

Klaus H¨ ansch , voorzitter van het Europese Parlement , drukte het iets sterker uit...

I

Ook de voorzitter van de CDA-delegatie in het Europese Parlement , oud-minister Maij ....

Automatisch vragen beantwoorden

I

Wanneer vond de Duitse hereniging plaats?

I

Sinds de Duitse hereniging in oktober 1990 is de sterfte in Oost-Duitsland sterk toegenomen.

I

Al in 1962 voorspelde hij de Duitse hereniging en het uiteenvallen van de Sovjet-Unie.

Zoeken

I

Tekst tokiniseren.

I

Opsporen lemma’s, andere schrijfwijzen.

I

Herkennen van bijvoorbeeld namen en vaste uitdrukkingen.

I

Afhandelen spelfouten in de tekst of query.

Makkelijk en moeilijk

Makkelijk? Spellingcontrole Voice Response systemen Rapporten genereren uit tabellen Vertaalhulp Domein-specifieke dialoogsystemen Web-search

Moeilijk? Grammaticale controle Volledige spraakherkenning Samenvatten van artikelen Automatisch vertalen Turing-test Vragen beantwoorden

Zelfs makkelijke toepassingen zijn moeilijk

I

Spellingcorrectie: I

I

Lijkt gemakkelijk: markeer alle woorden die niet in het woordenboek staan, Maar is moeilijk: geen woordenboek is volledig, iedere dag worden nieuwe woorden ge¨ıntroduceerd.

Omvang van een woordenboek

I

125K (Groene Boekje)

I

500K+ (van Dale). Soms ontbreekt 40% van de woordtypes in een tekst in het woordenboek.

I

I I

Tokens: aantal woorden in een tekst, Types: aantal verschillende woorden in een tekst.

Meer cijfers

I

Kun je een goede woordenlijst afleiden uit een corpus (verzameling tekst):

1 krant 1 maand 1 jaar TwNC DCOI

tokens 36K 1556K 18M 488M 54M

types 8K 96K 410K 3340K 1220K

3000000 2000000

woordenboek

1000000 0 0e+00

1e+08

2e+08

3e+08

corpus

4e+08

5e+08

Spellingcorrectie 6= opzoeken

I

Syntactische context: I I

Wat gebeurd/t er? Wat is er gebeurd/t?

Spellingcorrectie 6= opzoeken

I

Deze jongen vind(t) je aardig. I I

I

(Daarom wil hij een date.) (Daarom wil jij een date.)

Wel/geen spelfout hangt af van betekenis.

Brandt Corstius

I

De derde wet van de computer-taalkunde: I

I

Na een bepaalde tijd, bv 1 jaar, werken, krijg je 80% goede resultaten. Elke halvering van de gap tussen 80 en 100% betekent een vermenigvuldiging van de aanvankelijk bestede tijd met een vaste factor die groter is dan 1.

Wat je ook doet, de semantiek gooit roet.

Bijdrage vakgebieden

I

Computationele taalkunde: formalismes voor computationele grammatica’s, corpustaalkunde, computationele semantiek.

I

Informatica: ontleedalgoritmen, finite state technieken, (logische) programmeertalen.

I

Kunstmatige intelligentie: toepassing in robots, machine learning technieken.

I

Informatiekunde: slim coderen van data, integratie in toepassingen, interfaces.

Overzicht

Praktisch



Grammatica

I

Veel toepassingen vereisen een kennis van de structuur van zinnen (zinsbouw, grammatica): I I I I

Grammatica-correctie (jan word ziek); automatisch vertalen; generatie van zinnen; ....

Grammatica

I

Een taal is een (oneindige) verzameling zinnen;

I

zinnen zijn reeksen woorden;

I

niet alle reeksen woorden zijn zinnen; een grammatica beschrijft:

I

I I

Welke reeksen woorden goede zinnen vormen; en wat de structuur van die reeksen is.

Herschijfregels a→b a kan herschreven worden als b Bijvoorbeeld: I

NP → Det N

I

N → eendje

I

Det →

Conventies: I

Terminals met kleine letters;

I

non-terminals met hoofdletters;

I

voor de lege string;

Herschrijfregels (2)

I

Een grammatica bestaat uit een verzameling van herschrijfregels.

I

Een reeks van terminals (een zin) behoort tot de taal van een grammatica als het S symbool te herschrijven is tot die reeks van terminals.


Verzameling van regels met de volgende vorm: V→w I

V is één non-terminal symbool;

I

w is reeks van terminal, non-terminal of epsilon symbolen.

Zoek de CFG regels

1. A → 2. a B → c 3. A B → C 4. C → D E 5. D → d

Een CFG voor an b n , n > 0

S→aSb S→ab

Ontleding aaabbb

S aSb aaSbb aaabbb

S1

a

S2

a

b

S3

a

b

b

Bedenk een grammatica voor an b n , n ≥ 0

Ter inspiratie, de grammatica voor an b n , n > 0: S→aSb S→ab

Een kleine CFG voor het Nederlands

S NP N VP VP

→ → → → →

NP VP Det N AN V V NP

Det Det N N V V

→ → → → → →

een het eendje ei legt loopt

Ontleding het eendje loopt

S NP VP Det N VP het N VP het eendje VP het eendje V het eendje loopt

S1

NP2

VP5

Det3

N4

V6

het

eendje

loopt

Welke grammaticaregels zijn gebruikt? S

NP

VP

Det

N

V

het

eendje

legt

NP

Det

N

een

ei

Taal en grammatica

I

Een reeks woorden W wordt herkend door grammatica G , wanneer je, door S te herschrijven, W kunt genereren;

I

alle reeksen die door G worden herkend, vormen de taal van G.

All-and-only principe

I

All: Een grammatica moet alle zinnen van een taal kunnen herkennen,

I

Only: Een grammatica mag geen ongrammaticale zinnen herkennen.

I

Bijna alle grammatica’s voldoen niet aan All;

I

veel grammatica’s voldoen niet aan Only.

Ambigu¨ıteit

I

Wij willen dat ons dochtertje in vrede opgroeit

I

Wij hopen dat het dochtertje van Maxima slaapt

I

VP → VP PP

I

N → N PP

I

Bij ambigu¨ıteit is er meer dan één analyse van een zin.

Ambigu¨ıteit

CP

Compl

NP

dat

VP

PP

V

ons dochtertje opgroeit in vrede

Ambigu¨ıteit

CP

NP

Compl

dat

Det

het

VP

N

N

V

PP

dochtertje van Maxima

slaapt

Ambigu¨ıteit groeit exponentieel

I

Wanneer deel 1 van een zin 5 mogelijke analyses heeft, en deel 2 3, heeft de hele zin 3×5 analyses

I

Grammatica’s die duizenden analyses aan een zin van 20 woorden toekennen zijn niet ongewoon.

Natuurlijke-taalverwerking 1. Daniël de Kok

Recommend Documents