Jak funguje bayesovský antispamový filtr? (2.)

Vítám vás u druhého dílu seriálu o bayesovských filtrech. Minule jsem nastínil základní princip práce filtru. Dnešní výklad už nebude tak plynulý. Spíše jej doplním o některé podrobnosti, které jsem minule z důvodu zjednodušení vynechal - především problematiku parseru. Doufám, že se vám tento díl bude líbit stejně jako ten první.

Nejprve trocha abstrakce: Antispamový filtr vlastně implementuje klasifikační úlohu z oblasti umělé inteligence. Vstupem je e-mail, výstupem pak binární hodnota (je/není spam). U každé takovéto úlohy je důležité předzpracování vstupu na hodnoty, které mohou být předmětem nějakého vyhodnocování. Bayesovský filtr převede e-mail na sadu informací (skutečností), jako například „w-mail obsahuje v těle [slovo]“, případně „předmět obsahuje [slovo]“ nebo „odesílací počítač nemá reverzní DNS záznam“, „e-mail nemá předmět“, „e-mail je v HTML“ atd.

Z těchto informací pak algoritmem uvedeným v minulé části spočte výsledek. Ten algoritmus má ale jednu podmínku pro správné fungování, kterou jsem vám minule zatajil. Pravděpodobnosti, se kterými počítá, musí být nezávislé. To však není v praxi splněno. V jazyce se totiž často vyskytují ustálená spojení – v dopisech typicky oslovení: „Dobrý den“, „Vážený pane“ atp. Tedy pravděpodobnost výskytu slova „pane“ je vyšší v dopise, který obsahuje slovo „vážený“, než v tom, který ho neobsahuje. Naštěstí se ukázalo, že vliv těchto spojení není takový, aby práci filtru nějak zásadně ovlivňoval.

Co už ale vadí, je jiná korelace. Původní implementace bayesovského filtru totiž parsovala HTML skoro stejně jako text. Takže se na vstupu filtru objevovaly informace „e-mail obsahuje slovo BODY“, „e-mail obsahuje slovo HREF“ atd. Částečně to bylo k dobru. Například pokud uživatel dostával spamy s červeným textem, tak „slovo“ ff0000 (RGB pro červenou barvu) dostalo vysoké hodnocení a filtr lépe poznával spamy.

Ale problém nastal, pokud uživatel filtru dostával málo HTML hamů a hodně HTML spamů (ty jsou dost časté). Pak dávala všechna „obecná“ HTML slova/skutečnosti poměrně vysokou pravděpodobnost, že e-mail je spam. Když pak uživatel dostal ham v HTML, do výsledného hodnocení se dostala spousta HTML tagů a jmen parametrů. A ty z něj vytlačily všechna slova, která neměla opravdu velmi vysoké nebo nízké hodnocení. Takže e-mail byl většinou označen jako spam.

Všechna tato slova/skutečnosti byla ale důsledkem jen jednoho faktu – e-mail byl poslán v HTML. Tuto skutečnost je samozřejmě možné a vhodné do hodnocení započítat. Ale jelikož je to jedna skutečnost, tak pouze jednou. A ne mnohokrát, jak se to stalo zde. To je ono porušení principu nezávislosti pravděpodobností, které vadí a způsobuje špatnou práci původní verze filtru v takovýchto případech.

Proto musí slušný parser pro bayesovský filtr umět korektně parsovat HTML a extrahovat z něj slova. Přitom může dělat další kontroly – například „e-mail obsahuje obrázek, který je odkazem“, „e-mail obsahuje tag AREA“, „e-mail obsahuje červený text“ a podobně.

Ale ani parser pro normální text není tak úplně jednoduchý, jak by se na první pohled mohlo zdát. Základní otázkou totiž je, co je to vlastně slovo a jaké znaky rozdělují slova. V praxi se ukazuje, že je poměrně dobrým řešením počítat ke slovu co nejvíce znaků – například i vykřičníky na konci. Tím se nám také povede zachytit slova, ve kterých spameři nahradili některá písmena různými znaky (například /iagra).

Rovněž velikost písmen ve slově nese důležitou informaci. Obecně platí, že čím více informací o slově máme, tím lépe filtr funguje, neboť umí lépe rozlišovat různé situace. Na druhou stranu je zvýšená rozlišovací schopnost vykoupena větší databází, z toho vyplývajícím určitým zpomalením a delší dobou učení filtru.

Následující tabulka obsahuje pravděpodobnost pspam u variant slova „free“ a byla (opět) převzata z databáze antispamu Centrum.cz. Docela jasně ukazuje, že rozlišovat mezi variantami má smysl, neboť se jejich pravděpodobnosti dramaticky liší:

Slovo Pravděpodobnost
free 50 %
free! 59 %
FREE 66 %
FREE! 82 %
FREE!!! 93 %
free!!! 100 %

Teď se dostáváme k problému, který byl nakousnut v diskusi k minulému článku. A tím je hamletovské „Lematizovat, či nelematizovat“. K tomu se můžeme postavit třemi způsoby:

  1. převádět všechna slova na základní tvar a používat při vyhodnocování ten,
  2. převést slovo na základní tvar a spolu s ním používat i informaci o původním tvaru (druh slova, pád, čas a podobně),
  3. nelematizovat vůbec, slova brát čistě jako řetězce (různé tvary slov jsou pro nás různá slova).

První dvě možnosti se od sebe liší pouze tím, kolik informací ukládají do databáze, respektive jak podrobné ty informace o slovech jsou. V prvním případě bude databáze menší a filtr se bude rychleji učit. U druhé možnosti tomu bude přesně naopak. Na druhou stranu při jemnějším rozlišení bude mít filtr lepší výsledky – viz výše.

Délku učení lze kompenzovat tím, že pokud se v databázi nevyskytuje slovo v požadovaném tvaru, bude se hledat jiný tvar slova, nebo ještě lépe – bude se vést další databáze bez informací o tvaru slova (jako u první možnosti). A v případě nenalezení konkrétního tvaru se použije hodnota z ní. Tato varianta je z hlediska kvality filtru asi nejlepší.

Třetí možnost se od druhé liší ve dvou bodech. Jednak není možné kompenzovat délku učení. Ale – a to je nejdůležitější – není potřeba žádný lematizátor. Přitom množství informací a tedy i přesnost filtru jsou takřka rovnocenné. Je totiž jedno, jestli mám slovo v databázi uloženo jako „kačeně“, nebo „podstatné jméno kačer, ženský rod, 3. pád“.

Lematizátor je poměrně složitý, potřebuje ne zrovna malou databázi, a je docela pomalý. Navíc bychom museli řešit jeden „drobný“ problém – jakým jazykem je e-mail napsán? Byl by zjevný nesmysl používat český lematizátor na anglický e-mail. Problém se dále komplikuje tím, že různé části e-mailu mohou být v různých jazycích.

KL_NOMINACE

Nevýhodou zůstává pouze zvýšená délka učení. Nicméně i ta v praxi nepůsobí výraznější problémy – zejména proto, že většina spamů je psána anglicky. Takže stačí, aby filtr měl v databázi jen pár (českých) slov z e-mailu. Ta budou mít dostatečně nízkou váhu, aby byl e-mail rozpoznán jako ham.

Proto na celé čáře vítězí možnost třetí. Není o mnoho horší než ideální řešení, zato je řádově jednodušší. „V jednoduchosti je síla“ totiž platí v oblasti antispamů snad více než kde jinde.

Anketa

Kolik spamu denně vám bayesovské filtry pustí?

14 názorů Vstoupit do diskuse
poslední názor přidán 15. 3. 2005 15:53

Školení online marketingu - jak přivádět na web návštěvnost

  • Vyhledavače a PPC kampaně - jak fungují
  • Webová analytika - k čemu jí využít
  • Facebook a další sociální sítě - co a jak komunikovat

Detailní informace o Školení online marketingu »