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.

Historia

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.
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. Ohjelma oli aikaiseen julkaisuajankohtaansa nähden varsin edistynyt ja myöhemmälle tutkimukselle uraauurtava. 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.
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. Porterin itsensä kehittämän Snowball-ohjelmointikielen myötä algoritmista on muokattu versioita myös muille kuin englannin kielelle.
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. Krovetzin karsintaohjelma oli puolestaan Robert Krovetzin käsialaa. Hän esitteli kyseisen, englannin kielen sanakirjaa hyödyntävän karsintaohjelmansa vuonna 1993.

Stemmausmenetelmät

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

Algoritmiset karsintaohjelmat

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ä. Tunnetuimmat algoritmiset karsintaohjelmat lienevät Porterin, Lovinsin ja Paicen/Huskin stemmerit.

Lovins Stemmer (1968)

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.
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.
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.

Sanakirjaan perustuvat karsintaohjelmat

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.

Tilastolliset menetelmät

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ä.
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).

Snowball-kieli

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öä.
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, eivätkä ne tarvitse jatkuvaa, kielen muuttumisesta johtuvaa sanakirjan päivittämistä. Toisaalta Snowball-stemmereitä voidaan hyödyntää osana sanakirjaan perustuvia ratkaisuja.
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.
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-ää

Stemmauksen etuja ja ongelmia

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.

Alistemmaus, ylistemmaus, väärinstemmaus

Alistemmaus (understemming) tarkoittaa, että karsintaohjelma poistaa liian vähän sanasta: esimerkiksi poistetaan vain kirjain s sanasta babies. Alistemmaus vähentää haun saantia.
Ylistemmauksessa (overstemming) ongelma on päinvastainen, eli poistetaan liikaa: esimerkiksi stemmataan sana probably muotoon prob. Ylistemmaus vähentää haun tarkkuutta.
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).
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.
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. Joskus myös saman sanan eri muodot saattavat saada eri vartalon (esim. suomen kielessä mies, mieh, mie).
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.

Stemmaus suomen kielen käsittelyssä

Suomen kielen käsittelyyn tiedonhakujärjestelmissä on käytetty 1980-luvulta lähtien pääasiassa erilaisia perusmuoto- ja taivutusvartalo-ohjelmia. Perinteistä, päätteiden karsintaan perustuvaa stemmausta ei sen sijaan käytännön syistä ole suosittu , 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. 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.
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. 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ä.
Perusmuotoistamisen lisäksi toinen suomen kielen käsittelyyn paremmin soveltunut keino on ollut taivutusvartaloiden tuottaminen (inflectional stem generation). 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.