Stemmaus

Stemmaus (stemming) eli karsinta tai ”typistäminen” on tiedonhakuun liittyvä luonnollisen kielen käsittelyn menetelmä, jossa sanoista poistetaan niiden sanaliitteet (affixes) ja/tai johtimet (derivatives). Käytännössä stemmaus tapahtuu ns. stemmereiden eli karsintaohjelmien avulla, algoritmeja tai sanakirjaa (usein myös molempia) hyödyntäen. Saadut vartalot (stems) indeksoidaan hakuavaimiksi tietokantaan, ja tarvittaessa myös hakukyselyt stemmataan. Menetelmän tavoitteena on kyselyjen ja tekstitietokantojen indeksin keskinäinen yhdenmukaistaminen, mikä edesauttaa relevanttien dokumenttien löytymistä täsmäytysvaiheessa.

1950- ja 1960-lukujen ensimmäiset automaattiset tekstitiedonhakujärjestelmät olivat ns. viitehakujärjestelmiä, jotka painottuivat tieteellisiin artikkeli- ja kirjallisuusviitteisiin. Englanti oli tieteen kielenä tiedonhaun keskiössä, ja vaikka sen morfologia onkin melko yksinkertainen, hakutermeinä käytettyjen yksittäisten sanojen muodonvaihtelut hankaloittivat usein relevanttien dokumenttien löytämistä. Kielellisen kattavuuden ja tulosten parantamiseksi ryhdyttiin siksi kehittämään erilaisia tietokoneohjelmia.^[1]

Varhaisin tällainen menetelmä oli hakutermien katkaiseminen. Se jätti kuitenkin vastuun käyttäjälle, mikä ei ollut kovin luotettava ratkaisu. 1960-luvun lopulla alettiin suunnitella hakutermien ja teksteissä esiintyvien sanojen yhdenmukaistamiseen omaa ohjelmaansa. Ensimmäisen tähän tarkoitukseen soveltuvan stemmerin eli karsintaohjelman kehitti Julie Beth Lovins MIT:ssä vuonna 1968.^[1] Ohjelma oli aikaiseen julkaisuajankohtaansa nähden varsin edistynyt ja myöhemmälle tutkimukselle uraauurtava.^[2] Muutama vuosi myöhemmin John Dawson kehitteli oman, Lovinsin stemmeriä muistuttavan versionsa (Dawson Stemmer) Cambridgen yliopiston kirjallisuus- ja kielitieteiden keskuksessa. Hän julkaisi algoritminsa 1974.^[3]

Myöhemmistä stemmereistä suosituin on varmasti Porterin algoritmi, jonka Martin Porter sai valmiiksi 1980 – niin ikään Cambridgessä. Alkuperäinen ohjelma oli kirjoitettu BCPL-kielellä, mutta se on sittemmin käännetty myös useille muille ohjelmointikielille.^[4] Porterin itsensä kehittämän Snowball-ohjelmointikielen myötä algoritmista on muokattu versioita myös muille kuin englannin kielelle.^[5]

Tunnettuja karsintaohjelmia ovat lisäksi Paice/Husk ja Krovetz. Ensin mainitun julkaisivat Chris Paice ja Gareth Husk Lancasterin yliopistossa 1990. Ohjelma toteutettiin Pascal-ohjelmointikielellä; käännöksiä on myöhemmin tehty esimerkiksi C-, Java- ja Perl-kielille.^[6] Krovetzin karsintaohjelma oli puolestaan Robert Krovetzin käsialaa. Hän esitteli kyseisen, englannin kielen sanakirjaa hyödyntävän karsintaohjelmansa vuonna 1993.^[3]

Stemmausmenetelmät voidaan jakaa algoritmisiin, sanakirjallisiin ja tilastollisiin.^[7] Kaikilla menetelmillä on tiedonhaun kannalta omat hyvät ja huonot puolensa, ja niiden merkitys relevanttien dokumenttien löytämisessä vaihtelee kielikohtaisesti.^[8]

Algoritmiset stemmerit ovat pieniä ja kevyitä ohjelmia, jotka soveltuvat hyvin morfologisesti suppeampien kielien – kuten englannin – nopeaan ja automaattiseen käsittelyyn tiedonhakujärjestelmissä. Ensimmäiset stemmausalgoritmit suunniteltiin nimenomaan englannin kielen tarpeisiin, ja niissä on keskitytty poistamaan sanojen etu- ja/tai loppuliitteitä.^[8] Tunnetuimmat algoritmiset karsintaohjelmat lienevät Porterin, Lovinsin ja Paicen/Huskin stemmerit.

Martin Porterin vuonna 1980 julkaisema stemmausalgoritmi on karsintaohjelmista tunnetuin ja suosituin, ja sen pohjalta on myöhemmin kehitelty lukuisia paranneltuja versioita. Alkuperäinen ohjelma koostuu viidestä vaiheesta, jotka sisältävät sääntöjä englannin sanojen päätteiden (suffixes) poistamiseksi.^[9] Ensimmäinen vaihe – joka itsessään pitää sisällään kolme eri vaihetta (1a, 1b ja 1c) – käsittelee monikkoja ja menneen ajan partisiippimuotoja; loput neljä vaihetta (2, 3, 4, 5a ja 5b) ovat suoraviivaisempia.^[10]

Koska englannissa monimutkaisemmat päätteet koostuvat usein lyhyemmistä ja yksinkertaisemmista päätteistä, ohjelma karsii ne askel kerrallaan. Kun ehdot toteutuvat jonkin sanan kohdalla, pääte poistetaan kyseisen säännön määrittelemällä tavalla, minkä jälkeen siirrytään seuraavaan vaiheeseen. Näin edetään aina viimeisen, viidennen vaiheen loppuun.^[7]

Sääntöjä on yhteensä noin 60, ja ne ovat muodoltaan varsin yksinkertaisia:

(condition) S1 -> S2

Toisin sanoen, jos sanan pääte on S1, ja päätettä S1 edeltävä sanan osa täyttää sille suluissa annetut ehdot, pääte S1 korvataan päätteellä S2.^[10]

Esimerkiksi sana generalizations typistyisi seuraavasti:

Vaihe	Stemmattava	Sovellettava sääntö	Tulos	Selitys
1	generalizations	S ->	generalization	Jos sana päättyy s-kirjaimeen, pääte poistetaan.
2	generalization	(m>0) IZATION -> IZE	generalize	Jos päätettä -ization edeltävä sanan osa sisältää vähintään yhden vokaalia seuraavan konsonantin, päätteeksi muutetaan -ize.
3	generalize	(m>0) ALIZE -> AL	general	Jos päätettä -alize edeltävä sanan osa sisältää vähintään yhden vokaalia seuraavan konsonantin, päätteeksi muutetaan -al.
4	general	(m>1) AL ->	gener	Jos päätettä -al edeltävä sanan osa sisältää vähintään kaksi vokaalia seuraavaa konsonanttia, pääte poistetaan.
5	gener		gener	Yhdenkään viimeisen vaiheen sääntöjen ehdot eivät enää täyty, joten lopullinen vartalo on gener.

Porterin algoritmi tuotti kuitenkin myös virheitä. Se saattoi palauttaa eri vartalon samaa tarkoittaville sanoille (false negative) tai saman vartalon eri asiaa tarkoittaville sanoille (false positive). Uudemmassa versiossa (Porter2) näiden virheiden määrää on saatu alennettua.^[8]

Julie Beth Lovinsin 1960-luvun lopulla julkaisema englannin kielen stemmausalgoritmi oli järjestyksessä ensimmäinen karsintaohjelma, ja sillä on ollut huomattava merkitys automaattisen sananmuotojen käsittelyn kehityksessä. Ohjelma tukeutuu listaan, joka sisältää 294 päätettä (järjestettynä pituuden mukaan laskevasti), 29 kyseisiin päätteisiin liittyvää ehtoa sekä 35 muunnossääntöä. Se on kooltaan Porterin algoritmia suurempi – mutta myös erittäin nopea, sillä se tarvitsee vain 1-2 vaihetta päätteen poistamiseksi.^[11]

Ensimmäisessä vaiheessa pisin ehdot täyttävä loppuliite poistetaan. Esimerkiksi päätteeseen -ionate liittyy ehto D, jonka mukaan päätettä edeltävän vartalon täytyy koostua vähintään viidestä kirjaimesta, jotta poisto suoritetaan. Näin ollen pass-ionate ei läpäise ehtoa (pass sisältää vain neljä kirjainta), mutta sen sijaan passion-ate toteuttaa lyhyempään päätteeseen -ate liittyvän ehdon A, jossa edeltävän vartalon pituutta ei ole rajoitettu. Vartaloksi tulee siten passion.

Toisessa vaiheessa sovelletaan edellä mainittuja muunnossääntöjä, joilla voidaan poistaa muun muassa vartaloon jääneiden tuplakirjainten toinen esiintymä (esim. rubb(ing) » rub), epäsäännöllisiä monikkomuotoja ym. poikkeuksia.^[11]

Lovinsin karsintaohjelman ongelmana on, että jokaiseen päätteeseen liittyy stemmausvirheitä aiheuttavia, usein ainutkertaisia poikkeuksia, joiden kaikkien huomioon ottaminen uusien sääntöjen muodossa veisi paljon aikaa ja resursseja, eikä lopputulos olisi pitkällä aikavälillä silti juurikaan parempi. Tämän vuoksi kehityksessä onkin keskitytty lähinnä yleisimpiin poikkeuksiin.^[2]

Paice/Husk -karsintaohjelma on Chris Paicen ja Gareth Huskin vuonna 1990 julkaisema stemmeri englannin kielelle. Algoritmi koostuu neljästä päävaiheesta, joiden välillä ohjelma liikkuu iteratiivisesti. Mukaan kuuluu vain yksi taulukko sääntöjä, jotka on esitetty seuraavassa muodossa:

• sanan pääte käänteisessä järjestyksessä,
• valinnainen koskemattomuusmerkintä (intact flag) * (sääntöä sovelletaan vain sanoihin, joita ei ole vielä karsittu),
• poistettavien merkkien määrän ilmoittava numero (voi olla myös nolla),
• valinnainen lisämerkkijono,
• jatkamissymboli > tai . (ilmoittaa, jatketaanko stemmausta vai lopetetaanko).

Stemmattavan termin viimeinen kirjain tunnistetaan, ja sen loppuliitettä verrataan kyseisellä kirjaimella alkaviin sääntöihin. Jos säännön ehdot täyttyvät, pääte muutetaan (tai poistetaan) ja palataan joko alkuun tai lopetetaan. Jos ehdot eivät täyty, siirrytään seuraavaan sääntöön niin kauan, kunnes alkukirjain vaihtuu; tällöin ohjelma lopettaa tarkistamisen.^[12] Esimerkiksi sana dependency typistyisi seuraavasti:

Stemmattava	Sovellettava sääntö	Tulos	Selitys
dependency	ycn2t>	dependent	Jos sana loppuu -ncy, korvataan päätteen kaksi viimeistä kirjainta kirjaimella t ja käytetään sitten stemmeriä uudelleen.
dependent	tne3>	depend	Jos sana loppuu -ent, poistetaan päätteen kolme viimeistä kirjainta ja käytetään sitten stemmeriä uudelleen.
depend	dd1. dei3y> deec2ss. dee1. de2> dooh4>	depend	Yhdenkään d-kirjaimella alkavan säännön ehdot eivät toteudu sanan depend kohdalla, joten alkukirjaimen vaihtuessa e-kirjaimeen stemmaus lopetetaan, ja vartalo jää nykyiseen muotoonsa.

Paice/Husk -algoritmi on osoittautunut varsin tehokkaaksi, ja se on yksinkertainen ja helposti toteutettavissa. Korvaamalla liitteet pelkän poistamisen sijasta vältetään myös ylimääräinen vaihe poikkeusten määrittelyssä.^[13] Toisaalta ohjelma poistaa päätteitä hyvin aggressiivisesti ja voi siksi aiheuttaa ylistemmausvirheitä.^[7]

Muoto-opiltaan monimutkaisempien kielien kohdalla pelkällä päätteiden automaattisella karsinnalla ei yleensä saavuteta parasta tulosta (ks. Stemmaus suomen kielen käsittelyssä), minkä vuoksi apuna on käytetty laajoja, etukäteen määriteltyjä listoja termien välisten suhteiden määrittämiseksi. Ongelmaksi muodostuu tällöin sanakirjan koko: kielet kehittyvät ja niihin ilmestyy jatkuvasti uusia sanoja, mutta sanaston pituus ei voi olla rajaton. Niinpä sanakirjallistenkin menetelmien rinnalla käytetään usein algoritmeja.^[8]

Yksi tunnetuimmista sanakirjaan ja algoritmiin perustuvista hybridikarsintaohjelmista on Bob Krovetzin vuonna 1993 kehittämä stemmeri. Vaikka tämäkin menetelmä oli tarkoitettu alun perin englannin kielelle, sen idea on ehkä käytännöllisempi laajan morfologian kielissä (esim. arabia, unkari, heprea). Ohjelma on huomattavasti monimutkaisempi kuin puhtaasti algoritmiset ratkaisut, mutta yksinkertaistaen sen toiminta voidaan jakaa kolmeen vaiheeseen:^[14]

1. Sanan monikkomuodon muuttaminen yksikkömuotoon
2. Sanan menneen muodon muuttaminen preesensiin
3. Ing-muodon poistaminen

Ohjelma tarkistaa ennen jokaista vaihetta sanakirjasta, onko kyseinen sana olemassa. Jos on – eikä siihen liity poikkeuksia – sana jää stemmaamatta. Mikäli taas sanaa ei löydy, sen päätettä verrataan erilliseen, yleisten taivutus- ja johdospäätteiden listaan. Jos vastaava pääte löytyy, se poistetaan, minkä jälkeen tarkastetaan jälleen sanakirjasta sanan olemassaolo. Jos se löydetään, vartalo hyväksytään; muutoin sanan loppua muokataan poistetun päätteen perusteella.^[8] Esimerkiksi monikon sanasta dairies loppuliite -ies korvattaisiin ensin päätteellä -ie, mutta koska dairie ei ole englannin sanakirjassa, suffiksiksi vaihtuu -y.

Krovetzin karsintaohjelman etuna Porterin algoritmiin verrattuna on, että vartalot voidaan useimmiten indeksoida kokonaisina sanoina. Se myös palauttaa harvemmin saman vartalon eri asiaa tarkoittaville sanoille (false positive), mutta toisaalta myös useammin eri vartalon samaa tarkoittaville (false negative). Tuloksellisesti Krovetzin ja Porterin karsintaohjelmat ovat olleet melko lähellä toisiaan.^[8]

Krovetz itse ehdotti ohjelmansa käyttämistä eräänlaisena esikäsittelijänä jonkin toisen, varsinaisen stemmausalgoritmin rinnalla tarkkuuden lisäämiseksi.^[3]

Tilastolliset karsintaohjelmat käyttävät sanamuotojen käsittelyn apuna tilastollisia tekniikoita ja analyyseja. Esimerkiksi n-grammien jakaumaa koko tietokannan dokumenteissa voidaan hyödyntää etu- ja loppuliitteiden tunnistamisessa ja erottamisessa, sillä sanojen taipuneet muodot esiintyvät kantamuotoja huomattavasti useammin. Markovin piilomalliin (Hidden Markov Model, HMM) perustuvassa stemmauksessa puolestaan etsitään todennäköisyysfunktioiden avulla vartaloiden ja päätteiden katkaisupisteitä.^[7]

Useimpien tilastollisten menetelmien etuna on niiden riippumattomuus tiedonhaun kohteena olevasta kielestä, mikä säästää aikaa ja vaivaa. Toisaalta ongelmia tuottavat esimerkiksi muistin ja tallennustilan tarve (n-grammit) sekä ylistemmaus (HMM).^[7]

Snowball on Martin Porterin kehittämä merkkijonojen käsittelyyn perustuva kieli karsintaohjelmien eli stemmereiden ohjelmointiin. Sen syntaksi on verrattaen suppeahko ja yksinkertainen, tarkoituksena mahdollistaa erilaisten stemmausalgoritmien sujuva soveltaminen ja kehittäminen. Datatyyppeinä Snowball käyttää merkkijonoja, kokonaislukuja ja Boolen muuttujia, ja se tukee sekä laajennettua ASCII-merkistöä että 16-bittistä Unicode-merkistöä.^[15]

Kaikki Snowball-karsintaohjelmat ovat puhtaasti algoritmisia. Vaikka tulokset voivatkin jäädä jälkeen sanakirjaan perustuvista karsintaohjelmista (etenkin morfologisesti rikkaissa kielissä), Snowball-algoritmien etuna on keveys ja nopeus. Helppouteensa nähden ne ovat myös tuottaneet yllättävän hyviä tuloksia^[16], eivätkä ne tarvitse jatkuvaa, kielen muuttumisesta johtuvaa sanakirjan päivittämistä. Toisaalta Snowball-stemmereitä voidaan hyödyntää osana sanakirjaan perustuvia ratkaisuja.^[5]

Porterin idean taustalla oli paitsi edesauttaa helposti sovellettavien, ei-englanninkieliseen tiedonhakuun tarkoitettujen stemmausalgoritmien yleistymistä myös hälventää väärinymmärryksiä, joita ohjelmoijilla syntyi hänen vuonna 1980 julkaisemansa algoritminsa käytössä ja jotka johtivat usein virheellisiin toteutuksiin.^[5]

Myös suomen kielelle on kehitetty oma Snowball-algoritmi. Esimerikiksi sanan aarniometsä eri taivutusmuodoista päätteet karsittaisiin sillä seuraavasti:

aarniomets-ien
aarniomets-istä
aarniomets-iä
aarniomets-än
aarniomets-ää

Karsintaohjelmat palauttavat sanavariantteja automaattisesti yhteisiin vartalomuotoihin, mikä mahdollistaa paitsi kyselyn laajentamisen myös pienemmät hakemistot. Stemmauksesta on hyötyä ennen kaikkea hakijalle, jonka ei tarvitse välittää hakusanojen taivutuksista tai katkaisemisista.^[17]

Alistemmaus (understemming) tarkoittaa, että karsintaohjelma poistaa liian vähän sanasta: esimerkiksi poistetaan vain kirjain s sanasta babies.^[18]. Alistemmaus vähentää haun saantia.^[19]

Ylistemmauksessa (overstemming) ongelma on päinvastainen, eli poistetaan liikaa: esimerkiksi stemmataan sana probably muotoon prob.^[18] Ylistemmaus vähentää haun tarkkuutta.^[19]

Väärinstemmaus (mis-stemming) tarkoittaa, että karsintaohjelma erehtyy luulemaan sanan loppua liitteeksi. Esimerkiksi päätteen -ly poistaminen englannin kielen sanasta on yleensä oikein (mm. cheap-ly), mutta joidenkin sanojen kohdalla se tuottaa virheellisen vartalon (mm. rep-ly).^[18]

Kevyet karsintaohjelmat (light stemmers) välttävät ylistemmausvirheitä poistamalla loppuliitteitä varovaisesti, mutta ne jättävät tämän seurauksena alistemmausvirheitä. Raskaat karsintaohjelmat (heavy stemmers) taas eivät arkaile poistaa mitään päätteitä, mikä johtaa helposti ylistemmausvirheisiin.^[20]

Edellä kuvatut piirteet muodostavat karsintaohjelmien perimmäisen ongelman: samaa asiaa merkitseville sanoille saatetaan palauttaa eri vartalo (false positive), ja toisaalta eri asiaa merkitsevät sanat voivat typistyä samaan vartaloon (false negative), jolloin myös monitulkintaisuus lisääntyy.^[8] Joskus myös saman sanan eri muodot saattavat saada eri vartalon (esim. suomen kielessä mies, mieh, mie).^[18]

Kaikesta huolimatta algoritmiset karsintaohjelmat toimivat – kohdekielestä riippuen – melko hyvin. Alistemmaus ei varsinaisesti huononna tiedonhakujärjestelmän suorituskykyä, mutta ei parannakaan sitä (stemmauksen hyödyt jäävät siis toteutumatta). Väärinstemmauksessa taas päätteettömien sanojen karsitut vartalot (esim. deliber-ate) ani harvoin sekoittuvat muihin sanamuotoihin, joten haun kannalta virhe ei läheskään aina konkretisoidu. Ylistemmaus on vakavin ongelma, mutta edes virheellisesti muihin sanoihin yhdistyvällä vartalolla ei ole merkitystä, mikäli siihen ei törmätä tiedonhakujärjestelmässä, josta haku tehdään. Ylistemmausvirheitä voidaan myös vähentää sanakirjan avulla.^[5]

Suomen kielen käsittelyyn tiedonhakujärjestelmissä on käytetty 1980-luvulta lähtien pääasiassa erilaisia perusmuoto- ja taivutusvartalo-ohjelmia.^[16] Perinteistä, päätteiden karsintaan perustuvaa stemmausta ei sen sijaan käytännön syistä ole suosittu ^[16], vaikka sitä varten on kehitetty mm. oma Snowball-algoritmi. Syyt liittyvät suomen kielen laajaan morfologiaan: substantiiveilla voi teoriassa olla noin 2000, adjektiiveilla 6000 ja verbeillä 12 000 eri taivutusmuotoa.^[21] Johdoksineen määrät olisivat vielä moninkertaiset. Toisin kuin englannissa, suomen kielessä pelkkä taivutusmuotojen tai päätteiden karsiminen ei siten ole paras mahdollinen ratkaisu. Poistamalla esimerkiksi adjektiiveista päätteet -sti menetettäisiin substantiivit posti ja viesti.^[22]

Käytännössä tavallisessa tekstissä sanojen taipuminen on huomattavasti vähäisempää, minkä vuoksi päätteiden automaattisella poistamisella voidaan toisinaan yltää yllättävänkin hyviin tuloksiin – joskaan ei silti perusmuoto-ohjelmien (kuten FINTWOL) tasolle.^[16] Stemmauksen suhteen parhaat tulokset on saatu toistaiseksi sanakirjaa hyödyntämällä. Käsitteellinen ero täysimittaista sanakirjaa käyttävään perusmuotoistamiseen eli lemmaukseen alkaa kuitenkin tällöin olla häilyvä.^[16]

Perusmuotoistamisen lisäksi toinen suomen kielen käsittelyyn paremmin soveltunut keino on ollut taivutusvartaloiden tuottaminen (inflectional stem generation).^[16] Kyseessä on tavallaan lemmauksen ja stemmauksen käänteinen toiminto: ensin mainituissa vartalot tuotetaan reduktiivisesti palauttamalla taivutetut sanat perus- tai vartalomuotoonsa; taivutusvartalo-ohjelmat (esim. Finstems, Hahmotin) puolestaan tuottavat vartalot generatiivisesti perusmuotoisista sanoista.^[1]

• Kieliteknologia
• Tietokonelingvistiikka

• Introduction to Information Retrieval (Stemming and lemmatization)
• The Lancaster Stemming Algorithm (Arkistoitu – Internet Archive)
• Snowball-demo (JavaScript-sovellus)^{[vanhentunut linkki]}