Taalverwerking en Informatieontsluiting 2004/2005


Links naar: 
  Deel I: blok A (Sima'an)        Deel II: Blok B  (Scha)
Docenten: Remko Scha (scha aapstaart uva punt nl)   en  Khalil Sima'an (simaan aapstart science punt uva punt nl)
Assistent: Wouter Kuijper (wkuiper at science punt uva punt nl)

 Bekijk de  MEDEDELINGEN Blok A 0 (laatste toevoeging: 4 April 2005)  
Alle cijfers (opgaves, tussentoets, eindtoets, eindcijfers) http://cf.hum.uva.nl/computerlinguistiek/TVIO/cijfers/cijfers_tvio05_.xls


  CIJFERS tenatmenMaart2005     CIJFERS praktika  




Deel I: Blok A

Spelregels Practica / Huiswerk Boeken Blok A
Slides Blok A
0MEDEDELINGEN Blok A
Deel II: Blok B  (Scha)



Docent

K. Sima'an


 BOEKEN

We behandelen delen van het volgende boek
(kopieen liggen in de bibliotheek in Euclides: een map met de titels   TVIO,  NTV en NLP)

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

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

 


Beoordeling
Blok A




      Het eindcijfer voor blok A is een gewogengemiddelde van 50% practica en 50% schriftelijk tentamen.
Practicum
Lees de algemene regels alvorens opdrachten in te leveren:
                       
                  
0 Algemene Regels Practica en Huiswerk0

Practicum opgaves inleveren bij studentassistent (Wouter Kuijper): altijd op de vrijdag een week na het desbetreffende college (dus 10 dagen na het college -- behalve wanneer anders is vermeld bij het specifieke practicum).

                    Email opgaves naar     

    wkuijper  aapstart  science.uva.nl
                        De subject van de email schrijf je in de formaat:   
                                  TVIO + <naam student> + <opgavenr>






College 1
 7 Februari
Inleiding

Lees:

Practicum: geen practicum deze week.


College
      2
 14 Februari
Spellingscorrectie, Language Models en Markov Modellen (I)

 Lees

  • Hoofdstuk 5 (t/m section 5.6)
  • Hoofdstuk 6
  • SLIDES
Practicum 1  inleveren op vrijdag 25 Februari
 
1. Leid de volgende beweringen af gebruikmakend slechts van de drie axioma's
    van de waarschijnlijkheidsleer en van verzamelingentheorie:  pdf file van beweringen
    Lever de afleidingen met enige uitleg in.
2.  Schrijf een programma dat als input een natuurlijk getal  n  en een grote text bestand
    (een corpus) inleest. De output moet zijn een tabel van alle sequenties van
    lengte n woorden met het aantal keer (frequentie) dat de sequentie voorkomt in het
    corpus  (let op: de sequentie van n woorden moet letterlijk in het corpus voorkomen).
    Maak gebruik van AUSTEN TRAIN hieronder als invoer corpus voor jouw programma.

    In te leveren:
    A. Voor n=1, n=2 en n=3 lever je in de tabel van de 10 meest voorkomende sequenties.
    B. De som van de frequenties van alle sequenties van lengte n=1, n=2 en n=3.
    C. Programma met uitleg zoals aangegeven in de algemene regels voor practica.

     Training-set   AUSTEN TRAIN

College  3
 21 Februari
Spellingscorrectie, Language Models en Markov Modellen (II)

 Lees

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

Practicum 2 inleveren op vrijdag 4 maart
    
       1. Schrijf  een afleiding van de relatieve frequentie formule voor de estimatie van de volgende
            waarschijnlijkheden:  P(w | v, x) , P(w | v)  en  P(w) .
       2. Schrijf een programma (het liefst in delen die generiek zijn zodat je de onderdelen kan hergebruiken in
               verdere practica)
dat ieder van de volgende onderdelen uitvoert op de training
           coprus (
AUSTEN TRAIN ):
            (Neem aan dat begin en einde van een zin samenvallen met begin en einde van
             alineas: dus voeg een symbool START/END aan het  begin/eind van een alinea
             om zinnige statistiek over zinnen te krijgen)
           A. Extraheert twee tabellen (1) unigrammen (2) bigrammen  met hun frequenties.
                Rapporteer de lijst van de 10 meest frequente bigrammen met hun frequenties.
          B. Berekent (gebruik makend van de tabellen in onderdeel A) de schatting van
                de relatieve frequentie van een bigram: P(w_1, w_2 | w_1).
                Rapporteer de lijst van de 10 meest waarschijnlijke bigrammen met hun
                waarschijnlijkheden tot 4 cijfers na de comma)!!
          C.  Zinnen genereert ``at random" volgens de schattingen van waarschijnlijkheden
                van bigrammen: het programma begint de zin altijd met START en genereert dan
                een woord gegeven START (volgens de kansen), vervolgens weer een woord gegeven
                het eerste woord en zo door tot END wordt gegenereerd, dan stop het programma.
                Rapporteer 3 gegenereerde zinnen.
          In te leveren:  de raaportages hierboven in onderdelen A t/m C plus programma en
          uitleg over hoe het werkt (zie verder de algemen regels voor practica).

     
 
Training-set   AUSTEN TRAIN

College
          4
28 Februari
Basis Smoothing Technieken voor N-gram Statistiek

Lees


  • Hoofdstuk 6
  • Hoofdstuk 8 Jurafsky en Martin
  • SLIDES 

Practicum 3 inleveren op vrijdag 11 maart
      Een programma dat spellingscorrectie doet gebruikmakend van een taalmodel
       over woord-sequenties.

        Hulp programma (mag je gebruiken):
            het volgende programma (shell script)  maakt gebruik van het
ispell programma
            van Linux/Unix om mogelijke correcties van foute woorden  te genereren.

            De input voor dit programma moet zijn de volgende test-text-met-fouten .
            In de output vind je op iedere regel e'e'n van twee mogelijkheden:
                1. een woord: het woord is correct gespelled volgens ispell
                    of
                2. het teken "&" gevolgd door het foute-woord  w, gevolgd door twee getallen
                    waarvan slechts de eerste (getal A) van interesse is, gevolgd door een verzameling
                    voorstellen voor correcties (door ispell gegenereerd) met het teken "/" ertussen
                     (deze verzameling zullen we met C(w) aanduiden hieronder). Getal A geeft aan
                    wat de grootte is van de verzameling C(w).

        Taken:        
             I) Bouw een bigram
taalmodel op  woord niveau (om dit te realiseren mag je gebruik
                  maken van het taal model dat in de voorgaande practicum is gemaakt en getrained
                  op Austen Train).
             II) Transformeer de output van het hulp programma als volgt.
                   Iedere zin begint met START en eindigt met END.
                   Als een woord w een spellingsfout is, dan wordt het vervangen door e'e'n van de
                   mogelijke correctie uit de verzameling C(w) (anders dan blijft het woord zelf).
                   Op deze manier ontstaan er voor iedere zin dat fouten bevat meerdere mogelijke
                    hypotheses voor correctie van deze zin. Laten we deze verzameling van hypotheses
                    aanduiden met H.
             III) Laat het taal model uit onderdeel I los op ieder van de hypotheses gecreerd in
                  onderdeel II (verzameling H) en selecteer per zin e'e'n meest waarschijnlijke hypothese zin
                  (volgens het model in onderdeel I).

         In te leveren: (zie verder de algemene regels)
           - Het programma met duidelijke uitleg over hoe het werkt.
           - Maximum e'e'n A4 pagina met uitleg+ formules over hoe het taalmodel wordt gebruikt
             om III te realiseren (zie de slides van het hoorcollege).
           - Een lijst van paren: foute-woord  en beste-correctie (dat in de meest waarschijnlijke
             hypothese voorkomt -- zoals in onderdeel III).

          


College 5
7 Maart
Part-of-Speech Tagging en Hidden Markov Models (I)

Lees

  • SLIDES
  • Hoofdstuk 8 Jurafsky en Martin
Practicum 4  inleveren op vrijdag 25 maart
    Dit betreft twee POS 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
            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!!

                   - Aanwijzingen voor simplere test:  je mag in de test file alle
                      zinnen
langer dan 15 woorden negeren. Je kan dit beter niet doen op de
                      training set omdat je op deze manier statistiek kwijt raakt.
                  -  Negeer, zowel in training als in test sets, alle paren X/Y waarbij Y geen
                     alfanumerieke sequentie van tekens is of  "." (dus alle POS tags die geen punt
                     zijn en geen alfanumerieke symbolen zijn kan je uit je data weggooien).
                     De "./." is het einde van een zin in dat geval.

           
         In te leveren:
              - Het programma dat de tagger voorstelt en het programma dat de evaluatie van
                de tagger uitvoert. Beide met uitleg zoals aangegeven bij de algemene regels
              - De test text geheel getagged
              - De Precision en Recall van jouw tagger op deze test set


         *TRAINING AND TESTING MATERIAL bij assistent te verkrijgen!!   

         *


          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 6
14 maart
Part-of-Speech Tagging en Hidden Markov Models (II)
Afronding + Context-Vrije Grammatika en parsing
Lees
  • SLIDES
  • Hoofdstuk 8 Jurafsky en Martin

College 7
21 maart
Onderwijsvrije week: voorbereiding tentamens!





  Mededelingen



Algemene regels voor inleveren practicum opdrachten:
Practicum opgaves inleveren bij studentassistent (Wouter Kuijper):
altijd een week na het desbetreffende college (behalve wanneer anders
is vermeld bij het specifieke practicum).


                    Email opgaves naar     

    wkuijper  aapstart  science.uva.nl
                        De subject van de email schrijf je in de formaat:   
                                  TVIO + <naam student> + <opgavenr>


Eventuele bijzonderheden/klachten/complimenten kunt u in uw mail kwijt.
Je mag in paren werken.
Uw uitwerkingen levert u in als  2 afzonderlijke attachments:
 i) Uw programma in de 1e attachment:
      - Als uw programma uit meerdere files bestaat lever dan een .tar.gz  file aan
         voorzien van README file met beschrijving van wat elke file  doet.
      - Al uw broncode (bijvoorkeur in Python, maar Perl of Prolog zijn ook acceptabel)  moet leesbaar en gedocumenteerd zijn.
      - CORPUS FILE NIET BIJSLUITEN!
 ii) Lever als tweede attachment een .txt / .pdf file met daarin:
     - het gebruikelijke: vak, opgavenr., datum, uw naam, student-nummer,
     - uw uitwerkingen, daarin moeten ook de resultaten van uw programma op  een overzichtelijke
       manier zijn opgenomen (voor menselijke consumptie  geschikt gemaakt),
     - een korte beschrijving van hoe uw programma is opgebouwd, welk  algoritme u gebruikt,
        waarom het correct is, waarom het beter is dan  hetgeen op het college is voorgesteld etc.
     - een voorbeeldaanroep, wij stellen voor:  <myprog> -[a|b|c|d|...|help] <filename>



Cijfers  voor
    opgave 1          opgave 2        opgave 3    opgave 4
    Cijfers TENTAMEN Maart 2005