2017

Reprezentare si rationament

folosind clauze precise

Capitolul 2

2017

Agenti bazati pe cunostinte

• Una dintre abordarile clasice ale IA porneste de la premisa ca

inteligenta umana este rezultatul realizarii de catre oameni a

unor procese de rationament (engl. reasoning) efectuate

asupra unor reprezentari interne ale cunoasterii.

• Acest punct de vedere a condus la ideea ca inteligenta este

“incapsulata” in agenti bazati pe cunostinte (engl. knowledge-

based agents – KBA).

• Un KBA dispune de o componeenta speciala numita sistem de

reprezentare si rationament (engl. representation and

reasoning system – RRS) a cunostintelor ce foloseste logica

matematica / computationala ca mecanism de baza pentru

reprezentarea cunostintelor si efctuarea rationamentelor asupra

cunostintelor.

2017

Sisteme de reprezentare si rationament

• Sistemele de reprezentare si rationament sunt

instrumentele de baza pentru implementarea KBA. Un

RRS se compune din:

– Un limbaj formal pentru reprezentarea cunoasterii din

domeniul problemei (engl.task domain).

– O semantica pentru specificarea intelesului enunturilor

limbajului formal al RRS.

– O teorie a rationamentului (engl.reasoning theory) numita

si procedura de demonstrare (engl.proof procedure).

2017

RRS – sintaxa

• Un limbaj formal pentru reprezentarea cunoasterii din domeniul

problemei (engl.task domain). Reprezinta partea de sintaxa a

RRS. El este specificat printr-o gramatica. Se mai numeste si

limbaj de reprezentare a cunostintelor (engl. knowledge

representation language). O multime de enunturi (engl.

statements sau sentences) in acest limbaj formeaza o baza de

cunostinte (engl.knowledge base – KB).

2017

RRS – semantica

• O semantica pentru specificarea intelesului enunturilor limbajului formal al RRS. Permite aprecierea adevarului enunturilor din baza de cunostinte independent de implementare.

• Este baza a determinarii corectitudinii si completitudinii rationamentului.

2017

RRS – teoria rationamentului

• O teorie a rationamentului (engl.reasoning theory) numita si

procedura de demonstrare (engl.proof procedure).

• De obicei este constituita dintr-o multime de reguli de

inferenta (engl.inference rules). Ele reprezinta o specificatie

nedeterminista a modului in care se determina rezultatele unei

interogari.

2017

Implementarea RRS

• Contine doua componente:

– Un program de analiza sintactica si translatare

(engl.language parser). El recunoaste enunturile corecte

exprimate in formalismul de reprezentare a cunostintelor si le

traduce sub forma unor structuri de date interne.

– O procedura de rationament (engl.reasoning procedure).

Uneori se numeste si motor de inferenta (engl. reasoning

engine). Ea reprezinta implementarea unei teorii a

rationamentului si foloseste o strategie de cautare

(engl.search strategy). Strategia de cautare are rolul de a

rezolva problema nedeterminismului din cadrul teoriei

rationamentului.

• Servicii: ASK (interogare) si TELL (revizuire).

2017

Corectitudine si completitudine

• Observatie: semantica nu este reflectata direct intr-o implementare a SRR. Ea ne da doar o modalitate de apreciere a semnificatiei simbolurilor folosite si este utila pentru interpretarea rezultatelor.

• O procedura de rationament este:

– corecta (engl.sound) in raport cu semantica daca rezultatele obtinute de aceasta procedura sunt adevarate in raport cu semantica respectiva.

– completa in raport cu semantica daca orice enunt adevarat in raport cu semantica poate fi obtinut de procedura.

2017

Utilizarea RRS

1. Se porneste de la un domeniu problema (engl.task domain). Exemple:

topologia unui birou, sistemul electric al unei case, sistemul de cursuri

al unei universitati.

2. Se identifica obiectele/conceptele/relatiile din domeniul problemei.

Aceasta etapa se mai numeste si conceptualizarea domeniului.

3. Se asociaza simboluri pentru reprezentarea obiectelelor/

conceptelor/relatiilor din domeniul problemei.

4. Se construieste baza de cunostinte din domeniul problema. Pentru

aceasta se foloseste serviciul TELL. Ea poate cuprinde:

• Cunoastere referitoare la ceea ce este adevarat in domeniul respectiv.

• Cunoastere referitoare la rezolvarea de probleme in domeniul respectiv.

5. Se interogheaza RRS folosind serviciul ASK. Rezultatele se

interpreteaza conform semanticii.

2017

Functia unui KBA

• Agentul “transmite” KB prin TELL ceea ce a perceput.

• Agentul “intreaba” KB prin ASK ce actiune trebuie sa execute.

• In final agentul “transmite” KB prin TELL ce actiune trebuie sa

execute, efectul fiind executia acestei actiuni.

2017

Rolul semanticii in RRS

2017

Metodologia de reprezentare intr-un RRS

• Se poate face o analogie intre un limbaj de programare si un RRS. La fel cum avem o metodologie de programare, tot asa exista si o metodologie de reprezentare intr-un RRS.

• Separarea teoriei rationamentului de strategia de control intr-un RRS corespunde separarii dintre logica domeniului si controlul calculului solutiei in limbajele de programare.

• Diferenta dintre un limbaj de programare ordinar si un RRS este modul de definirre a semanticii. Aceasta conduce la imposibilitatea de interpretare a rezultatelor intr-o maniera independenta de modul cum au fost ele calculate.

• Drept RRS vom folosi logica matematica. Logica permite specificarea semanticii printr-o functie de interpretare a simbolurilor limbajului in termenii entitatilor din domeniul problemei. O astfel de semantica se numeste semantica Tarskiana.

2017

Ipoteze simplificatoare in RRS

• Ipoteza IR (engl.Individuals and Relations): cunoasterea unui agent poate fi descrisa in termeni de indivizi si relatii intre indivizi. Relatiile sunt n-are. Daca n = 0 relatiile se numesc propozitii, daca n = 1 se numesc relatii unare, daca n = 2 se numesc relatii binare, etc.

• Ipoteza DK (engl.Definite Knowledge): cunoasterea unui agent consta din enunturi precise (engl.definite) si pozitive. Acest lucru inseamna ca enunturile nu sunt vagi (cu disjunctii) sau negative.

• Ipoteza SE (engl.Static Environment): mediul agentului este static.

• Ipoteza FD (engl.Finite Domain): exista un numar finit de indivizi de interes in domeniul agentului.

• SRR cu ipotezele IR, DK, SE se numeste logica clauzelor precise (engl.definite clause logic).

• SRR cu ipotezele IR, DK, SE, FD se numeste Datalog.

2017

Sintaxa Datalog (I)

• Variabila: secvente de litere, cifre si „_‟ ce incep cu litera mare sau „_‟. Exemple: X, Persoana, Lista, _002, Cel_mai_mare.

• Constanta: secvente de litere , cifre si „_‟ incepand cu litera mica (simboluri) sau secvente de cifre (numere). Exemple: carte, 120, celMaiMare, cel_mai_mare.

• Simbol de predicate: secvente de litere, cifre si „_‟ incepand cu litera mica. Exemple: p, bunic, mai_mare. Un simbol de predicat are o anumita aritate ce este un numar natural. Un simbol de predicat de aritate 0 se numeste simbol de propozitie.

• Termen: variabile sau constante.

• Atom: p, unde p este un simbol de propozitie sau p(t1, …, tn) unde p este un simbol de predicat de aritate n 1 si ti sunt termeni. Exemple: pozitiv(2), preda(costin,ia), vremea_este_frumoasa.

2017

Sintaxa Datalog (II)

• Corp: a1 ... an unde ai sunt atomi, n 1. Un corp

este o conjunctie de atomi. este simbolul “si logic” (conjunctie). Exemple: ploua bate_vantul.

• Fapt: a, unde a este atom. Exemplu: pozitiv(3).

• Regula: a b unde a este atom si b este corp.

Exemplu:

% in(P,S) profesorul P este in sala S

in(P,S)

preda(P,C)

planificat(C,S)

2017

Sintaxa Datalog (III)

• Clauza precisa: fapt sau regula.

• Interogare: ?b unde b este corp.

• Expresie: termen, atom, clauza precisa sau interogare.

O expresie se numeste de baza sau complet instantiata

(engl.ground) daca nu contine variabile.

• Baza de cunostinte: multime de clauze precise.

• Comentariu: linie ce incepe cu „%‟.

2017

Exemplu de baza de cunostinte

depozitare(X,container_metalic)

consistenta(X,solid)

proprietate(X,toxic)

depozitare(X,container_metalic)

consistenta(X,solid)

proprietate(X,inflamabil)

depozitare(X,rezervor_presurizat)

consistenta(X,gaz)

proprietate(X,inflamabil)

2017

Conceptul de semantica Tarskiana

• Semantica (engl.semantics) = o metoda de specificare a

intelesului enunturilor unui limbaj.

• In SRR bazate pe logica matematica se adopta o semantica

Tarskiana. O astfel de semantica cuprinde doua parti:

– O multime de obiecte numite si indivizi din lumea inconjuratoare, ce

formeaza domeniul problemei si o multime de relatii intre acestia.

– O corespondenta intre simbolurile din limbaj si obiectele si relatiile

din lumea inconjuratoare.

• Constantele simbolice desemneaza indivizii

• Simbolurile de relatii (predicate) desemneaza relatiile

• Aceasta corespondenta se numeste functie de interpretare.

2017

Semantica formala

• Formal inseamna in acest context precis, bine-definit, clar.

• Interpretare = un triplet I = D,, unde:

– D este o multime nevida numita domeniu. Elementele lui D se numesc indivizi.

– este o functie care asociaza fiecarui simbol de constanta c un element (c) D.

– este o functie care asociaza fiecarui simbol de predicat n-ar o functie definita pe Dn cu valori in multimea {adevarat,fals}.

• Domeniul D poate contine fie obiecte reale (de ex. persoane), fie obiecte abstracte (de ex. numere).

• Daca p este un simbol de predicat n-ar, n 1, atunci (p) este o relatie pe Dn.

• Daca p este un simbol de propozitie atunci (p) este adevarat sau fals.

2017

Exemplu de interpretare

• D = {persoana numita Alan, camera 123, camera 023, cladirea departamentului de Computer Science}. Facem observatia ca D nu este o multime de simboluri, ci o multime formata chiar din obiectele desemnate de simbolurile respective.

• Constantele simbolice sunt: alan, r123, r023, cs_building.

• Functia se defineste astfel: (alan) = persoana numita Alan, (r123) = camera 123, (r023) = camera 023, (cs_building) = cladirea departamentului de Computer Science

• Simbolurile de predicate sunt: person/1 (person de aritate 1), in/2, part_of/2

• Functia se defineste astfel:

– (person) = {(persoana numita Alan)}

– (in) = {(persoana numita Alan,camera 123), (persoana numita Alan,cladirea departamentului de Computer Science)}

– (part_of) = {(camera 123,cladirea departamentului de Computer Science), (camera 023,cladirea departamentului de Computer Science)}

2017

Adevar intr-o interpretare

• Fiecare termen de baza desemneaza printr-o interpretare I un individ. Constanta simbolica c desemneaza in I individul cI = (c) D.

• Simbolul de predicat n-ar p desemneaza in I relatia n-ara pI = (p) Dn.

• [p(t1, …, tn)]I = pI(t1

I,…,tnI)

• [p q]I = pI qI

• [p q]I = pI qI

• [h b1 ... bn]I = fals daca hI = fals si bi

I = adevarat pentru toti i =1,n altfel [h b1 ... bn]

I = adevarat.

p q p q p q

adevarat adevarat adevarat adevarat

adevarat fals fals adevarat

fals adevarat fals fals

fals fals fals adevarat

2017

• O baza de cunostinte Δ este adevarata intr-o interpretare 𝐼 daca fiecare clauza din este adevarata in I, adica Δ𝐼 = 𝑎𝑑𝑒𝑣𝑎𝑟𝑎𝑡 daca si numai daca 𝜙𝐼 = 𝑎𝑑𝑒𝑣𝑎𝑟𝑎𝑡 pentru orice 𝜙 ∈ Δ.

• Se numeste model pentru o baza de cunostinte Δ o interpretare 𝐼 astfel incat Δ𝐼 = 𝑎𝑑𝑒𝑣𝑎𝑟𝑎𝑡. Acest lucru se noteaza prin:

⊨𝐼 Δ.

• Daca Δ este o baza de cunostinte si 𝑔 este o conjunctie de atomi de baza atunci se spune ca 𝑔 este o consecinta logica a lui Δ, fapt notat prin Δ ⊨ 𝑔 daca si numai daca 𝑔 este adevarata in toate modelele lui Δ.

• Cu alte cuvinte Δ ⊨ 𝑔 daca si numai daca nu exista nici o interpretare in care Δ este adevarata si 𝑔 falsa.

Model si consecinta logica

2017

Exemple de modele si consecinte logica

(p) (q) (r) (s)

I1 adevarat adevarat adevarat adevarat

I2 fals fals fals fals

I3 adevarat adevarat fals fals

I4 adevarat adevarat adevarat fals

I5 adevarat adevarat fals adevarat

2017

Semantica din punctul de vedere al utilizatorului

1. Se alege domeniul problema. Acesta va furniza interpretarea intentionata

(engl.intended interpretation). Ea va cuprinde o multime de indivizi si o

multime de relatii.

2. Se asociaza constante simbolice indivizilor din interpretarea intentionata.

3. Se asociaza simboluri de predicate relatiilor din interpretarea intentionata.

4. Se construieste baza de cunostinte. Ea va fi formata din clauze precise

care sunt adevarate in interpretarea intentionata. Aceasta etapa se mai

numeste si axiomatizarea domeniului problema. Clauzele scrise se

numesc si axiomele domeniului.

5. Se formuleaza interogari, rezultatele fiind interpretate conform

interpretarii intentionate.

- Daca Δ ⊨ 𝑔 atunci 𝑔 va fi in particular adevarata si pentru interpretarea intentionata.

- Daca insa nu este adevarat ca Δ ⊨ 𝑔 atunci va exista un model 𝐼 al lui Δ in care 𝑔 este

falsa. Acesta poate fi tocmai interpretarea intentionata. In concluzie in aceasta situatie nu

putem sti daca 𝑔 este adevarata sau nu in interpretarea intentionata.

2017

Variabile

• Pentru definirea semanticii clauzelor cu variabile se defineste notiunea de asignare a variabilelor (engl.variable assignment). Aceasta este o functie definita pe multimea simbolurilor de variabile cu valori in domeniul D.

• Find date o interpretare I = D,, si o asignare a variabilelor , fiecarui termen t i se va asocia un individ t, din D.

– Daca t este un simbol de constanta atunci t, = (t).

– Daca t este un simbol de variabila atunci t, = (t).

• Fiind date o intepretare si o asignare a variabilelor, se poate determina valoarea de adevar a unui atom cu variabile si a unei clauze cu variabile.

• Variabilele dintr-o clauza se considera cuantificate universal. Acest lucru inseamna ca o clauza este adevarata daca si numai daca ea este adevarata pentru toate asignarile variabilelor.

2017

Interogari si raspunsuri

• Interogarile ofera posibilitatea de a determina daca o conjunctie de atomi (corp) este sau nu o consecinta logica a unei baze de cunostinte:

?b1 ... bn

• O instanta (engl.instance) a unei interogari se obtine prin inlocuirea variabilelor interogarii cu termeni (constante sau variabile) astfel incat aparitiile diferite ale aceleiasi variabile sa fie inlocuite cu acelasi termen. O astfel de inlocuire se numeste substitutie.

• Un raspuns poate fi:

– O instanta a unei interogari ce este o consecinta logica a bazei de cunostinte. Raspunsul se poate da sub forma substitutiei ce a generat instanta respectiva.

– Raspunsul „nu‟ daca nici o instanta a interogarii nu este o consecinta logica a bazei de cunostinte.

• Fie ?B o interogare si fie V1, …, Vk variabilele ce apar in conjunctia de atomi B. Se construieste urmatoarea clauza raspuns: da(V1, …, Vk) B. Determinarea raspunsului la interogare se reduce acum la determinarea tuturor instantelor atomului da(V1, …, Vk) ce sunt consecinte logice ale bazei de cunostinte reunita cu {da(V1, …, Vk) B}.

2017

Exemplu

Interogare Raspuns

?part_of(r123,B) part_of(r123,cs_building)

?part_of(r023,cs_building) nu

?in(alan,r023) nu

?in(alan,B) in(alan,r123)

in(alan,cs_building)

2017

Colorarea hartilor

color(red)

color(blue)

color(green)

color(yellow)

?coloring(C1,C2,C3,C4,C5)

C1 = red

C2 = blue

C3 = green

C4 = red

C5 = blue

120 solutions

coloring(C1,C2,C3,C4,C5)

color(C1),

color(C2),

C2 C1,

color(C3),

C3 C1, C3 C2,

color(C4),

C4 C1, ...