bild
Skolan för
elektroteknik
och datavetenskap

Språkteknologi

Laboration 5

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. Din uppgift i denna labb är att skriva stemmingregler till en enkel sökmotor för att på så sätt öka täckningen, helst utan sänkning i precision.

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

Uppgiftsbeskrivning
Om du känner dig osäker på vad stemming är kan du läsa det sista stycket, "Bakgrund".     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.     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 som vi kör på två olika servrar: Stemming Lab och 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:

1bil
2bil hund olycka
3dator fråga peka
4cykling löpa simma
5springer tid
6springer 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 eller 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. Detta innebär att 0-3 regler tillämpas för varje ord, dvs att ett ord förändras maximalt tre gånger.
    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 [Sök] för att utföra en sökning med den ovan givna sökfrågan, samt en knapp [Testa reglerna på sökfrågan] 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 ;. Tyvärr fungerar kommentarer lite dåligt i dagsläget och kan störa reglerna, det kan därför vara bäst att undvika dem tillsvidare.
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:

Steg1Steg2Steg3
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.1
    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.2 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ättning3 och ett kort stycke med reflektioner kring labben och stemming/sökning) och kan ske på två sätt. Antingen muntligt genom att du tillkallar en labbhandledare vid labbtillfället och ber att få redovisa, eller genom att du mailar din regelfil och dina reflektioner till jboye@csc.kth.se (där det första alternativet om möjligt är att föredra). Om du väljer att skicka 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 laddar 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 och redovisas labben senast samma dag som labben går erhåller man bonuspoäng på den skriftliga tentamen.

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 som är intresserad kan läsa en artikel om en undersökning vi gjort här på KTH 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.
Fotnot:
1) Du kan naturligtvis också kopiera regelfilen och klistra in den i en texteditor, mailklient etc.
2) 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.
3) Notera att en regelfil skall täcka samtliga sökfrågor, du/ni skall alltså inte skriva en regelfil för varje fråga.

Teoretisk uppgift

Till varje laboration finns en teoriuppgift knuten. Syftet är att uppmuntra till tidigare inläsning av stoffet. Varje teoriuppgift skall redovisas på papper (ca. 100 ord) vid aktuellt labbtillfälle. Hur bonuspoängen fungerar beskrivs i KursPM. Teoriuppgifterna är inte obligatoriska utan skall ses som ett stöd för att utveckla de teoretiska kunskaperna i språkteknologi.

Fråga:Vilka är de huvudsakliga komponenterna i en sökmotor som Google (och vilka uppgifter utför dessa komponenter)?
Copyright © Sidansvarig: Johan Boye <jboye@csc.kth.se>
Uppdaterad 2011-09-01