1

Curs nr. 5
Reprezentarea cunostintelor incerte
◼ Teoria probabilitatilor
◼ Retele Bayesiene

2
 1. Teoria probabilitatilor
1.1 Cunostinte incerte
◼ Teoria probabilitatilor ➔ un grad numeric de
incredere sau plauzibilitate a afirmatiilor in [0,1]
◼ Valorile variabilelor pot fi din diferite domenii si
acestor valori li se adauga un grad de
incredere/plauzibilitate
◼ Fuzzy logic ➔ grad numeric de adevar / al
adevarului
◼ Valorile variabilelor arata un grad de adevar in [0,1]
◼ Gradul de incredere  gradul de adevar
3
 1.2 Definitii TP
◼ Probabilitatea unui eveniment incert A este masura gradului
de incredere sau plauzibilitatea produceri unui eveniment
◼ Camp de probabilitate, S

◼ Probabilitate neconditionata (apriori) - inaintea obtinerii de

probe pt o ipoteza / eveniment
◼ Probabilitate conditionata (aposteriori) - dupa obtinerea de
probe
Exemple
P(Carie) = 0.1
P(Vreme = Soare) = 0.7
P(Vreme = Ploaie) = 0.2 P(Vreme = Nor) = 0.1
Vreme - variabila aleatoare
◼ Distributie de probabilitate
4
 Definitii TP - cont
◼ Probabilitate conditionata (aposteriori) - P(A|B)
P(Carie | Dur_d) = 0.8
Masura probabilitatii producerii unui eveniment A
este o functie P:S → R care satisface axiomele:
◼ 0  P(A)  1
◼ P(S) = 1 ( sau P(adev) = 1 si P(fals) = 0)
◼ P(A  B) = P(A) + P(B) - P(A  B)

P(A  ~A) = P(A)+P(~A) –P(fals) = P(adev)

 P(~A) = 1 – P(A)
5
 Definitii TP - cont
Evenimente mutual exclusive
Moneda – cap/pajura – mutual exclusive
Zar – 1, 2, 3 – mutual exclusive

Evenimente exhaustive
Moneda – cap/pajura – mutual exhaustive
Zar – 1, 2, 3, 4, 5, 6 – mutual exhaustive

6
 Definitii TP - cont
A si B mutual exclusive ➔
P(A  B) = P(A) + P(B)
P(e1  e2  e3  … en) =
P(e1) + P(e2) + P(e3) + … + P(en)

e(a) – multimea de evenimente atomice mutual

exclusive si exhaustive in care apare a
P(a) =  P(ei)
eie(a)
7
 1.3 Regula produsului

Probabilitatea conditionata de producere a

evenimentului A in conditiile producerii
evenimentului B
◼ P(A|B) = P(A  B) / P(B)

P(A  B) = P(A|B) * P(B) – regula

produsului

8
 Regula produsului

◼ A si B sunt evenimente independente daca

P(A|B) =P(A)
◼ In acest caz regula produsului devine
P(A  B) = P(A) * P(B)

◼ Daca A si B sunt evenimente independente

conditional fiind dat C
P(A  B|C) = P(A|C) * P(B|C)
9
 1.4 Teorema lui Bayes
P(A|B) = P(A  B) / P(B) – regula produsului

P(A|B) = P(A  B) / P(B)

P(B|A) = P(A  B) / P(A)

P(B|A) = P(A|B) *P(B)/ P(A)

APosteriori = Plauzibilitate x APriori / Evidenta

10
 Teorema lui Bayes
P(B|A) = P(A|B) *P(B)/ P(A)

◼ Daca B si B sunt mutual exclusive si exhaustive,

probabilitatea de producere a lui A in conditiile producerii lui
B se poate scrie

P(A) = P(A  B) + P(A  B) = P(A|B)*P(B) +P(A| B)*P(B)

P(B|A) =
P(A | B) * P(B) / [P(A|B)*P(B) +P(A| B)*P(B)]

11
 Teorema lui Bayes - generalizare
Notand cu B - h, A – e, rescriu formula precedenta
P(h|e) = P(e | h) * P(h) / [P(e|h)*P(h) +P(e| h)*P(h)]
Generalizarea la mai multe ipoteze hi
Daca hi mutual exclusive si exhaustive, i=1,k

P(e|h i )  P(h i )
P(h i |e) = k
, i = 1, k
 P(e|h j )  P(h j )
j=1

12
 Teorema lui Bayes generala
Generalizarea la mai multe ipoteze hi si probe ei
hi – evenimente / ipoteze probabile (i=1,k);
e1,…,en – probe (evenimente)
P(hi)
P(hi | e1,…,en)
P(e1,…,en| hi)
P(e1 ,e2 ,...,e n |h i )  P(h i )
P(h i |e1 ,e2 ,...,e n ) = k
, i = 1, k
 P(e1 ,e2 ,...,e n |h j )  P(h j )
j =1

13
 Teorema lui Bayes - cont
P(e1 ,e2 ,...,e n |h i )  P(h i )
P(h i |e1 ,e2 ,...,e n ) = k
, i = 1, k
 P(e1 ,e2 ,...,e n |h j )  P(h j )
j =1
Daca e1,…,en sunt ipoteze independente conditional fiind dat hj
atunci

P(e|h j ) = P(e1 ,e2 ,...,e n |h j ) = P(e1|h j )  P(e2 |h j )...P(e n |h j ), j = 1, k

PROSPECTOR – sistem expert pentru consultari

privind exploatari miniere si evaluarea
resurselor
14
1.5 Inferente pe baza Distributiei de
Probabilitate si a Teoremei lui Bayes
Distributie de probabilitate P(Carie, Dur_d)
Dur_d Dur_d
Carie 0.04 0.06
Carie 0.01 0.89

P(Carie) = 0.04 + 0.06 = 0.1

P(Carie  Dur_d) = 0.04 + 0.01 + 0.06 = 0.11
P(Carie|Dur_d) = P(Carie  Dur_d) / P(Dur_d) = 0.04 / 0.05

15
Inferente din DP si TB
Dur_d ~Dur_d
Evid ~Evid Evid ~Evid
Carie 0.108 0.012 0.072 0.008
~Carie 0.016 0.064 0.144 0.576
Distributie de probabilitate P(Carie, Dur_d, Evid)

P(Carie) = 0.108 + 0.012 + 0.72 + 0.008 = 0.2

P(Carie  Dur_d) = 0.108 + 0.012 + 0.072 + 0.008 + 0.016
+ 0.064 = 0.28

P(Carie, Dur_d, Vreme) – o tabela cu 2 x 2 x 3 = 12 intrari

Distributie de probablitate completa

16
 Inferente din DP si TB
Dur_d ~Dur_d
Evid ~Evid Evid ~Evid
Carie 0.108 0.012 0.072 0.008
~Carie 0.016 0.064 0.144 0.576

P(Carie | Dur_d) = P(Carie  Dur_d) / P(Dur_d)

P(~Carie | Dur_d) = P(~Carie  Dur_d) / P(Dur_d)
 = 1 / P(Dur_d) – constanta de normalizare a distributiei

P(Carie | Dur_d) =  P(Carie  Dur_d) =

 [P(Carie  Dur_d  Evid) + P(Carie  Dur_d  ~Evid)] =
 [<0.108, 0.016> + <0.012, 0.064>] =  <0.12, 0.08> = <0.6, 0.4>

Chiar daca nu cunoastem , adica P(Dur_d), putem calcula 

 = 1/(0.12+0.08) = 1/0.2
17
 Inferente din DP si TB
Generalizare – procedura generala de inferenta bazata
pe DP
Interogare asupra lui X

X – variabila de interogat (in ex anterior Carie)

E – lista de variabile probe (in ex anterior Dur_d)
e – lista valorilor observate pt aceste variabile E
Y – lista variabilelor neobservate (restul) (in ex anterior Evid)

P(Carie | Dur_d) =  [P(Carie  Dur_d  Evid) + P(Carie  Dur_d  ~Evid)]

Insumarea se face peste toate combinatiile de valori ale variab. neobservate Y

P(X | e) =  P(X , e) =  Y=y P(X, e, Y)

18
 Inferente din DP si TB

P(X | e) =  P(X , e) = Y=y P(X, e, Y)

Avand DP ecuatia poate da raspuns la

interogari cu variabile discrete
Complex computational
n var Bool – tabela O(2n)
- timp O(2n)

19
 1.6 Independenta conditionala
◼ Evenimentele A si B sunt independente conditional fiind dat
un eveniment C daca
Stiind ca C apare, aparitia lui A nu influenteaza aparitia lui B si
aparitia lui B nu influenteaza aparitia lui A
P(A|C) = P(A|B,C)
A si B sunt independente conditional fiind dat un eveniment C
daca, pentru orice valoare a lui C:
o distributia de probabilitate a lui A este aceeasi pentru orice
valoare ar lua B
o distributia de probabilitate a lui B este aceeasi pentru orice
valoare ar lua A
P(A,B|C) = P(A|C)*P(B|C)
20
 Independenta conditionala

P(cauza | efect) = P(efect | cauza) * P(cauza) / P(efect)

P(y | x1,..,xn) = P(x1,..,xn |y) * P(y) / P(x1,..xn)
P(y | x1,..,xn) =  * P(x1,..,xn |y) * P(y)
Daca x1,..,xn sunt independente conditional fiind dat y
atunci
P(x1,..xn |y) = i P(xi|y)

P(Cauza | Efect1, Efect2, …) =

 P(Cauza) * i P(Efecti|Cauza)

21
 1.7 Model Bayesian naiv

P(Cauzay | Efect1, Efect2, …) =  P(Cauzay) * i P(Efecti|Cauzay)

Ipoteza de independenta
conditionala / naiva

Cauza_MAP = argmaxy P(Cauzay) * i P(Efecti|Cauzay)

Model Bayesian naiv

22
 Model Bayesian naiv

Vector de caracteristici x1,..,xn si o serie de clase Ck

P(Ck | x1, x2, …) =  P(Ck) * i P(xi|Ck)

C_MAP = argmaxk P(Ck) * i P(xi|Ck)

Model Bayesian naiv Clasa

MAP – Maximum a Posteriori

X1 X2 … Xn
23
 1.8 Modele grafice probabiliste

◼ Fiecare nod reprezinta o variabila aleatoare si fiecare

legatura reprezinta o relatie probabilistica
◼ Retele Bayesiene – modele grafice orientate -
permit reprezentare compacta a DP si punerea in
evidenta a independentei conditionale
◼ Modele Markov – lanturi Markov – stari si tranzitii
probabilistice

24
 2 Retele Bayesiene
◼ Reprezinta dependente intre variabile aleatoare
◼ Specifica distributiei de probabilitate
◼ Simplifica calculele
◼ Au asociata o reprezentare grafica convenabila
◼ DAG care reprezinta relatiile cauzale intre variabile
◼ Pe baza structurii retelei se pot realiza diverse tipuri
de inferente
◼ Calcule complexe in general dar se pot simplifica
pentru structuri particulare
25
 2.1 Structura retelelor Bayesiene

O RB este un DAG in care:

◼ Nodurile reprezinta variabilele aleatoare

◼ Legaturile orientate X→Y: X are o influenta

directa asupra lui Y, X=Parinte(Y)
◼ Fiecare nod are asociata o tabela de probabilitati

conditionate care cuantifica efectul parintilor

asupra nodului
◼ P(Xi | Parinti(Xi))

26
 Structura retelelor Bayesiene - cont
P(H)
0.001 Hot Cutremur P(C)
0.002
H C P(A|H,C)
T T 0.95
T F 0.94 Alarma
F T 0.29
F F 0.001
A P(M|A) A P(D|A)
T 0.9 TelMihai TelDana T 0.7
F 0.05 F 0.01

H C P(A | H, C)
T F
Tabela de probabilitati T T 0.95 0.05
conditionate T F 0.94 0.06
F T 0.29 0.71
F F 0.001 0.999
27
 Structura retelelor Bayesiene

In general X (Cauza) → Y (Efect)

◼ Stabilesc topologia
◼ Specifica distributia de probabilitati conditionate
◼ Combinarea topologiei si distributia de probabilitati
conditionate este suficienta pentru a specifica
(implicit) intreaga DPC
◼ DPC poate raspunde la interogari
◼ Si RB la fel, mai eficient
28
 2.2 Semantica retelelor Bayesiene

◼ Reprezentare a distributiei de probabilitate

◼ Specificare a independentei conditionale –
constructia retelei

◼ Fiecare valoare din distributia de probabilitate poate

fi calculata ca:
P(X1=x1  … Xn=xn) = P(x1,…, xn) =
i=1,n P(xi | parinti(xi))
unde parinti(xi) reprezinat valorile specifice ale
variabilelor Parinti(Xi)
29
 2.3 Construirea retelei
Cum sa construim o retea a.i. RB/DPC sa fie o buna
reprezentare?
Ecuatia P(x1,…, xn) = i=1,n P(xi | parinti(xi)) implica anumite
relatii de independenta conditionala care pot ghida construirea
retelei
P(X1=x1  … Xn=xn) = P(x1,…, xn) =
P(xn | xn-1,…, x1) * P(xn-1,…, x1) = … =
P(xn | xn-1,…, x1) * P(xn-1 | xn-2,…, x1)* … P(x2|x1) * P(x1) =
i=1,n P(xi | xi-1,…, x1) – valabila in general

• DPC daca, pt fiecare variabila Xi din RB

P(Xi | Xi-1,…, X1) = P(xi | Parinti(Xi)) cu conditia ca
Parinti(Xi)  { Xi-1,…, X1}

30
 Construirea retelei
Pt fiecare variabila Xi din RB
P(Xi | Xi-1,…, X1) = P(xi | Parinti(Xi)) cu
conditia ca
Parinti(Xi)  { Xi-1,…, X1}

• O RB este o reprezentare corecta a domeniului

cu conditia ca fiecare nod sa fie independent
conditional de nondescendenti, fiind dati
parintii lui
31
 Construirea retelei

• Conditia poate fi satisfactuta prin etichetarea

nodurilor intr-o ordine consitenta cu DAG

• Intuitiv, parintii unui nod Xi trebuie sa fie toate

acele noduri
Xi-1,…, X1 care influenteaza direct Xi.

32
 Construirea retelei - cont

• Alege o multime de variabile aleatoare relevante care descriu

problema
• Alege o ordonare a acestor variabile
• cat timp mai sunt variabile repeta
(a) alege o variabila Xi si adauga un nod corespunzator lui Xi
(b) atribuie Parinti(Xi)  un set minim de noduri deja
existente in retea a.i. proprietatea de independenta
conditionala este satisfacuta
(c) defineste tabela de probabilitati conditionate pentru Xi

Deoarece fiecare nod este legat numai la noduri anterioare →

DAG

33
 2.4 Inferente probabilistice

A V B

P(A  V  B) = P(A) * P(V|A) * P(B|V)

V

A B
P(A  V  B) = P(V) * P(A|V) * P(B|V)

A B

V P(A  V  B) = P(A) * P(B) * P(V|A,B)

34
 Inferente probabilistice
P(H)
0.001 Hot Cutremur P(C)
0.002
H C P(A|H,C)
T T 0.95
T F 0.94 Alarma
F T 0.29
F F 0.001
A P(M|A) A P(D|A)
T 0.9 TelMihai TelDana T 0.7
F 0.05 F 0.01

P(M  D  A H C ) =

P(M|A)* P(D|A)*P(A|H C )*P(H) P(C)=
0.9 * 0.7 * 0.001 * 0.999 * 0.998 = 0.00062
35
 Inferente probabilistice
P(H)
0.001 Hot Cutremur P(C)
0.002
H C P(A|H,C)
T T 0.95
T F 0.94 Alarma
F T 0.29
F F 0.001
A P(M|A) A P(D|A)
T 0.9 TelMihai TelDana T 0.7
F 0.05 F 0.01

P(A|H) = P(A|H,C) *P(C|H) + P(A| H,C)*P(C|H)

= P(A|H,C) *P(C) + P(A| H,C)*P(C)
= 0.95 * 0.002 + 0.94 * 0.998 = 0.94002
36