Universitatea babeş-bolyai cluj-napoca facultatea de matematicǎ Şi informaticǎ specializarea informatică

Clasificatorul optimal Bayes

Acest clasificator mai este numit și algoritmul optim de învățare Bayesiană, având în vedere faptul că nicio altă metodă de clasificare nu poate să îl surclaseze, dacă sunt luate în considerare aceleași cunoștințe inițiale și același spațiu al ipotezelor. Acest lucru se datorează faptului că pentru clasificarea unei instanțe noi sunt observate toate ipotezele h, eliminându-se conceptul de independență al acestora.

Pentru exemplificare, să presupunem că avem un spațiu al ipotezelor , probabilitățile posterioare ale acestora după observarea datelor de antrenament fiind: , , . Corespunzător acestor valori, este ipoteza cu probabilitatea maximă. Considerăm că o instanță nouă a fost clasificată ca fiind corectă de către ipoteza , respectiv greșită de către ipotezele și . Luând toate ipotezele în considerare, probabilitatea ca instanța să fie corectă este 0.5 (valoare corespunzătoare ipotezei ), respectiv 0.8 probabilitatea ca instanța să fie greșită (valoare corespunzătoare însumării probabilitățiler posterioare ale ipotezelor și ). După cum se poate observa, clasificarea noii instanţe negative în cazul de faţă este diferită de clasificarea generată de ipoteza cu probabilitatea maximă.

Astfel, considerăm că probabilitatea unei noi instanțe a cărei clasificări poate lua orice valoare , este determinată de următoarea expresie:

Desigur, scopul nostru este acela de a identifica acea ipoteză cu probabilitatea maximă de a fi corectă, adică valoarea pentru care este maximă:

Ceea ce este interesant la acest clasificator este faptul că există posibilitatea ca anumite predicții să nu corespundă unei anumite ipoteze aflată în spațiul ipotezelor , deoarece etichetarea acestora este diferită de etichetarea instanțelor noi.

O abordare a acestei situații este constituită de considerarea unui spațiu al ipotezelor pentru Clasificatorul optimal Bayes diferit de spațiul ipotezelor pe care este aplicată efectiv teorema lui Bayes. Astfel, conține ipotezele comparative corespunzătoare combinațiilor liniare ale predicțiilor pentru ipotezele din [13].

Din păcate, acest clasificator nu poate fi aplicat în practică decât pentru problemele simple, iar în continuare vor fi prezentate câteva motive:

• 
  Spațiile ipotezelor sunt în general mult prea mari astfel încât iterarea să poată fi facută corespunzător formulei.
  
• 
  Anumite ipoteze reprezintă predicții ale unei singure clase/categorii, astfel că determinarea probabilității pentru fiecare categorie în parte nu își mai are sensul.
  

Având în vedere faptul că algoritmul de clasificare optimal Bayes este destul de costisitor, s-a dorit identificarea unei abordări noi care să elimine acestă problemă. Astfel, a apărut algoritmul Gibbs, o simplificare a predecesorului său, care se axează pe alegerea aleatoare a unei ipoteze în conformitate cu distribuția probabilităților posterioare peste . Această ipoteză aleasă este folosită ulterior pentru clasificarea următoarei instanțe.

Totuși, deși ne-am aștepta la obținerea unui algoritm nu foarte performant, în anumite circumstanțe, eroarea de clasificare obținută este de cel mult două ori mai mare decât eroarea obținută prin utilizarea clasificatorului optimal Bayes.

Această abordare a estimării Bayesiene nu doar că a făcut posibilă rezolvarea problemelor complexe, ci a și devenit o rutină în anumite cazuri în care s-a demonstarat faptul că această metodă de clasificare se pretează cel mai bine.

4. Clasificatorul naiv Bayes

Clasificatorul naiv Bayes (CNB) face parte din familia clasificatorilor probabilistici, are la bază teorema lui Bayes și presupune independența caracteristicilor. A început să fie studiat din anul 1950 și s-a evidențiat prin capacitatea de a surclasa în anumite cazuri alți algoritmi de învățare automată considerați robuști și puternici, precum rețelele neuronale, arborii de decizie sau mașinile cu suport vectorial. În domeniul clasificării documentelor de tip text, clasificatorul naiv Bayes se descurcă neașteptat de bine, mai ales în cazul în care partea de preprocesare este realizată corespunzător.

Este ușor adaptabil, datorită simplității sale. Modelele care asignează etichete instanțelor problemei sunt reprezentate sub forma unui vector de atribute, iar procesul de antrenare decurge foarte bine, mai ales în cazul în care setările sistemului corespund învățării supervizate. În majoritatea aplicațiilor practice, estimarea parametrilor pentru aceste modele naive se realizează prin metoda probabilității maxime, prezentată anterior, nefiind necesară utilizarea altor metode de învățare Bayesiană.

Clasificatorul naiv Bayes se aplică la acele probleme de învățare, unde fiecare instanță este descrisă de succesiunea unor valori corespunzătoare atributelor , iar fiecare funcție target poate lua orice valoare dintr-un spațiu finit .

Algoritmul de învățare este constituit de următorii pași esențiali: pentru fiecare funcție target în parte este oferit un set de date de antrenament, iar în momentul în care este prezentată o instanță nouă, sistemul își va evidenția decizia luată cu privire la clasificarea acesteia. Abordarea Bayesiană constă deci, în determinarea funcției țintă cu probabilitatea cea mai mare luând în considerare vectorul de valori corespunzătoare atributelor ce descriu noua instanță [13].

Putem folosi teorema lui Bayes pentru a rescrie această expresie, obținând:

În vederea estimării valorii s-ar putea determina frecvența apariției valorii în cadrul setului de date pentru antrenament. Totuși, aplicarea aceleiași metode pentru estimarea termenilor nu este fezabilă decât în cazul în care avem un set foarte mare de date.

Întrucât clasificatorul naiv Bayes se bazează pe conceptul conform căruia valorile atributelor sunt independente în raport cu valoarea funcției țintă, putem considera că probabilitatea de a observa succesiunea este determinată de produsul probabilităților pentru fiecare atribut în parte, astfel că:

Înlocuind aceasta în expresia de mai sus, obținem modul de lucru al Clasificatorului naiv Bayes, unde reprezintă funcția target identificată:

După cum se poate observa, numărul de termeni distincți care trebuie estimați pe baza setului de date de antrenament este redus drastic, comparativ cu abordarea anterioară care necesita estimarea tuturor termenilor .

În mod normal, probabilitatea se calculează după formula . Deși în majoritatea cazurilor probabilitatea obținută este bună, s-a observat faptul că în momentul în care numărul cazurilor favorabile este foarte mic, estimările obținute nu sunt extraordinare. De asemenea, dacă estimarea probabilității este 0, clasificatorul va fi influențat în viitor, tocmai datorită faptului că formula de identificare a rezultatului presupune multiplicarea acestei valori cu celelalte probabilități.

Pentru evitarea acestei probleme, s-a adoptat o nouă abordare a clasificatorului, estimarea probabilităților realizându-se prin intermediul următoarei formule:

Astfel, reprezintă estimarea inițială a probabilității pe care dorim să o determinăm, iar reprezintă o constantă, care influențează valoarea lui raportată la setul de date de antrenament. În cazul în care nu există cunoștințe inițiale, se ia în considerare metoda atribuirii uniforme a probabilităților.

Totuși, acest clasificator are și limitările sale. În cazul problemelor de clasificare binară, nu se poate învăța decât o funcție liniară, astfel încât optimalitatea scade în cazul conceptelor inseparabile din punct de vedere liniar (un exemplu clasic reprezentativ ar putea fi constituit de funcția XOR). Odată cu creșterea numărului valorilor pe care le poate avea funcția țintă, clasificatorul poate învăța și funcții polinomiale.

Aceste limitări nu constituie însă o piedică în calea succesului clasificatorului naiv Bayes, acesta obținând performanțe foarte bune în practică, iar deciziile de clasificare sunt de multe ori corecte, chiar dacă estimarea probabilităților este inexactă.

În urma unor cercetări, CNB s-a dovedit a fi la nivelul maxim al performanței, în două cazuri concrete: când este luată în considerare independența completă a caracteristicilor (ceea ce este de așteptat), respectiv dependența funcțională a caracteristicilor (ceea ce este surprinzător) [15].

5.