Inteligenta Artificiala Universitatea Politehnica Bucuresti Anul universitar 2008-2009
Adina Magda Florea
http://turing.cs.pub.ro/ia_08 si curs.cs.pub.ro
2.3 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)
Se observa ca P(Xi | Xi-1,…, X1) = P(xi | Parinti(Xi)) daca
Parinti(Xi) { Xi-1,…, X1}
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.
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
2.4 Inferente probabilistice
* P(A V B) = P(A) * P(V|A) * P(B|V) V A B B V A A V B P(A V B) = P(V) * P(A|V) * P(B|V) P(A V B) = P(A) * P(B) * P(V|A,B)
Inferente probabilistice
* Cutremur Alarma TelMihai TelDana Hot P(H)
0.001 P(C)
0.002 H C P(A)
T T 0.95
T F 0.94
F T 0.29
F F 0.001 A P(M)
T 0.9
F 0.05 A P(D)
T 0.7
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
Inferente probabilistice
* Cutremur Alarma TelMihai TelDana Hot P(H)
0.001 P(C)
0.002 H C P(A)
T T 0.95
T F 0.94
F T 0.29
F F 0.001 A P(M)
T 0.9
F 0.05 A P(D)
T 0.7
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
* Modelul MYCIN
Factori de certitudine / Coeficienti de incredere (CF)
Model euristic al reprezentarii cunostintelor incerte
In sistemul MYCIN se folosesc doua functii probabilistice pentru a modela increderea si neincrederea intr-o ipoteza:
functia de masura a increderii, notata MB
functia de masura a neincrederii, notata MD
MB[h,e] - reprezinta masura cresterii increderii in ipoteza h pe baza probei e
MD[h,e] - reprezinta masura cresterii neincrederii in ipoteza h pe baza probei e
3.1 Functii de incredere
* Factorul (coeficientul) de certitudine
Functii de incredere - caracteristici
* Domeniul de valori
Ipotezele sustinute de probe sunt independente
Daca se stie ca h este o ipoteza sigura, i.e. P(h|e) = 1, atunci
Daca se stie ca negatia lui h este sigura, i.e. , P(h|e) = 0 atunci
MYCIN - Exemplu de utilizare CF
* Regula in sistemul MYCIN
daca tipul organismului este gram-pozitiv, si
morfologia organismului este coc, si
conformatia cresterii organismului este lant
atunci exista o incredere puternica (0.7)
ca identitatea organismului este streptococ.
Exemple de fapte in sistemul MYCIN :
(identitate organism-1 pseudomonas 0.8)
(identitate organism-2 e.coli 0.15)
(loc cultura-2 git 1.0)
3.2 Functii de combinare a incertitudinii
* (1) Probe adunate incremental
Aceeasi valoare de atribut, h, este obtinuta pe doua cai de deductie distincte, cu doua perechi diferite de valori pentru CF, CF[h,s1] si CF[h,s2]
Cele doua cai de deductie distincte, corespunzatoare probelor sau ipotezelor s1 si s2 pot fi ramuri diferite ale arborelui de cautare generat prin aplicarea regulilor sau probe indicate explicit sistemului de medic.
CF[h, s1&s2] = CF[h,s1] + CF[h,s2] – CF[h,s1]*CF[h,s2]
(identitate organism-1 pseudomonas 0.8)
(identitate organism-1 pseudomonas 0.7)
Functii de combinare a incertitudinii
* (2) Conjunctie de ipoteze
Se aplica pentru calculul CF asociat unei premise de regula care contine mai multe conditii
daca A = a1 si B = b1 atunci …
ML: (A a1 s1 cf1) (B b1 s2 cf2)
CF[h1&h2, s] = min(CF[h1,s], CF[h2,s])
Se generalizeaza pt mai multe conditii
Functii de combinare a incertitudinii
* (3) Combinarea increderii
O valoare incerta este dedusa pe baza unei reguli care are drept conditie de intrare alte valori incerte (deduse eventual prin aplicarea altor reguli).
Permite calculul factorului de certitudine asociat valorii deduse pe baza aplicarii unei reguli care refera valoarea in concluzie, tinind cont de CF-ul asociat premisei regulii.
CF[s,e] - increderea intr-o ipoteza s pe baza unor probe anterioare e
CF[h,s] - CF in h in cazul in care s este sigura
CF’[h,s] = CF[h,s] * CF [s,e]
Functii de combinare a incertitudinii
* (3) Combinarea increderii – cont
daca A = a1 si B = b1 atunci C = c1 0.7
ML: (A a1 0.9) (B b1 0.6)
CF(premisa) = min(0.9, 0.6) = 0.6
CF (concluzie) = CF(premisa) * CF(regula) = 0.6 * 0.7
ML: (C c1 0.42)
3.3 Limitari ale modelului CF
* Modelul coeficientilor de certitudine din MYCIN presupune ca ipotezele sustinute de probe sunt independente.
Un exemplu care arata ce se intimpla in cazul in care aceasta conditie este violata.
Fie urmatoarele fapte:
A: Aspersorul a functionat noaptea trecuta.
U: Iarba este uda dimineata.
P: Noaptea trecuta a plouat.
Limitari ale modelului CF - cont
* A: Aspersorul a functionat noaptea trecuta.
U: Iarba este uda dimineata.
P: Noaptea trecuta a plouat.
si urmatoarele doua reguli care leaga intre ele aceste fapte:
R1: daca aspersorul a functionat noaptea trecuta
atunci exista o incredere puternica (0.9) ca iarba este uda dimineata
R2: daca iarba este uda dimineata
atunci exista o incredere puternica (0.8) ca noaptea trecuta a plouat
Limitari ale modelului CF - cont
* CF[U,A] = 0.9
deci proba aspersor sustine iarba uda cu 0.9
CF[P,U] = 0.8
deci iarba uda sustine ploaie cu 0.8
CF[P,A] = 0.8 * 0.9 = 0.72
deci aspersorul sustine ploaia cu 0.72
Solutii
Comments