Assuntos para 2o exercício
Métodos de Computação Inteligente
1o semestre de 2002
Jacques Robin
CIn-UFPE
Assuntos para o 2o exercício



Tema do 2o exercício: sistemas especialistas
Leitura: capítulos 15 e 16 de Prolog Programming for Artificial
Intelligence, 3rd Ed. de Ivan Bratko
Tarefas:
 Implementar um shell de sistema especialista com funcionalidades de:




Máquina de inferência
Aquisição interativa de conhecimento
Justificação das perguntas de aquisição
Explicação de raciocínio
 Implementar uma base de conhecimento brinquedo na linguagem de
representação do conhecimento aceita pelo shell
 Testar o shell com essa base de conhecimento

Equipes de 4 alunos
Assuntos para o 2o exercício





Sistema especialista baseado em redes bayesianas em
Prolog, Flora, JEOPS ou Java
Sistema especialista combinando encadeamento de
regras para frente e para trás em Prolog, Flora,
JEOPS ou Java
Sistema especialista combinado frames com regras
encadeadas para frente em Prolog ou Java
Sistema especialista combinado frames com regras
encadeadas para trás em Prolog ou Java
2 equipes podem escolher o mesmo assunto, do momento
que escolhem duas linguagens de programação diferentes
Implementação Prolog de máquina de
inferência encadeando regras
Codificação da base de fatos
•
fact(TermoProlog).
Codificação da base de regras
•
•
•
if P1 conj ... conj Pn then C onde
P1 ... Pn e C são termos Prolog
conj é and ou or
Codificação das consultas
•
forward deriva todos os fatos
Exemplo de base de conhecimento
if hallWet and kitchenDry then leakInBathroom
if hallWet and bathroonDry then problemInKitchen
if windowClosed or noRain then noWaterFromOutside
if problemInKitchen and noWaterFromOutside
then leakInKitchen
Exemplos de consulta
?- forward
Derive: problemInKitchen
Derive: noWaterFromOutside
Derive: leakInKitchen
No more facts
?- is_true(leak_in_kitchen).
yes
Implementação Prolog de máquina de
inferência encadeando regras
Para frente:
::::-
op( 800, fx, if).
op( 700, xfx, then).
op( 300, xfy, or).
op( 200, xfy, and).
forward :- new_derived_fact(P), !,
write('Derived: '), write(P), nl, assert(fact(P)),
forward ; write('No more facts').
new_derived_fact(Concl) :- if Cond then Concl,
not fact(Concl), composed_fact(Cond).
composed_fact(Cond) :- fact(Cond).
composed_fact(Cond1 and Cond2) :composed_fact(Cond1), composed_fact(Cond2).
composed_fact(Cond1 or Cond2) :composed_fact(Cond1) ; composed_fact(Cond2).
Pata trás:
::::-
op( 800, fx, if).
op( 700, xfx, then).
op( 300, xfy, or).
op( 200, xfy, and).
is_true( P) :- fact( P).
is_true( P) :- if Condition then P,
is_true( Condition).
is_true( P1 and P2) :- is_true( P1), is_true( P2).
is_true( P1 or P2) :- is_true( P1) ; is_true( P2).
Implementação Prolog de máquina de
inferência encadeando regras para trás
Implementação Prolog de máquina de
inferência baseada em frames
Codificação dos triplos <frame slot value>
•
•
fatos frame(Slot,Value).
com um predicado por cada frame do domínio
Codificação dos gatilhos
•
•
regras da forma: trigger(Frame,Value) :- ....
com um predicado trigger por cada gatilho do domínio
Associação dos triplos <frame slot trigger>
•
•
fatos frame(Slot, execute(gatilho(Frame,Value), Frame,Value)).
um por par <frame trigger> do domínio
Codificação das consultas
•
calcular valor de um slot de um frame
value(Frame, Slot,Value)
Implementação Prolog de máquina de
inferência baseada em frames
Hierarquia de conceitos:
Sobrescrita de propriedades default:
bird(a_kind_of, animal).
albatross(a_kind_of, bird).
kiwi(a_kind_of, bird).
kiwi(moving_method, walk).
kiwi(active_at, night).
albert(size, 120).
ross(size, 40).
Propriedades dos conceitos e default das
suas especializações e instâncias:
Gatilho:
bird(moving_method, fly).
bird(active_at, daylight).
albatross(colour, black_and_white).
albatross(size, 115).
kiwi(size, 40).
kiwi(colour, brown).
animal(relative_size,
execute(relative_size(Object, Value),
Object, Value) ).
relative_size(Object,RelativeSize) :value(Object,size,Objsize),
value(Object,instance_of,ObjClass),
value(ObjClass,size,ClassSize),
RelativeSize is ObjSize/ClassSize * 100.
Instâncias de conceitos:
Exemplo de consultas
albert(instance_of, albatross).
ross(instance_of, albatross).
?- value(ross,moving_method,M).
M = fly.
?- value(ross,relative_size,R)
R = 34.78.
Implementação Prolog de máquina de
inferência baseada em frames
% Valor declarada no próprio frame:
value(Frame,Slot,Value) :value(Frame,Frame,Slot,Value).
% Valor herdada do super conceito imediato:
value(Frame,SuperFrame,Slot,Value) :Query =.. [SuperFrame,Slot,Information],
call(Query),
process(Information,Frame,Value), !.
% Valor herdada de conceitos mais altos na
hierarquia:
value(Frame,SuperFrame,Slot,Value) :parent(SuperFrame,ParentSuperFrame),
value(Frame,ParentSuperFrame,Slot,Value).
% Acessar super-conceito na hierarquia:
parent(Frame,ParentFrame) :(Query =.. [Frame,a_kind_of,ParentFrame]
; Query =.. [Frame,instance_of,ParentFrame]),
call(Query).
% Information é derivada por um gatilho
process(execute(Goal,Frame,Value),Frame,Value)
:- !, call(Goal).
% Information é um valor declarado
process(Value,_,Value).
Implementação Prolog de máquina de
inferência baseada redes bayesianas
Codificação da estrutura da rede
•
predicado parent(ParentNode, Node)
Codificação das probabilidades da rede
•
•
predicado p(Node, PriorProbability)
predicado p(Node, ListOfParentNodeValues,
ConditionalProbability)
i.e., p(N0 | N1  ...  Nn)
Codificação das consultas a rede
•
predicado probs(Node, ListOfNodeValues
ConditionalProbability)
i.e., p(N0 | N1  ...  Nn)
Exemplo de rede:
parent(burglary, sensor).
parent(lightning, sensor).
parent(sensor, alarm).
parent(sensor, call).
p(burglary, 0.001).
p(lightning, 0.02).
p(sensor, [ burglary, lightning], 0.9).
p(sensor, [ burglary, not lightning], 0.9).
p(sensor, [ not burglary, lightning], 0.1).
p(sensor, [ not burglary, not lightning], 0.001).
p(alarm, [ sensor], 0.95).
p(alarm, [ not sensor], 0.001).
p(call, [ sensor], 0.9).
p(call, [ not sensor], 0.0).
Exemplo de consulta:
?- prob(burglary, [call, not lightning], P).
P = 0.473934
Implementação Prolog de máquina de
inferência baseada redes bayesianas
prob([X | Xs], Cond, P) :- !, prob(X, Cond, Px),
prob(Xs, [X | Cond], PRest), P is Px * PRest.
prob([], _, 1) :- !.
prob(X, Cond, 1) :- member(X, Cond), !.
prob(X, Cond, 0) :- member(not X, Cond), !.
prob(not X, Cond, P) :- !,
prob(X, Cond, P0), P is 1 - P0.
prob(X, Cond0, P) :- delete(Y, Cond0, Cond),
predecessor(X, Y), !, prob(X, Cond, Px),
prob(Y, [X | Cond], PyGivenX),
prob(Y, Cond, Py), P is Px * PyGivenX / Py.
prob(X, Cond, P) :- p(X, P), !.
% Coloca
prob(X, Cond, P) :- !,
findall((CONDi,Pi), p(X,CONDi,Pi), CPlist),
sum_probs(CPlist, Cond, P).
% Calcula p(X|Cond) como somatórios nos
% predecessores Si de X na rede de
% p(X|Si)*p(Si|Cond)
sum_probs([], _, 0).
sum_probs([(COND1,P1)|CondsProbs], COND, P)
:- prob(COND1, COND, PC1),
sum_probs(CondsProbs, COND, PRest),
P is P1 * PC1 + PRest.
% Busca por predecessores subindo na rede
predecessor(X, not Y) :- !, predecessor(X, Y).
predecessor(X, Y) :- parent(X, Y).
predecessor(X, Z) :- parent(X, Y),
predecessor(Y, Z).
% Predicados utilitários
member(X, [X | _]).
member(X, [_ | L]) :- member(X, L).
delete(X, [X | L], L).
delete(X, [Y | L], [Y | L2]) :- delete(X, L, L2).
Implementação Prolog de shell de sistema
especialista encadeando regras para trás
Codificação das regras para o shell:


RuleName :: if Condition then Conclusion,
onde:
 Condition é um termo Prolog
 Conclusion são termos Prolog conectados por and, or ou not
Codificação dos fatos para o shell:


fact :: ShellFact
onde: ShellFact é um fato Prolog ou uma regras Prolog
Sintaxe natural:

Operadores Prolog podem ser usados para definir propriedades podem ser definidos e aparecer nas
regras e fatos do shell para tornar a aparência da base de conhecimento “mais natural”
Aquisição interativa dos fatos via o shell:

askable(Term) indica que o termo Prolog Term é um dos fatos do shell cujo valor (os valores das
suas variáveis não instanciadas) pode ser pedido para o usuário durante o raciocínio
Implementação Prolog de shell de sistema
especialista encadeando regras para trás
% Operadores de ‘sintaxe natural’
:- op( 100, xfx, [ has, gives, 'does not', eats, lays, isa]).
:- op( 100, xf, [ swims, flies]).
% Base de regras
rule1 :: if Animal has hair or Animal gives milk then Animal isa mammal.
rule2 :: if Animal has feathers or (Animal flies and Animal lays eggs) then Animal isa bird.
rule3 :: if Animal isa mammal and (Animal eats meat or (Animal has 'pointed teeth' and
Animal has claws and
Animal has 'forward pointing eyes' )
then Animal isa carnivore.
rule4 :: if Animal isa carnivore and Animal has 'tawny color' and Animal has 'dark spots'
then Animal isa cheetah.
rule5 :: if Animal isa carnivore and Animal has 'tawny color' and Animal has 'black stripes'
then Animal isa tiger.
rule6 :: if Animal isa bird and Animal 'does not' fly and Animal swims then Animal isa penguin.
rule7 :: if Animal isa bird and Animal isa 'good flyer' then Animal isa albatross.
% Base de fatos
fact :: X isa animal :- member( X, [cheetah, tiger, penguin, albatross]).
askable( _ gives _, 'Animal' gives 'What'). askable( _ flies, 'Animal' flies).
askable( _ lays eggs, 'Animal' lays eggs). askable( _ eats _, 'Animal' eats 'What').
askable( _ has _, 'Animal' has 'Something'). askable( _ 'does not' _, 'Animal' 'does not' fly).
askable( _ swims, 'Animal' swims). askable( _ isa 'good flyer', 'Animal' isa 'good flyer').
member(X,[X | _]).
member( X, [_ | Rest]) :- member( X, Rest).
Implementação Prolog de shell de sistema
especialista encadeando regras para trás
% Base de regras
broken_rule :: if on(Device) and device( Device) and (not working(Device))
and connected( Device, Fuse) and proved( intact( Fuse))
then proved( broken( Device)).
fuse_ok_rule :: if connected( Device, Fuse) and working( Device) then proved( intact( Fuse)).
fused_rule :: if connected( Device1, Fuse) and on( Device1) and (not working( Device1))
and samefuse( Device2, Device1) and on( Device2) and (not working( Device2))
then proved( failed( Fuse)).
same_fuse_rule :: if connected( Device1, Fuse) and connected( Device2, Fuse)
and different( Device1, Device2)
then samefuse( Device1, Device2).
device_on_rule :: if working( Device) then on( Device).
% Base de fatos
fact :: different( X, Y) :- not (X = Y).
fact :: device( heater). fact :: device( light1). fact :: device( light2). fact :: device( light3).
fact :: device( light4).
fact :: connected( light1, fuse1). fact :: connected( light2, fuse1). fact :: connected( heater, fuse1).
fact :: connected( light3, fuse2). fact :: connected( light4, fuse2).
askable( on(D), on('Device')). askable( working(D), working('Device')).
Implementação Prolog de shell de sistema
especialista encadeando regras para trás
Question, please:
peter isa tiger.
Is it true: peter has hair?
yes.
Is it true: peter eats meat?
no.
Is it true: peter has pointed teeth?
yes.
Is it true: peter has claws?
why.
To investigate, by rule3, peter is a carnivore
To investigate, by rule 5, peter is a tiger
This was your question.
Is it true: peter has claws?
yes.
Is it true: peter has forward pointing eyes?
yes.
Is it true: peter has tawny colour?
yes.
Is it true: peter has black stripes?
yes.
(peter is a tiger) is true
Would you like to see how?
yes.
peter is a tiger was derived by rule5 from
peter isa carnivore was derived by rule3 from
peter is mamamal was derived by rule1 from
peter has hair was told
and peter has pointed teeth was told
and peter has claws was told
and peter has forward pointing eyes was told
and peter has tawny color was told
and peter has black stripes was told
Question, please:
Implementação Prolog de shell de sistema
especialista encadeando regras para trás
Predicados principais:
expert: dispara o sistemas especialista
 explore(Goal,Trace,Answer):
 dispara encadeamento de regras para trás
para tentar provar objetivo Goal
 guarda em Trace a lista dos objetivos
intermediários que foram provados, junto
a regra utilizada para prova cada um
 guarda em Answer a árvore da prova de
Goal
 useranswer(Goal,Trace,Answer):

 caso Goal for askable, pergunta Goal para o
usuário
 caso a resposta a essa pergunta for yes or no,
instância Answer com essa resposta
 caso a resposta a essa pergunta for why,
apresenta Trace como respota
 usa getreply(Reply) para recuperar de maneira
robusta a resposta do usuário

present(Answer): apresenta Answer para o
usuário como resposta a perguntas de tipo
how?
Implementação Prolog de shell de sistema
especialista encadeando regras para trás
% Operadores do shell
:- op( 900, xfx, ::).
:- op( 800, xfx, was).
:- op( 870, fx, if).
:- op( 880, xfx, then).
:- op( 550, xfy, or).
:- op( 540, xfy, and).
:- op( 300, fx, 'derived by').
:- op( 600, xfx, from).
:- op( 600, xfx, by).
:- op( 900, fy, not).
% Predicado driver do shell
expert :- getquestion(Question),
(answeryes(Question) ; answerno( Question)).
getquestion(Question) :- nl,
write( 'Question, please '), nl, read( Question).
answeryes(Question) :- markstatus( negative),
explore( Question, [], Answer), positive( Answer),
markstatus( positive), present( Answer), nl,
write('More solutions? '), getreply( Reply),
Reply = no.
answerno( Question) :retract(no_positive_answer_yet), !,
explore( Question, [], Answer), negative( Answer),
present( Answer), nl,
write('More negative solutions? '),
getreply( Reply), Reply = no.
markstatus( negative) :assert(no_positive_answer_yet).
markstatus( positive) :retract(no_positive_answer_yet), ! ; true.
Implementação Prolog de shell de sistema
especialista encadeando regras para trás
explore(Goal,Trace, _) :- copy_term( Goal, Copy), member( Copy by Rule, Trace),
instance_of( Copy, Goal), !, fail.
explore(Goal,Trace, Goal is true was 'found as a fact') :- fact :: Goal.
explore(Goal,Trace, Goal is TruthValue was 'derived by' Rule from Answer) :Rule :: if Condition then Goal, explore( Condition, [Goal by Rule | Trace], Answer),
truth( Answer, TruthValue).
explore( Goal1 and Goal2, Trace, Answer) :- !, explore( Goal1, Trace, Answer1),
continue( Answer1, Goal1 and Goal2, Trace, Answer).
explore( Goal1 or Goal2, Trace, Answer) :- exploreyes( Goal1, Trace, Answer) ;
exploreyes( Goal2, Trace, Answer).
explore( Goal1 or Goal2, Trace, Answer1 and Answer2) :- !, not exploreyes( Goal1, Trace, _),
not exploreyes( Goal2, Trace, _), explore( Goal1, Trace, Answer1), explore( Goal2, Trace, Answer2).
explore( not Goal, Trace, Answer) :- !, explore( Goal, Trace, Answer1), invert( Answer1, Answer).
explore( Goal, Trace, Goal is Answer was told) :- useranswer( Goal, Trace, Answer).
Implementação Prolog de shell de sistema
especialista encadeando regras para trás
exploreyes( Goal, Trace, Answer) :- explore( Goal, Trace, Answer), positive( Answer).
continue( Answer1, Goal1 and Goal2, Trace, Answer) :positive( Answer1), explore( Goal2, Trace, Answer2),
(positive( Answer2), Answer = Answer1 and Answer2 ; negative( Answer2), Answer = Answer2 ).
continue( Answer1, Goal1 and Goal2, _, Answer1) :- negative( Answer1).
truth( Question is TruthValue was Found, TruthValue) :- !.
truth( Answer1 and Answer2, TruthValue) :- truth( Answer1, true), truth( Answer2, true), !,
TruthValue = true ; TruthValue = false.
positive( Answer) :- truth( Answer, true).
negative( Answer) :- truth( Answer, false).
invert( Quest is true was Found, (not Quest) is false was Found).
invert( Quest is false was Found, (not Quest) is true was Found).
instantiated( Term) :- numbervars(Term, 0, 0).
Implementação Prolog de shell de sistema
especialista encadeando regras para trás
useranswer( Goal, Trace, Answer) :- askable( Goal, _), freshcopy( Goal, Copy),
useranswer( Goal, Copy, Trace, Answer, 1).
useranswer( Goal, _, _, _, N) :- N > 1, instantiated( Goal), !, fail.
useranswer( Goal, Copy, _, Answer, _) :- wastold( Copy, Answer, _), instance_of( Copy, Goal), !.
useranswer( Goal, _, _, true, N) :- wastold( Goal, true, M), M >= N.
useranswer( Goal, Copy, _, Answer, N) :- end_answers( Copy), instance_of( Copy, Goal), !,
not wastold( Goal, _, _), Answer = false.
useranswer( Goal, _, Trace, Answer, N) :- askuser( Goal, Trace, Answer, N).
askuser( Goal, Trace, Answer, N) :- askable( Goal, ExternFormat),
format( Goal, ExternFormat, Question, [], Variables),
ask( Goal, Question, Variables, Trace, Answer, N).
ask( Goal, Question, Variables, Trace, Answer, N) :- nl,
( Variables = [], !, write( 'Is it true: ') ; write( 'Any (more) solution to: ')),
write( Question), write('? '), getreply( Reply), !,
process( Reply, Goal, Question, Variables, Trace, Answer, N).
Implementação Prolog de shell de sistema
especialista encadeando regras para trás
process( no, Goal, _, _, _, false, N) :- freshcopy( Goal, Copy), wastold( Copy, true, _), !,
assertz( end_answers( Goal)), fail ; nextindex( Next), assertz( wastold( Goal, false, Next)).
format( Var, Name, Name, Vars, [Var/Name|Vars]) :- var( Var), !.
format( Atom, Name, Atom, Vars, Vars) :- atomic( Atom), !, atomic( Name).
format( Goal, Form, Question, Vars0, Vars) :- Goal =.. [Functor|Args1], Form =.. [Functor|Forms],
formatall( Args1, Forms, Args2, Vars0, Vars), Question =.. [Functor|Args2], !.
format( Goal, _, Question, Vars0, Vars) :- format( Goal, Goal, Question, Vars0, Vars).
formatall( [], [], [], Vars, Vars).
formatall( [X|XL], [F|FL], [Q|QL], Vars0, Vars) :- formatall( XL, FL, QL, Vars0, Vars1),
format( X, F, Q, Vars1, Vars).
askvars( []).
askvars( [Variable/Name|Variables]) :- nl, write( Name), write( ' = '), read( Variable), askvars( Variables).
showtrace([]) :- nl, write('This was your question'), nl.
showtrace( [Goal by Rule | Trace]) :- nl, write( 'To investigate, by '), write( Rule), write( ', '),
write( Goal), showtrace( Trace).
Implementação Prolog de shell de sistema
especialista encadeando regras para trás
instance_of( Term, Term1) :- copy_term( Term1, Term2), numbervars( Term2, 0, _), !, Term = Term2.
freshcopy( Term, FreshTerm) :- asserta( copy( Term)), retract( copy( FreshTerm)), !.
nextindex( Next) :- retract( lastindex( Last)), !, Next is Last + 1, assert( lastindex( Next)).
:- assert( lastindex( 0)), assert( wastold( dummy, false, 0)), assert( end_answers( dummy)).
Implementação Prolog de shell de sistema
especialista encadeando regras para trás
present( Answer) :- nl, showconclusion( Answer), nl, write( 'Would you like to see how?'),
nl, getreply( Reply), ( Reply = yes, !, show( Answer) ; true ).
showconclusion( Answer1 and Answer2) :- !, showconclusion( Answer1), write( ' and '),
showconclusion( Answer2).
showconclusion( Conclusion was Found) :- write( Conclusion).
show( Solution) :- nl, show( Solution, 0), !.
show( Answer1 and Answer2, H) :- !, show( Answer1, H), tab( H), write(and), nl, show( Answer2, H).
show( Answer was Found, H) :- tab( H), writeans( Answer), nl, tab( H), write( ' was '), show1( Found, H).
show1( Derived from Answer, H) :- !, write( Derived), write(' from'), nl, H1 is H + 4, show( Answer, H1).
show1( Found, _) :- write( Found), nl.
writeans( Goal is true) :- !, write( Goal).
writeans( Answer) :- write( Answer).
getreply(Meaning) :- read( Reply), means( Reply, Meaning), ! ;
nl, write('Answer unknown, try again please!'), nl, getreply( Meaning).
Implementação Prolog de shell de sistema
especialista encadeando regras para trás
means( why, why) :- !.
means( w, why) :- !.
means( yes, yes) :- !.
means( y, yes) :- !.
means( no, no) :- !.
means( n, no) :- !.
member( X, [X|_]).
member( X, [_|L]) :- member( X, L).
numbervars( Term, N, Nplus1) :- var( Term), !, Term = var/N, Nplus1 is N + 1.
numbervars( Term, N, M) :- Term =.. [Functor | Args], numberargs( Args, N, M).
numberargs( [], N, N) :- !.
numberargs( [X | L], N, M) :- numbervars( X, N, N1), numberargs( L, N1, M).