Universitatea “Lucian Blaga” SibiuCatedra de Calculatoare si Automatizari

Retele Bayesiene

SIBIU, 2008

I. Introducere. Modelul probabilistic Bayesian

Metoda Bayesiana de calcul probabilistic a fost introdusa de preotul Thomas Bayes in

secolul al XVIII-lea. Aceasta forma de rationament se bazeaza pe utilizarea probabilitatilor

conditionate ale unor evenimente specifice in prezenta producerii unor alte evenimente. In teoria

probabilitatilor, notiunea de eveniment este o notiune primara; evenimentele se considera numai din

punctul de vedere al producerii sau al neproducerii lor in decursul unui experiment. Evenimentul

contrar unui eveniment A, notat cu ~A, este evenimentul care se produce atunci si numai atunci

cand nu se produce evenimentul A.

Definitie. Probabilitatea unui eveniment incert A este masura gradului de plauzibilitate al

producerii acelui eveniment. Multimea tuturor evenimentelor posibile se numeste camp de

evenimente sau spatiu de esantioane, notat in continuare cu S.

Definitie. O masura a probabilitatii unui eveniment A este o functie care pune in

corespondenta orice eveniment din S cu numere reale si care satisface urmatoarele

axiome ale teoriei probabilitatii:

(1) pentru orice eveniment

(2)

(3)Daca , pentru , i.e. sunt evenimente mutual

exclusive, atunci

Definitie. Pentru doua evenimente h si e, cu probabilitatea , probabilitatea conditionata

a evenimentului h in conditiile producerii evenimentului e, este definita prin urmatoarea formula

(1)

Probabilitatea conditionata de producere a evenimentului e in conditiile producerii evenimentului h

se defineste simetric prin formula

(2)

Din ecuatiile (1) si (2) rezulta una dintre regulile modelului Bayesian, si anume

(3)

Considerind doua evenimente A si ~A care sunt mutual exclusive, i.e. , si exhaustive, i.e. , probabilitatea de aparitie a unui eveniment B se poate exprima astfel:

(4)

Utilizind aceasta formula, ecuatia (3) poate fi rescrisa obtinindu-se urmatoarea formula pentru

probabilitatea conditionata de aparitie a evenimentului h in conditiile producerii evenimentului e.

2

(5)

Ecuatia (5) poate fi generalizata pentru un numar arbitrar de evenimente , independente si mutual exclusive, in conditiile producerii evenimentului e, astfel:

(6)

si deci

(7)

Evenimentele hi pot fi vazute ca ipoteze probabile, numite si ipoteze statistice, in conditiile existentei probei e. Probabilitatile condititionate ale ipotezelor hi in conditiile existentei probei e pot fi utilizate in modelarea rationamentului incert pentru a selecta ipoteza cea mai probabila in conditiile unei probe observate. In cazul in care exista surse multiple de probe, deci

, formula (7) se defineste ca mai jos, obtinandu-se teorema lui Bayes:

(8)

Considerind exemplul diagnosticarii medicale, selectarea unei ipoteze hi dintr-o multime de

ipoteze pe baza unei multimi de probe observate poate fi vazuta ca selectarea unui diagnostic hi pe baza probelor clinice . In aceasta interpretare, evenimentele si probabilitatile lor conditionate au urmatoarea semnificatie:

este multimea probelor clinice considerate

hi este al i-lea diagnostic considerat ( )

este probabilitatea ca pacientului sa i potriveasca diagnosticul hi

este probabilitatea ca pacientul sa aiba diagnosticul hi pe baza probelor clinice e

este probabilitatea ca sa existe toate probele clinice e daca diagnosticul hi este

adevarat, deci probabilitatea ca pacientul sa aiba totalitatea simptomelor e (simptomatologie completa) daca i se pune diagnosticul hi.

Teorema lui Bayes data de formula (8) ofera o modalitate de calcul al diagnosticului probabil al unui pacient in conditiile cunoasterii probelor clinice e. In cazul in care exista mai multe ipoteze plauzibile si mai multe surse de probe, formula (8) poate duce la calcule extrem de complicate. Daca se presupune ca sunt probe independente, calculul probabilitatii

se poate face ca mai jos, ducand la o simplificare a formulei (8).

(9)

In general, in multe probleme reale probele sunt acumulate pe rand. De exemplu, in

diagnosticarea medicala este posibil ca probele clinice sa apara la diverse momente de timp. Din

3

aceasta cauza sistemele care folosesc modelul Bayesian utilizeaza o varianta modificata de calcul al

probabilitatii care reflecta obtinerea incrementala de probe. Daca sunt probele deja observate, s1 este o noua proba si atunci probabilitatea ipotezei hi in

conditiile existentei probelor e se poate calcula pe baza probabilitatii aceleasi ipoteze (presupus a fi deja calculata) in conditiile existentei probelor e1, prin cumularea efectului lui s1, astfel:

si (10)

Modelul probabilistic Bayesian a fost aplicat in diverse domenii cum ar fi diagnosticarea

medicala si cercetarile geologice. Sistemul PROSPECTOR, sistem expert in domeniul geologiei,

este unul din marile succese ale sistemelor bazate pe cunostinte aplicate. Sistemul utilizeaza

modelul Bayesian si a fost folosit cu succes in localizarea unor zacaminte de minerale, cum ar fi

cupru si uraniu. Ideea de baza a abordarii probabilistice in sistemul PROSPECTOR este

urmatoarea. Se doreste examinarea probelor geologice ale unui anumit loc pentru a determina daca

in acest loc este posibil sa se gaseasca mineralul dorit. Daca se cunosc probabilitatile a priori de

gasire a diverselor minerale si probabilitatile de gasire a unui mineral in functie de anumite

caracteristici fizice, atunci teorema lui Bayes poate calcula probabilitatea de descoperire a unui

zacamint intr-un anumit loc, pe baza probelor geologice accumulate.

Modelul probabilistic Bayesian are o serie de dezavantaje, atit din punct de vedere al

eficientei de calcul cit si din punct de vedere al puterii de expresivitate a reprezentarii cunostintelor

incerte. Dezavantajele si limitarile semnificative ale abordarii bayesiene sint:

Programele care folosesc un astfel de model necesita o cantitate mare de date statistice care

sint greu de adunat si calculat. Complexitatea timp este exponentiala in raport cu numarul

de probe si ipoteze. Modelul presupune independenta ipotezelor, pentru ca formula sa fie

practic aplicabila pe cazuri reale ce contin foarte multe date. De multe ori, independenta

ipotezelor este greu sau imposibil de realizat.

Probabilitatile sunt descrise printr-o valoare numerica unica. Acest lucru poate fi o

simplificare a modelului de gindire umana. De cele mai multe ori, expertii au dificultati in

a estima cu precizie probabilitatea unei ipoteze printr-o singura valoare, avind tendinta de a

specifica un interval de probabilitate.

Modelul Bayesian nu poate discerne intre ignoranta si incertitudine. De exemplu, fie trei

organizatii teroriste A, B si C care sint suspecte de un atac asupra unei institutii publice.

Exista anumite probe care sustin ipoteza vinovatiei organizatiei C cu probabilitatea 0.8. Cu

toate acestea, fara alte probe asupra vinovatiei organizatiilor A si B, nu se poate spune ca A

si B sint vinovate, fiecare cu probabilitatea 0.1.

Modelul Bayesian considera increderea intr-o ipoteza si neincrederea in negarea ei ca doua

functii opuse, i.e.

4

Abordarea conform careia probele in favoarea unei ipoteze trebuie considerate probe in favoarea negarii acelei ipoteze este in multe cazuri falsa.

In plus, interpretarea probabilitatii unei ipoteze in conditiile existentei unei probe ca o forma de confirmare a ipotezei pe baza acestei probe poate duce la rezultate surprinzatoare. In acest sens se poate cita paradoxul lui Carl Hempel care consta in urmatorul exemplu. Fie:

(a) - confirmarea ipotezei h pe baza probei e

(b)h1 = ipoteza "Toti corbii sint negrii"

(c)h2 = ipoteza "Orice obiect care nu este negru nu este corb"

(d)e = proba "Vaza este verde"

Evident, h1 este logic echivalent cu h2. Daca s-ar face o analogie a confirmarii unei ipoteze pe baza unei probe cu probabilitatile conditionate s-ar putea stabili egalitatea

, pentru orice proba e. Cu toate acestea, este total neintuitiv sa se spuna ca observarea probei e, "Vaza este verde", confirma ipoteza h1, "Toti corbii sint negrii". In anumite domenii, cum ar fi medicina, in care semnificatia certitudinii unei ipoteze pe baza probelor este mai mult o confirmare a ipotezei decit o probabilitate de aparitie, este necesar sa se introduca o diferenta intre increderea si neincrederea intr-o ipoteza.

II. Retele Bayesiene

Modelul retelelor Bayesiene, introdus de Judea Pearl [1988], porneste de la modelul

probabilistic Bayesian, dar elimina numarul enorm de calcule necesare in acesta prin considerarea

caracteristicilor de modularitate si de cauzalitate ale domeniului problemei. Ideea de baza a

retelelor Bayesiene este aceea ca, pentru a descrie domeniul problemei, nu este necesar sa se

considere probabilitatile tuturor perechilor de evenimente (fapte) posibile. Cele mai multe

evenimente sunt independente intre ele si interactiunile dintre acestea nu trebuie considerate,

deoarece nu exista.

Retele Bayesiene, numite si retele de incredere apartin familiei modelelor grafice

probabilistice. Modelele grafice reprezinta grafuri in care nodurile sunt variabile aleatoare si

arcurile sunt conditii de propagare. Aceste structuri sunt utilizate pentru reprezentarea cunoasterii

despre un anumit domeniu incert. In mod particiular, fiecare nod dintr-un asemenea graf reprezinta

o variabila aleatoare, in timp ce liniile dintre noduri reprezinta dependente probabilistice intre

variabilele aleatoare corespondente. Aceste dependente conditionale din graf sunt in general

estimate folosind metode statistice de calcul. Deci, retelele Bayesiene combina principii din teoria

grafurilor, teoria probabilitatilor, stiinta calculatoarelor si din statistica.

Retelele Bayesiene sunt de fapt modelele grafice unidirectionale. Acest tip de grafuri

implica o notiune mai complicata a independentei in care se ia in consideratie si directia arcurilor.

5

Modelul retelelor Bayesiene foloseste un graf orientat aciclic pentru a reprezenta gradele de

incredere in faptele din baza de cunostinte si dependentele cauzale existente intre aceste fapte.

Structura unui graf orientat aciclic este definita de 2 seturi: setul nodurilor (vertexuri) si

setul arcelor orientate. Nodurile reprezinta variabile aleatoare si sunt desenate ca cercuri etichetate

cu numele variabilelor. Arcele reprezinta dependenta directa intre variabila si sunt desenate ca

sageti intre noduri. Spre exemplu, un arc din nodul Xi spre nodul Xj reprezinta o dependenta

statistica intre cele doua variabile corespondente. Deci, sageata indica ca o valoare luata de variabila

Xj depinde de valoarea luata de variabila Xi, sau mai direct, “variabila xi influenteaza variabila Xj”.

Pe langa structura grafului este necesar sa atragem atentia asupra unor parametri ai

modelului. Pentru o retea bayesiana trebuie sa se specifice distributia probabilitatilor conditionale

(Conditional Probability Distribution CPD) pentru fiecare nod. Daca se lucreaza cu variabile

discrete atunci aceste probabilitati pot fi reprezentate ca tabele (CPT), care reprezinta probabilitatea

ca nodul fiu sa ia toate valorile sale posibile pentru fiecare combinatie de valori a nodului parinte.

Sa consideram exemplul urmator in care avem noduri binare, adica din fiecare nod avem doua

posibile valori pentru a parcurge graful mai departe, pe care le vom nota cu A (Adevarat) si F

(Fals).

Din graful de mai jos se vede ca evenimentul “Iarba Umeda” (IU=A) are doua posibile

cauze: sau udata de stropitoare (S=A) sau din cauza ploii (P=A). Spre exemplu, din tabel se vede ca

P(IU=A | S=A, P=F) = 0.9 si P(IU=F | S=A, P=F) = 1 - 0.9 = 0.1, deci suma fiecarui rand din tabel

trebuie sa fie 1. Din cauza ca primul nod (Inourat) nu are parinti probabilitatea evenimentului

specificat de el este bazata pe observatiile anterioare si reprezinta 0.5 in acest caz.

Figura 1. Exemplu retea Bayesiana (Sprinkler example, [1])Conform regulilor probabilitatii avem:

P(VN, S, P, IU) = P(VN) * P(S | VN) * P(P | VN, S) * P(IU | VN, S, P)Folosind relatiile independente conditionale, putem rescrie astfel:

P(VN, S, P, IU) = P(VN) * P(S | VN) * P(P | VN) * P(IU | S, P)

Am putut simplifica al treilea termen deoarece P este independent de S avand ca parinte I, si ultimul

termen deoarece IU este independent de I avand ca parinti S si P.

6

Putem vedea ca relatiile conditionale independente ne permit sa reprezentam mai compact setul de probabilitati. In cazul de fata simplificarea a fost minima, insa in cazul a n noduri relatia ar fi fost cu mult mai complicata ceea ce ar ingreuna cu mult studiul.

Independenta conditionala

Fie X, Y, si Z 3 variabile aleatoare cu valori discrete. Putem spune ca X este independenta

conditional de Y dat fiind Z, daca distributia probabilitatilor lui X este independenta de valoarea lui

Y in cazul unei anumite valori pentru Z. Adica daca:

unde xi E V(X), yj E V(Y), si zk E V(Z). Aceasta se scrie de obicei ca:

Reprezentarea retelelor Bayesiene

O retea de incredere Bayesiana reprezinta distributia probabilitatilor totale pentru un set de

variabile. De exemplu, reteaua bayesiana din figura de mai jos reprezinta distributia probabilitatilor

totale ale variabilelor Storm, Lightning, Thunder, ForestFire, Campjre and BusTourGroup.

Figura 2. Exemplu de retea de incredere Bayesiana

Reteaua din partea stanga reprezinta un set de asumptii de independete conditionale. Cu alte

cuvinte, fiecare nod este considerat a fi independent conditional de non-descendetii sai, dat fiindu-i

parintii imediati. Fiecarui nod ii este asociat un tabel de probabilitati conditionale, care specifica

distributia conditionala pentru variabila in functie de parintii imediati din graf. Tabelul

probabilitatilor conditionale pentru variabila Campfire este infatisat in partea dreapta a figurii, unde

Campfire a fost notat cu C, Storm cu S si BusTourGroup cu B.

In general, reteaua Bayesiana reprezinta distributia probabilitatilor totale prin specificarea

unui set de asumptii de independente conditionale (reprezintate cu ajutorul unui graf orientat

aciclic), impreuna cu seturi de probabilitati conditionale locale. Fiecare variabila din spatiul comun

este reprezentata de un nod in retea. Pentru fiecare variabila doua tipuri de informatii sunt

specificate. In primul rand, arcele retele reprezinta faptul ca variabila este conditional-independenta

de non-descendentii sai din retea. Spunem ca X este un descendent al lui Y daca este o cale directa

in graf de la Y la X. In al doilea rand, un tabel cu probabilitati conditionale este dat pentru fiecare

variabila, descriind distributia probabilitatilor pentru acea variabila in functie de predecesorii sai

imediati. Probabilitatea totala pentru orice atribuire de valori (yl, . . . , y,) catre un tuplu de variabile

ale retelei (YI . . . Y,) poate fi calculata cu ajutorul formulei:

7

unde Parents(Yi) denota un set de predecesori imediati ai lui Yi in retea. De notat este ca valorile lui

P(yi|P arents(Yi)) sunt exact valorile memorate in tabel probabilitatilor conditionale asociat nodului

Yi.

Pentru a ilustra aceste afirmatii, luam ca exemplu reteaua Bayesiana din figura 2 care

reprezinta distributia probabilitatilor totale peste variabilele booleene Storm, Lightning, Thunder,

ForestFire, Campfire si BusTourGroup. In cazul nodului Campfire nodurile si arcele retelei

reprezinta afirmatia ca variabila CampJire este independent conditional de non-descendentii sai,

Lightning si Thunder, avand in vedere parintii imediati, Storm si BusTourGroup. Acest lucru

inseamna ca odata ce stim valorile variabilelor Storm si BusTourGroup, variabilele Lightning si

Thunder nu ne vor da nici o informatie suplimentara despre Campfire. In partea dreapta a figurii 2

putem observa tabel probabilitatilor conditionale asociate variabilei Campfire. De exemplu, ntrarea

din stanga sus a acestui tabel exprima afirmatia ca

De notat este ca acest tabel prezinta doar probabilitatile conditionale ale lui Campjire cunoscute

fiind variabilele parinte, Storm si BusTourGroup. Distributia completa probabilitatilor totale pentru

aceasta retea este formata de fapt din setul tabelelor cu probabilitati conditionale locale pentru toate

variabilele, impreuna cu setul de asumptii de independete conditionale descrise de retea. O trasatura

atractiva a retelelor de incredere Bayesiene este aceea ca acestea permit o modalitate convenienta de

a reprezenta cunostinte cauzale ca de exemplu faptul ca Lightning cauzeaza Thunder. Folosind

terminologia independetelor conditionale, acest fapt se poate exprima prin “Thunder este

independent conditional de celelalte variabile ale retelei, cunoscuta fiind valoarea lui Lightning.

Inferinta in retelele Bayesiene

O retea Bayesiana poate fi folosita pentru a predictiona valoarea unei variabile tinta (de

exemplu, ForestFire) in functie de valorile observate pentru alte variabile. Desigur, cum avem de a

face cu variabile aleatoare, nu ar fi corect sa atribuim o singura valoare determina variabilei tinta.

Ceea ce dorim sa determinam este distributia probabilitatilor pentru variabila tinta, care vor

specifica probabilitatea obtinuta pentru fiecare dintre valorile posibile, tinand cont si de valorile

celorlalte variabile. Acest pas de inferinta poate fi simplu daca sunt cunoscute exact valorile pentru

toate celelalte variabile ale retelei. Intr-o situatie mai generala, poate dorim sa predictionam

distributia probabilitatilor pentru o variabila ca ForestFire in functie de valorile observate pentru

doar un subset al celorlalte variabile (spre exemplu, poate doar valorile variabilelor Thunder si

BusTourGroup sunt cunoscute la un anumit moment).

Numeroase metode au fost propuse pentru inferinta probabilitatilor in retelele Bayesiene,

incluzand aici metode exacte de predictie sau metode de predictie aproximative care sacrifica

precizie in favoarea castigului in eficienta. De exemplu, metodele Monte Carlo ofera solutii

aproximative prin alegerea aleatoare de esantioane din distributia variabilelor neobservate (Pradham

8

and Dagum 1996). In teorie insa, atat inferinta prin metode exacte cat si cea prin metode

aproximative pot fi o problema NP (Dagum and Luby 1993). Din fericire, in practica metodele

aproximative s-a demonstrat ca pot fi extrem de folositoare in multe cazuri.

Avantaje ale retelelor Bayesiene

Exista numeroase metode de reprezentare disponibile pentru analiza datelor cum ar fi seturi de

reguli, arbori de decizii si retele neuronale artificiale; de asemenea exista multe tehnici de analizare

a datelor ca estimarea densitatii, clasificarea, regresia si clustering-ul. Deci, prin ce sunt speciale

metodele si retelele bayesiene? Exista minim patru raspunsuri la aceasta intrebare:

Retelele bayesiene pot utiliza seturi de date incomplete. Spre exemplu sa consideram o

problema in care doua dintre variabilele de intrare nu sunt nici intr-un fel corelate. Aceasta

relatie dintre variabilele respective normal nu prezinta o piedica in modurile standard de

abordare a problemelor, deoarece toate intrarile sunt examinate in fiecare caz. In cazul in

care una dintre intrari nu este observata majoritatea modelelor vor produce o predictie

eronanta, deoarece ele nu iau in consideratie relatiile dintre variabilele de intrare. Retelele

bayesiene ofera un mod natural de abordare a astfel de dependente.

Retelele bayesiene permit studierea relatiilor cauzale. Acest proces este util in cazul in care

se doreste intelegerea unui domeniu de probleme. Mai mult, cunoasterea relatiilor cauzale ne

permite sa facem predictii in cazul unor interventii. Spre exemplu, un manager, analizand

piata, doreste sa afle daca se merita marirea cheltuielilor pentru publicitatea unui produs in

scopul de a creste numarul de vanzari. Pentru a raspunde la aceasta intrebare el poate

determina daca publicitatea este sau nu cauza maririi vanzarilor si in ce masura. Utilizarea

retelelor bayesiene permite aflarea raspunsului la astfel de probleme chiar si in cazurile in

care nu se cunosc date despre efectele maririi vanzarilor.

Retelele bayesiene in conjunctie cu tehnicile de statistica bayesiana faciliteaza combinarea

domeniului cunoasterii cu domeniul datelor. Se stie ca cunostintele capatate anterior au o

importanta foarte mare in studiul problemelor din lumea reala, in special cand datele ce pot

ajuta la analiza nu sunt complete sau colectarea lor induce costuri prea mari. Faptul ca unele

aplicatii comerciale (spre exemplu sistemele expert) se pot axa pe baza cunostintelor

capatate anterior, reprezinta un atu in favoarea acestui model. In plus retelele bayesiene

intaresc puterea relatiilor cauzale cu teoria probabilitatilor. Deci, cunostintele anterioare pot

fi combinate cu datele utile folosind tehnicile de statistica bayesiana.

Metodele bayesiene de analiza in conjunctie cu retelele bayesiene si alte tipuri de modele

ofera o abordare eficienta si principiala in vederea evitarii suprapunerii datelor. Folosind

retelele bayesiene se poate ajung la antrenarea tuturor datelor, pe care le avem, in

solutionareaproblemei.

9

III. Concluzii

Retelele Bayesiene sunt folosite in o serie larga de aplicatii. Aplicatii ce le folosim in fiecare

zi, care implica asa-numitii Answering Wizard, majoritatea au la baza retele bayesiene.

Alte aplicatii de mentionat ale retelelor de incredere ar fi in urmatoarele domenii:

IT (Email Spam, IR, AI, clasificare, Windows Troubleshooters)

Medicina (diagnosticarea bolilor)

Marketing (analiza pietei si luarea de decizii)

Armata (vehicule cu pilot automat, automatic target recognition)

Prediction/Forecasting in diverse alte domenii

Retelele bayesiene au luat nastere din incercarea de a adauga probabilitatile in sistemele

expert. Un exemplu important este aplicatia QMR-DT (Quick Medical Reference). In aceasta

structura partea superioara reprezinta nodurile corespunzatoare bolilor, iar partea inferioara – cele

corespunzatoare simptomelor. Scopul acestui model este de a depista bolile pe baza simptomelor

observate.

Figura 3. Retea Bayesiana pentru determinarea bolilor

IV. Bibliografie[1] Kevin Murphy – “A Brief Introduction to Graphical Models and Bayesian Networks”, 1998

[2] Yang Xiang - “Probabilistic Reasoning in Multiagent Systems: A Graphical Models

Approach”, Cambridge University Press, 2002

[3] K. R. Koch – “Introduction to Bayesian Statistics”, 5th Edition, Springer, 2007

[4] Jayanta K. Ghosh et. al - “An Introduction to Bayesian Analysis”, Springer, 2006

[5] Eugene Charniak – “Bayesian Networks without Tears”, 1991

[6] Darlye Niedermayer - “An Introduction to Bayesian Networks and their Contemporary

Applications”, 1998

[7] Irad Ben-Gal - “Bayesian Networks”

[8] Adina Magda Florea – “Elemente de inteligenta artificiala”

1

[9] Tom M. Mitchell – “Machine Learning”, McGraw-Hill Science/Engineering/Math 1997.

1