Taalverwerking 2005/2006  BLOK A
(BLOK B wordt gegeven door dr. Andy Pimentel   andy@science.uva.nl)


Cijfers   practica
 Boeken
 Docenten:
    Khalil Sima'an (blok A)   
Andy Pimentel (blok B)
 0MEDEDELINGEN 

      Maandag 9:00-11:00 (H)          
      Maandag 11:00-13:00 (P)     
Richtlijnen
practicum opgaves


Docenten: Khalil Sima'an (simaan@science.uva.nl)  en Andy Pimentel (andy@science.uva.nl)
Assistent: Koen van de Sande (ksande@science.uva.nl)


Docent

K. Sima'an


  BOEKEN BLOK A

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 (extra lees  materiaal):
 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
    Koen van de Sande (studentassistent)

                     Email opgaves naar     ksande@science.uva.nl

                        De subject van de email schrijf je in de formaat:   
                                  NLP + <naam student> + <opgavenr>
Lees de richtlijnen voor practicum opgaves Blok A




College 1
Inleiding NLP

Lees:
 Practicum 0 (5-12 Sep)
   Een terugblik op simpele waarschijnlijkheden en statistiek:
   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.

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

 Lees
  • Hoofdstuk 5 (t/m section 5.6)
  • Hoofdstuk 6
  • SLIDES
Practicum 1 (12-19 Sep)
  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

 		Spellingscorrectie, Language Models en Markov Modellen (II)

 Lees
  • Hoofdstuk 5 (t/m section 5.6)
  • Hoofdstuk 6
  • SLIDES
   Practicum 2 (19 Sep - 2 Okt Let op: twee weken!!)
    
  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) .  De symbolen w, v en x staan voor woorden uit een eindige vocabulair (formeel ook letters uit een eindige alfabet). (De relatieve frequentie formule is behandeld tijdens het college van maandag 19 sep).
  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).
    1. Extraheert twee tabellen (1) unigrammen (2) bigrammen  met hun frequenties.
      Rapporteer de lijst van de 10 meest frequente bigrammen met hun frequenties
      (Let op: maak gebruik van de programma's uit practicum 1).
    2. Berekent (gebruik makend van de tabellen in onderdeel A) de schatting van de relatieve frequentie schatting van de kans voor ieder *geordend* paar woorden <w_1, w_2> .   In andere woorden:  P(w_1, w_2) .
      Rapporteer de lijst van de 10 meest waarschijnlijke bigrammen met hun waarschijnlijkheden tot 4 cijfers na de comma.
    3. Gegeven de verzamelingen van woorden
      A ={She, daughters, youngest, was, the, of, the, two}
      B = {She, was, the, youngest}
      1. Maak een procedure die alle woord-sequenties genereert uit verzameling A zodat iedere sequentie alle woorden uit A bevat en ieder woord precies 1 keer daarin voorkomt (dus   iedere sequentie heeft precies lengte 8 woorden).
      2. Voeg aan deze procedure een waarchijnlijkheidsberekening voor sequenties volgens het model P(w_2 | w_1) van onderdelen A en B.  Let op, de waarschijnlijkheid van een sequentie/zin is gelijk aan het product van de waarschijnlijkheden van ieder woord gegeven het voorgaande woord: 
        P(w_1, ..., w_n)  = P(START) P(w_1|START) P(w_2|w_1)   ...   P(END | w_n) 
        Laat jouw procedure nu de * twee meest waarschijlijke zinnen* uitrekenen.
        Rapporteer de 2 meest waarschijnlijke zinnen met waarschijnlijkheden tot 4 cijfers na de komma.
      3. Doe hetzelfde voor verzameling B.

Hint: bij de berekening van de twee meest waarschijnlijke zinnen hoef je niet alle zinnen eerst te genereren om vervolgens de 2 meest waarschijnlijke te kiezen:  op ieder moment waarin je een nieuwe zin genereert,  hoef je slechts twee zinnen en twee waarschijnlijkheden te bewaren.

 In te leveren:  de oplossingen voor vraag 1 en de raaportages hierboven in onderdelen A t/m C van vraag 2 plus programma en uitleg over hoe het werkt (zie verder de algemen regels voor practica).
     
 Training-set   AUSTEN TRAIN

Colleges
          4
 
Basis Smoothing Technieken voor N-gram Statistiek
Lees
  • Hoofdstuk 6
  • Hoofdstuk 8 Jurafsky en Martin
  • SLIDES 
  Practicum 3 (2 Oct - 9 Oct)
    
Voor dit practicum hoor je het Austen train van het vorige practicum te gebruiken.
Echter, deze keer gerbuik je maar ongeveer 90% van de zinnen in dit corpus voor
training en 10% reserveer je voor testing in onderdeel (IIII)  hieronder:
  1. 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).
  2. Programmer een ``smoothing" programma op basis van het Good-Turing formule en pas dat toe op de statistieken van het bigram model in onderdeel (I) zodat het model kan omgaan met onbekende bigrammen. Na discounting volgens Good-Turing mag je uitgaan van een uniforme verdeling van de gereserveerde massa (zie slides van het hoorcollege).
  3. Test beide resulterede modellen op de zinnen in het 90% training deel van Austen als volgt:
    •  Rapporteer de percentage zinnen die nul waarschijnlijkheid hebben gekregen volgens ieder van de modellen
    • Rapporteer de totale waarschijnlijkheid van alle zinnen in het *trainingscorpus* (90%) volgens ieder van de modellen. Geef uitleg aan het verschil tussen de drie modellen.
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 gesmooth met deze technieken.


College 5
Part-of-Speech Tagging en Hidden Markov Models (I + II)

Lees
  • SLIDES
  • Hoofdstuk 8 Jurafsky en Martin
Practicum 4+5 (9 Oct - 21 Oct.   Twee Weken Dus!)
Zie ook de pagina van Koen: 
http://student.science.uva.nl/~ksande/practicum4.html

       Dit betreft een standaard stochastische POS tagger:
           Taal-model: conditioneert iedere POS tag op de twee voorgaande
                      Dus  2de orde Markov model op POS tags (tri-grams)
            Lexicale model:  zoals gewonelijk (zie slides)

       Opdrachten:
          - Schrijf de formules voor de tagger op
          - Programmeer de tagger 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)
          - 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 Good-Turing methode
             (vorige practicum) en doe de evaluatie opnieuw m.b.v. Precision en Recall

          Aanwijzingen betreffende de structuur van het programma:
           Om deze modellen te bouwen kan je de twee stappen in twee programma's implementeren
            gebruikmakend van alles wat je opgebouwd hebt in voorgaande practica:
            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
                 E. Maak een gesmoothe versie van de tabellen
            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!!   

College 6 Parsing en Context-Vrije Grammatika (CFG)

Slides

Geen nieuwe opgaves meer!
College 7
 Geen College: werk aan laatste practicum!

Geen nieuwe opgaves meer!





  Mededelingen
Richtlijnen voor practicum opgaves Blok A
 Eventuele bijzonderheden/klachten/complimenten kunt u in uw mail kwijt.
 Aan programmeeropdrachten hoort u in paren  samen te 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>





-----------------------------------------------------------------------------------------
Accuracy/correctheidsmaten voor POS tagging:
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)

---------------------------------------------------------------------------------------------------------------------

  Cijfers van Practica:
        P0 en P1