Reasoning
Forward and Backward Chaining
Fábio de Azevedo Soares
[email protected]
Sumário
• Introdução a Reasoning.
• Sistemas Baseados em Conhecimento.
• Forward Chaining
– Apresentação
– Exemplos
• Backward Chaining
– Apresentação
– Exemplos
• JTP API
• Conclusões
© LES/PUC-Rio
Reasoning
• Em Português: argumentar, justificar, raciocinar.
• Reasoning é usar a razão para chegar à conclusão.
• É um campo multidisciplinar:
– Filosofia (Qualificação);
– Psicologia (Cognição);
– Matemática (Lógica);
© LES/PUC-Rio
Qual o interesse em Reasoning?
• Construção de Agentes Inteligentes.
– “A arte de criar máquinas que executam funções que exigem
inteligência quando executadas por pessoas.”
– Raciocínio automatizado para usar informações
armazenadas com a finalidade de responder a perguntas e
chegar a novas conclusões (conhecimento):
• Sistemas Baseados em Conhecimento (Em 1969, software
DENDRAL – análise estrutura molecular – primeiro sistema bem
sucedido de conhecimento).
© LES/PUC-Rio
Sistemas Baseados em Conhecimento (SBC)
• Definição: são programas de computador que usam o
conhecimento representado explicitamente para resolver
problemas.
• Baseados no seguinte pensamento:
– Quando o ser humano é mais bem sucedido do que as
máquinas para resolver um problema, então, as máquinas
precisam saber o que o ser humano sabe sobre o assunto.
• Utilizados há mais de 20 anos.
• Possuem como principal característica a utilização de uma
Base de Conhecimento.
© LES/PUC-Rio
SBC :: Arquitetura Básica
Perguntas
Respostas
Core
UI/GUI
Motor de Inferência
Usuário
<- Percepção
Ação ->
BC
Agente
Ambiente
© LES/PUC-Rio
SBC :: Agentes Inteligentes
• Um agente é tudo o que pode ser considerado capaz de
perceber seu ambiente por meio de sensores e de agir
sobre esse ambiente por intermédio de atuadores.
Percepções
Sensores
Ambiente
?
Ações
Atuadores
Agente
© LES/PUC-Rio
SBC :: Base de Conhecimento
• Contém a descrição do conhecimento necessário para a
resolução do problema abordado na aplicação.
• É composta por um conjunto de representações de ações:
– Cada representação individual é chamada de sentença;
– As sentenças são expressas em uma linguagem específica,
chamada linguagem de Representação de Conhecimento.
– A maioria das sentenças descreve relações de causa e efeito
(SE condição, ENTÃO conclusão):
• SE temperatura está acima de 37.5°C, ENTÃO o paciente tem
febre;
• SE A e B, ENTÃO C.
• Podem ser compostas por milhares de regras.
© LES/PUC-Rio
SBC :: Base de Conhecimento
• Diferente de uma codificação qualquer, a representação do
conhecimento deve ser compreensível ao homem.
• Ser robusta o suficiente para que todas as situações
possível de determinado problema sejam abordadas.
• Geralmente, tem seu conhecimento expresso sob
representação lógica:
– PROLOG é a linguagem mais utilizada.
© LES/PUC-Rio
SBC e Reasoning
• SBCs são dotados de duas características principais:
– Conhecimento, processável pelo homem;
– Capacidade de resolver problemas;
• O processo utilizado para a resolução de problemas é
baseado na capacidade de raciocínio destes sistemas.
• Esta capacidade de raciocínio aliada a base de
conhecimento determina o quão boa será a estratégia de
inferência destes sistemas.
© LES/PUC-Rio
SBC :: Arquitetura Básica
Perguntas
Respostas
REASONING
Core
UI/GUI
Motor de Inferência
Usuário
BC
© LES/PUC-Rio
SBC :: Motor de Inferência
• É responsável pelo desenvolvimento do raciocínio baseado
nas informações obtidas do mundo externo e no
conhecimento representado na BC.
• Inferir é derivar novas sentenças a partir de sentenças
antigas.
• Existem algumas estratégias (linhas de raciocínio,
reasoning) que podem ser seguidas pelos SBCs (motor de
inferência):
– Encadeamento progressivo ou forward chaining;
– Encadeamento regressivo ou backward chaining.
© LES/PUC-Rio
Reasoning :: Forward Chaining
• Tenta chegar a uma conclusão a partir das informações
fornecidas sobre a situação atual (BC + fatos):
– “o quê se pode concluir com os dados que tenho?”.
• Data oriented reasoning;
• Mesmo que não exista, explicitamente, na Base de
Conhecimento o que se deseja concluir, o mecanismo de
inferência procura pelos antecedentes que satisfaçam a
situação atual para, então, tentar inferir outros
antecedentes e conclusões.
• Em geral, cada solução (gerada) é inserida na Base de
Conhecimento.
© LES/PUC-Rio
Reasoning :: Forward Chaining
• Exemplo (01)
– Objetivo desejado: qual a cor do Bob?
– Fatos:
• Bob come moscas;
• Bob grasna.
– Base de Conhecimento
1. SE X grasna e come moscas, ENTÃO X é um sapo.
2. SE X gorjeia E canta – ENTÃO X é um canário.
3. SE X é um sapo, ENTÃO X é verde.
4. SE X é um canário, ENTÃO X é amarelo.
– Regras inferidas:
• R1, R3
© LES/PUC-Rio
Reasoning :: Forward Chaining
– Base de Conhecimento
1. SE X grasna e come moscas, ENTÃO X é um sapo.
2. SE X gorjeia E canta – ENTÃO X é um canário.
3. SE X é um sapo, ENTÃO X é verde.
4. SE X é um canário, ENTÃO X é amarelo.
– Regras inferidas:
• R1, R3
• A BC é procurada e a R1 é selecionada, pois, seu
antecedente combina com os fatos.
– Conseqüente “X é um sapo” é adicionado aos fatos.
– A BC é, novamente, procurada e a R3 é selecionada, pois, seus
antecedente (SE X é um sapo) combina com os fatos.
– Conseqüente “X é verde”é adicionado aos fatos.
© LES/PUC-Rio
Reasoning :: Forward Chaining
• As regras inferidas também podem ser visualizadas por
meio de um grafo orientado.
grasna
Sapo
Verde
come
mosca
R1: SE X grasna e come moscas, ENTÃO X é um sapo.
R3: SE X é um sapo, ENTÃO X é verde.
© LES/PUC-Rio
Reasoning :: Forward Chaining
• Exemplo (02)
– Objetivo desejado: Q.
– Fatos:
• A;
• B.
– Base de Conhecimento
1.
SE P, ENTÃO Q.
2.
SE L e M, ENTÃO P.
3.
SE B e L, ENTÃO M.
4.
SE A e P, ENTÃO L.
5.
SE A e B, ENTÃO L.
© LES/PUC-Rio
Reasoning :: Forward Chaining
– Base de Conhecimento
1.
SE P, ENTÃO Q.
2.
SE L e M, ENTÃO P.
3.
SE B e L, ENTÃO M.
4.
SE A e P, ENTÃO L.
5.
SE A e B, ENTÃO L.
– Fatos:
• A;
• B;
• L (R5).
© LES/PUC-Rio
Reasoning :: Forward Chaining
– Base de Conhecimento
1.
SE P, ENTÃO Q.
2.
SE L e M, ENTÃO P.
3.
SE B e L, ENTÃO M.
4.
SE A e P, ENTÃO L.
5.
SE A e B, ENTÃO L.
– Fatos:
• A;
• B;
• L;
• M (R3).
© LES/PUC-Rio
Reasoning :: Forward Chaining
– Base de Conhecimento
1.
SE P, ENTÃO Q.
2.
SE L e M, ENTÃO P.
3.
SE B e L, ENTÃO M.
4.
SE A e P, ENTÃO L.
5.
SE A e B, ENTÃO L.
– Fatos:
• A;
• B;
• L;
• M;
• P (R2);
© LES/PUC-Rio
Reasoning :: Forward Chaining
– Base de Conhecimento
1.
SE P, ENTÃO Q.
2.
SE L e M, ENTÃO P.
3.
SE B e L, ENTÃO M.
4.
SE A e P, ENTÃO L.
5.
SE A e B, ENTÃO L.
– Fatos:
• A;
• B;
• L;
• M;
• P;
• Q (R1).
© LES/PUC-Rio
Reasoning :: Backward Chaining
• Parte da suposição de que cada solução é verdadeira. A
partir disto, busca evidências que comprovem ser correta a
solução considerada inicialmente:
– “posso concluir esta solução com os dados que tenho?”.
• Goal-driven reasoning.
• Mesmo que não exista, explicitamente, na Base de
Conhecimento o que se deseja concluir, o mecanismo de
inferência procura pelos consequentes que satisfaçam a
situação atual para, então, tentar inferir outros
antecedentes e conclusões.
© LES/PUC-Rio
Reasoning :: Backward Chaining
• Exemplo
– Objetivo desejado: Bob pode ser verde?
– Fatos:
• Bob come moscas;
• Bob grasna.
– Base de Conhecimento
1. SE X grasna e come moscas, ENTÃO X é um sapo.
2. SE X gorjeia E canta – ENTÃO X é um canário.
3. SE X é um sapo, ENTÃO X é verde.
4. SE X é um canário, ENTÃO X é amarelo.
– Regras inferidas:
• R3, R4, R1, R2
© LES/PUC-Rio
Reasoning :: Backward Chaining
– Base de Conhecimento
1. SE X grasna e come moscas, ENTÃO X é um sapo.
2. SE X gorjeia E canta – ENTÃO X é um canário.
3. SE X é um sapo, ENTÃO X é verde.
4. SE X é um canário, ENTÃO X é amarelo.
– Regras inferidas:
• R3, R4, R1, R2
• Bob é verde se ele for um sapo, ou, amarelo se ele for um
canário.
– Como Bob grasna e como moscas, ele é um sapo, logo, não é
um canário.
© LES/PUC-Rio
Reasoning :: Backward Chaining
• Exemplo (02)
– Objetivo desejado: Q.
– Fatos:
• A;
• B.
– Base de Conhecimento
1.
SE P, ENTÃO Q.
2.
SE L e M, ENTÃO P.
3.
SE B e L, ENTÃO M.
4.
SE A e P, ENTÃO L.
5.
SE A e B, ENTÃO L.
© LES/PUC-Rio
Reasoning :: Backward Chaining
– Base de Conhecimento
1.
SE P, ENTÃO Q.
2.
SE L e M, ENTÃO P.
3.
SE B e L, ENTÃO M.
4.
SE A e P, ENTÃO L.
5.
SE A e B, ENTÃO L.
– Fatos:
• Q;
• P (R1).
© LES/PUC-Rio
Reasoning :: Backward Chaining
– Base de Conhecimento
1.
SE P, ENTÃO Q.
2.
SE L e M, ENTÃO P.
3.
SE B e L, ENTÃO M.
4.
SE A e P, ENTÃO L.
5.
SE A e B, ENTÃO L.
– Fatos:
• Q;
• P;
• L e M (R2).
© LES/PUC-Rio
Reasoning :: Backward Chaining
– Base de Conhecimento
1.
SE P, ENTÃO Q.
2.
SE L e M, ENTÃO P.
3.
SE B e L, ENTÃO M.
4.
SE A e P, ENTÃO L.
5.
SE A e B, ENTÃO L.
– Fatos:
• Q;
• P;
• L;
• M;
• A e P (R4).
© LES/PUC-Rio
Reasoning :: Backward Chaining
– Base de Conhecimento
1.
SE P, ENTÃO Q.
2.
SE L e M, ENTÃO P.
3.
SE B e L, ENTÃO M.
4.
SE A e P, ENTÃO L.
5.
SE A e B, ENTÃO L.
– Fatos:
• Q;
• P;
• L;
• M;
• A;
• P;
• A e B (R5);
© LES/PUC-Rio
Reasoning :: Backward Chaining
– Base de Conhecimento
1.
SE P, ENTÃO Q.
2.
SE L e M, ENTÃO P.
3.
SE B e L, ENTÃO M.
4.
SE A e P, ENTÃO L.
5.
SE A e B, ENTÃO L.
– Fatos:
• Q;
• P;
• L;
• M;
• A;
• P;
• B;
• R3; R2; R1.
© LES/PUC-Rio
Reasoning :: FC x BC
Forward Chaining
Backward Chaining
Presente-Futuro
Presente-Passado
Data-driven
Goal-driven
Busca em largura
Busca em profundidade
Antecedentes determinam a
busca
Conseqüentes determinam a
busca
Planejamento, Monitoramento,
Controle
Diagnóstico
Determinam soluções que
derivam dos fatos
Determinam fatos que
comprovam as soluções
© LES/PUC-Rio
SBC :: Outras Arquiteturas
Perguntas
Respostas
REASONING
Core
UI/GUI
Motor de Inferência
Usuário
Memória
de
Trabalho
BC
© LES/PUC-Rio
SBC :: Conhecimento Incremental
• SBCs podem ser dotados de um processo de aprendizagem
autônomo que alimente a BC incrementalmente.
Conhecimento
à priori
Observações
Aprendizagem
Indutiva
© LES/PUC-Rio
Hipóteses
Previsões
SBC :: Aplicações
• SBCs são aplicados nos mais variados ramos. Entretanto, as
heurísticas utilizadas podem ser classificadas da seguinte
forma:
– Interpretação: análise de dados para determinação do seu
significado;
– Classificação: identificação de uma classe dado um conjunto de
sintomas/observações;
– Monitoramento: observação contínua do comportamento de um
sistema a fim de realizar ações quando alguma falha ocorre;
– Planejamento: determinação de uma seqüência de ações que
devem ser realizadas para alcançar algum objetivo.
© LES/PUC-Rio
JTP: Reasoning System OO API
• Desenvolvida pelo Knowledge Systems Laboratory of
Computer Science Department in Stanford University.
• Em linguagem Java.
• JTP utiliza uma arquitetura muito simples e genérica de
reasoning.
• Implementa backward chaining e forward chaining.
• Reasoner é o principal componente desta arquitetura.
© LES/PUC-Rio
Bibliografia
• ALVARES, L. O. Motor de Inferência para Sistemas
Especialistas baseados em Regras de Produção.
Informática, UFRGS.
• API JTP Web site. Disponível em http://wwwksl.stanford.edu/software/jtp/, Atualizado em 22/01/2008.
Acesso em 18/08/2008.
• DIVERIO, T.; MENEZES, P. Teoria da Computação:
máquinas universais e computabilidade. 2.ed. Porto
Alegre: Sagra-Luzzatto, 2000.
© LES/PUC-Rio
Bibliografia
• PY, M. X. Sistemas Especialistas: uma introdução.
Instituto de Informática, UFRGS.
• RUSSEL, S.; NORVIG, P. Inteligência Artificial. 2. ed. Rio
de Janeiro: Elsevier, 2004.
© LES/PUC-Rio
Fim.