bild
Skolan för
elektroteknik
och datavetenskap

Spr�kteknologi

Laboration 5

Informationss�kning med stemming

Magnus Rosell
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 knutsson@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.

Copyright © Sidansvarig: Magnus Rosell <rosell@csc.kth.se>
Uppdaterad 2009-10-01