M C

S I S T E M E D E R A Ț I O N A M E N T C U R E G U L I D E P R O D U C Ț I E

BAZE DE CUNOŞTINŢE

MI

HAELA

COLHON

ISTORIC

Deși din punct de vedere formal, regulile de producție provin din modelul computațional propus de Post (în 1943), forma de exprimare a cunoștințelor utilizând reguli precede cu mult apariția calculatoarelor. Jaynes (în 1976) descria o colecție de 20 00030 000 de tăblițe babiloniene, dintre care aproximativ 20% conțin o mulțime de reguli de productie, numite omenuri, pentru îndrumarea activității de zi cu zi. Aceste reguli au numite omenuri, pentru îndrumarea activității de zi cu zi. Aceste reguli au fost catalogate încă din anul 650 I.C. și aveau o formă asemănătoare celei din sistemele bazate pe reguli din IA, de exemplu:

"Dacă un cal intră în casa unui om și mușcă acel om, atunci proprietarul casei va muri și casa lui se va prăbuși."

"Dacă un om calcă, din neatenție, o șopîrlă și o omoară, atunci el va triumfa asupra unui adversar al său."

SISTEME BAZATE PE CUNOȘTINȚE

Caracteristici:

• sunt definite pentru un

domeniul precis de

cunoaștere/cunoștințecunoaștere/cunoștințe

• sunt proiectate pentru

rezolvarea problemelor ce

necesită un volum mare de

cunoștințe

• sunt înzestrate cu toate cunoștințe pe care le are un expert uman în domeniul sistemului

STRUCTURA UNUI S.B.C.

Metoda de reprezentare a cunoștințelor

STRUCTURA DE BAZĂ A UNUI SBC

Principalele trei module ale unui SBC sunt:

• o bază de cunoștințe

• un motor de inferență

• o interfață cu utilizatorul• o interfață cu utilizatorul

Baza de cunoștințe: cuprinde toate cunoștințele sistemului ce pot avea diverse reprezentări: fapte, reguli,metode, euristici sau diverse informații pentru rezolvarea problemei

Motorul de inferență: utilizează în mod activ cunoștințele din baza de cunoștințe

Interfața cu utilizatorul: împreuna cu motorul de inferență formează shell-ul SBCurilor

REPREZENTAREA CUNOȘTINȚELOR CU REGULI IF-THEN

Regulile de tip if-then numite și reguli de producție constituie o formă naturală de exprimare a cunoștințelor:

• modularitate: fiecare regulă definește o cantitate relativ mică și independentă de cunoștințerelativ mică și independentă de cunoștințe

• icrementabilitate: noi reguli pot fi adăugate relativ independent de celelalte reguli din bază

• modificabilitate: rezultă din modularitate

• susțin transparența sistemului (transparența = abilitatea sistemului de a genera explicații la soluțiile găsite)

TIPURI DE REGULI.REGULI DE PRODUCTIE

Caracteristici:

• construite manual de catre experti

• sunt executate de motoare de inferenta specifice (ex. Jess, CLIPS, etc.)

Exemple:

IF temperatura=„foarte_mare” THEN risc_cardiac=„mare”

TIPURI DE REGULI.REGULI DE PRODUCTIE CU EXCEPTII

Caracteristici:

• construite manual de catre experti

• exista motoare de inferenta care le suporta

Exemple:Exemple:

IF Forma_angajare=„salariat” THEN Nivel Risc=„mic” UNLESS Nivel debit=„mare”

TIPURI DE REGULI.REGULA DE PRODUCTIE FUZZY

Caracteristici:

• construite manual de catre experti

• exista motoare de inferenta (fuzzy) care le suporta

Exemple:Exemple:

IF temperatura=„mare” AND nas_infundat=„yes” THEN diagnostic=„gripa” CF 80%

GENERAREA EXPLICAȚIILOR FOLOSIND REGULI DE PRODUCȚIE

Regulile de producție facilitează generarea răspunsului pentru următoarele doua tipuri de întrebări:

• întrebări de tipul cum: Cum s-a ajuns la acest răspuns/această soluție?

intrebări de tipul de ce: De ce s-a folosit această • intrebări de tipul de ce: De ce s-a folosit această informație?

Generarea explicațiilor este o trasătură importantă a SBC pentru că în felul acesta se pot verifica raționamentele și astfel se pot depista ușor posibilele erori.

STUDIU DE CAZ

bucatarie_uscat

hol_ud

scurgere_baie

fereastra

bucatarie

baie

baie_uscat

fereastra_inchisa

fara_ploaie

problema la bucatarie

fara_apa_din_afara

scurgere_in_bucatarie

baie hol

SBC CU REGULI DE PRODUCȚIE

Mecanismul de inferenţă poate folosi trei moduri de raţionament:

• forward, dirijat de fapte (inferenţă cu înlănţuire înainte)

• backward, dirijat de scop (inferenţă cu înlănţuire înapoi)

• mixt

INFERENȚA IN SBC CU REGULI DE PRODUCȚIE

ÎNLĂNȚUIRE ÎNAINTE VS ÎNLĂNȚUIRE ÎNAPOI

Regulile if-then formează lanțuri de forma:

informatie_input →→→→ ... →→→→ informatie_dedusă

Informația de intrare = datele sistemului

Informația dedusă = ipotezele sistemuluiInformația dedusă = ipotezele sistemului

Atât înlănțuirea înapoi cât și înlănțuirea înainte presupun căutare, însă direcția de căutare este diferită.

• înlănțuirea înapoi este orientată către scop

• înlănțuirea înainte este orientată către date

SBC CU REGULI DE PRODUCȚIE. FORMALISM

Un SBC cu reguli de producție este un tuplu (CP, CD, CF, R, M) , în care:

• CP = {s1,……,sk} este o mulţime finită de simboluri care reprezintăcunoştinţele primare.

• CD = {q1,……,qr} este o mulţime finită, ale cărei elemente• CD = {q1,……,qr} este o mulţime finită, ale cărei elementereprezintă cunoştinţele intermediare deduse.

• CF = {p1,……,pn} este o mulţime finită de simboluri astfel încât fiecare simbol pi reprezintă o concluzie finală sau o cunoştinţă finală.

• R este o mulţime finită de reguli de forma

• IF premiză THEN concluzie

• M este motorul de inferenţe. Sarcina principală a acestuia estede a combina regulile din R pentru a obţine ca rezultat unul saumai multe elemente din CF.

SBC CU REGULI DE PRODUCȚIE

Este necesar să facem următoarele precizări:

• Un sistem de deducţie este capabil să efectueze un raţionament într-un anumit domeniu precizat foarte exact încă de la proiectarea lui. De aceea, mulţimea CF este mulţimea tuturor concluziilor pe care le poate CF este mulţimea tuturor concluziilor pe care le poate deduce.

• Mulţimea CP reprezintă mulţimea tuturor cunoştinţelorprimare pe care le poate utiliza sistemul. Astfel spus, elementele lui CP reprezintă toate situaţiile iniţiale posibile.

ÎNLANȚUIRE ÎNAINTE

Pentru realizarea unei deducţii particulare folosind înlănțuirea înainte motorul de inferenţe utilizează o submulţime CP0 ⊆ CP şi pe baza regulilor din R obţine, dacă este posibil, o submulţime CF0 ⊆ CF. Avem următoarele două cazuri:următoarele două cazuri:

• CF0 = ∅; în acest caz motorul de inferenţe nu poaterealiza deducţia pe baza cunoştinţelor din CP0.

• CF0 ≠ ∅; în acest caz rezultatul deducţiei esteconjunţia logică a elementelor din CF0.

ÎNLĂNȚUIREA ÎNAINTE

Considerăm secvenţa {Xi}i de mulţimi definite recursivastfel:

X0 = CP0

Xn+1 = Xn ∪ {d| ∃ Ri : Ri (c1 , ……, ck ; d), c1 , ……, ck ∈ Xn}n+1 n i i 1 k 1 k n

Relativ la secvenţa de mulţimi {Xn}n definită mai sus, putem demonstra urmatoarele proprietăţi:

Propoziţie:

• Există n0 astfel încât X0 ⊂ X1 ⊂ … ⊂ Xn0 = Xn+1 şi Xn0 = Xn0+t

pentru orice t ≥ 0

• d ∈ Xn0 dacă şi numai dacă d este deductibil din CP0

ÎNLĂNȚUIREA ÎNAINTE

Un element d ∈ CD ∪ CF este deductibil din CP0

dacă există o secvență (y1, ..., yr) a.î.

1) d= yr

2) pt. ∀ i ∈ {1,...,r} avem yi ∈ CP0 sau există o regulă R ∈ R i există (y , ..., y ) cu m , ..., m < i a.î.

i 0

Rj ∈ R și există (ym1, ..., ymk) cu m1, ..., mk < i a.î. Rj(ym1, ..., ymk; yi)

ÎNLĂNȚUIREA ÎNAINTE

Propoziție.

1) Există n0 a.î. X0 ⊂ X1 ⊂ ... Xn0 = Xn0+1 și Xn0 = Xn0+t, ∀t ≥1.

2) d ∈ Xn0 dacă și numai dacă d este deductibil din CP .

n0

CP0.

ÎNLĂNȚUIREA ÎNAPOI

Pentru o submulțime D ⊆ CP ∪ CD ∪ CF vom nota cu Subst(D) mulţimea submulţimilor A ⊆ CP ∪ CD ∪ CF obţinute din D astfel:

• D ∩ CP ⊆ A

pentru fiecare element y ∈ D\CP se alege o regulă IF • pentru fiecare element y ∈ D\CP se alege o regulă IF x1 ∧ ... xr THEN y din R și se înlocuiește y din A cu elementele x1,..., xr.

Fie X = {D1,..., Dm}. Definim:

Subst(X) = {Subst(D1), ..., Subst(Dm)}

ÎNLĂNȚUIREA ÎNAPOI

Metoda backward se realizează astfel:

• Se consideră un element p ∈ CF.

• Se calculează secvenţa

X0 = {p}X0 = {p}

Xn+1 = Subst(Xn) , n≥0

Calculul secvenţei X0, X1, ……se opreşte la acel indice n pentru care Xn ⊆ 2CP deoarece în acest caz

Xn+1 = Subst(Xn) = Xn .

ÎNLĂNȚUIRE ÎNAINTE VS ÎNLĂNȚUIRE ÎNAPOI

Care tip de raționament este preferabil?

date →→→→ scop

scop →→→→ date

ÎNLĂNȚUIRE ÎNAINTE VS ÎNLĂNȚUIRE ÎNAPOI

Dacă se dorește verificarea unei anumite ipoteze –raționament înapoi.

Dacă există o multitudine de ipoteze și nicio motivație cu privire la testarea cu prioritate a unei ipoteze particulare – raționament înainte.particulare – raționament înainte.

Sistemele care presupun achiziția constantă de date de intrare de asemenea se pretează raționamentelor înainte.

În general:

număr mic de date de intrare și unul ridicat de scopuri ⇒ raționament înainte

număr mic de scopuri și unul ridicat de date de intrare ⇒ raționament înapoi

STRATEGII DE CONTROL IN MECANISME INFERENTIALE

STATEGIA DE CONTROL ÎNAINTEStare Iniţială

Regula 1

Stare Succesivă

Regula 2Regula 2

Stare succesivă 2

Regula 3(operatorul 3)

.

.

.

Regula n (operatorul n)

<Stare finală> = <obiectivul problemă>

STRATEGII DE CONTROL IN MECANISME INFERENTIALE

STRATEGIA DE CONTROL INAINTE

Aplicarea acestor reguli determină date sau chiar fapte noi. Astfel se poate obţine un set de derivări valabile prinaplicarea mai multor reguli, dar numai un element din acest aplicarea mai multor reguli, dar numai un element din acest set face parte din pasul ce conduce la soluţia problemei. A-priori nu se cunoaşte care regulă duce la rezolvarea problemei astfel incat trebuie să se parcurgă toate regulile ce sunt posibile de aplicat, obţinându-se la fiecare pas al problemei o mulţime de stări numite fapte. Procesul continuă până când mulţimea regulilor care urmeaza se se aplicedevine null.

STRATEGII DE CONTROL IN MECANISME INFERENTIALE

STRATEGIA DE CONTROL ÎNAPOI

Obiectiv problemă = Stare finală

Regula 1Regula 1

Stare precedenta 1

Regula 2

Stare precedenta 2

……………………………..

Regula n

Stare precedenta n = Stare iniţială

STRATEGII DE CONTROL IN MECANISME INFERENTIALE

STRATEGIA DE CONTROL ÎNAPOI

Acest control mai poartă numele şi de control orientat de obiectivul problemei sau de căutare de sus în jos. sus în jos.

Condiţiile necunoscute devin în acest mod subscopuri ce se vor putea demonstra. Procesul se continua până când toate subscopurile se rezolvă.

ARBORI DE DECIZIE

Formal, un arbore de decizie este o pereche (N,A) cu urmatoarele proprietati:

• N={n1,..., nk} este multimea de noduri ale arborelui

• A={(n1, n2)| n1, n2 ∈ N} este multimea de arce ale arborelui

1 2 1 2

arborelui

• ∃!R∈N, a.î. Card{(m,R)∈A|m∈N}=0, iar R este radacina arborelui

• ∀n∈N, n≠R, Card{(m,n)∈A|m∈N}=1

ARBORI DE DECIZIE

O secventa de arce: C=(n1, n2), (n2, n3), ..., (nk-1, nk) se numeste cale intre nodurile n1 si nk. Daca nodul nk

este frunza atunci C se numeste cale de demonstrare.

Propozitie. Daca exista o cale intre nodurile n si n in Propozitie. Daca exista o cale intre nodurile n1 si nk in arborele de decizie, atunci aceasta cale este unica.

Demonstratie

Presupunem ca C1=(n1, n21 ..., nk-1

1, nk) si

C2 = (n1, n22, ..., nk-1

2, nk) doua cai distincte in arbore. Rezulta ca ∃ nj a.î. Card{(m,nj)∈A}=2. imposibil

GENERAREA EXPLICAȚIILOR

Explicațiile sistemului la întrebări de tipul cum implică construirea arborelui de demonstrație pentru modul în care a fost dedusă concluzia finală din regulile și faptele aflate în baza de cunoștințe.

Astfel, dacă propoziția rezultată este P atunci:Astfel, dacă propoziția rezultată este P atunci:

• dacă P este un fapt atunci arborele de demonstrație este P

• dacă P a fost dedus folosind o regulă de forma

If Cond Then P

atunci arborele de demosntrație este P ⇐⇐⇐⇐ DemCond

unde DemCond este arborele de demonstrație a lui

Cond.

Vă mulţumesc!