Teorema lui Bayes

Panou de neon la Autonomy Corporation, arătând formula simplificată a teoremei 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), K₀ și K₁, respectiv P(C|K₀) și P(C|K₁). 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 C_i care există în K₀ dar nu există în K₁, se adaugă un cuvânt de acesta în K₁, mărind numărul total de cuvinte, și schimbând probabilitățile apariției fiecărui cuvânt, și anume P(C_i) și P(C_i|K₁). 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:

$S_{j}=\prod _{i=1}^{n}{\frac {P(C_{i}|K_{j})}{P(C_{i})}}$

unde S_j este punctajul pentru categoria j, C_i - un cuvânt din mesajul nou, n - numărul de cuvinte din mesajul nou, K_j - 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:

$S_{0}={\frac {0.001}{0.0007}}\cdot {\frac {0.000167}{0.0003}}\approx 0.7952$

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

$S_{1}={\frac {0.00025}{0.0007}}\cdot {\frac {0.0005}{0.0003}}\approx 0,5952$

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ă:

$S'_{j}=\sum _{i=1}^{n}\log {\frac {P(C_{i}|K_{j})}{P(C_{i})}}$

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:

$S_{j}=10^{S'_{j}}$

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.

Bibliografie

• McGrayne, Sharon Bertsch (2011). The Theory That Would Not Die: How Bayes' Rule Cracked the Enigma Code, Hunted Down Russian Submarines & Emerged Triumphant from Two Centuries of Controversy. Yale University Press. ISBN 978-0-300-18822-6. 
• 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 [1] Arhivat în 27 iulie 2011, la Wayback Machine..
• 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.
• Hazewinkel, Michiel, ed. (2001), „Bayes formula”, Encyclopaedia of Mathematics, Kluwer Academic Publishers, ISBN 978-1556080104 
• 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".
• Eric W. Weisstein, Bayes' Theorem la MathWorld.
• Bayes' theorem la PlanetMath
• A tutorial on probability and Bayes’ theorem devised for Oxford University psychology students
• An Intuitive Explanation of Bayes' Theorem by Eliezer S. Yudkowsky