[Muokattu: 26.11.2010]

Bayes ja spam (3-B) [ < Henkilön suoja ... < Yhteiskunta ]

Roskapostin suodattimet käyttävät lähes poikkeuksetta suodatusta, joka perustuu 1700-luvulla eläneen Thomas Bayesin teoriaan.

Lähtökohtana on valmiiksi luokiteltuja viestejä, joista siis tiedetään ovatko ne roskapostia (s) vai eivät (¬s). Näistä viesteistä voidaan muodostaa sanasto W = {w1, w2,...,wk} ja kullekin indeksille i=1,...,k laskea ja tallettaa tietokantaan esim. seuraavanlaisia todennäköisyyksiä :
P( wi ) = sanan wi esiintymisen todennäköisyys.
P( wi | s) = ehdollinen tn. sille että wi esiintyy roskapostiviestissä
P( wi | ¬s) = tn. sille että wi esiintyy ei-roskapostiviestissä
P( s | wi ) = tn. sille että viesti on roskapostia, jos wi esiintyy siinä. Tämä plus P( ¬s | wi) = 1.
Tietysti myös roskapostin osuus voidaan laskea ja P( s ) + P( ¬s ) = 1.

Jokaiselle sanalle lasketaan siis luokiteltujen viestien perusteella todennäköisyys ovatko ne osa roskapostia tai osa kunnollista postia (ham). Esimerkiksi ”viagra” ja ”Nigeria” esiintyvät suurella todennäköisyydellä roskapostissa, kun taas vaikkapa ”tietoturvallisuuden” ja ”jatkokurssi” esiintyvät suurella todennäköisyydellä kunnollisessa postissa. Tarkalleen ottaen ei kuitenkaan tarvitse rajautua sanoihin, vaan myös muille viestin ominaisuuksille voidaan laskea todennäköisyyksiä.

Viestejä luokitellaan kantaan, josta lasketaan todennäköisyyksiä --> oppimiskyky ja mahdollisuus henkilökohtaiseen luokitukseen.

Koska todennäköisyydet lasketaan todellisista viesteistä, tämä on järjestelmällisempää ja täsmällisempää kuin pelkät heuristiset säännöt tai itse lasketut todennäköisyydet.

Kun jossain uudessa viestissä esiintyy jokin W:n osasanasto w, haluttaisiin tietää P( s | w ). Tietenkin w voi olla vain osa viestissä esiintyvistä sanoista ja toisaalta siinä voi olla mukana paljon muitakin piirteitä, esim. sanaryhmiä, otsikkotietoja, muotoilukoodeja, kunhan nämä ovat myös tietokannassa W.

Todennäköisyyteen P( s | w ) päästään käsiksi Bayesin kaavan kautta. Se saadaan yksinkertaisella laskelmalla ehdollisen todennäköisyyden kaavasta:

                 P( s JA w )
   P( s | w ) = -------------
                    P( w )    
Ratkaistaan osoittaja, käytetään symmetriaa ja ratkaistaan lopulta P( s | w ):
   P( s JA w ) = P( w | s ) P( s ) =  P( s | w ) P( w )

                P( w | s ) P( s ) 
   P( s | w ) = -------------------          (Bayes)
                     P( w )
Yksinkertainen suodatin saadaan tulkitsemalla viesti roskapostiksi jos se on osasanaston w puitteissa tietokannassa todennäköisempää kuin ei-roskaposti:
   P( s | w ) > P( ¬s | w ).
Kun tähän epäyhtälöön sovelletaan em. kaavoja, molemmille puolille tulee nimittäjään P( w ). Kun se kerrotaan pois, jää kriteeriksi
   P( w | s ) P( s ) > P( w | ¬s ) P( ¬s ).   (*)
Arvot P(s) ja P(¬s) saadaan suoraan tietokannasta, mutta arvoja P( w | [-]s ) voi olla hankala laskea. Joka kerta hieman erilainen sanajoukko w pitäisi aina tarkistaa alkuperäisistä viesteistä. Naiivi Bayesin teoria olettaa (kuvittelee), että sanojen esiintyminen on riippumatonta toisistaan. Tällä perusteella saadaan todennäköisyydet hajoitetuksi tulomuotoon:
   P( w | s ) = TULO_i P( wi | s)   ja   P( w | ¬s ) = TULO_i P( wi | ¬s).     (**) 
Tätä varten tarvitaan kaikki roskapostiksi/ei-roskapostiksi todettujen viestien sisältämät sanat ja niiden esiintymistiheydet. Tämähän on voitu tehdä valmiiksi ja päivittää sitä mukaa kun uusia viestejä tulee tietokantaan. Koska molemmilla puolilla pitää laskea tulo samoista osasanaston w sanoista, voi toiseen tulla nolla-todennäköisyyksiä. Tätä varten tietokantaan täytyy uusia sanoja tuotaessa varmistaa että niitä on ainakin yksi sekä s:n että ¬s:n puolella. Tästä huolimatta jotkut todennäköisyydet ovat hyvin pieniä ja tulotkin ovat kertaluvultaan erittäin pieniä ja lisäksi vaihtelevia. On kätevämpää laskea suoraan "kertaluvuilla " eli logaritmeilla. Kun tulot ensin sijoitetaan kaavaan (*) ja sitten otetaan logaritmi, saadaan
   SUM_i Log P( wi | s ) + Log P( s )  >  SUM_i Log P( wi | ¬s )  + Log P( ¬s ).      (***)
Tällainen laskelma ja vertailu on nopea, kun logaritmit on valmiiksi laskettu. Tarvitaan vain summat kiinnostavien sanojen tiedoista. Kun luokiteltua aineistoa kertyy lisää, voidaan tietoja päivittää kerralla tai tarpeen mukaan. Sanastoa ei voi etukäteen rajata kovin tiukasti, mutta suodatusvertailuun kannattaa ottaa huomioon vain sellaiset sanat joilla on suuri tai pieni "spamisiteetti" eli P( s | wi), koska keskimääräiset sanat eivät erottele hyvin.

Suodatin tarvitsee lisäparametrin jolla voi säätää virheellisten positiivisten osuutta pienemmäksi, esim. ei-roskapostisanojen painoarvo suhteessa roskaposti-sanojen painoon.

Jos halutaan varsinaisesti laskea todennäköisyys P( s | w ), voidaan kaavaan (Bayes) laskea todennäköisyydet P( w ) ja P( w | s) riippumattomuusoletuksella kaavan (**) mukaisesti ottaen huomioon että P( w ) = P( w | s ) + P( w | ¬s ). Nimittäjässä olevaan summaan ei logaritmi "pure", joten tulos näyttää jäävän tällaiseksi:

                           P( s ) TULO_i P( wi | s ) 
   P( s | w ) = ------------------------------------------------------------
                 P( s ) TULO_i P( wi | s)  +  P( ¬s ) TULO_i P( wi | ¬s)
Harjoitus: Tämä on tietenkin muotoa 1 / (1 + x/y)), ja jos a-kantaisia logaritmeja halutaan käyttää, saadaan edelleen = 1 / ( 1+ a^(Log x - Log y) ) ja huomataan, että Log x - Log y on sama kuin se, mitä epäyhtälössä (***) on, kun kaikki termit on siirretty oikealle puolelle.

Useissa toteutuksissa ei tehdä ennakko-oletusta roskapostin kokonaisosuudesta. Toisin sanoen P(s) ja P(¬s) oletetaan aina 0.5:ksi, jolloin ne jätetään huomioimatta.

Bayesin teoriaa on käytetty tekstien luokittelussa aiemminkin mutta roskapostin erotteluun se otettiin ilmeisesti vasta 1990-luvun lopulla.

Harjoitus:Miksi Bayesin teoria toimii tai ei toimi roskapostin suodatuksessa? Mitä tehokas bayesilainen suodatus edellyttää?

Harjoitus: Mitä seuraa roskapostittajien käyttämästä myrkyttämisestä (Bayesian poisoning), jossa viestiin lisätään tarkoituksella suurella todennäköisyydellä hyviä sanoja eli tavoite on, että P( wi | ¬s) on mahdollisimman suuri?