Intelligent systems

ARTIFICIAL INTELLIGENCE

Intelligent systems

Rule-based systems – uncertainty

BABEŞ-BOLYAI UNIVERSITY

Faculty of Computer Science and Mathematics

Topics

A. Short introduction in Artificial Intelligence (AI)

B. Solving search problems

A. Definition of search problems

B. Search strategies

A.

Uninformed search strategies

B.

Informed search strategies

C.

Local search strategies (Hill Climbing, Simulated Annealing, Tabu Search, Evolutionary algorithms, PSO, ACO)

D.

Adversarial search strategies

C. Intelligent systems

A. Rule-based systems in certain environments

B. Rule-based systems in uncertain environments (Bayes, Fuzzy)

C. Learning systems

A.

Decision Trees

B.

Artificial Neural Networks

C.

Support Vector Machines

D.

Evolutionary algorithms

D. Hybrid systems

Useful information

 Chapter V of S. Russell, P. Norvig, Artificial Intelligence: A Modern Approach, Prentice Hall, 1995

 Chapter 3 of Adrian A. Hopgood, Intelligent Systems for Engineers and Scientists, CRC Press, 2001

 Chapters 8 and 9 of C. Groşan, A. Abraham, Intelligent

Systems: A Modern Approach, Springer, 2011

Content

 Intelligent systems

 Knowledge-based systems

 Rule-based systems in uncertain environments

Intelligent systems

Knowledge based systems (KBS) Computational intelligence

Expert systems

Rule-based systems

Bayes Fuzzy

Objects, frames,

agents

Decision trees

Artificial Neural Networks

Support Vector Machines

Evolutionary Algorithms

Intelligent systems – knowledge-based systems(KBS)

 Computational systems – composed of 2 parts:

 Knowledge base (KB)

 Specific information of the domain

 Inference engine (IE)

 Rules for generating new information

 Domain-independent algorithms

Intelligent systems - KBS

Knowledge base

 Content

 Information (in a given representation) about environment

 Required information for problem solving

 Set of propositions that describe the environment

 Typology

 Perfect information



Classical logic

 IF A is true THEN A is ┐false

 IF B is false THEN B is ┐true

 Imperfect information



Non-exact



Incomplete



Incommensurable

Intelligent systems - KBS

 Sources of uncertainty



Imperfection of rules



Doubt of rules



Using a vague (imprecise) language

 Modalities to express the uncertainty



Probabilities



Fuzzy logic



Bayes theorem



Theory of Dempster-Shafer

 Modalities to represent the uncertainty



By using a single value  certainty factors, confidence, truth value

 How sure we are that the given facts are valid



By using more values  logic based on ranges

 Min  lower limit of uncertainty (confidence, necessity)

 Max  upper limit of uncertainty (plausibility, possibility)

Intelligent systems - KBS

 Reasoning techniques for uncertainty

 Teory of Bayes – probabilistic method

 Theory of certainty

 Theory of possibility (fuzzy logic)

Heuristic

methods

Intelligent systems – KBS – certainty factors

 Bayes systems

 KBS with probabilistic facts and rules

 Systems based on certainty factors

 KBS – facts and rules have associated a certainty factor (confidence factors)

 A kind of Bayes systems with the probabilities replaced by certainty factors



If A and B then C [CF

₁

]



If C and D

_[FC2]

then F [CF

₃

]

SBR cu FC



IF A and B then C



IF C and D then F

SBR classic

A B

D

C

F FC₁

FC₂

FC₃



If A and B then C [with prob p

₁

]



If C and D then F [with prob p

₂

]

SBR de tip Bayes

A

B

D

C

F p1

p2

A B

D

C F

Intelligent systems – KBS – certainty factors

 Bayes KBSs vs. KBSs based on CFs

Bayes CF

Theory of probabilities is old and

has a mathematical foundation Theory of CFs is new and without mathematical demonstrations

Require statistical information Do not require statistical data Certainty propagation

exponentially increases Information is quickly and efficiently passed

Require to apriori compute some

probabilities Do not require to apriori compute some probabilities

Hypothesis could be independent or

not Hypothesis are independent

Intelligent systems – KBS – Bayes systems

 Elements of probability theory

 Content and design

 Typology

 Tools

 Advantages and limits

Intelligent systems – KBS – Bayes systems

Amintim componenţa unui SBC

 Baza de cunoştinţe (BC)  Modalităţi de reprezentare a cunoştinţelor



Logica formală (limbaje formale)



Definiţie

 Ştiinţa principiilor formale de raţionament



Componente

 Sintaxă

 Semantică

 Metodă de inferenţă sintactică



Tipologie

 În funcţie de numărul valorilor de adevăr:

 logică duală

 logică polivalentă

 În funcţie de tipul elementelor de bază:

 clasică  primitivele = propoziţii (predicate)

 probabilistică  primitivele = variabile aleatoare

 În funcţie de obiectul de lucru:

 logica propoziţională  se lucrează doar cu propoziţii declarative, iar obiectele descrise sunt fixe sau unice (Ionică este student)

 logica predicatelor de ordin I  se lucrează cu propziţii declarative, cu predicate şi cuantificări , iar obiectele descrise pot fi unice sau variabile asociate unui obiect unic (Toţi studenţii sunt prezenţi)



Reguli



Reţele semantice

 Modulul de control (MC – pentru inferenţă)

Intelligent systems – KBS – Bayes systems

Elemente de teoria probabilităţilor

 Teorii ale probabilităţilor

 Concepte de bază

 Teoria clasică şi teoria modernă

 Eveniment

 Probabilitate simplă

 Probabilitate condiţionată

 Axiome

Intelligent systems – KBS – Bayes systems

Elemente de teoria probabilităţilor

 Teorii ale probabilităţilor

 Teoria clasică (a priori)



Propusă de Pascal şi Fermat în 1654



Lucrează cu sisteme ideale:

 toate posibilele evenimente sunt cunoscute

 toate evenimentele se pot produce cu aceeaşi probabilitate (sunt uniform distribuite)



evenimente discrete



metode combinatoriale



spaţiul rezultatelor posibile este continuu

 Teoria modernă



evenimente continue



metode combinatoriale



spaţiul rezultatelor posibile este cuantificabil

Intelligent systems – KBS – Bayes systems

Elemente de teoria probabilităţilor

 Concepte de bază

 Considerăm un experiment care poate produce mai multe ieşiri (rezultate)



Ex. Ev1: Aruncarea unui zar poate produce apariţia uneia din cele 6 feţe ale zarului (deci 6 rezultate)

 Eveniment



Definiţie

 producerea unui anumit rezultat

 Ex. Ev2: Apariţia feţei cu nr 3

 Ex. Ev3: Apariţia unei feţe cu un nr par (2,4,6)



Tipologie

 Evenimente independente şi mutual exclusive

 Nu se pot produce simultan

 Ex. Ev4: Apariţia feţei 1 la aruncarea unui zar şi Ev5: Apariţia feţei 3 la aruncarea unui zar

 Dependente

 Producerea unor evenimente afectează producerea altor evenimente

 Ex. Ev6: Apariţia feţei 6 la prima aruncare a unui zar şi Ev7: Apariţia unor feţe a căror numere însumate să dea 8 la 2 aruncări succesive ale unui zar

 Mulţimea tuturor rezultatelor = sample space al experimentului



Ex. pentru Ev1: (1,2,3,4,5,6)

 Mulţimea tuturor rezultatelor tuturor evenimentelor posibile = power set

(mulţimea părţilor)

Intelligent systems – KBS – Bayes systems

Elemente de teoria probabilităţilor

 Concepte de bază

 Probabilitate simplă p(A)



probabilitatea producerii unui eveniment A independent de alte evenimente (B)



şansa ca acel eveniment să se producă



proporţia cazurilor de producere a evenimnetului în mulţimea tuturor cazurilor posibile



nr cazurileor favorabile / nr cazurilor posibile



un număr real în [0,1]

 0 – imposibilitate absolută

 1 – posibilitate absolută



Ex. P(Ev1) =1/6, P(Ev3)=3/6

 Probabilitate condiţionată p(A|B)



probabilitatea producerii unui eveniment A dependentă de producerea altor evenimente (B)



proporţia cazurilor de producere a evenimnetului A şi a evenimentului B în mulţimea tuturor cazurilor producerii evenimentului B



probabilitatea comună /proabilitatea lui B )

( ) ) (

|

( p B

B A B p

A

p  

Intelligent systems – KBS – Bayes systems

Elemente de teoria probabilităţilor

 Concepte de bază

 Axiome



0 ≤ p(E) ≤ 1 pentru orice eveniment E



p(Adevărat) = 1, p(Fals) = 0





Dacă A şi B sunt independente

 p(A U B) = p(A) + p(B)

 p(A B ∩ ) = p(A) * p(B)



Dacă A şi B nu sunt independente

 Dacă A depinde de B

 p(A  B)=p(A) + p(B)-p(A  B)

 p(A  B) = p(A|B) * p(B)

 p(B  A) = p(A  B)



 Dacă A depinde de B

₁

, B

₂

, ..., B

_n

(evenimente mutual exclusive)

 _{( ) ( | ) ( ) (a)}



1





ⁿ

i

i

i

p B

B A p A

p

(b) )

( ) ( )

| ) (

|

( p B

A p A B B p

A

p 

 ^

i

E

i

p ( ) 1

Intelligent systems – KBS – Bayes systems

Elemente de teoria probabilităţilor

 Concepte de bază

 Exemplu



Dacă A depinde de 2 evenimente mutual exclusive (B şi ┐B), FC ec.

avem:

 p(B) = p(B|A)p(A) + p(B|┐A)p(┐A)



Înlocuind pe p(B) în ec. se obţine ec.:



Ecuaţia (c) se foloseşte pentru controlul incertitudinii în sistemele expert

) ( )

| ( )

(



1





ⁿ

i

p A B i p B i

A p

) (

) ( )

| ) (

|

( p B

A p A B B p

A

p 

(c) ) ( )

| ( ) ( )

| (

) ( )

| ) (

|

( p B A p A p B A p A

A p A B B p

A

p    

Intelligent systems – KBS – Bayes systems

Reamintim ca un SBR are următoarea Arhitectură



Baza de cunoştinţe (BC)

 Informaţiile specifice despre un domeniu



Modulul de control (MC)

 Regulile prin care se pot obţine informaţii noi



Interfața cu utilizatorul

 permite dialogul cu utilizatorii în timpul sesiunilor de consultare, precum și accesul acestora la faptele și cunoștințele din BC pentru adăugare sau actualizare



Modulul de îmbogățire a cunoașterii

 ajută utilizatorul expert să introducă în bază noi cunoștințe

într-o formă acceptată de sistem sau să actualizeze baza de cunoștințe.



Modulul explicativ

 are rolul de a explica utilizatorilor atât cunoștințele de care dispune sistemul, cât și raționamentele sale pentru obținerea soluțiilor în cadrul sesiunilor de consultare. Explicațiile într-un astfel de sistem, atunci când sunt proiectate corespunzător, îmbunătățesc la rândul lor modul în care utilizatorul percepe și acceptă

sistemul

Intelligent systems – KBS – Bayes systems

Reamintim: SBR – arhitectură

 baza de cunoştinţe



Conţinut

 Informaţiile specifice despre un domeniu sub forma unor

 fapte – afirmaţii corecte

 reguli - euristici speciale care generează informaţii (cunoştinţe)



Rol

 stocarea tuturor elementelor cunoașterii (fapte, reguli, metode de rezolvare, euristici) specifice domeniului de aplicație, preluate de la experții umani sau din alte surse

 modulul de control



Conţinut



regulile prin care se pot obţine informaţii noi



algoritmi independenţi de domeniu



creierul SBR – un algoritm de deducere bazat pe BC şi specific metodei de raţionare

 un program în care s-a implementat cunoașterea de control, procedurală sau operatorie, cu ajutorul căruia se exploatează baza de cunoștințe pentru efectuarea de raționamente în vederea obținerii de soluții, recomandări sau concluzii.



depinde de complexitate şi tipul cunoştinţelor cu care are de-a face



Rol



cu ajutorul lui se exploatează baza de cunoștințe pentru efectuarea de raționamente în

vederea obținerii de soluții, recomandări sau concluzii

Intelligent systems – KBS – Bayes systems

Conţinut şi arhitectură

 Ideea de bază

 SBR (Sisteme expert) în care faptele şi regulile sunt probabilistice

A B D

C F

 Dacă A şi B atunci C [cu probabilitatea p

₁

]

 Dacă C şi D atunci F [cu probabilitatea p

₂

]

SBR de tip Bayes

 Dacă A şi B atunci C

 Dacă C şi D atunci F

SBR classic

A B D

C F

p

₁

p

₂

Intelligent systems – KBS – Bayes systems

Conţinut şi arhitectură

 Regulile din BC sunt (în general) de forma:

 Dacă evenimentul (faptul) I este adevărat, atunci evenimentul (faptul) D este adevărat [cu probabilitatea p]

 Dacă evenimentul I s-a produs, atunci evenimentul D se va produce cu probabilitatea p



I – ipoteza (aserţiune, concluzie)



D – dovada (premisa) care susţine ipoteza

 unde:



p(I) – probabilitatea apriori ca ipoteza I să fie adevărată



p(D|I) – probabilitatea ca ipoteza I fiind adevărată să implice dovada D



p(┐I) – probabilitatea apriori ca ipoteza I să fie falsă



p(D|┐I) - probabilitatea găsirii dovezii D chiar dacă ipoteza I este falsă

 Cum şi cine calculează aceste probabilităţi?  modulul de control

(d) ) ( )

| ( ) ( )

| (

) ( )

| ) (

|

( p D I p I p D I p I

I p I D D p

I

p    

Intelligent systems – KBS – Bayes systems

Conţinut şi arhitectură

 Cum calculează MC aceste probabilităţi într-un SBR?

 utilizatorul furnizează informaţii privind dovezile observate

 experţii determină probabilităţile necesare rezolvării problemei



Probabilităţi apriori pentru posibile ipoteze (adevărate sau false) – p(I) şi p(┐I)



Probabilităţile condiţionate pentru observarea dovezii D dacă ipoteza I este adevărată p(D|I), respectiv falsă p(D|┐I)

 SBR calculează probabilitatea posteriori p(I|D) pentru ipoteza I în condiţiile dovezilor D furnizate de utilizator

 Actualizare de tip Bayes

 O tehnică de actualizare a probabilităţii p asociate unei reguli care susţine o ipoteză pe baza dovezilor (pro sau contra)

 Inferenţă (raţionament) de tip Bayes

(d) ) ( )

| ( ) ( )

| (

) ( )

| ) (

|

( p D I p I p D I p I

I p I D D p

I

p    

Intelligent systems – KBS – Bayes systems

Conţinut şi arhitectură

 Actualizare de tip Bayes

 O tehnică de actualizare a probabilităţii p asociate unei reguli care susţine o ipoteză pe baza dovezilor (pro sau contra)

 Actualizarea poate ţine cont de:



una sau mai multe (m) ipoteze (exclusive şi exhaustive)



una sau mai multe (n) dovezi (exclusive şi exhaustive)

 Cazuri:



Mai multe ipoteze şi o singură dovadă



Mai multe ipoteze şi mai multe dovezi







_m

k

k k

i i i

I p I D p

I p I D D p

I p

1

) ( )

| (

) ( )

| ) (

| (



 ^



_m

k k n

i i n i

i m

k k n

i i n n

i

I p I D D D p

I p I D p I D p I D p I p I D D D p

I p I D D D D p

D D I p

2 1

2 1

2 1

2 2 1

1

) ( )

| ...

(

) ( )

| ( )...

| ( )

| ( ) ( )

| ...

(

) ( )

| ...

) ( ...

|

(

Intelligent systems – KBS – Bayes systems

Conţinut şi arhitectură

 Exemplu numeric

 Pp. un SBR în care:



utilizatorul

 furnizează 3 dovezi condiţionate independente D

₁

, D

₂

şi D

₃



expertul

 crează 3 ipoteze mutual exclusive şi exhaustive I

₁

, I

₂

şi I

₃

şi stabileşte probabilităţile asociate lor – p(I

₁

), p(I

₂

) şi p(I

₃

)

 determină probabilităţile condiţionate pentru observarea fiecărei dovezi pentru toate ipotezele posibile

probabilitatea Ipotezele

i = 1 i = 2 i = 3

p(I

_i

) 0.40 0.35 0.25

p(D

₁

|I

_i

) 0.30 0.80 0.50

p(D

₂

|I

_i

) 0.90 0.00 0.70

p(D

₃

|I

_i

) 0.60 0.70 0.90

Intelligent systems – KBS – Bayes systems

Conţinut şi arhitectură

 Exemplu numeric

 Presupunem că prima dovadă observată este D

₃

 SE calculează probabilităţile posteriori p(I

_i

|D

₃

) pentru toate ipotezele:

 După observarea dovezii D

₃



încrederea în ipoteza I

₂

este aceeaşi cu încrederea în ipoteza I

₁



încrederea în ipoteza I

₃

creşte

32 . 25 0 . 0 90 . 0 35 . 0 70 . 0 40 . 0 60 . 0

25 . 0 90 . ) 0

| (

34 . 25 0 . 0 90 . 0 35 . 0 70 . 0 40 . 0 60 . 0

35 . 0 70 . ) 0

| (

34 . 25 0 . 0 90 . 0 35 . 0 70 . 0 40 . 0 60 . 0

40 . 0 60 . ) 0

| (

3 3

3 2

3 1

 









 

 









 

 









 

D I p

D I p

D I p

probabilitatea Ipotezele

i = 1 i = 2 i = 3

p(I_i) 0.40 0.35 0.25

p(D₁|I_i) 0.30 0.80 0.50 p(D₂|I_i) 0.90 0.00 0.70 p(D₃|I_i) 0.60 0.70 0.90

Intelligent systems – KBS – Bayes systems

Conţinut şi arhitectură

 Exemplu numeric

 Presupunem că a doua dovadă observată este D ₁

 SE calculează probabilităţile posteriori p(I _i |D ₁ D ₃ ) pentru toate ipotezele:

 După observarea dovezii D ₁



încrederea în ipoteza I

₁

scade



încrederea în ipoteza I

₂

creşte (fiind cea mai probabilă de a fi adevărată)



încrederea în ipoteza I creşte

probabilitatea Ipotezele

i = 1 i = 2 i = 3

p(I_i) 0.40 0.35 0.25

p(D₁|I_i) 0.30 0.80 0.50 p(D₂|I_i) 0.90 0.00 0.70 p(D₃|I_i) 0.60 0.70 0.90

29 . 25 0 . 0 90 . 0 50 . 0 35 . 0 70 . 0 80 . 0 40 . 0 60 . 0 30 . 0

25 . 0 90 . 0 50 . ) 0

| (

52 . 25 0 . 0 90 . 0 50 . 0 35 . 0 70 . 0 80 . 0 40 . 0 60 . 0 30 . 0

35 . 0 70 . 0 80 . ) 0

| (

19 . 25 0 . 0 90 . 0 50 . 0 35 . 0 70 . 0 80 . 0 40 . 0 60 . 0 30 . 0

40 . 0 60 . 0 30 . ) 0

| (

3 1 3

3 1 2

3 1 1

 

















 

 

















 

 

















 

D D I p

D D I p

D

D

I

p

Intelligent systems – KBS – Bayes systems

Conţinut şi arhitectură

 Exemplu numeric

 Presupunem că ultima dovadă observată este D ₂

 Se calculează probabilităţile posteriori p(I _i |D ₂ D ₁ D ₃ ) pentru toate ipotezele:

 După observarea dovezii D ₂



încrederea în ipoteza I

₁

creşte



încrederea în ipoteza I

₂

e nulă (ipoteza e falsă)



Încrederea în ipoteza I

₃

creşte

probabilitatea Ipotezele

i = 1 i = 2 i = 3

p(I_i) 0.40 0.35 0.25

p(D₁|I_i) 0.30 0.80 0.50 p(D₂|I_i) 0.90 0.00 0.70 p(D₃|I_i) 0.60 0.70 0.90

55 . 25 0 . 0 90 . 0 50 . 0 70 . 0 35 . 0 70 . 0 80 . 0 00 . 0 40 . 0 60 . 0 30 . 0 90 . 0

25 . 0 90 . 0 50 . 0 70 . ) 0

| (

00 . 25 0 . 0 90 . 0 50 . 0 70 . 0 35 . 0 70 . 0 80 . 0 00 . 0 40 . 0 60 . 0 30 . 0 90 . 0

35 . 0 70 . 0 80 . 0 00 . ) 0

| (

45 . 25 0 . 0 90 . 0 50 . 0 70 . 0 35 . 0 70 . 0 80 . 0 00 . 0 40 . 0 60 . 0 30 . 0 90 . 0

40 . 0 60 . 0 30 . 0 90 . ) 0

| (

3 1 2 3

3 1 2 2

3 1 2 1

 

























 

 

























 

 

























 

D D D I p

D D D I p

D

D

D

I

p

Intelligent systems – KBS – Bayes systems

Conţinut şi arhitectură

 Exemplu practic

 Presupunem cazul unei maşini care nu porneşte când este accelerată, dar scoate fum



Dacă scoate fum, atunci acceleraţia este defectă [cu probabilitatea 0.7]



P(I

₁

|D

₁

) = 0.7

 Pe baza unor observări statistice, experţii au constatat:



următoarea regulă:

 Dacă acceleraţia este defectă, atunci maşina scoate fum [cu probabilitatea 0.85]



probabilitatea ca maşina să pornească din cauză că acceleraţia este defectă = 0.05 (probabilitate apriori)



deci avem

 2 ipoteze:

 I₁: acceleraţia este defectă

 I₂: acceleraţia nu este defectă

 o dovadă

 D₁: maşina scoate fum

 probabilitatea că acceleraţia este defectă dacă maşina scoate fum

 P(I₁|D₁)=p(D₁|I₁)*p(I₁)/(p(D₁|I₁)*p(I₁)+p(D₁|I₂)*p(I₂))

 P(I₁|D₁)=0.23 < 0.7

I

₁

I

₂

p(I

_i

) 0.05 1-0.05=0.95

P(D

₁

|I

_i

) 0.85 1-0.85=0.15

Intelligent systems – KBS – Bayes systems

Tipologie

 Sisteme simple de tip Bayes

 Consecinţele unei ipoteze nu sunt corelate

 Reţele de tip Bayes

 Consecinţele unei ipoteze pot fi corelate

 De exemplu, reţinem informaţii despre vârsta (V), educaţia (E), câştigurile (C) şi preferinţa pentru teatru (T) ale unor persoane

V

E T

C V

E T

C

Sistem Bayes simplu (naiv) Reţea Bayes simplu

Intelligent systems – KBS – Bayes systems

 Tool-uri

 MSBNx – view

 JavaBayes – view

 BNJ – view

Intelligent systems – KBS – Bayes systems

 Avantaje ale inferenţei de tip Bayes

 Tehnică bazată pe teoreme statistice

 Probabilitatea dovezilor (simptomelor) în

ipotezele (cauzele) date sunt posibil de furnizat

 Probabilitatea unei ipoteze se poate modifica datorită uneia sau mai multor dovezi

 Dezavantaje ale inferenţei de tip Bayes

 Trebuie cunoscute (sau ghicite) probabilităţile

apriori ale unor ipoteze

Intelligent systems – KBS

 Tehnici de raţionare în medii nesigure

 Teoria Bayesiana – metodă probabilistică

 Teoria certitudinii

 Teoria posibilităţii (logica fuzzy)

Metode

euristice

Intelligent systems – KBS – certainty factors

 Conţinut şi arhitectură

 Tipologie

 Tool-uri

 Avantaje şi dezavantaje

Intelligent systems – KBS – certainty factors

Conţinut şi arhitectură

 Ideea de bază

 SBR (sisteme expert) în care faptele şi regulile au asociate câte un factor de certitudine (FC)/coeficienţ de încredere

 Un fel de sisteme de tip Bayes în care probabilităţile sunt înlocuite cu factori de certitudine



Dacă A şi B atunci C [FC

₁

]



Dacă C şi D

_[FC2]

atunci F [FC

₃

]

SBR cu FC



Dacă A şi B atunci C



Dacă C şi D atunci F

SBR classic

A B

D

C

F FC₁

FC₂

FC₃



Dacă A şi B atunci C [cu prob p

₁

]



Dacă C şi D atunci F [cu prob p

₂

]

SBR de tip Bayes

A

B

D

C

F p1

p2

A B

D

C F

Intelligent systems – KBS – certainty factors

Conţinut şi arhitectură

 FC măsoară încrederea acordată unor fapte sau reguli

 Utilizarea FC  alternativă la actualizarea de tip Bayes

 FC pot fi aplicaţi

 faptelor

 regulilor (concluziei/concluzilor unei reguli)

 fapte + reguli

 Într-un SBR (sistem expert) cu factori de certitudine



regulile sunt de forma:



dacă dovada atunci ipoteza [FC]



dacă dovada

_[FC]

atunci ipoteza



dacă dovada

_[FC]

atunci ipoteza [FC]

 ipotezele susţinute de probe sunt independente

Intelligent systems – KBS – certainty factors

Conţinut şi arhitectură

 FC – mod de calcul



Măsura încrederii (measure of belief – MB)



măsura creşterii încrederii în ipoteza I pe baza dovezii D



Măsura neîncrederii (measure of disbelief – MD)



măsura creşterii neîncrederii în ipoteza I pe baza dovezii D



Pentru evitarea valorilor negative ale MB şi MD:



FC – încrederea în ipoteza I dată fiind dovada D



Număr din [-1,1]



FC=-1 dacă se ştie că ipoteza I este falsă



FC=0 dacă nu se ştie nimic despre ipoteza I



FC=1 dacă se ştie că ipoteza I este adevărată



 



 

 

 dacă 1

) ( 1

) ( )

|

( 1 , dacă 1

) ,

( p(I)

I p

I p D I

p p(I)

D I MB



 



  

 dacă 0

) (

)

| ( ) (

0

dacă ,

1 )

,

( p(I)

I p

D I p I p

p(I) D

I MD

 



 



 

 

 dacă 1

) ( 1

) ( ) ( ),

| ( max

1

dacă ,

1 )

,

( p(I)

I p

I p I p D I p

p(I) D

I

MB  



 



 

 

 dacă 0

) ( 0

) ( ) ( ),

| ( min

0

dacă ,

1 )

,

( p(I)

I p

I p I p D I p

p(I) D

I MD

 ( , ), ( , ) 

min 1

) , ( )

, ) (

,

( MB I D MD I D

D I MD D

I D MB

I

FC 

 

Intelligent systems – KBS – certainty factors

Conţinut şi arhitectură

 FC – mod de calcul

 încrederea în ipoteza I dată fiind dovada D

 FC=-1 dacă se ştie că ipoteza este falsă

 FC=0 dacă nu se ştie nimic despre ipoteză

 FC=1 dacă se ştie că ipoteza este adevărată

Intelligent systems – KBS – certainty factors

Conţinut şi arhitectură

 FC – mod de calcul

 încrederea în ipoteza I dată fiind dovada D

 ipoteza I poate fi:

 simplă (ex. Dacă D atunci I)

 compusă (ex. Dacă D atunci I

₁

şi I

₂

şi ... I

_n

)

 dovada D poate fi

 dpdv al compoziţiei:



simplă (ex. Dacă D atunci I)



compusă (ex. Dacă D1 şi D2 şi ... Dn atunci I)

 dpdv al incertitudinii (încrederii în dovadă):



sigură (ex. Dacă D atunci I)



nesigură (ex. Dacă D[FC] atunci I)

Intelligent systems – KBS – certainty factors

Conţinut şi arhitectură

 FC – mod de calcul pentru combinarea încrederii

 o dovadă incertă care susţine sigur o ipoteză

 mai multe dovezi incerte care susţin sigur o singură ipoteză

 o dovadă incertă care susţine incert o ipoteză

 mai multe dovezi incerte care susţin incert o ipoteză

Intelligent systems – KBS – certainty factors

Conţinut şi arhitectură

 FC – mod de calcul pentru combinarea încrederii

 O dovadă incertă care susţine sigur o ipoteză

 Exemplul 1



R

₁

: Dacă A

_[FC=0.9]

atunci B



R

₂

: Dacă B atunci C



FC(B)=FC(A)=0.9



FC(C)=FC(B)=0.9

 Exemplul 2



R

₁

: Dacă E

_[FC=-0.2]

atunci F



FC(E este adevărat) = -0.2  dovadă negativă  nu putem spune nimic despre faptul că E este adevărat  nu se poate spune nimic despre F

 

 

 0, altfel

0 dacă

), ) (

( FC D FC(D)

I FC

A B C

FC=0.9 FC=0.9 FC=0.9

E F

FC=-0.2

Intelligent systems – KBS – certainty factors

Conţinut şi arhitectură

 FC – mod de calcul pentru combinarea încrederii



Mai multe dovezi incerte care susţin sigur o singură ipoteză

 Dovezi (probe) adunate incremental

 Mai multe reguli care, pe baza unor dovezi diferite, furnizează aceeaşi concluzi

 Aceeaşi ipoteză (valoare de atribut) I este obţinută pe două căi de deducţie distincte, cu două perechi diferite de valori pentru FC, FC[I,D

₁

] si FC[I,D

₂

]

 Cele doua cai de deductie distincte, corespunzatoare dovezilor (probelor) D

₁

şi D

₂

pot fi:

 ramuri diferite ale arborelui de cautare generat prin aplicarea regulilor

 dovezi (probe) indicate explicit sistemului



Exemplu

 R₁: Dacă D_{1 [FC=0.6]} atunci I

 R₂: Dacă D_2[FC=-0.3] atunci I

 FC(I,D ˄D)=(0.6+(-0.3))/(1-0.3)=0.42

 

 



 





 

  













)) sign(CF(D ))

sign(CF(D D

CF D CF

D D

) ), CF(D CF(D

D CF D

CF D CF

) ), CF(D CF(D

D CF D

CF D CF D

D I FC

2 1

2 1

2 1

2 1

1 2

1

2 1

1 2

1 2

1

dacă

| , ) (

|

|, (

| min 1

) CF(

) CF(

0 dacă

), ( 1 )(

( ) (

0 dacă

), ( 1 )(

( ) ( )

, (

D₁

D₂ FC=0.6 I

FC=0.3

FC=0.42

Intelligent systems – KBS – certainty factors

Conţinut şi arhitectură

 FC – mod de calcul pentru combinarea încrederii

 O dovadă incertă care susţine incert o ipoteză

 Exemplul 1



R

₁

: Dacă A

_[FC=0.9]

atunci B [FC=0.4]



R

₂

: Dacă B atunci C [FC=0.3]



FC(B)=FC(A)*FC(R

₁

)=0.9*0.4=0.36



FC(C)=FC(B)*FC(R

₂

)=0.36*0.3=0.108

 Exemplul 2



R

₁

: Dacă E

_[FC=-0.2]

atunci F [FC=0.6]



FC(E este adevărat) = -0.2  dovadă negativă  nu putem spune nimic despre faptul că E este adevărat  nu se poate spune nimic despre F

 

 

 0, altfel

0 dacă

), (

* ) ) (

( FC D FC regulă FC(D) I

FC

A B C

FC=0.9

FC=0.3

FC=0.108 FC=0.4

FC=0.36

E F

FC=-0.2

FC=0.6

Intelligent systems – KBS – certainty factors

Conţinut şi arhitectură

 FC – mod de calcul pentru combinarea încrederii

 Mai multe dovezi incerte care susţin incert o ipoteză

 Dovezile sunt legate prin ŞI logic

 Una sau mai multe dintre dovezile incerte care susţin incert o ipoteză

 Dovezile sunt legate prin SAU logic

 Exemplul 1

 R

₁

: Dacă D

1[FC = 0.8]

şi D

2[FC = 0.7]

şi D

3[FC = 0.5]

şi D

4[FC = 0.3]

şi D

5[FC = 0.9]

atunci I [FC = 0.65]

 

 

  

 0, altfel

n 1,2,..., i

0, ) CF(D ),

(

* ), ( ),..., ( ), ( ) min

( CF D

¹

CF D

²

CF D CF regulă dacă

ⁱ

I

CF

ⁿ

D₁

D₂

I FC=0.8

FC=0.7

FC=0.195 D₃

FC=0.5 D₄ FC=0.3

FC=0.65 ŞI

 

 

  

 0, altfel

n 1,2,..., i

0, ) CF(D ),

(

* ), ( ),..., ( ), ( ) max

( CF D

¹

CF D

²

CF D CF regulă dacă

ⁱ

I

CF

ⁿ

Intelligent systems – KBS – certainty factors

Conţinut şi arhitectură

 FC – mod de calcul pentru combinarea încrederii

 Mai multe dovezi incerte care susţin incert o ipoteză

 Dovezile sunt legate prin ŞI logic

 Una sau mai multe dintre dovezile incerte susţin incert o ipoteză

 Dovezile sunt legate prin SAU logic

 Exemplul 2

 R

₁

: Dacă D

1[FC = 0.8]

sau D

2[FC = 0.7]

sau D

3[FC = 0.5]

sau D

4[FC = 0.3]

sau D

5[FC = 0.9]

atunci I [FC = 0.65]

 FC(I) = 0.9 * 0.65 = 0.585

 

 

  

 0, altfel

n 1,2,..., i

0, ) CF(D ),

(

* ), ( ),..., ( ), ( ) min

( CF D

¹

CF D

²

CF D CF regulă dacă

ⁱ

I

CF

ⁿ

 

 

  

 0, altfel

n 1,2,..., i

0, ) CF(D ),

(

* ), ( ),..., ( ), ( ) max

( CF D

¹

CF D

²

CF D CF regulă dacă

ⁱ

I

CF

ⁿ

D₁

D₂

I FC=0.8

FC=0.7

FC=0.585 D₃

FC=0.5 D₄ FC=0.3

D₅

FC=0.65 SAU

Intelligent systems – KBS – certainty factors

Exemplu



Sistem expert pentru diagnosticarea unei răceli



Fapte în baza de date:



Febra pacientului 37.4



Pacientul tuşeşte de mai puţin de 24 ore



Pacientul nu are expectoraţii



Pacientul are o durere de cap cu FC = 0.4



Pacientul are nasul înfundat cu FC = 0.5



Reguli:



R

₁

: Dacă A: febra < 37.5 atunci

B: simptomele de răceală sunt prezente [FC=0.5]



R

₂

: Dacă C: febra > 37.5 atunci

B: simptomele de răceală sunt prezente [FC=0.9]



R

₃

: Dacă D: tuşeşte > 24 ore atunci E: durerea de gât e prezentă [FC=0.5]



R

₄

: Dacă F: tuşeşte > 48 ore atunci E: durerea de gât e prezentă [FC=1.0]



R

₅

: Dacă B: are simptome de răceală şi G: nu expectorează atunci H: a răcit [FC=-0.2]



R

₆

: Dacă E: îl doare gâtul atunci H: a răcit [FC=0.5]



R

₇

: Dacă I: îl doare capul şi

J: are nasul înfundat atunci H: a răcit [FC=0.7]



Concluzia:



Pacientul este sau nu răcit?

A

B

FC=0.5

C ^FC=0.9

D

E

FC=0.5

F ^FC=1.0

G

H

FC=-0.2

FC=0.5

I J

FC = 0.7

Intelligent systems – KBS – certainty factors

Exemplu



Sistem expert pentru diagnosticarea unei răceli



Fapte în baza de date:



Febra pacientului 37.4



Pacientul tuşeşte de mai puţin de 24 ore



Pacientul nu are expectoraţii



Pacientul are o durere de cap cu FC = 0.4



Pacientul are nasul înfundat cu FC = 0.5



Reguli:



R

₁

: Dacă A: febra < 37.5 atunci

B: simptomele de răceală sunt prezente [FC=0.5]



R

₂

: Dacă C: febra > 37.5 atunci

B: simptomele de răceală sunt prezente [FC=0.9]



R

₃

: Dacă D: tuşeşte > 24 ore atunci E: durerea de gât e prezentă [FC=0.5]



R

₄

: Dacă F: tuşeşte > 48 ore atunci E: durerea de gât e prezentă [FC=1.0]



R

₅

: Dacă B: are simptome de răceală şi G: nu expectorează atunci H: a răcit [FC=-0.2]



R

₆

: Dacă E: îl doare gâtul atunci H: a răcit [FC=0.5]



R

₇

: Dacă I: îl doare capul şi

J: are nasul înfundat atunci H: a răcit [FC=0.7]



Concluzia:



Pacientul este sau nu răcit?

A

B

FC=0.5

C ^FC=0.9

D

E

FC=0.5

F ^FC=1.0

G

H

FC=-0.2

FC=0.5

I J

FC = 0.7 FC=1

FC=-1

FC=-1

FC=-1 FC=1

FC=0.4

FC=1*0.5=0.5

FC=0.0

FC=0.2*min{0.5,1}

FC=-0.1

FC=0*0.5 FC=0 FC=0.7*min{0.4, 0.5}

FC=0.28

FC=(-0.1+0.28)/(1-min{|-0.1|,|0.28|})

FC=0.2

Intelligent systems – KBS – certainty factors

 Avantaje

 Nu este necesar calculul apriori a probabilităţilor

 Limite

 ipotezele sustinute de probe sunt independente.

 exemplu:



Fie următoarele fapte:

 A: Aspersorul a funcţionat noaptea trecută

 U: Iarba este udă dimineaţă

 P: Noaptea trecută a plouat.



şi următoarele două reguli care leagă între ele aceste fapte:

 R₁: dacă aspersorul a funcţionat noaptea trecută atunci există o încredere puternică (0.9) că iarba este udă dimineaţa

 R₂: dacă iarba este udă dimineaţa atunci există o încredere puternică (0.8) că noaptea trecută a plouat



Deci:

 FC[U,A] = 0.9 - deci proba aspersor sustine iarba uda cu 0.9

 FC[P,U] = 0.8 - deci iarba uda sustine ploaie cu 0.8

 FC[P,A] = 0.8 * 0.9 = 0.72 - deci aspersorul sustine ploaia cu 0.72

Intelligent systems – KBS – certainty factors

 SBR de tip Bayes vs. SBR cu FC

Bayes FC

Teorie probabilităţilor este veche

şi fundamentată matematic Teoria FC este nouă şi fără demostrţii matematice

Necesită existenţa unor

informaţii statistice Nu necesită existenţa unor date statistice

Propagarea încrederii creşte în

timp exponenţial Informaţia circulă repede şi

eficient în SBR

Intelligent systems - KBS

 Reasoning techniques for uncertainty

 Teory of Bayes – probabilistic method

 Theory of certainty

 Theory of possibility (fuzzy logic)

Heuristic

methods

Intelligent systems – KBS – Fuzzy systems

 Theory of possibility

 Content and design

 Typology

 Tools

 Advantages and limits

Intelligent systems – KBS – Fuzzy systems

Teoria posibilităţii (logica fuzzy)

 Why fuzzy?

 Problem: translate in C++ code the following sentences:



Georgel is tall.



It is cold outside.

 When fuzzy is important?

 Natural queries

 Knowledge representation for a KBS

 Fuzzy control – then we dead by imprecise phenomena

(noisy phenomena)

Intelligent systems – KBS – Fuzzy systems

Remember the components of a KBS

 Knowledge base  knowledge representation



Formal logic (formal languages)

 Definition

 Science of formal principles for rationing

 Components

 Syntax – atomic symbols used by language and the constructing rules of the language

 Semantic – associates a meaning to each symbol and a truth value (true or false) to each rule

 Syntactic inference – rules for identifying a subset of logic expressions  theorems (for generating new expressions)

 Typology

 True value

 Dual logic

 Polyvalent logic

 Basic elements

 Classic  primitives = sentences (predicates)

 Probabilistic  primitives = random variables

 Working manner

 Propositional logic  declarative propositions and fix or unique objects (Ionica is student)

 First-order logic  declarative propositions, predicates and quantified variables, unique objects or variables associated to a unique object

 Rules

 Semantic nets

 Inference engine

Intelligent systems – KBS – Fuzzy systems

Theory of possibility – a little bit of history

 Parminedes (400 B.C.)

 Aristotle

 "Law of the Excluded Middle“ – every sentence must be True or False

 Plato

 A third region, between True and False

 Forms the basis of fuzzy logic

 Lukasiewicz (1900)

 Has proposed an alternative and sistematic approach related to bi-valent logic of Aristotle – trivalent logic: true, false or possible

 Lotfi A. Zadeh (1965)

 Mathematical description of fuzzy set theory and fuzzy logic: truth functions takes values in [0,1] (instead of {True, False})



He as proposed new operations in fuzzy logic



He has considered the fuzzy logic as a generalisation of the classic logic

 He has written the first paper about fuzzy sets

Intelligent systems – KBS – Fuzzy systems

Theory of possibility

 Fuzzy logic

 Generalisation of Boolean logic

 Deals by the concept of partial truth



Classical logic – all things are expressed by binary elements

 0 or 1, white or black, yes or no



Fuzzy logic – gradual expression of a truth

 Values between 0 and 1

 Logic vs. algebra

 Logical operators are expressed by using mathematical terms (George Boole)



Conjunction = minimum  a  b = min (a, b)



Disjunction = maximum  a  b = max (a, b)



Negation = difference  a = 1- a

Intelligent systems – KBS – Fuzzy systems

Remember: KBS - design

 Knowledge base

 Content



Specific information

 Facts – correct affirmations

 Rules – special heuristics that generate knowledge

 Aim



Store all the information (facts, rules, solving methods, heuristics) about a given domain (taken from some experts)

 Inference engine



Content



Rules for generating new information



Domain-independent algorithms



Brain of a KBS



Aim



Help to explore the KB by reasoning for obtaining solutions, recommendations or

conclusions

Intelligent systems – KBS – Fuzzy systems

Content and design



Main idea



Cf. to certainty theory:

 Popescu is tall



Cf. to uncertainty theory

 Cf. to probability theory

 There is 80% chance that Popescu is young

 Cf. fuzzy logic



Cf. teoriei informaţiilor certe

 Popescu este tânăr



Cf. teoriei informaţiilor incerte

 Cf. teoriei probabilităţilor:

 Există 80% şanse ca Popescu să fie tânăr

 Cf. logicii fuzzy:

 Popescu’s degree of membership to the group of young people is 0.80



Necessity



Real phenomena involve fuzzy sets



Example

 The room’s temperature can be:

 low,

 Medium or

 high

 These sets of possible temperatures can overlap

 A temperature can belong to more classes (groups) depends on the person that evaluates that temperature

Intelligent systems – KBS – Fuzzy systems

Content and design

 Steps for constructing a fuzzy system



Define the inputs and the outputs – by an expert

 Raw inputs and outputs

 Fuzzification of inputs and outputs

 Fix the fuzzy variables and fuzzy sets based on membership functions

 Construct a base of rules – by an expert



Decision matrix

 Evaluate the rules



Inference – transform the fuzzy inputs into fuzzy outputs by applying all the rules

 Aggregate the results

 Defuzzificate the result

 Interpret the result

intrări Fuzzificare ^{Motor de} _inferenţă Defuzzificare ieşiri

Definirea mulţimilor

Fuzzy şi stabilirea funcţiilor de apartenenţă

Observaţii

(date brute)

Intelligent systems – KBS – Fuzzy systems

Content and design  fuzzification of input data

 Elements from probability theory (fuzzy logic)



Fuzzy facts (fuzzy sets)



Definition



Representation



Operations – complements, containment, intersection, reunion, equality, algebraic product, algebraic sum



Properties – associativity, commutativity, distributivity, transitivity, idempotency, identity, involution



Hedges



Fuzzy variables



Definition



Properties

 Establish the fuzzy variables and the fuzzy sets based on

membership functions

Intelligent systems – KBS – Fuzzy systems

Content and design  fuzzification of input data

 Elements from probability theory (fuzzy logic)  Fuzzy facts (fuzzy sets)  definition



Set definition – 2 possibilities:



By enumeration of elements

 Ex. Set of students = {Ana, Maria, Ioana}



By specifying a property of elements

 Ex. Set of even numbers ={x| x = 2n, where n = 2k}



Characteristic function μ for a set



Let X a universal set and x an element of this set (xєX)



Classical logic

 Let R a sub-set of X: RX, R – regular set

 Every element x belong to set R

 μ_R : X  {0, 1}, where



Fuzzy logic

 Let F a sub-set of X (a univers) : FX, F – fuzzy set

 Every elemt x belongs to F by a given degree of membership μ_F(x)

 μ_F : X  [0, 1], μ_F(x)=g, where gє [0,1] – membership degree of x to F

 g = 0  not-belong

 g = 1  belong

 A fuzzy set = a pair (F, μ_F ), where

 





 

R x

R x x

R

0 ,

, ) 1

 (

 

 







) number fuzzy

a is ( of part is if ) 1 , 0 (

in not is if ,

0

in totaly is

if ,

1 )

(

x F x

F x

F x

F

x

