Natuurlijketaal Verwerking 2004/2005


Boeken
Slides
0MEDEDELINGEN
Dinsdag 11:00-13:00 (H)            REC-I.101

Donderdag 11:00-13:00 (P)      REC-P.127
CIJFERS


Docent: Khalil Sima'an (simaan@science.uva.nl)
Assistent: Jasper Uijlings  (jrruijli@science.uva.nl)



Docent

K. Sima'an


 BOEKEN

We behandelen delen van het volgende boek (kopieen worden gelegd in de bibliotheek in Euclides)

Daniel Jurafsky and  James H. Martin. `"SPEECH and LANGUAGE PROCESSING": An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition. Prentice-Hall, 2000.

Hoofstukken 1, 2,  5, 6 en 8.
     -------------------------------------------------------------------------
Andere boeken: 

 Chris Manning and Hinrich Schütze. "Foundations of Statistical Natural Language Processing", MIT Press.
 Cambridge, MA: May 1999.  (see http://nlp.stanford.edu/fsnlp/ )


Practicum opgaves inleveren bij Jasper Uijlings (studentassistent): altijd een week na het desbetreffende college (behalve wanneer anders is vermeld bij het specifieke practicum).

                    Email opgaves naar  
jrruijli@science.uva.nl

                        De subject van de email schrijf je in de formaat:   
                                  NLP + <naam student> + <opgavenr>





College 1

Inleiding NLP

Lees:

Practicum: geen practicum deze week.



College 2

Reguliere Expressies, FSA's en Reguliere Talen
 
Lees:
  • Hoofdstuk 2 uit het boek van Jurafsky and Martin
  • SLIDES 
Practicum 1
1.  Exercise 2.1  van ``Jurafsky and Martin"
2.  Exercise 2.3 van ``Jurafsky and Martin"  (programmeren!)
3.  Computer oefening: download de volgende text file
    Zoek de  regels in deze file die de volgende pattronen bevatten, gebruik makend van
    reguliere expressies in Perl (of egrep): bewaar de reguliere expressies en vergelijk ze
    met het werk van je medestudenten:
    
      A. Zoek naar het woord "weer" in de text  (dus met white-space eromheen)
      B. Zoek alle patronen die beginnen met "/" en eindigen met "/"
      C. Zoek alle patronen die bevatten het woord "weer"
      D. Zoek alle patronen die getallen bevatten en eindigen met "/"
      E. Zoek alle internet adressen (dus beginnen met "http..." en een adres vormen)
      F. Zoek alle patronen die "telegraaf" gevolgd door "weer" bevat (er kan van alles tussen zitten).


Colleges
      3
     +
     4
(eerste helft)
Spellingscorrectie, Language Models en Markov Modellen

 Lees

  • Hoofdstuk 5 (t/m section 5.6)
  • Hoofdstuk 6
  • SLIDES

Practicum 2+3
    (Inleveren op 6 October 2004:  boete 25% van opdracht-cijfer bij inleveren op 13 October 2004 )
       Uit ``Jurafsky and Martin" 
       1. Exercise 6.1 (pagina 232)  
       2. Exercises  6.3, 6.4 en 6.5 (paginas 232--233)
       3. Maak gebruik van het ispell programma van Unix om een programma te schrijven
            dat  1) ispell gebruikt om mogelijke correcties van foute woorden  te genereren
                   2) een trigram taalmodel op  woord niveau gebruikt om de meest waarschijnlijke
                          correctie te kiezen uit de suggesties die uit ispell ontstaan.

           
Test-set voor deze opdracht is de volgende text: fiftyspellingerrors.html
                             die fouten bevat. Om jouw spellingscorrectie programma te testen,
                             moet je deze text eerst vergelijken met de correcte text
                              correct_fiftyspellingerrors.html. Waar jij verschillen vindt laat je ispell
                             los op het foute gedeelte van de text gevolgd door jouw  correctie-programma.
                             Je zal merken dat niet alle fouten zo gecorrigeerd kunnen worden, probeer
                             uit te leggen waarom dat niet lukt. (Om de taak simpler te maken zou je slechts de
                             eerste 10  spellings-fouten kunnen behandelen).

          
Training-set   AUSTEN TRAIN     (geen copy-right problemen)
          

Colleges
          4
(tweede helft)
       +
       5

Smoothing Technieken voor N-gram Statistiek
 
Lees

  • Hoofdstuk 5 (t/m section 5.6)
  • Hoofdstuk 6
  • SLIDES 
 Vervolg Practicum 2+3 uit ``Jurafsky and Martin"
     (inleveren ook op 6 October 2004:  boete 25% van opdracht-cijfer bij inleveren op 13 October 2004 )
     Exercises:  (slechts een kleine toevoeging op de vorige practicum)
          *  6.1 pagina 232
          *  Programmeer de volgende taken in e'e'n programma.
              -  6.3 pagina 232
              - Voeg een optie toe voor  Add-One smoothing
              - 6.4 pagina 232
              - 6.5 pagina 232
      
       Maak gebruik van de volgende data om je programma te testen:
       maak een vergelijking in exercise 6.4 tussen de AUSTEN TRAIN
       en de TEST.

       Training materiaal voor de N-grammen kan je krijgen hier AUSTEN TRAIN
       Test materiaal hier TEST

College 6
Part-of-Speech Tagging en Hidden Markov Models

Lees

  • SLIDES
  • Hoofdstuk 8 Jurafsky en Martin
Practicum 4  (inleveren op 4 November 2004 - uiterste datum voor inlevering opgave)

        Dit betreft twee taggers:
           Tagger A: een standaard stochastische POS tagger:
                  1. taal-model  conditioneert iedere POS tag op de twee voorgaande
                      Dus  2de orde Markov model op POS tags (tri-grams)

                  2. lexicale model zoals gewonelijk (zie slides)
           Tagger B:  een tweede POS tagger waarin
                 1. taal-model zoals in tagger A
                 2. het lexicale model: ieder woord conditioneert op eigen POS tag

                     en tevens op het voorgaande woord!!

         Opdrachten:
          - Schrijf de formules voor beide taggers op
          - Programmeer slechts e'e'n van deze taggers in twee stappen:
             stap 1: een trainings-stap waarin trainings data wordt gebruikt om de waarschijnlijkheden
                         te schatten
             stap 2: een toepassing stap waarin een zin als input wordt gegeven aan jouw tagger,
                        en de output is de meest waarschijnlijke tag sequentie gegeven de zin, dus
                            argmax_tags P(tags | input zin)
          - Definitie:
             De correctheidsmaat van een tagger op een text (test-set) van lengte N woorden (dus over de gehele
             corpus -- niet per zin):

                                                          (aantal woorden correct ge-tagged door tagger)
                          Recall(tagger) = ----------------------------------------------------------------------------------------
                                                                                 N
                                                             (aantal woorden correct ge-tagged door tagger) 
                         
Precision(tagger) = ----------------------------------------------------------------------------------------
                                                              (aantal woorden die een tag hebben gekregen van de tagger)

          - Test jouw tagger op de test-set zinnen en doe de evaluatie van de output ten opzichte van
             de correcte test-set en rapporteer Precision en Recall
          - Smooth beide, het lexicale en het taal model, in de tagger met de (Add 1) methode
             en doe de evaluatie opnieuw m.b.v. Precision&Recall


          Hints:
           Om deze modellen te bouwen kan je de twee stappen in twee programma's implementeren:
            Stap 1 (programma 1)
                 A. tabellen van frequencies van de benodigde N-grammen uit de training materiaal
                      extraheren en in geschikte tabellen plaatsen.
                 B. Deze tabellen gerbuik je om de waarschijnlijkheden te schatten middels relatieve frequencies
                      om op deze manier nieuwe tabellen van waarschijlijkheden te verkrijgen
                 C. Schrijf de tabbelen uit in een speciale file (zegmaar genaamd TABFILE)
                 D. Vergeet de extra begin-of-sentence en end-of-sentence symbolen niet in de waarschijnlijkheden.
            Stap 2 (programma 2)
                  A. Leest de file  TABFILE met de tabellen in en bewaart die in memory
                  B. Leest de test zinnen in (t/m end of file) en output voor iedere zin de meest waarschijnlijke tagging.
                      
(Let op: dit programma kan hetzelfde zijn voor beide taggers - met een klein beetje creativiteit
                         wel te verstaan!!)

            Stap 3 (programma 3)
                  Een programma dat een test-file (die getagged is) inleest, de output van jouw tagger voor dezelfde
                  test-zinnen ook inleest, en de precision & recall berekent. Let op de extra begin/end-of-sentence
                  symbolen worden niet meegerekend in de precision en recall!!
           
 
          EXTRA!!!  (Is niet vereist)!!
          Gebruik deze modellen om de spellingscorrectie van opdracht 3 opnieuw te de doen:
          voor een input zin dat spellingsfouten bevat gebruik je ispell om suggesties van
          correcte-zinnen te maken. Vervolgens kies je nu de meest waarschijnlijke correcte-zin    
          waarbij je de waarschijnlijkheid van een zin berekent aan de hand van  
                       
                                   P(zin) = som_over_alle_postag_sequenties  P(zin,  postag_sequentie)
             
          Data voor training kan worden verkregen bij de assistent.

College 7
Een overzicht van de voorgaande colleges en een kort overzicht van gerelateerde vakken.

Slides





  Mededelingen