Jistě jste o něm slyšeli. Filtr, který dokáže eliminovat většinu reklamních e-mailů – takzvaný spam. Princip funkce je jednoduchý – uživatel algoritmu předá několik vzorových zpráv, které jsou spamem, a které nejsou (těm se říká ham). Ten si na základě jistých statistických metod všechno "zapamatuje", a poté je schopen určit, co je spam, a co není.
Tohle byl popis z hlediska uživatele, ale co se skrývá pod pokličkou? Jak je Bayesův filtr účinný? Ačkoliv problematika spadá do oblasti informatiky s názvem strojové učení (machine learning), metoda je překvapivě jednoduchá. Je založena na tvrzení nazývaném O pravděpodobnosti příčin, jež poprvé vyslovil a dokázal matematik Thomas Bayes, a které se v jednoduché formě učí na středních školách v kapitole o pravděpodobnosti.
Tvrzení mohu vysvětlit matematicky, nebo prakticky. Zvolím druhou variantu, jeden příklad je lepší než tisíc vzorců. Dovolím si použít příklad od Paula Grahama (paulgraham.com/naivebayes.html). Předpokládejme, že člověk měřící více než 190 centimetrů je z 60% basketbalista a dále člověk, který má v ruce basketbalový míč, že je z 72% basketbalista. Nyní se zamysleme, jaká je pravděpodobnost, že člověk měřící nad 190 centimetrů s basketbalovým míčem v ruce je basketbalista.
Bayes zjistil, že pokud máme dva neslučitelné jevy, jejichž průnikem je jev jistý (tzv. úplný systém jevů), pak se pravděpodobnost po provedení pokusu, při kterém nastaly oba jevy, dá snadno vypočítat. V našem jednoduchém případě o dvou jevech by to podle Bayesova vzorce bylo (0,6 * 0,72) / [(0,6 * 0,72) + (1 - 0,6) * (1 - 0,72)]. Výsledkem je 0,794, což mi trošku připomnělo základní školu a paní učitelku, která mě nabádala odpovídat celou větou: Pravděpodobnost, že vysoký člověk s míčem je basketbalistou, je 79,4%. Podobný vzorec platí nejen pro dvojici, ale také obecně pro n jevů (k pochopení obecného vzorce je nutná základní znalost teorie pravděpodobnosti, dobrou stránkou je například en.wikipedia.org/wiki/Bayes'_theorem).
Bayesovo filtrování funguje právě na uvedeném principu, přičemž se předpokládá, že jevy jsou nezávislé, což v praxi není pravda. I přesto metoda (někdy označovaná jako "naivní") podává výborné výsledky. Mějme množinu textů (e-mailů), které jsou spamem, a množinu textů, již spamem nejsou (ham). Je nutno si uvědomit, že příliš nezáleží na počtu těchto textů jako spíše na jejich "kvalitě" – měly by pokrývat svým obsahem širokou škálu e-mailů obsahově reklamních, respektive "čistých". Nejdříve první i druhou množinu profiltrujeme a rozdělíme ji na slova. Dnešní filtry umějí odhalit slova z hlavičky e-mailu nebo HTML, nám postačí obyčejné rozdělení na slova, přičemž je vhodné zachovat velikost písmen (nekonvertovat vše na malá). Nyní se spočtou výskyty slov, což je jednoduchá operace, kterou počítač pomocí hashovacích tabulek zvládne velmi rychle. Tuto strukturu je možné velmi snadno a efektivně ukládat i aktualizovat.
Přichází nejtěžší část – je nutno z obou tabulek (slovo-počet výskytů) sestavit tabulku jednu (slovo-pravděpodobnost), ve které bude uvedeno, s jakou pravděpodobností se dané slovo vyskytuje ve spamu resp. hamu. Číslo 0,5 bude reprezentovat stejný počet ham-slov i spam-slov v obou množinách, číslo 0,01 bude znamenat, že se slovo vyskytuje pouze jako ham a 0,99 pouze jako spam. Není však dobré tuto tabulku vytvořit pouhým sloučením obou počtů, pokusy ukazují, že je dobré počty ham-slov násobit dvěma – filtr je pak přesnější. Každá implementace to má jinak, právě na tomto místě je prostor pro další bádání a testy.
Jestliže vytvoření bayesovských tabulek slov bylo rychlé, klasifikace příchozího e-mailu (jestli je, nebo není spam) je ještě rychlejší. Text se rozdělí na slova a v tabulkách se vyhledají pravděpodobnosti všech těchto slov. Vybere se rozumný počet (zdroje uvádějí například patnáct) slov, která mají pravděpodobnost nejdále od středu, tj. 0,5. Na tyto pravděpodobnosti se použije Bayesovo pravidlo a výsledkem je pravděpodobnost, že je daný e-mail spam.
Malý příklad vybereme z reklamního mailu tato (pro didaktické účely pouze tři) "nejzajímavější" slova: sex (91%), viagra (99%) a Perl (0,09%). Jak je vidět, slovo "sex" se vyskytovalo ve spamu často, "viagra" se nikdy v hamu nevyskytovala (výchozí hodnota 0,99) a slovo "Perl" se ve spamu zřejmě párkrát již vyskytlo (spammeři se snaží na konec reklamních mailů zařazovat slova netýkající se tématu). Pravděpodobnost, že daný e-mail je spam je (0.91 * 0.99 * 0.09) / ((0.91 * 0.99 * 0.09) + (1 - 0.91) * (1 - 0.99) * (1 - 0.09)) = 0,99. Takový e-mail je z 99% spam.
A jak je bayesovský filtr účinný? To je těžká otázka, záleží na tom, jak si ho "vychová" sám uživatel. Pokud mu dodá nevhodné vzorky, nemusí být účinný vůbec, ale jestliže někdo pečlivě označuje reklamní zprávy, pak se účinnost blíží ke 100%. Záleží na implementaci – dnešní filtry se umějí vypořádat s různými technikami, kterými se snaží spammeři tuto metodu oblafnout. Například SpamAssassin přidává různé heuristické testy a takzvané bonusy, které při správném nastavení ve výsledku fungují téměř s jistotou.
Bayesova metoda nachází uplatnění nejen při boji se spamem, ale v libovolné kategorizaci textů (dokumentů). Následující odstaveček bude takovým nahlédnutím do oblasti dolování dat (data mining). Představte si, že máte obrovský počet dokumentů o Linuxu (které jste například stáhli pomocí Google vyhledávače), ale zajímají vás jen některé články (například kde se srovnává výkon Linuxu a operačního systému Solaris). Bayesovu kategorizaci využijete tak, že přečtete například sto článků a u každého stanovíte, zda je to pro vás článek zajímavý nebo nezajímavý. Na zbytek textů použijete Bayesův algoritmus a jestliže vyberete pro obě třídy vhodné vzory, algoritmus velmi rychle dokumenty rozdělí do dvou tříd. V jedné najdete pro vás zajímavé dokumenty (kde se budou vyskytovat podobná slova), v té druhé pak zbytek.
