Clasificator bayesian naiv

În învățarea automată, clasificatorii bayesieni naivi reprezintă o familie de „clasificatori probabilistici” simpli, bazați pe aplicarea teoremei lui Bayes cu ipoteze puternice (naive) de independență între descriptori.

Aceste modele au fost intens studiate încă din anii 1960. A apărut (deși nu sub acest nume) în comunitatea recuperării de texte la începutul anilor 1960^[1] și rămâne o metodă populară de categorisire de text, care este problema de a eticheta documente ca aparținând unei categorii sau alteia (precum spam sau legitime, sport sau politică etc.) folosind frecvențele cuvintelor drept caracteristici. Adăugând metode adecvate de pre-procesare, un astfel de clasificator poate concura în acest domeniu cu metode mai avansate, printre care mașini cu suport vectorial^[2]. Este utilizat, de asemenea, în diagnosticarea medicală automată^[3].

Clasificatorii naivi bayesieni sunt extrem de scalabili, necesitând un număr de parametri liniar cu numărul de variabile (caracteristici/predictori) într-o problemă de învățare. Antrenarea cu probabilitatea maximă se poate efectua prin evaluarea unei expresii de formă închisă^[4]^:718, care necesită timp liniar, față de aproximarea iterativă mai scumpă folosită pentru multe alte tipuri de clasificatori.

În literatura de statistică și informatică, modelele bayesiene naive sunt cunoscute sub o varietate de nume, inclusiv Bayes simplu și Bayes cu independență^[5]. Toate aceste nume fac referință la utilizarea teoremei lui Bayes în regula de decizie a clasificatorului, dar un mode bayesian naiv nu este (neapărat) o metodă bayesiană^[4]^[5].

Introducere[modificare | modificare sursă]

Bayes naiv este o tehnică simplă pentru construirea clasificatorilor: modele care atribuie etichete de clasă pentru instanțe noi, reprezentate ca vectori de valori pentru diverse caracteristici, unde etichetele de clasă fac parte trase dintr-o mulțime finită. Nu există un singur algoritm pentru antrenarea astfel de clasificatori, ci o familie de algoritmi bazați pe un principiu comun: toți clasificatorii bayesieni naivi presupun că valoarea unei anumite caracteristică este independentă de valoarea oricărei altă caracteristici, dat fiind variabila de clasă. De exemplu, un fruct poate fi considerat a fi un măr dacă este roșu, rotund, și de aproximativ 10 cm în diametru. Un clasificator naiv bayesian consideră că fiecare dintre aceste caracteristici contribuie în mod independent la probabilitatea ca acest fruct să fie un măr, indiferent de eventualele corelații între culoare, rotunjime și diametru.

Pentru unele tipuri de modele de probabilitate, clasificatorii bayesieni naivi pot fi antrenați foarte eficient în contextul învățării supervizate. În multe aplicații practice, pentru estimarea parametrilor pentru modelele bayesiene naiv se folosește metoda de probabilitate maximă. Cu alte cuvinte, se poate lucra cu modelul naiv bayesian fără a accepta probabilitatea bayesiană sau a folosi orice metode bayesiene.

În ciuda designului naiv și ipotezelor aparent supra-simplificate, clasificatorii bayesieni naivi funcționează destul de bine în multe situații reale complexe. În 2004, o analiză a problemei de clasificare bayesiene a arătat că există motive teoretice pentru eficacitatea aparent neverosimilă a clasificatorilor bayesieni naivi^[6]. Totuși, o comparație cuprinzătoare cu alți algoritmi de clasificare din 2006 a arătat că această metodă este depășită de alte abordări, precum păduri de arbori decizionali^[7].

Un avantaj al acestui clasificator bayesian naiv este că necesită doar un număr mic de date de antrenament pentru a estima parametrii necesari pentru clasificare^{[necesită citare]}.

Model probabilistic[modificare | modificare sursă]

Abstract, Bayes naiv este un model de probabilitate condiționată: având o instanță pentru clasificare, reprezentată printr-un vector $\mathbf {x} =(x_{1},\dots ,x_{n})$ de $n$ caracteristici (variabile independente), se atribuie acestei instanțe probabilitățile

p(C_{k}\mid x_{1},\dots ,x_{n})\,

pentru fiecare $K$ rezultate posibile sau clase $C_{k}$ ^[8].

Formularea de mai sus este problematică în sensul că dacă numărul de caracteristici $n$ este mare sau dacă o caracteristică poate avea un număr mare de valori, atunci un astfel de model bazat pe tabele de probabilitate devine nefezabil. Prin urmare, reformularea modelului pentru a-l face fezabil folosește teorema lui Bayes, unde probabilitatea condiționată poate fi descompusă ca

p(C_{k}\mid \mathbf {x} )={\frac {p(C_{k})\ p(\mathbf {x} \mid C_{k})}{p(\mathbf {x} )}}\,

Cu alte cuvinte, folosind terminologia din probabilitatea bayesiană, ecuația de mai sus poate fi scrisă ca

{\text{posterior}}={\frac {{\text{prior}}\times {\text{posibilitate}}}{\text{medie}}}\,

În practică, este relevant doar numărătorul acestei fracții, deoarece numitorul nu depinde de $C$ și valorile $x_{i}$ sunt cunoscute, fiind astfel constant. Numărătorul este echivalent cu probabilitatea comună

p(C_{k},x_{1},\dots ,x_{n})\,

care poate fi rescrisă după cum urmează, utilizând regula lanțului pentru aplicarea repetată a definiției probabilității condiționate:

{\begin{aligned}p(C_{k},x_{1},\dots ,x_{n})&=p(x_{1},\dots ,x_{n},C_{k})\\&=p(x_{1}\mid x_{2},\dots ,x_{n},C_{k})\ p(x_{2},\dots ,x_{n},C_{k})\\&=p(x_{1}\mid x_{2},\dots ,x_{n},C_{k})\ p(x_{2}\mid x_{3},\dots ,x_{n},C_{k})\ p(x_{3},\dots ,x_{n},C_{k})\\&=\dots \\&=p(x_{1}\mid x_{2},\dots ,x_{n},C_{k})\ p(x_{2}\mid x_{3},\dots ,x_{n},C_{k})\dots p(x_{n-1}\mid x_{n},C_{k})\ p(x_{n}\mid C_{k})\ p(C_{k})\\\end{aligned}}

Acum poate fi aplicată independența condiționată naivă: să presupunem că toate caracteristicile din $\mathbf {x}$ sunt reciproc independente, condiționate de categoria $C_{k}$ . Sub această ipoteză,

p(x_{i}\mid x_{i+1},\dots ,x_{n},C_{k})=p(x_{i}\mid C_{k})\,

.

Astfel, în modelul comun poate fi exprimat ca

{\begin{aligned}p(C_{k}\mid x_{1},\dots ,x_{n})&\varpropto p(C_{k},x_{1},\dots ,x_{n})\\&=p(C_{k})\ p(x_{1}\mid C_{k})\ p(x_{2}\mid C_{k})\ p(x_{3}\mid C_{k})\ \cdots \\&=p(C_{k})\prod _{i=1}^{n}p(x_{i}\mid C_{k})\,,\end{aligned}}

unde $\varpropto$ denotă proporționalitatea.

Acest lucru înseamnă că, sub ipoteza de independență de mai sus, distribuția condiționată a variabilei $C$ este:

p(C_{k}\mid x_{1},\dots ,x_{n})={\frac {1}{Z}}p(C_{k})\prod _{i=1}^{n}p(x_{i}\mid C_{k})

unde media $Z=p(\mathbf {x} )=\sum _{k}p(C_{k})\ p(\mathbf {x} \mid C_{k})$ este un factor de scalare care depinde doar de $x_{1},\dots ,x_{n}$ , adică este o constantă dacă valorile caracteristicii variabile sunt cunoscute.

Construirea unui clasificator de la modelul de probabilitate[modificare | modificare sursă]

Discuția de până acum a derivat modelul de caracteristici independente, adică modelul de probabilitate bayesian naiv. Clasificatorul bayesian naiv combină acest model cu o regulă de decizie. O regulă des utilizată este alegerea ipotezei care este mai probabilă. Aceasta este cunoscută drept maximum a posteriori sau regula de decizie MAP. Clasificatorul bayesian corespunzător este o funcție care atribuie o clasă ${\hat {y}}=C_{k}$ pentru un $k$ după cum urmează:

{\hat {y}}={\underset {k\in \{1,\dots ,K\}}{\operatorname {argmax} }}\ p(C_{k})\displaystyle \prod _{i=1}^{n}p(x_{i}\mid C_{k}).

Exemplu[modificare | modificare sursă]

Clasificarea persoanelor[modificare | modificare sursă]

Problemă: clasificați dacă o anumită persoană este bărbat sau femeie, pe baza unor caracteristici măsurate. Caracteristicile includ înălțimea, greutatea și mărimea piciorului.

Antrenare[modificare | modificare sursă]

Un exemplu de set de date de antrenament este oferit mai jos.

Persoana	înălțime (m)	greutate (kg)	mărimea piciorului (cm)
bărbat	1,83	81,65	30,48
bărbat	1,80	86,18	27,94
bărbat	1,70	77,11	30,48
bărbat	1,80	74,84	25,4
femeie	1,52	45,36	15,24
femeie	1,67	68,04	20,32
femeie	1,65	58,97	17,78
femeie	1,75	68,04	22,86

Clasificatorul creat din setul de antrenament folosind o distribuție ipotetic Gaussiană ar fi:

Persoana	medie (înălțime)	varianța (înălțime)	medie (greutate)	varianța (greutate)	medie (mărimea piciorului)	varianța (mărimea piciorului)
bărbat	1,7825	3,2250*10⁻³	79,94	0,2529*10²	28,57	5,9139
femeie	1,6475	9,0917*10⁻³	60,10	1,1487*10²	19,05	0,1075*10²

Să presupunem că avem clase cu probabilitate egală, astfel încât P(bărbat)= P(femeie) = 0,5. Această probabilitate a priori ar putea fi bazată pe cunoașterea de frecvențe pe o populație mai mare sau a frecvenței în setul de antrenament.

Testare[modificare | modificare sursă]

Mai jos este un set de date care trebuie clasificate ca bărbat sau femeie.

Persoana	înălțime (m)	greutate (kg)	mărimea piciorului (cm)
test	1,83	58,97	20,32

Dorim să determinăm care probabilitate posterioară este mai mare, bărbat sau femeie. Pentru clasificarea ca bărbat, probabilitatea este dată de

{\text{posterior (bărbat)}}={\frac {P({\text{bărbat}})\,p({\text{înălțime}}\mid {\text{bărbat}})\,p({\text{greutate}}\mid {\text{bărbat}})\,p({\text{picior}}\mid {\text{bărbat}})}{medie}}

Pentru clasificarea ca femeie, probabilitatea este dată de

{\text{posterior (femeie)}}={\frac {P({\text{femeie}})\,p({\text{înălțime}}\mid {\text{femeie}})\,p({\text{greutate}}\mid {\text{femeie}})\,p({\text{picior}}\mid {\text{femeie}})}{medie}}

Media așteptată (numită, de asemenea, constantă de normalizare) poate fi calculată:

${\begin{aligned}{\text{evidence}}=P({\text{bărbat}})\,p({\text{înălțime}}\mid {\text{bărbat}})\,p({\text{greutate}}\mid {\text{bărbat}})\,p({\text{picior}}\mid {\text{bărbat}})\\+P({\text{femeie}})\,p({\text{înălțime}}\mid {\text{femeie}})\,p({\text{greutate}}\mid {\text{femeie}})\,p({\text{picior}}\mid {\text{femeie}})\end{aligned}}$

Cu toate acestea, având în vedere datele, media este constantă și, astfel, normalizează în mod egal ambele probabilități posterioare. Prin urmare, nu afectează clasificarea și poate fi ignorată. Acum putem determina distribuția de probabilitate pentru sexul datelor de test.

P({\text{bărbat}})=0.5

p({\text{înălțime}}\mid {\text{bărbat}})={\frac {1}{\sqrt {2\pi \sigma ^{2}}}}\exp \left({\frac {-(1,83-\mu )^{2}}{2\sigma ^{2}}}\right)\approx 4,9515

,

unde $\mu =1,7825$ și $\sigma ^{2}=3,2250\cdot 10^{-3}$ sunt parametrii distribuției normale care au fost determinate anterior din setul de antrenament. Este important de reținut că o valoare mai mare decât 1 este în regulă aici – este o densitate de probabilitate în loc de o probabilitate, pentru că înălțimea este variabilă continuă.

p({\text{greutate}}\mid {\text{bărbat}})=1,3255\cdot 10^{-5}

p({\text{picior}}\mid {\text{bărbat}})=5,1624\cdot 10^{-4}

{\text{numărătorul posteriorului (bărbat)}}={\text{produsul lor}}=1,6941\cdot 10^{-8}

P({\text{femeie}})=0.5

p({\text{înălțime}}\mid {\text{femeie}})=6,7004\cdot 10^{-1}

p({\text{greutate}}\mid {\text{femeie}})=3,7015\cdot 10^{-2}

p({\text{picior}}\mid {\text{femeie}})=1,1287\cdot 10^{-1}

{\text{numărătorul posteriorului (femeie)}}={\text{produsul lor}}=1,3997\cdot 10^{-3}

Deoarece numărătorul posteriorului este mai mare în cazul femeii, putem prezice că datele de test aparțin unei femei.

Vezi și[modificare | modificare sursă]

Note[modificare | modificare sursă]

^ Maron, M. E. (1961). „Automatic Indexing: An Experimental Inquiry” (PDF). Journal of the ACM. 8 (3): 404–417. doi:10.1145/321075.321084.
^ Rennie, J.; Shih, L.; Teevan, J.; Karger, D. (2003). Tackling the poor assumptions of Naive Bayes classifiers (PDF). ICML.
^ Rish, Irina (2001). An empirical study of the naive Bayes classifier (PDF). IJCAI Workshop on Empirical Methods in AI. Arhivat din original (PDF) la 10 decembrie 2017. Accesat în 2 iunie 2019.
^ ^a ^b Russell, Stuart; Norvig, Peter (2003) [1995]. Artificial Intelligence: A Modern Approach^⁠(d) (ed. 2nd). Prentice Hall. ISBN 978-0137903955.
^ ^a ^b Hand, D. J.; Yu, K. (2001). „Idiot's Bayes — not so stupid after all?”. International Statistical Review. 69 (3): 385–399. doi:10.2307/1403452. ISSN 0306-7734. JSTOR 1403452.
^ Zhang, Harry. The Optimality of Naive Bayes (PDF). FLAIRS2004 conference.
^ Caruana, R.; Niculescu-Mizil, A. (2006). An empirical comparison of supervised learning algorithms. Proc. 23rd International Conference on Machine Learning.
^ Narasimha Murty, M.; Susheela Devi, V. (2011). Pattern Recognition: An Algorithmic Approach. ISBN 978-0857294944.

Bibliografie suplimentară[modificare | modificare sursă]

Domingos, Pedro; Pazzani, Michael (1997). „On the optimality of the simple Bayesian classifier under zero-one loss”. Machine Learning. 29 (2/3): 103–137. doi:10.1023/A:1007413511361.
Webb, G. I.; Boughton, J.; Wang, Z. (2005). „Not So Naive Bayes: Aggregating One-Dependence Estimators”. Machine Learning. 58 (1): 5–24. doi:10.1007/s10994-005-4258-6.
Mozina, M.; Demsar, J.; Kattan, M.; Zupan, B. (2004). Nomograms for Visualization of Naive Bayesian Classifier (PDF). Proc. PKDD-2004. pp. 337–348.
Maron, M. E. (1961). „Automatic Indexing: An Experimental Inquiry”. Journal of the ACM. 8 (3): 404–417. doi:10.1145/321075.321084.
Minsky, M. (1961). Steps toward Artificial Intelligence. Proc. IRE. 49. pp. 8–30.

[1] Maron, M. E. (1961). „Automatic Indexing: An Experimental Inquiry” (PDF). Journal of the ACM. 8 (3): 404–417. doi:10.1145/321075.321084.

[rennie-2] Rennie, J.; Shih, L.; Teevan, J.; Karger, D. (2003). Tackling the poor assumptions of Naive Bayes classifiers (PDF). ICML.

[rish-3] Rish, Irina (2001). An empirical study of the naive Bayes classifier (PDF). IJCAI Workshop on Empirical Methods in AI. Arhivat din original (PDF) la 10 decembrie 2017. Accesat în 2 iunie 2019.

[aima-4] Russell, Stuart; Norvig, Peter (2003) [1995]. Artificial Intelligence: A Modern Approach^⁠(d) (ed. 2nd). Prentice Hall. ISBN 978-0137903955.

[idiots-5] Hand, D. J.; Yu, K. (2001). „Idiot's Bayes — not so stupid after all?”. International Statistical Review. 69 (3): 385–399. doi:10.2307/1403452. ISSN 0306-7734. JSTOR 1403452.

[6] Zhang, Harry. The Optimality of Naive Bayes (PDF). FLAIRS2004 conference.

[7] Caruana, R.; Niculescu-Mizil, A. (2006). An empirical comparison of supervised learning algorithms. Proc. 23rd International Conference on Machine Learning.

[8] Narasimha Murty, M.; Susheela Devi, V. (2011). Pattern Recognition: An Algorithmic Approach. ISBN 978-0857294944.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]