Betere Bayesiaanse Filtering

Januari 2003

(Dit artikel werd gepresenteerd als lezing op de Spam Conferentie van 2003. Het beschrijft het werk dat ik heb gedaan om de prestaties van het algoritme te verbeteren zoals beschreven in A Plan for Spam, en wat ik in de toekomst van plan ben te doen.)

De eerste ontdekking die ik hier wil presenteren is een algoritme voor het lui evalueren van onderzoeksartikelen. Schrijf gewoon wat je wilt en citeer geen eerder werk, en verontwaardigde lezers zullen je verwijzingen sturen naar alle artikelen die je had moeten citeren. Ik ontdekte dit algoritme nadat "A Plan for Spam" [1] op Slashdot stond.

Spamfiltering is een subset van tekstclassificatie, een gevestigd vakgebied, maar de eerste artikelen over Bayesiaanse spamfiltering per se lijken twee te zijn geweest die in 1998 op dezelfde conferentie werden gepresenteerd, één door Pantel en Lin [2], en een andere door een groep van Microsoft Research [3].

Toen ik over dit werk hoorde, was ik een beetje verrast. Als mensen al vier jaar bezig waren met Bayesiaanse filtering, waarom gebruikte niet iedereen het? Toen ik de artikelen las, ontdekte ik waarom. Het filter van Pantel en Lin was het meest effectieve van de twee, maar het ving slechts 92% van de spam, met 1.16% false positives.

Toen ik probeerde een Bayesiaans spamfilter te schrijven, ving het 99.5% van de spam met minder dan 0.03% false positives [4]. Het is altijd alarmerend wanneer twee mensen die hetzelfde experiment uitvoeren, sterk uiteenlopende resultaten krijgen. Het is hier vooral alarmerend omdat die twee sets getallen tot tegenovergestelde conclusies kunnen leiden. Verschillende gebruikers hebben verschillende vereisten, maar ik denk dat voor veel mensen een filterpercentage van 92% met 1.16% false positives betekent dat filtering geen acceptabele oplossing is, terwijl 99.5% met minder dan 0.03% false positives betekent dat het dat wel is.

Dus waarom kregen we zulke verschillende cijfers? Ik heb niet geprobeerd de resultaten van Pantel en Lin te reproduceren, maar door het artikel te lezen zie ik vijf dingen die waarschijnlijk het verschil verklaren.

Eén is simpelweg dat ze hun filter trainden op heel weinig data: 160 spam- en 466 niet-spam-e-mails. De prestaties van het filter zouden nog steeds moeten stijgen met zulke kleine datasets. Hun cijfers zijn dus mogelijk geen nauwkeurige maatstaf voor de prestaties van hun algoritme, laat staan voor Bayesiaanse spamfiltering in het algemeen.

Maar ik denk dat het belangrijkste verschil waarschijnlijk is dat ze de berichtkoppen negeerden. Voor iedereen die aan spamfilters heeft gewerkt, zal dit een verkeerde beslissing lijken. En toch negeerde ik in de allereerste filters die ik probeerde te schrijven, ook de koppen. Waarom? Omdat ik het probleem netjes wilde houden. Ik wist toen niet veel van e-mailkoppen, en ze leken me vol te zitten met willekeurige dingen. Hier is een les voor filterauteurs: negeer geen data. Je zou denken dat deze les te voor de hand liggend is om te vermelden, maar ik heb het verschillende keren moeten leren.

Ten derde stemden Pantel en Lin de tokens, wat betekende dat ze bijvoorbeeld zowel "mailing" als "mailed" reduceerden tot de wortel "mail". Ze voelden zich misschien gedwongen dit te doen vanwege de kleine omvang van hun corpus, maar zo ja, dan is dit een soort voortijdige optimalisatie.

Ten vierde berekenden ze de waarschijnlijkheden anders. Ze gebruikten alle tokens, terwijl ik slechts de 15 meest significante gebruik. Als je alle tokens gebruikt, mis je langer spams, het type waarbij iemand je zijn levensverhaal vertelt tot het punt waarop hij rijk werd van een of ander multilevel marketing schema. En zo'n algoritme zou voor spammers gemakkelijk te vervalsen zijn: voeg gewoon een grote hoeveelheid willekeurige tekst toe om de spamtermen te compenseren.

Ten slotte gaven ze geen voorkeur aan false positives. Ik denk dat elk spamfilteralgoritme een handige knop moet hebben waaraan je kunt draaien om de false positive rate te verlagen ten koste van de filter rate. Ik doe dit door de voorkomens van tokens in het niet-spam corpus dubbel te tellen.

Ik denk niet dat het een goed idee is om spamfiltering als een rechttoe rechtaan tekstclassificatieprobleem te behandelen. Je kunt technieken voor tekstclassificatie gebruiken, maar oplossingen kunnen en moeten het feit weerspiegelen dat de tekst e-mail is, en spam in het bijzonder. E-mail is niet alleen tekst; het heeft structuur. Spamfiltering is niet alleen classificatie, omdat false positives zoveel erger zijn dan false negatives dat je ze als een ander soort fout moet behandelen. En de bron van de fout is niet alleen willekeurige variatie, maar een levende menselijke spammer die actief werkt om je filter te verslaan.

Tokens

Een ander project waar ik over hoorde na het Slashdot-artikel was Bill Yerazunis' CRM114 [5]. Dit is het tegenvoorbeeld van het ontwerpprincipe dat ik zojuist noemde. Het is een rechttoe rechtaan tekstclassificator, maar zo verbluffend effectief dat het erin slaagt spam bijna perfect te filteren zonder zelfs maar te weten wat het doet.

Toen ik eenmaal begreep hoe CRM114 werkte, leek het onvermijdelijk dat ik uiteindelijk zou moeten overstappen van filtering op basis van enkele woorden naar een aanpak zoals deze. Maar eerst, dacht ik, zal ik zien hoe ver ik kan komen met enkele woorden. En het antwoord is, verrassend ver.

Meestal heb ik gewerkt aan slimmere tokenisatie. Op huidige spam heb ik filterpercentages kunnen bereiken die die van CRM114 benaderen. Deze technieken zijn grotendeels orthogonaal aan die van Bill; een optimale oplossing zou beide kunnen omvatten.

"A Plan for Spam" gebruikt een zeer eenvoudige definitie van een token. Letters, cijfers, streepjes, apostrofs en dollartekens zijn samenstellende tekens, en al het andere is een tokenseparator. Ik negeerde ook hoofdletters.

Nu heb ik een ingewikkeldere definitie van een token:

1. Hoofdletters worden behouden.
2. Uitroeptekens zijn samenstellende tekens.
3. Punten en komma's zijn samenstellend als ze tussen twee cijfers voorkomen. Dit stelt me in staat om IP-adressen en prijzen intact te krijgen.
4. Een prijsbereik zoals $20-25 levert twee tokens op, $20 en $25.
5. Tokens die voorkomen in de regels To, From, Subject en Return-Path, of in URL's, worden dienovereenkomstig gemarkeerd. Bijvoorbeeld, "foo" in de Subject-regel wordt "Subject*foo". (De asterisk kan elk teken zijn dat je niet als samenstellend toestaat.)

Dergelijke maatregelen vergroten het vocabulaire van het filter, waardoor het discriminerender wordt. Bijvoorbeeld, in het huidige filter heeft "free" in de Subject-regel een spamwaarschijnlijkheid van 98%, terwijl hetzelfde token in de hoofdtekst een spamwaarschijnlijkheid van slechts 65% heeft.

Hier zijn enkele van de huidige waarschijnlijkheden [6]:

SubjectFREE 0.9999 free!! 0.9999 Tofree 0.9998 Subjectfree 0.9782 free! 0.9199 Free 0.9198 Urlfree 0.9091 FREE 0.8747 From*free 0.7636 free 0.6546

In het Plan for Spam-filter zouden al deze tokens dezelfde waarschijnlijkheid hebben gehad, 0.7602. Dat filter herkende ongeveer 23.000 tokens. Het huidige herkent er ongeveer 187.000.

Het nadeel van een groter universum aan tokens is dat er meer kans is op missers. Het verspreiden van je corpus over meer tokens heeft hetzelfde effect als het kleiner maken ervan. Als je bijvoorbeeld uitroeptekens als samenstellend beschouwt, kun je eindigen met geen spamwaarschijnlijkheid voor "free" met zeven uitroeptekens, ook al weet je dat "free" met slechts twee uitroeptekens een waarschijnlijkheid van 99.99% heeft.

Een oplossing hiervoor is wat ik degeneratie noem. Als je geen exacte overeenkomst voor een token kunt vinden, behandel het dan alsof het een minder specifieke versie is. Ik beschouw terminale uitroeptekens, hoofdletters en voorkomen in een van de vijf gemarkeerde contexten als het specifieker maken van een token. Als ik bijvoorbeeld geen waarschijnlijkheid vind voor "Subjectfree!", zoek ik naar waarschijnlijkheden voor "Subjectfree", "free!", en "free", en neem degene die het verst van 0.5 af ligt.

Hier zijn de alternatieven [7] die worden overwogen als het filter "FREE!!!" in de Subject-regel ziet en er geen waarschijnlijkheid voor heeft.

SubjectFree!!! Subjectfree!!! SubjectFREE! SubjectFree! Subjectfree! SubjectFREE SubjectFree Subjectfree FREE!!! Free!!! free!!! FREE! Free! free! FREE Free free

Als je dit doet, zorg er dan voor dat je versies met beginhoofdletters meeneemt, evenals volledig hoofdletters en volledig kleine letters. Spams bevatten meer zinnen in de gebiedende wijs, en daarin is het eerste woord een werkwoord. Dus werkwoorden met beginhoofdletters hebben hogere spamwaarschijnlijkheden dan wanneer ze volledig klein geschreven zouden zijn. In mijn filter is de spamwaarschijnlijkheid van "Act" 98% en voor "act" slechts 62%.

Als je het vocabulaire van je filter vergroot, kun je uiteindelijk hetzelfde woord meerdere keren tellen, volgens je oude definitie van "hetzelfde". Logisch gezien zijn het geen dezelfde tokens meer. Maar als dit je nog steeds stoort, laat me dan uit ervaring toevoegen dat de woorden die je meerdere keren lijkt te tellen precies degene zijn die je zou willen hebben.

Een ander effect van een groter vocabulaire is dat wanneer je een inkomende e-mail bekijkt, je meer interessante tokens vindt, d.w.z. die met waarschijnlijkheden ver van 0.5. Ik gebruik de 15 meest interessante om te beslissen of een e-mail spam is. Maar je kunt tegen een probleem aanlopen als je een vast getal als dit gebruikt. Als je veel maximaal interessante tokens vindt, kan het resultaat worden bepaald door welke willekeurige factor dan ook die de volgorde van even interessante tokens bepaalt. Een manier om hiermee om te gaan, is om sommige als interessanter dan andere te behandelen.

Bijvoorbeeld, het token "dalco" komt 3 keer voor in mijn spamcorpus en nooit in mijn legitieme corpus. Het token "Url*optmails" (wat "optmails" binnen een URL betekent) komt 1223 keer voor. En toch, zoals ik vroeger waarschijnlijkheden voor tokens berekende, zouden beide dezelfde spamwaarschijnlijkheid hebben gehad, de drempel van 0.99.

Dat voelt niet goed. Er zijn theoretische argumenten om deze twee tokens aanzienlijk verschillende waarschijnlijkheden te geven (Pantel en Lin doen dat), maar dat heb ik nog niet geprobeerd. Het lijkt op zijn minst dat als we meer dan 15 tokens vinden die alleen in het ene of het andere corpus voorkomen, we prioriteit moeten geven aan degene die veel voorkomen. Dus nu zijn er twee drempelwaarden. Voor tokens die alleen in het spamcorpus voorkomen, is de waarschijnlijkheid 0.9999 als ze meer dan 10 keer voorkomen en 0.9998 anders. Hetzelfde aan de andere kant van de schaal voor tokens die alleen in het legitieme corpus worden gevonden.

Ik kan de tokenwaarschijnlijkheden later aanzienlijk schalen, maar deze kleine schaling zorgt er tenminste voor dat tokens op de juiste manier worden gesorteerd.

Een andere mogelijkheid zou zijn om niet slechts 15 tokens te beschouwen, maar alle tokens boven een bepaalde drempel van interessantheid. Steven Hauser doet dit in zijn statistische spamfilter [8]. Als je een drempel gebruikt, maak deze dan erg hoog, anders kunnen spammers je misleiden door berichten te vullen met meer onschuldige woorden.

Tot slot, wat moet je doen met html? Ik heb het hele spectrum van opties geprobeerd, van het negeren tot het volledig parsen. Het negeren van html is een slecht idee, omdat het vol zit met nuttige spamaanduidingen. Maar als je het allemaal parset, kan je filter ontaarden in een loutere html-herkenner. De meest effectieve aanpak lijkt de middenweg te zijn, om sommige tokens op te merken, maar niet andere. Ik kijk naar a-, img- en font-tags, en negeer de rest. Links en afbeeldingen moet je zeker bekijken, omdat ze URL's bevatten.

Ik zou waarschijnlijk slimmer kunnen omgaan met html, maar ik denk niet dat het de moeite waard is om hier veel tijd aan te besteden. Spams vol met html zijn gemakkelijk te filteren. De slimmere spammers vermijden het al. Dus de prestaties in de toekomst zouden niet veel moeten afhangen van hoe je met html omgaat.

Prestaties

Tussen 10 december 2002 en 10 januari 2003 ontving ik ongeveer 1750 spams. Hiervan kwamen er 4 door. Dat is een filterpercentage van ongeveer 99.75%.

Twee van de vier gemiste spams kwamen door omdat ze toevallig woorden gebruikten die vaak voorkomen in mijn legitieme e-mail.

De derde was een van die spams die een onveilige cgi-script gebruiken om e-mail naar derden te sturen. Ze zijn moeilijk te filteren op basis van alleen de inhoud, omdat de headers onschuldig zijn en ze voorzichtig zijn met de woorden die ze gebruiken. Toch kan ik ze meestal vangen. Deze glipte erdoor met een waarschijnlijkheid van 0.88, net onder de drempel van 0.9.

Natuurlijk zou het bekijken van meerdere tokensequenties het gemakkelijk vangen. "Hieronder vindt u het resultaat van uw feedbackformulier" is een directe aanwijzing.

De vierde spam was wat ik een spam-van-de-toekomst noem, omdat dit is hoe ik verwacht dat spam zich zal ontwikkelen: volledig neutrale tekst gevolgd door een URL. In dit geval was het van iemand die zei dat hij eindelijk zijn homepage had afgerond en of ik ernaar wilde kijken. (De pagina was natuurlijk een advertentie voor een pornosite.)

Als de spammers voorzichtig zijn met de headers en een nieuwe URL gebruiken, is er niets in spam-van-de-toekomst dat filters kunnen opmerken. We kunnen natuurlijk tegenwerken door een crawler te sturen om de pagina te bekijken. Maar dat is misschien niet nodig. De responsratio voor spam-van-de-toekomst moet laag zijn, anders zou iedereen het doen. Als het laag genoeg is, zal het niet lonen voor spammers om het te sturen, en hoeven wij niet te hard te werken om het te filteren.

Nu het echt schokkende nieuws: gedurende dezelfde periode van een maand ontving ik drie false positives.

Op een bepaalde manier is het een opluchting om enkele false positives te krijgen. Toen ik "A Plan for Spam" schreef, had ik er geen gehad, en ik wist niet hoe ze zouden zijn. Nu ik er een paar heb gehad, ben ik opgelucht dat ze niet zo erg zijn als ik vreesde. False positives die door statistische filters worden gegenereerd, blijken e-mails te zijn die veel op spam lijken, en dit zijn vaak degene die je het minst zou willen missen [9].

Twee van de false positives waren nieuwsbrieven van bedrijven waar ik dingen van had gekocht. Ik heb er nooit om gevraagd, dus men zou kunnen zeggen dat het spam was, maar ik tel ze als false positives omdat ik ze daarvoor niet als spam aan het verwijderen was. De reden dat de filters ze oppikten, was dat beide bedrijven in januari overstapten op commerciële e-mailverzenders in plaats van de e-mails vanaf hun eigen servers te verzenden, en zowel de headers als de hoofdteksten werden veel spammier.

De derde false positive was echter een slechte. Het was van iemand uit Egypte en geschreven in volledig hoofdletters. Dit was een direct gevolg van het hoofdlettergevoelig maken van tokens; het Plan for Spam-filter zou het niet hebben opgevangen.

Het is moeilijk te zeggen wat de algehele false positive rate is, omdat we statistisch gezien in de ruis zitten. Iedereen die aan filters heeft gewerkt (althans, effectieve filters) zal zich bewust zijn van dit probleem. Bij sommige e-mails is het moeilijk te zeggen of ze spam zijn of niet, en dit zijn degene waar je naar kijkt als je filters echt strak afstelt. Zo heeft het filter tot nu toe twee e-mails opgevangen die vanwege een typefout naar mijn adres werden gestuurd, en één die naar mij werd gestuurd in de overtuiging dat ik iemand anders was. Men zou kunnen zeggen dat dit noch mijn spam, noch mijn niet-spam e-mail is.

Een andere false positive was van een vice-president bij Virtumundo. Ik schreef naar hen en deed me voor als een klant, en aangezien het antwoord via de mailservers van Virtumundo terugkwam, had het de meest belastende headers denkbaar. Men zou kunnen zeggen dat dit ook geen echte false positive is, maar een soort Heisenberg-onzekerheidseffect: ik kreeg het alleen omdat ik over spamfiltering schreef.

Zonder deze mee te rekenen, heb ik tot nu toe in totaal vijf false positives gehad, van de ongeveer 7740 legitieme e-mails, een percentage van 0.06%. De andere twee waren een melding dat iets dat ik had gekocht back-ordered was, en een feestherinnering van Evite.

Ik denk niet dat dit aantal betrouwbaar is, deels omdat de steekproef zo klein is, en deels omdat ik denk dat ik het filter kan aanpassen om sommige hiervan niet op te vangen.

False positives lijken mij een ander soort fout dan false negatives. Het filterpercentage is een maatstaf voor prestaties. False positives beschouw ik meer als bugs. Ik benader het verbeteren van de filter rate als optimalisatie, en het verlagen van false positives als debugging.

Dus deze vijf false positives zijn mijn buglijst. Bijvoorbeeld, de e-mail uit Egypte werd gepakt omdat de hoofdletters het filter deden lijken op Nigeriaanse spam. Dit is echt een soort bug. Net als bij html is de e-mail die volledig in hoofdletters is geschreven conceptueel één functie, niet één voor elk woord. Ik moet hoofdletters op een meer geavanceerde manier behandelen.

Dus wat moeten we van deze 0.06% maken? Niet veel, denk ik. Je zou het kunnen beschouwen als een bovengrens, rekening houdend met de kleine steekproefomvang. Maar in dit stadium is het meer een maatstaf voor de bugs in mijn implementatie dan een intrinsieke false positive rate van Bayesiaanse filtering.

Toekomst

Wat nu? Filtering is een optimalisatieprobleem, en de sleutel tot optimalisatie is profiling. Probeer niet te raden waar je code traag is, want je zult fout raden. Kijk waar je code traag is, en repareer dat. In filtering vertaalt dit zich naar: kijk naar de spams die je mist, en bedenk wat je had kunnen doen om ze te vangen.

Bijvoorbeeld, spammers werken nu agressief om filters te ontwijken, en een van de dingen die ze doen is woorden opbreken en verkeerd spellen om te voorkomen dat filters ze herkennen. Maar hieraan werken is niet mijn eerste prioriteit, omdat ik nog steeds geen moeite heb om deze spams te vangen [10].

Er zijn twee soorten spams waar ik momenteel wel moeite mee heb. Eén is het type dat zich voordoet als een e-mail van een vrouw die je uitnodigt om met haar te chatten of haar profiel op een datingsite te bekijken. Deze komen door omdat het het enige type verkooppraatje is dat je kunt houden zonder verkooppraatjes te gebruiken. Ze gebruiken hetzelfde vocabulaire als gewone e-mail.

De andere soort spams die ik moeilijk kan filteren zijn die van bedrijven in bijvoorbeeld Bulgarije die contractprogrammeerdiensten aanbieden. Deze komen door omdat ik ook een programmeur ben, en de spams vol staan met dezelfde woorden als mijn echte e-mail.

Ik zal me waarschijnlijk eerst richten op het type persoonlijke advertenties. Ik denk dat als ik beter kijk, ik statistische verschillen kan vinden tussen deze en mijn echte e-mail. De schrijfstijl is zeker anders, hoewel het misschien multi-woord filtering vereist om dat te vangen. Ook merk ik dat ze de URL neigen te herhalen, en iemand die een URL in een legitieme e-mail opneemt, zou dat niet doen [11].

De outsourcing-types zullen moeilijk te vangen zijn. Zelfs als je een crawler naar de site zou sturen, zou je geen overtuigend statistisch bewijs vinden. Misschien is het enige antwoord een centrale lijst van domeinen die in spams worden geadverteerd [12]. Maar er kunnen niet zoveel van dit soort e-mails zijn. Als de enige overgebleven spams ongevraagde aanbiedingen van contractprogrammeerdiensten uit Bulgarije waren, konden we ons waarschijnlijk allemaal bezighouden met iets anders.

Zal statistische filtering ons dat punt daadwerkelijk brengen? Dat weet ik niet. Op dit moment is spam voor mij persoonlijk geen probleem. Maar spammers hebben nog geen serieuze poging gedaan om statistische filters te vervalsen. Wat gebeurt er als ze dat wel doen?

Ik ben niet optimistisch over filters die op netwerkniveau werken [13]. Wanneer er een statisch obstakel is dat de moeite waard is om te omzeilen, zijn spammers behoorlijk efficiënt in het omzeilen ervan. Er is al een bedrijf genaamd Assurance Systems dat je e-mail door Spamassassin zal laten lopen en je zal vertellen of het wordt gefilterd.

Netwerk-level filters zullen niet volledig nutteloos zijn. Ze kunnen voldoende zijn om alle "opt-in" spam te doden, d.w.z. spam van bedrijven zoals Virtumundo en Equalamail die beweren dat ze echt opt-in lijsten draaien. Je kunt die filteren op basis van alleen de headers, ongeacht wat ze in de hoofdtekst zeggen. Maar iedereen die bereid is headers te vervalsen of open relays te gebruiken, inclusief waarschijnlijk de meeste porno-spammers, zou in staat moeten zijn om enige boodschap langs netwerk-level filters te krijgen als ze dat willen. (Lang niet de boodschap die ze zouden willen sturen, wat iets is.)

Het soort filters waar ik optimistisch over ben, zijn degene die waarschijnlijkheden berekenen op basis van de e-mail van elke individuele gebruiker. Deze kunnen veel effectiever zijn, niet alleen in het vermijden van false positives, maar ook in het filteren: bijvoorbeeld, het vinden van het e-mailadres van de ontvanger base-64 gecodeerd ergens in een bericht is een zeer goede spamindicator.

Maar het werkelijke voordeel van individuele filters is dat ze allemaal verschillend zullen zijn. Als ieders filters verschillende waarschijnlijkheden hebben, zal dit de optimalisatieloop van de spammers, wat programmeurs hun edit-compile-testcyclus zouden noemen, afschuwelijk langzaam maken. In plaats van simpelweg een spam aan te passen totdat deze door een kopie van een filter op hun desktop komt, zullen ze voor elke aanpassing een testmailing moeten doen. Het zou zijn als programmeren in een taal zonder interactieve toplevel, en dat zou ik niemand toewensen.

Noten

[1] Paul Graham. "A Plan for Spam." Augustus 2002. http://paulgraham.com/spam.html.

Waarschijnlijkheden in dit algoritme worden berekend met behulp van een degeneratieve vorm van de Regel van Bayes. Er zijn twee vereenvoudigende aannames: dat de waarschijnlijkheden van kenmerken (d.w.z. woorden) onafhankelijk zijn, en dat we niets weten over de prior waarschijnlijkheid dat een e-mail spam is.

De eerste aanname is wijdverbreid in tekstclassificatie. Algoritmen die het gebruiken, worden "naive Bayesian" genoemd.

De tweede aanname deed ik omdat de verhouding van spam tot niet-spam in mijn inkomende e-mail van dag tot dag (sterker nog, van uur tot uur) zo sterk fluctueerde dat de algehele prior ratio waardeloos leek als voorspeller. Als je aanneemt dat P(spam) en P(nonspam) beide 0.5 zijn, heffen ze elkaar op en kun je ze uit de formule verwijderen.

Als je Bayesiaanse filtering zou toepassen in een situatie waarin de verhouding van spam tot niet-spam consistent erg hoog of (vooral) erg laag was, zou je de prestaties van het filter waarschijnlijk kunnen verbeteren door prior waarschijnlijkheden op te nemen. Om dit goed te doen, zou je verhoudingen per tijdstip moeten bijhouden, omdat zowel spam als legitieme mailvolume duidelijke dagelijkse patronen hebben.

[2] Patrick Pantel en Dekang Lin. "SpamCop-- A Spam Classification & Organization Program." Proceedings of AAAI-98 Workshop on Learning for Text Categorization.

[3] Mehran Sahami, Susan Dumais, David Heckerman en Eric Horvitz. "A Bayesian Approach to Filtering Junk E-Mail." Proceedings of AAAI-98 Workshop on Learning for Text Categorization.

[4] Op dat moment had ik nul false positives van ongeveer 4.000 legitieme e-mails. Als de volgende legitieme e-mail een false positive was, zou dit ons 0.03% opleveren. Deze false positive rates zijn onbetrouwbaar, zoals ik later zal uitleggen. Ik citeer hier een getal alleen om te benadrukken dat wat de false positive rate ook is, deze minder is dan 1.16%.

[5] Bill Yerazunis. "Sparse Binary Polynomial Hash Message Filtering and The CRM114 Discriminator." Proceedings of 2003 Spam Conference.

[6] In "A Plan for Spam" gebruikte ik drempels van 0.99 en 0.01. Het lijkt gerechtvaardigd om drempels te gebruiken die evenredig zijn met de grootte van de corpora. Aangezien ik nu ongeveer 10.000 van elk type e-mail heb, gebruik ik 0.9999 en 0.0001.

[7] Hier is een fout die ik waarschijnlijk zou moeten corrigeren. Momenteel, wanneer "Subjectfoo" degradeert tot alleen "foo", betekent dit dat je de statistieken krijgt voor voorkomens van "foo" in de hoofdtekst of headerregels anders dan degene die ik markeer. Wat ik zou moeten doen, is statistieken bijhouden voor "foo" in het algemeen, evenals specifieke versies, en degraderen van "Subjectfoo" niet naar "foo", maar naar "Anywhere*foo". Hetzelfde geldt voor hoofdletters: ik zou moeten degraderen van hoofdletters naar willekeurige hoofdletters, niet naar kleine letters.

Het zou waarschijnlijk een winst zijn om dit ook met prijzen te doen, bijvoorbeeld om te degraderen van "$129.99" naar "$--9.99", "$--.99", en "$--".

Je zou ook kunnen degraderen van woorden naar hun stammen, maar dit zou waarschijnlijk alleen de filterpercentages verbeteren in het begin, wanneer je kleine corpora hebt.

[8] Steven Hauser. "Statistical Spam Filter Works for Me." http://www.sofbot.com.

[9] False positives zijn niet allemaal gelijk, en we moeten dit onthouden bij het vergelijken van technieken voor het stoppen van spam. Terwijl veel van de false positives veroorzaakt door filters bijna-spams zullen zijn die je niet erg zou vinden om te missen, zullen false positives veroorzaakt door bijvoorbeeld blacklists gewoon e-mails zijn van mensen die de verkeerde ISP hebben gekozen. In beide gevallen vang je e-mail die dicht bij spam ligt, maar voor blacklists is de nabijheid fysiek, en voor filters tekstueel.

[10] Als spammers goed genoeg worden in het verhullen van tokens zodat dit een probleem wordt, kunnen we reageren door simpelweg witruimte, punten, komma's, enz. te verwijderen en een woordenboek te gebruiken om de woorden uit de resulterende reeks te halen. En natuurlijk zou het vinden van woorden op deze manier die niet zichtbaar waren in de originele tekst, op zichzelf al bewijs van spam zijn.

Het uitkiezen van de woorden zal niet triviaal zijn. Het vereist meer dan alleen het reconstrueren van woordgrenzen; spammers voegen ("xHot nPorn cSite") en laten weg ("P#rn") letters weg. Zichtonderzoek kan hier nuttig zijn, aangezien het menselijk zicht de limiet is die dergelijke trucs zullen benaderen.

[11] Over het algemeen zijn spams repetitiever dan reguliere e-mail. Ze willen die boodschap erin rammen. Ik sta momenteel geen duplicaten toe in de top 15 tokens, omdat je een false positive kunt krijgen als de afzender toevallig een slecht woord meerdere keren gebruikt. (In mijn huidige filter heeft "dick" een spamwaarschijnlijkheid van 0.9999, maar het is ook een naam.) Het lijkt erop dat we duplicatie op zijn minst moeten opmerken, dus ik zal proberen tot twee van elk token toe te staan, zoals Brian Burton doet in SpamProbe.

[12] Dit is waar benaderingen zoals die van Brightmail op zullen uitdraaien zodra spammers gedwongen worden om mad-lib technieken te gebruiken om al het andere in het bericht te genereren.

[13] Er wordt soms beweerd dat we op netwerkniveau zouden moeten werken aan filtering, omdat het efficiënter is. Wat mensen meestal bedoelen als ze dit zeggen, is: we filteren momenteel op netwerkniveau, en we willen niet opnieuw beginnen. Maar je kunt het probleem niet dicteren om bij je oplossing te passen.

Historisch gezien zijn schaarse-hulpbronnenargumenten de verliezende partij geweest in debatten over softwareontwerp. Mensen gebruiken ze meestal alleen om keuzes (vooral inactiviteit) te rechtvaardigen die om andere redenen zijn gemaakt.

Dank aan Sarah Harlin, Trevor Blackwell en Dan Giffin voor het lezen van concepten van dit artikel, en nogmaals aan Dan voor de meeste infrastructuur waarop dit filter draait.

Gerelateerd: