ISBI Laboration 2: Informationssökning med stemming

Syfte

Syftet med laborationen är att se hur man med en relativt enkel språkteknologisk metod, här stemming, kan förbättra resultaten i ett språkteknologiskt system. Er uppgift i denna labb är att skriva stemmingregler till en enkel sökmotor för att på sätt öka täckningen, helst utan sänkning i precision.

Ni bör arbeta i grupper om 3. Denna laboration finns även i en engelskspråkig version.

Först

Ögna igenom hela labbpeket innan du börjar, i synnerhet det sista avsnittet, Redovising.

Bakgrund

Sökmotorer är ett informationshanteringsverktyg som många av oss använder dagligen, och som de flesta som varit ute på Internet stött på. De flesta sökmotorer är idag anpassade för de stora språken med engelska i spetsen, i den mån de är anpassade för språk alls och inte bara betraktar texten som arbiträra strängar av tecken. Detta förhållningssätt kan vara smått förödande för ett språk som svenska som inte bara har en rik morfologi, utan även är väldigt produktivt när det gäller att bilda nya ordformer genom sammansättning, avledning etc.
    Ett av de problem som en rik morfologi kan leda till i en traditionell sökmotor är en sänkning i täckning, dvs att man inte hittar alla relevanta dokument. Detta kan t.ex. bero på att man söker efter 'cykel' men inte får träff på 'cyklar'. Ett annat sådant är att man kan få en opålitlig precision på grund av att sökmotorn inte "förstår" att olika böjningsformer refererar till samma "koncept". Om man inte behandlar 'katt', 'katten', 'katternas' etc som (i grund och botten) samma ord så kommer ett dokument som använder olika böjningsformer att rankas lägre än ett som genomgående använder en och samma form, trots att de kanske talar om katter i samma utsträckning (ett liknande, men mycket svårare, problem är synonymer).
    Stemming är en relativt billig metod (både i termer av utveckling och krävd datorkraft) som kan användas för att försöka komma till rätta med de två ovanstående problemen. I denna labb skall vi främst titta på det första. Stemming kan också, till skillnad från lemmatisering, användas för att överbrygga böjningsparadigmer och även på så sätt öka täckningen. Ett exempel på detta skulle kunna vara att föra ner orden 'cykel', 'cyklar' och 'cyklande' till den gemensamma stammen 'cykl'. Dock måste man se upp så att stemmingreglerna inte övergenererar, dvs producerar allt för generella stammar. Detta leder ofta till en sänkning av precisionen (t.ex. genom att 'tomte' och 'tomat' båda stemmas ner till 'tom').
    Den stemmer som används i den här labben är skriven i PHP och är skriven för att vara generell och för att göra allt i realtid vid varje sökning. Detta enligt mottot "smidighet före hastighet". Använd därför inte denna som ett mått på "kostnaden" att införa en stemmer i en sökmotor. Den som är intresserad kan läsa en artikel om en undersökning vi gjort för att försöka utröna vilken inverkan användning av stemming i en sökmotor kan ge för svenska:
Improving Precision in Information Retrieval for Swedish using Stemming. J. Carlberger, H. Dalianis, M. Hassel, O. Knutsson 2001. In the Proceedings of NODALIDA'01 - 13th Nordic Conference on Computational Linguistics, May 21-22 2001, Uppsala, Sweden.
Den intresserade kan också titta på Snowball, ett stränghanteringsspråk designat just för att skapa stemmingalgoritmer för informationssökning, där det också finns en stemmer för bl.a. svenska.

Uppgiftsbeskrivning

Din uppgift i denna labb är som sagt att skriva stemmingregler för att öka täckningen vid sökning av dokument. För detta syfte har vi tagit fram en enkel sökmotor: Stemming Lab. I denna kan du enligt en ofta använd tre-stegs-modell skriva stemmingregler för att stemma ner de eftersökta orden till lämpliga stammar. Sex dokument med sökorden i filnamnet finns att hitta till var och en av följande sökfrågor:

1	bil
2	bil hund olycka
3	dator fråga peka
4	cykling löpa simma
5	springer tid
6	springer tidning

Du kan i gränssnittet givetvis skriva in vilka sökfrågor du vill, och även använda olika former av ovanstående ord då du söker ut dokument, men det är ovanstående sökfrågor din regelsamling skall hitta de rätta dokumenten för och det är med ovanstående sökfrågor din regeluppsättning kommer att kontrolleras.

För att komma igång

Gå till Stemming Lab och bekanta dig med gränsnittet. Gränsnittet består av tre stycken regelfält benämnda Regler steg1-3. Det är i dessa (eller i en separat textfil) som du skall skriva dina regler. Stegen representerar de tre steg som stemmern går igenom när den stemmar ner ett ord till lämplig stam (observera att en lämplig stam inte behöver vara, och ofta inte är, ett riktigt ord). Stemmern kommer att tillämpa reglerna i de respektive stegen uppifrån och ner. Så fort den lyckats tillämpa en regel går den vidare till nästa steg, det är därför viktigt att du placerar dina regler i och inom stegen så att de samverkar på ett bra sätt.
Under regelrutorna finns ett sökfält för att skriva sökfrågor samt en listbox med fördefinierade sökningar. Det är för dessa sökfrågor du med stemmerns hjälp skall få sökmotorn att hitta sex dokument för respektive fråga. När du väljer en av dessa sökfrågor dyker den automatiskt upp i sökfältet bredvid.
Vidare finns det under dessa en knapp för att utföra en sökning med den ovan givna sökfrågan, samt en knapp för att testa sina stemmingregler på de ord som står inskrivna i sökrutan. Detta innebär att om man är osäker på vad ens regler egentligen gör, så kan man skriva in lite olika ord i olika böjningsformer i sökrutan för att se vilken stam reglerna leder till för respektive (kryssar man dessutom i Spårutskrift får man även se vilka regler som tillämpats och vilka transformationer som gjorts i varje steg).

Regelsyntax och tips

Reglerna skrivs med följande syntax: ^vänsterkontext|morfem$->ersättning;
där följande operatorer finns:

#	Kommentar
^	NOT (dvs negering)
\|	Markerar slutet på vänsterkontexten
$	Markerar slutet på ett matchat ord
->	Transformation från vänster till höger
;	Markerar regelslut

Alla delar av en regel är optionella förutom -> och ;
Oftast är det dock lättast att alltid även sätta ut $ vilket indikerar att matchning enbart skall göras mot slutet av ett ord (suffixregler). Matchningar inne i ord (infixregler) behövs i allmänhet inte i svenskan¹ och är ofta svårare att förutsäga följden av. Nedan följer ett exempel på en ytterst begränsad regeluppsättning:

Steg1	Steg2	Steg3
s$->;	eln$->el; en$->;	cyk\|el$->l; a$->;

Reglerna tillämpas uppifrån och ned tills en regel matchar, därefter går stemmern över till nästa steg. Detta innebär att max 3 regler tillämpas, en i varje steg. Reglerna du arbetar med förs med vid sökning, test av regler och även mellan de två gränssnittvyerna (se nedan). Du skall alltså teoretiskt kunna behålla dina regler i gränssnittet genom hela labben. Vis av erfarenhet vet vi dock att olyckan kan vara framme (servern svarar inte, man råkar trycka på fel knapp eller stänga fönstret etc), så det är nog att rekommendera att spara undan reglerna lite då och då. Detta görs enklast genom att klicka på den lilla blå disketten och välja spara som text i browserns Fil-meny.²
Vill man ladda in sina regler i gränssnittet igen kan man göra det genom att klicka på den lilla oranga symbolen precis ovanför disketten, vilket tar en till en något kompaktare vy för uppladdning av regler. Bläddra till din regelfil sparad på disk och gör en sökning, testning eller växla vy för att ladda in reglerna i gränssnittet.³ I denna vy kan man även få lite information om regelformatet, samt titta på den ursprungliga regeluppsättningen, genom att klicka på det lilla frågetecknet till höger om bläddringsknappen.

Redovisning

Redovisningen skall innehålla två delar, en regeluppsättning och ett kort stycke med reflektioner kring labben och stemming/sökning, och skall skickas till FirstClass-konferensen ISBI Laborations. Innan du skickar in din redovisning så se noga till att din regelfil har korrekt syntax och att den gör så att sökmotorn hittar alla sex dokument för var och en av de fördefinierade sökfrågorna. Regelfilens syntax kan du testa genom att ladda upp din regeluppsättning till sökmotorn och testköra den mot de givna frågorna. Regeluppsättningar som inte omedelbart laddas korrekt skickas åter utan åtgärd.
Funderingar och frågor ställs lämpligast till labbhandledaren vid labbtillfället. Observera att redovisning av laborationen är obligatorisk för godkänt på kursen.

Fotnot:
1) Se gärna stycke 2.2 i Östen Dahls Grammatik (Studentlitteratur 1982) för en introduktion till affix och morfologi.
2) Du kan naturligtvis också kopiera regelfilen och klistra in den i en texteditor, mailklient etc.
3) Man kan även klistra in en komplett regelfil i den första regelrutan Regler steg1 i startvyn, varpå eventuella regler i steg 2-3 ignoreras.