Teorema lui Bayes

Teorema lui Bayes este una din teoremele fundamentale ale teoriei probabilităților, care determină probabilitatea apartenenței evenimentelor și a obiectelor la o anumită grupă. A fost enunțată de matematicianul britanic Thomas Bayes.

Aplicații în domeniul informaticii
În cazul filtrelor spam bazate pe teorema lui Bayes (numite și filtre bayesiene), pentru determinarea probabilității apartenenței unui anumit mesaj la spam, sunt utilizate dicționarele create în timpul „învățării” filtrului. De regulă programul „învață” analizând arhivele de e-mail-uri, selectate în prealabil manual. Când dicționarele sunt create definitiv, probabilitatea apartenenței unui nou mesaj la spam este calculată prin normalizarea și sumarea probabilității fiecărui cuvânt în parte. Prin urmare, adunând informații statistice despre rata de apariție a unor diferite cuvinte și structuri în mesajele de tip spam sau în mesajele legitime, filtrul compară apoi noile mesaje cu aceste modele și le clasifică corespunzător.

Filtrele bayesiene oferă o precizie de filtrare de 97%-99%, iar fiind corect „antrenat” se poate apropia de 100%.

Descrierea clasificatorului Bayes Naiv
Pentru exemplu luăm același filtru de spam. Construirea algoritmului de clasificare a unui mesaj în anumite categorii predefinite presupune 2 etape:

Antrenarea sistemului
Se construiește o bază de date de cuvinte, și probabilitatea apariției lor într-un mesaj dintr-o anumită categorie. În cazul dat avem 2 categorii: "spam", și "nu spam". Se realizează aceasta prin analiza unui număr mare de mesaje, marcate manual ca "spam", și alt număr mare de mesaje marcat ca "nu spam". Din fiecare mesaj se extrag doar cuvintele, și se calculează probabilitatea apariției fiecărui cuvânt (C), în una din categorii (K), K0 și K1, respectiv P(C|K0) și P(C|K1). Simultan se calculează și probabilitatea apariției acestui cuvânt în general, necătând la categorie (ceea ce denotă frecvența utilizării lui în limbaj în general), P(C). Cel mai des, există cuvinte care au fost depistate în doar o categorie. Un sistem antrenat pe acest principiu va considera că probabilitatea folosirii lui într-un mesaj din a doua categorie este zero, ceea ce ulterior putem vedea că are efecte devastatoare la rezultat. Din această cauză, pentru fiecare cuvânt Ci care există în K0 dar nu există în K1, se adaugă un cuvânt de acesta în K1, mărind numărul total de cuvinte, și schimbând probabilitățile apariției fiecărui cuvânt, și anume P(Ci) și P(Ci|K1). Nici o categorie nu trebuie să conțină cuvinte cu probabilitatea zero.
Exemplu:
Având 2 categorii, "nu spam" și "spam", și în total 9998 de cuvinte în toate mesajele cercetate, dintre care 3999 cuvinte în "nu spam" și 5999 cuvinte în categoria "spam", (printre altele aceasta este foarte puțin, dar pentru exemplu se potrivește), cuvântul "cumpără" este prezent în total de 6 ori, dintre care de 6 ori în mesaje marcate drept spam, și niciodată în mesajele marcate drept "nu spam". Iar cuvântul "raport" este de 2 ori observat în categoria "nu spam" și de 0 ori în categoria "spam". Suntem nevoiți să considerăm că cuvântul "cumpără" este prezent o dată în categoria "nu spam", iar cuvântul "raport" este prezent o dată în categoria "spam". Astfel adăugăm 2 cuvinte la numărul total, și câte un cuvânt în fiecare categorie, ducând numărul total la 10000 de cuvinte, și 4000 de cuvinte în "nu spam", și respectiv 6000 de cuvinte în "spam". Probabilitățile care ne interesează deci sunt:
P("cumpără") = (6+1)/(9998+2) = 0.0007,
P("cumpără"|"spam") = 6/(5999+1) = 0.001,
P("cumpără"|"nu spam") = 1/(3999+1) = 0.00025,
P("raport") = (2+1)/(9998+2) = 0.0003,
P("raport"|"spam") = 1/(5999+1) = 0.000167,
P("raport"|"nu spam") = 2/(3999+1) = 0,0005

Utilizarea clasificatorului
Primind un mesaj nou, se calculează "punctajul" mesajului în fiecare categorie. Acest punctaj este reprezentat prin următorul produs:

unde Sj este punctajul pentru categoria j, Ci - un cuvânt din mesajul nou, n - numărul de cuvinte din mesajul nou, Kj - una din categorii. 
Deci în exemplul nostru dacă mesajul nou este "cumpără raport":
 j = 0 sau 1, în dependență de "spam" și "nu spam"
 n = 2 deoarece avem 2 cuvinte
Punctajul oferit mesajului pentru categoria "spam" este:

Iar punctajul oferit mesajului pentru categoria "nu spam" este:

Observați că în sumă nu dă 1, cum s-ar aștepta de la probabilități, deoarece deși lucrăm cu probabilități, rezultatul nu reprezintă o probabilitate. Doar după normalizare putem conclude că probabilitatea apartenenței mesajului în categoria "spam" este de aproximativ 0.5719, iar apartenenței sale în categoria "nu spam" este de 0.4281.
Observați că dacă n-am introduce sintetic cuvinte în categorii pentru a evita probabilitatea zero, primeam punctajul pentru ambele categorii egal cu zero.

Deoarece în tehnologiile informaționale se folosesc tipuri de date cu precizie limitată, utilizarea acestui algoritm în forma actuală este descurajată, deoarece produsul numerelor atât de mici, în final, o să cauzeze probleme mari cu precizia rezultatului. În loc de a calcula produsul produsul indicat anterior, se recomandă calculul sumei logaritmilor, primind această formulă:

Pentru a utiliza clasificatorul este suficient de ales S'j maximal pentru a plasa mesajul în acea categorie. Relația între S și S' este următoarea:

Deoarece în mesajul nou primit pot exista cuvinte care nu au fost prezente în mesajele folosite la etapa antrenamentului (cauzând anularea punctajului sau chiar diviziunea la zero), la depistarea acestor cuvinte, modelul pentru antrenament este ajustat, și aceste cuvinte sunt adăugate în fiecare caregorie unde lipsesc, sporind și numărul de cuvinte total în setul de antrenament.
Deoarece cuvintele "cumpără" și "cumpărați" sunt diferite, dar înseamnă același lucru, cuvintele pot fi transformate prin filtre morfologice, aducând toate derivatele pe bază de gen și număr la un singur cuvânt.

Referințe și note

Bibliografie
 
 Andrew Gelman, John B. Carlin, Hal S. Stern, and Donald B. Rubin (2003), "Bayesian Data Analysis", Second Edition, CRC Press.
 Charles M. Grinstead and J. Laurie Snell (1997), "Introduction to Probability (2nd edition)", American Mathematical Society (free pdf available  .
 Pierre-Simon Laplace. (1774/1986), "Memoir on the Probability of the Causes of Events", Statistical Science 1(3):364–378.
 Peter M. Lee (2012), "Bayesian Statistics: An Introduction", Wiley.
 Rosenthal, Jeffrey S. (2005): "Struck by Lightning: the Curious World of Probabilities". Harper Collings.
 Stephen M. Stigler (1986), "Laplace's 1774 Memoir on Inverse Probability", Statistical Science 1(3):359–363.
 
 Stone, JV (2013). Chapter 1 of book "Bayes’ Rule: A Tutorial Introduction", University of Sheffield, Psychology.

Legături externe 
 SpamAssassin - filtru anti-spam cu funcții de filtrare bayesiană
 SpamBully - filtru anti-spam Bayesian pentru Outlook și Outlook Express
 The Theory That Would Not Die by Sharon Bertsch McGrayne New York Times Book Review by John Allen Paulos on 5 august 2011
 Visual explanation of Bayes using trees (video)
 Bayes' frequentist interpretation explained visually (video)
 Earliest Known Uses of Some of the Words of Mathematics (B). Contains origins of "Bayesian", "Bayes' Theorem", "Bayes Estimate/Risk/Solution", "Empirical Bayes", and "Bayes Factor".
 
 
 A tutorial on  probability and Bayes’ theorem devised for Oxford University psychology students
 An Intuitive Explanation of Bayes' Theorem by Eliezer S. Yudkowsky

Bayes, Teorema lui
Probabilități