Laboration 4: Dependensparsning (Nivres "arc-standard" shift-reduce-algoritm) med orakel

Lärandemål som detta avser (citat ur kursplan): redogöra för parsningsproblemet i relation till [...] någon form av dependensgrammatik; implementera i ett imperativt/objektorienterat språk (exempel på) [...] "shift-reduce" [...] samt testa och informellt förklara arbetssättet hos dessa implementationer [...]; dokumentera aktuell kod på ett användbart sätt.

Poäng: Denna lab ger ytterligare övning i transitionssystem och distinktionen deterministisk/icke-deterministisk parsning. Den ger vidare övning i dependensparsning och en introduktion till begreppet orakel, som ger en länk till vidare arbete med statistisk och robust parsning (kursen Tekniker för storskalig parsning). Denna lab. bygger på samma javakod som i Lab. 1 och spinner vidare på temat transitionssystem, backtracking och determinsering av icke-deterministiska system.

Rapportering: Beskriv hur ni har tänkt/gjort. Inkludera relevant källkod i rapporten. Klasser ni skrivit själva skall återges i sin helhet med väl utformade förklarande kommentarer. Testa bra sätt utifrån valt exempel och redogör för utfallet i rapporten. Demonstrera resulterande program för läraren.

Bedömning: Minimal nivå anges nedan.

VG kan ges om uppgiften genomförs särskilt väl eller med ambitioner som visar på särskild insikt.

Uppgiften kan ersättas av en individuellt upplagd jämförbar insats.

Utgångsmaterial

• Kod att börja med: ALSY.tar.gz (samma som i Lab. 1, se instruktioner där), men de två filerna här är ändrade.
• Relevanta overheadbilder: Dependensparsning

Klassen DependencySR ger en implementation av Nivres (2008, s. 521) shift-reduce-transitionssystem "arc-standard" med Kuhlmanns modifikation och utifrån den typ av grammatik som beskrivs i OH-bilderna och med full icke-determinism. Systemet ger typiskt upphov till backtrackingmöjligheter (som systemet i Lab. 1). Kika först på det fördefinierade exemplet i menyn (utifrån grammatiken depgram1.txt).

Uppgifter

Lämplig, frivillig inledande övning: Modifiera DependencySR så att den ger en av grammatik och orakel helt obegränsad implementation av "arc-standard", som alltså är så icke-deterministisk att alla dependensträd kan produceras. (Sätt bara ut defaultetiketter.)

(a) Gör om DependencySR till en OracularDependencySR så att den bygger på ett orakel (Nivre s. 519), snarare än på en grammatik och se till att få det hela att fungera med ett leksaksorakel som du själv skräddarsyr för ett lämpligt exempel (en mening med minst 6 ord) och en "normal" dependensanalys av det. Om fantasin tryter kan ni ta det i Nivre (2008, s. 522). Det är nog lättast att utgå från ett exempel/en grammatik i det icke-deterministiska systemet, och sedan konstruera oraklet för en väg från initialkonfiguration till acceptanskonfiguration.

I befintlig icke-deterministisk implementation används konstruktorn DependencySR(String grammar, String[] words) Du bör ha en konstruktor OracularDependencySR(Oracle oracle, String[] words), där följande gränssnitt visar vad vi kräver av ett orakel.

package se.uu.lingfil.stp.alsy.transit;
public interface Oracle {
    public Transit findTransit(Config config);       
}

Lämplig, frivillig övning: Skriv ett orakel som (utan hänsyn till någon grammatik) bara knyter ihop en godtycklig sekvens av ord med vänsterbågar. Och samma sak, fast med högerbågar. (Olika sätt är möjliga. Hur?)

Minimal (G) nivå är att ni hårdkodar ett eget orakel (som kanske heter MyOracle) och som kan vägleda systemet (deterministiskt) till avsedd analys av det valda exemplet. Ambitionsnivån blir att detta görs ad hoc och leksaksmässigt. Smärre förändringar i andra klasser krävs, t.ex. för att skapa och anropa OracularDependencySR-instanser. Kanske vill ni också ha fler möjligheter att kika på konfigurationernas innehåll.

Annan (kul?) övning (ger plus i kanten vid bedömning): Skriv ett slumporakel som slumpmässigt föreslår en transition som är i enlighet med "arc-standard". (Använd gärna befintlig standardslump från java.util.Random.) Ett slumporakel kan producera vilket projektivt träd som helst, fast slumpmässigt. Testa! Om man har lite tålamod kan man upprepa tills önskat träd erhålles.

Annan VG-idé: Lagra oraklet som en serie av någon typ av påståenden, som kan skrivas ned, hanteras och laddas som en textfil.

Referens

Joakim Nivre (2008) "Algorithms for deterministic incremental dependency parsing" Computational Linguistics, Vol. 34. (Valda delar.)