inteligenta artificiala

40
Inteligenta Inteligenta Artificiala Artificiala Universitatea Politehnica Bucuresti Anul universitar 2005-2006 Adina Magda Florea http://www.cs.pub.ro/ ia_06

Upload: inga

Post on 26-Jan-2016

29 views

Category:

Documents


1 download

DESCRIPTION

Inteligenta Artificiala. Universitatea Politehnica Bucuresti Anul universitar 2005-2006 Adina Magda Florea http://www.cs.pub.ro/ia_06. Curs nr. 9. Reprezentarea cunostintelor incerte Teoria probabilitatilor Retele Bayesiene Factori de certitudine Logica vaga (fuzzy). 2. - PowerPoint PPT Presentation

TRANSCRIPT

Page 1: Inteligenta Artificiala

Inteligenta ArtificialaInteligenta Artificiala

Universitatea Politehnica BucurestiAnul universitar 2005-2006

Adina Magda Florea

http://www.cs.pub.ro/ia_06

Page 2: Inteligenta Artificiala

Curs nr. 9

Reprezentarea cunostintelor incerte Teoria probabilitatilor Retele Bayesiene Factori de certitudine Logica vaga (fuzzy)

2

Page 3: Inteligenta Artificiala

1. Teoria probabilitatilor

1.1 Cunostinte incertep simpt(p, Dur_d) factor(p,carie)

p simpt(p, Dur_d) factor(p,carie) factor(p,infl_ging) … LP

- dificultate (« lene »)

- ignoranta teoretica

- ignoranta practica Teoria probabilitatilor un grad numeric de

incredere sau plauzibilitate a afirmatiilor in [0,1] Gradul de adevar (fuzzy logic) gradul de incredere

3

Page 4: Inteligenta Artificiala

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

probeExemple

P(Carie) = 0.1P(Vreme = Soare) = 0.7P(Vreme = Ploaie) = 0.2

Vreme - variabila aleatoare Distributie de probabilitate

4

Page 5: Inteligenta Artificiala

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

Page 6: Inteligenta Artificiala

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 in care apare a

P(a) = P(ei)eie(a)

Ex: Carie Dur_d

Multimea de evenimente atomice: mutual exclusive si exhaustive

6

Page 7: Inteligenta Artificiala

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)

7

Page 8: Inteligenta Artificiala

1.4 Teorema lui Bayes

Daca A si A sunt mutual exclusive si exhaustive, probabilutatea de aparitie a lui B in conditiile producerii lui A este

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

Generalizare la mai multe evenimente exclusive si exhaustive

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

B - h, A - e

P(h|e) = P(e | h) * P(h) / [P(e|h)*P(h) +P(e| h)*P(h)]

8

P(h |e) =P(e|h ) P(h )

P(e|h ) P(h )

i = 1,kii i

j jj=1

k

,

Page 9: Inteligenta Artificiala

Teorema lui Bayes

hi – evenimente / ipoteze probabile (i=1,k);

e1,…,en - probe

P(hi)

P(hi | e1,…,en)

P(e1,…,en| hi)

9

P(h |e ,e ,...,e ) =P(e ,e ,...,e |h ) P(h )

P(e ,e ,...,e |h ) P(h )

, i = 1,ki 1 2 n1 2 n i i

1 2 n j jj 1

k

Page 10: Inteligenta Artificiala

Teorema lui Bayes - cont

Daca e1,…,en sunt ipoteze independente atunci

PROSPECTOR

10

P(e|h ) = P(e ,e ,...,e |h ) = P(e |h ) P(e |h ) ... P(e |h ), j = 1,kj 1 2 n j 1 j 2 j n j

Page 11: Inteligenta Artificiala

1.5 Inferente din DP si RB

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

11

Page 12: Inteligenta Artificiala

Inferente din DP si RB

Distributie de probabilitate P(Carie, Dur_d, Evid)

P(Carie) = 0.108 + 0.012 + 0.72 + 0.008 = 0.2P(Carie Dur_d) = 0.108 + 0.012 + 0.072 + 0.008 + 0.016+ 0.064 = 0.28P(Carie | Dur_d) = P(Carie Dur_d) / P(Dur_d) = [P(Carie Dur_d Evid) + P(Carie Dur_d ~Evid)] *Constanta de normalizare

12

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

Page 13: Inteligenta Artificiala

Inferente din DP si RB

X – variabila de interogat (Carie)

E – multimea de probe (Dur_d), e – valorile observate pt E

Y – variabile neobservate (Evid)

P(X | e) = * P(X , e) = * y P(X, e, y)

1 – utilizam regula produsului P(A|B) = P(A B) / P(B)

2 – evaluam probabilitatea neconditionata din distributia de probabilitate

13

Page 14: Inteligenta Artificiala

1.6 Limitari ale TP

Cantitate mare de date statistice Valoare numerica unica Ignoranta = incertitudine Increderea intr-o ipoteza = neincrederea in negarea ei Interpretarea probabilitatii unei ipoteze pe baza unei probe ca

o confirmare a ipotezei Paradoxul lui Hempel• P(h|e)• h1 - toti corbii sunt negrii

• h2 - orice obiect care nu este negru nu este corb

• e - vaza este verde• P(h2|e) h1 logic echivalent cu h2 P(h1|e)

14

Page 15: Inteligenta Artificiala

2 Retele Bayesiene

Reprezinta dependente intre variabile aleatoare Dau o specificare concisa a distributiei de probabilitate Nu trebuie indicate probabilitatile conditionate ale tuturor

combinatiilor de evenimente deoarece multe sunt independente conditional

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 particulare15

Page 16: Inteligenta Artificiala

2.1 Structura retelelor Bayesiene

O RB este un DAG in care: Nodurile reprezinta variabilele aleatoare Legaturile orientate XY: X are o influenta directa

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

conditionate care cuantifica efectul parintilor asupra nodului, P(Xi | Parinti(Xi))

Exemplu Vreme, Carie Dur_d, Carie Detect

16

Page 17: Inteligenta Artificiala

Structura retelelor Bayesiene - cont

17

Cutremur

Alarma

TelMihai TelDana

HotP(H)0.001

P(C)0.002

H C P(A)T T 0.95T F 0.94F T 0.29F F 0.001

A P(M)T 0.9F 0.05

A P(D)T 0.7F 0.01

H C P(A | H, C)T F

T T 0.95 0.05T F 0.94 0.06F T 0.29 0.71F F 0.001 0.999

Tabela de probabilitaticonditionate

Page 18: Inteligenta Artificiala

2.2 Semantica retelelor Bayesiene

A) Reprezentare a distributiei de probabilitate

B) Specificare a independentei conditionale – constructia retelei

A) 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)

18

Page 19: Inteligenta Artificiala

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 consitenat cu DAG• Intuitiv, parintii unui nod Xi trebuie sa fie toate acele noduri

Xi-1,…, X1 care influenteaza direct Xi.19

Page 20: Inteligenta Artificiala

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

P(TelMaria | TelMihai, Alarma, Hot, Cutremur) = P(TelMaria | Alarma)

20

Page 21: Inteligenta Artificiala

2.4 Inferente probabilistice

21

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)

Page 22: Inteligenta Artificiala

Inferente probabilistice

22

Cutremur

Alarma

TelMihai TelDana

HotP(H)0.001

P(C)0.002

H C P(A)T T 0.95T F 0.94F T 0.29F F 0.001

A P(M)T 0.9F 0.05

A P(D)T 0.7F 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

Page 23: Inteligenta Artificiala

Inferente probabilistice

23

Cutremur

Alarma

TelMihai TelDana

HotP(H)0.001

P(C)0.002

H C P(A)T T 0.95T F 0.94F T 0.29F F 0.001

A P(M)T 0.9F 0.05

A P(D)T 0.7F 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

Page 24: Inteligenta Artificiala

Inferente probabilistice

P(H|M,D) = P(HM D) / P(M D) =

*P(H,M,D) = *c a P(H,C,A,M,D) =

*c a P(H)*P(C)*P(A|H,C)*P(M|A)*P(D|A) =

* P(H)* c P(C)* a P(A|H,C)*P(M|A)*P(D|A) =

* 0.00059224

Page 25: Inteligenta Artificiala

Enumerare(X,e,RB)Q(X) <- distrib X initial vida

pentru fiecare valoare xi a lui X repeta

extinde e cu xi pt X

Q(xi) <- Enum_Toate(Variabile(RB),e)intoarce normalizare(Q(X))

Enum_Toate(vars, e)daca vars=[ ] atunci intoarce 1.0Y<- Prim(vars)daca Y are valoarea y in eatunci intoarce P(y|parinti(y)) * -Enum_Toate(Rest(vars),e)

altfel intoarce yP(y|parinti(y) * Enum_Toate(Rest(vars), ey)// unde ey este e extins cu Y=y

Page 26: Inteligenta Artificiala

2.5 Forme de inferenta

26

Cutremur

Alarma

TelMihai TelDana

Hot

Inferente intercauzale (intre cauza si efecte comune)P(Hot | Alarma Cutremur)

Inferente mixteP(Alarma | TelMihai Cutremur) diag + cauzalP(Hot | TelMihai Cutremur) diag + intercauzal

Inferente de diagnosticare (efect cauza)P(Hot | TelMihai)

Inferente cauzale (cauza efect) P(TelMihai |Hot), P(TelDana | Hot)

Page 27: Inteligenta Artificiala

3. Factori de certitudine

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

27

Page 28: Inteligenta Artificiala

3.1 Functii de incredere

Factorul (coeficientul) de certitudine

28

contrar cazin P(h)max(0,1)

P(h)P(h))e),|max(P(h1=P(h) daca 1

=e]MB[h,

contrar cazin P(h)min(0,1)

P(h)P(h))e),|min(P(h0=P(h) daca 1

=e]MD[h,

CF[h,e] = MB[h,e] MD[h,e]

Page 29: Inteligenta Artificiala

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

29

0 MB[h,e] 1 0 MD[h,e] 1 1 CF[h,e] 1

MB[h,e] =1 P(h)

1 P(h)= 1

MD[h,e] = 0 CF[h,e] = 1

MB[h,e] = 0 1=P(h)0

P(h)0=e]MD[h,

CF[h,e] = 1

Page 30: Inteligenta Artificiala

Functii de incredere - caracteristici

Lipsa probelor

MB[h,e] = 0 daca h nu este confirmat de e, i.e. e si h sunt independente sau e infirma h.

MD[h,e] = 0 daca h nu este infirmat de e, i.e. e si h sunt independente sau e confirma h.

CF[h,e] = 0 daca e nici nu confirma nici nu infirma h, i.e. e si h sunt independente.

30

Page 31: Inteligenta Artificiala

Exemplu de utilizare CF

O regula in sistemul MYCIN, exprimata intr-un limbaj asemanator celui din MYCIN, este

daca (1) tipul organismului este gram-pozitiv, si (2) morfologia organismului este coc, si (3) conformatia cresterii organismului este lant atunci exista o incredere puternica (0.7) ca identitatea organismului

este streptococ.

Exemple de fapte in sistemul MYCIN sint urmatoarele: (identitate organism-1 pseudomonas 0.8) (identitate organism-2 e.coli 0.15) (loc cultura-2 git 1.0)

31

Page 32: Inteligenta Artificiala

3.2 Functii de combinare a incertitudinii

32

(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)

Page 33: Inteligenta Artificiala

Functii de combinare a incertitudinii

33

(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 la fel pt mai multe conditii

Page 34: Inteligenta Artificiala

Functii de combinare a incertitudinii

34

(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]

Page 35: Inteligenta Artificiala

Functii de combinare a incertitudinii

35

(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)

Page 36: Inteligenta Artificiala

3.3 Limitari ale modelului CF

36

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.

Page 37: Inteligenta Artificiala

Limitari ale modelului CF - cont

37

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

Page 38: Inteligenta Artificiala

Limitari ale modelului CF - cont

38

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

Page 39: Inteligenta Artificiala

4. Logica fuzzy

Motivatia logicii fuzzy = Reprezentarea propozitiilor cum ar fi:

Mihai este foarte bogat Maria este cam bolnava Maria si Elena sunt prietene foarte bune Exceptiile de la aceasta regula sunt aproape

imposibile Cuantifica gradul de adevar al unei afirmatii

39

Page 40: Inteligenta Artificiala

Logica fuzzy - cont

Motivatia logicii fuzzy = Reprezentarea propozitiilor cum ar fi:

L. Zadeh (1965) Apartenenta la o multime este cuantificata printr-o

valoare intre 0 si 1 De exemplu: M- multimea oamenilor bogati Mihai este miliardar - apartine lui M 90% Iulian este milionar - apartine lui M 70% Inferente: reguli de combinare a faptelor cu diverse

grade de apartenenta si a multimilor fuzzy asociate

40