09 - Knowledge Based Systems

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

CIn- UFPE
 *
Agentes Baseados em Conhecimento
Danielle Rousy & Veronica Teichrieb
 CIn- UFPE
 *
De volta ao exemplo de West...
West é criminoso ou não? 	
“A lei americana diz que é proibido vender armas a uma nação hostil. Cuba possui alguns mísseis, e todos eles foram vendidos pelo Capitão West, que é americano”
Como resolver automaticamente este problema de classificação? 
Segundo a IA (simbólica), é preciso:
Identificar o conhecimento do domínio (modelo do problema)
Representá-lo utilizando uma linguagem formal de representação
Implementar um mecanismo de inferência para utilizar esse conhecimento
 CIn- UFPE
 *
Solucionando o caso do cap. West (linguagem natural)
A) Todo americano que vende uma arma a uma nação hostil é criminoso
B) Todo país em guerra com uma nação X é hostil a X
C) Todo país inimigo político de uma nação X é hostil a X
D) Todo míssil é um arma
E) Toda bomba é um arma
F) Cuba é uma nação
G) USA é uma nação
H) Cuba é inimigo político dos USA
I) Irã é inimigo político dos USA
conhecimento prévio
 CIn- UFPE
 *
Questões levantadas pelo exemplo
Seria possível resolver esse problema com busca?
Por que? 
Danielle Rousy & Veronica Teichrieb
 CIn- UFPE
 *
Limitações da resolução de 
problemas por Busca
Agentes de Busca são muito eficientes na solução de problemas que podem ser formalizados por:
1. um estado inicial;
2. ações (operadores);
3. um conjunto de estados finais.
Porém, não são capazes de resolver problemas que exigem raciocínio baseado em conhecimento sobre o mundo:
porque seu modelo do mundo é pobre e o raciocínio é limitado
e.g., diagnóstico médico, controle aero-espacial, prova de teoremas, sistemas especialistas em geral,...
mesmo em casos aparentemente solucionáveis por busca (planejamento), pode ser preciso adicionar conhecimento explícito
Danielle Rousy & Veronica Teichrieb
 CIn- UFPE
 *
Plano de aula 
Agentes Baseados em Conhecimento (BC)
definição geral
Categorias de conhecimento e de raciocínio
Linguagens de representação de conhecimento
Mecanismos de raciocínio
Arquitetura e algoritmo básico do Agente BC (caso dedutivo)
Sistemas baseados em conhecimento
Danielle Rousy & Veronica Teichrieb
 CIn- UFPE
 *
Agentes Baseados em Conhecimento
São agentes que
conhecem seu mundo
esse conhecimento está representado na Base de Conhecimento
raciocinam sobre suas possíveis ações
com auxílio de uma Máquina de Inferência
Sabem:
o estado atual do mundo (propriedades relevantes)
como o mundo evolui
como identificar estados desejáveis do mundo
como avaliar o resultado das ações
conhecimento sobre conhecimento (meta-conhecimento)
etc.
Danielle Rousy & Veronica Teichrieb
 CIn- UFPE
 *
Esclarecendo... 
Dados:
cadeias numéricas ou alfanuméricas que não possuem significado associado
podem ser fatos ou figuras a processar
Informação:
dados organizados
significam alguma coisa para quem os recebe
Conhecimento:
representa objetos (entidades) de algum domínio, com suas propriedades e relações
Meta-conhecimento:
conhecimento sobre o conhecimento disponível
ex. regras sobre “como” manipular as regras sobre conhecimento que estão em uma base
Danielle Rousy & Veronica Teichrieb
 CIn- UFPE
 *
Categorias de Conhecimento 
Procedimental:
fatos e seqüências de instruções para manipular esses fatos
ex.: como desmontar uma bicicleta
Declarativo:
representação descritiva dos fatos, relacionamentos e regras
as partes de uma bicicleta e seus relacionamentos 
o pai do pai é o avô
Episódico:
fatos vividos, casos, exemplos...
ex. D. Maria tem dor de cabeça e dengue
Danielle Rousy & Veronica Teichrieb
 CIn- UFPE
 *
Categorias de Raciocínio (Inferência)
Dedução: fatos + regras de inferência => novos fatos.
ex. Onde há fogo, há fumaça. Aqui tem fogo, logo... 
Abdução: inverso da dedução.
ex. Se há fumaça, há fogo.
Indução: parte-se dos fatos para gerar regras.
ex. Se Sr. Antônio, assim como D. Maria, tem dor de cabeça e dengue, então todo mundo que tem dengue, tem dor de cabeça.
Analógico: casos + regras de adaptação
ex.: Para construir este hospital, vou me basear no projeto daquele outro
Danielle Rousy & Veronica Teichrieb
 CIn- UFPE
 *
Agentes Baseados em Conhecimento (dedutivo)
Principais componentes:
Base de Conhecimento
Mecanismo de Inferência
Base de Conhecimento:
contém sentenças em uma Linguagem de Representação de Conhecimento
representações de fatos e regras
conhecimento em forma “tratável” pelo computador
ex. míssil é uma arma, M1 é um míssil 
Mecanismo (máquina) de Inferência:
responsável por inferir, a partir do conhecimento da base, novos fatos ou hipóteses intermediárias/temporárias
ex. M1 é uma arma
Danielle Rousy & Veronica Teichrieb
 CIn- UFPE
 *
Agentes Baseados em Conhecimento Dedutivo: Arquitetura
Tell - adiciona novas sentenças à BC
Ask - consulta a BC
Danielle Rousy & Veronica Teichrieb
 CIn- UFPE
 *
Implementando raciocínio (dedutivo): 
laço principal de TODO agente
Programa Agente Baseado em Conhecimento
t := 0 		//contador de tempo
enquanto Agente-BC vivo, faça
		Tell(BC, Percepções-Sentença(percepção,t))
	 ação <- Ask(BC, Pergunta-Ação(t))
	 Executa(ação)
	 Tell(BC, Ação-Sentença(ação,t))
	 t <- t + 1
Danielle Rousy & Veronica Teichrieb
 CIn- UFPE
 *
Sistemas baseados em conhecimento
Sistemas baseados em conhecimento
Têm uma base de conhecimento e uma máquina de inferência associadas
Formalizam e implementam parte dos agentes
Qual a diferença?
Agentes interagem com o ambiente onde estão imersos
através dos sensores e efetuadores
Danielle Rousy & Veronica Teichrieb
 CIn- UFPE
 *
Ciclo de vida dos sistemas baseados em conhecimento
Nível de Conhecimento
Nível Lógico
Nível de Implementação
BC
AQUISIÇÃO
FORMALIZAÇÃO
IMPLEMENTAÇÃO
REFINAMENTO
linguagem natural
linguagem de representação de
conhecimento
linguagens de 
programação
Danielle Rousy & Veronica Teichrieb
 CIn- UFPE
 *
Engenharia do Conhecimento
Engenharia do Conhecimento
estuda como construir uma Base de Conhecimento (BC) 
1. Nível do conhecimento: aquisição de conhecimento
conhecimento em “estado puro” - linguagem natural
e.g., táxi automático: a ponte Princesa Isabel liga a Rua da Imperatriz à Rua Nova
2. Nível lógico: formalização
conhecimento codificado em sentenças - linguagem formal
e.g. sentença lógica: liga(Ponte-PI,RI,RN)
3. Nível de máquina: implementação
estrutura de dados representando as sentenças do nível lógico
e.g., listas, tabelas, objetos, etc.
Danielle Rousy & Veronica Teichrieb
 CIn- UFPE
 *
Linguagens de Representação do Conhecimento
Linguagens de programação:
são precisas, porém não são suficientemente expressivas
Linguagens naturais:
são muito expressivas, porém são ambíguas
Linguagens de representação de conhecimento (LRC):
utilizadas para expressar as sentenças das BC
estão entre as anteriores...
existem 3 grandes classes:
linguagens (predominantemente) declarativas
linguagens procedimentais
linguagens híbridas
Danielle Rousy & Veronica Teichrieb
 CIn- UFPE
 *
Tipos de Linguagens de Representação do Conhecimento
Linguagens procedimentais: dizem como
representam fatos (através de constantes ou variáveis instanciadas) e seqüências de instruções para manipular esses fatos
representação e implementação estão intrinsecamente ligados
ex. C, Pascal, Lisp, ... 
Linguagens declarativas: dizem o que
representam fatos, seus relacionamentos e regras (conhecimento puro)
esse conhecimento necessita ser processado por algum código!
Linguagens Lógicas (ex. Lógica de primeira ordem)
Linguagens baseadas em Regras (ex. regras se-então)
Linguagens baseadas em Objetos (ex. frames, ontologias, etc.)
Danielle Rousy & Veronica Teichrieb
 CIn- UFPE
 *
Tipos de Linguagens de Representação do Conhecimento
Linguagens híbridas
objetos + regras
lógica + objetos 
lógica + objetos + regras 
etc...
Danielle Rousy & Veronica Teichrieb
 CIn- UFPE
 *
Linguagens de Representação do Conhecimento
Uma Linguagem de Representação do Conhecimento é definida por:
1) uma sintaxe, que descreve as configurações que podem constituir sentenças daquela linguagem;
2) uma semântica, que liga cada sentença aos fatos no mundo que ela representa
cada sentença faz uma afirmação a respeito do mundo;
o agente acredita nas sentenças que correspondem a sua configuração interna.
E geralmente ... 
tem um mecanismo de inferência associado = raciocínio
Danielle Rousy & Veronica Teichrieb
 CIn- UFPE
 *
Representação & Raciocínio
Raciocínio é um processo de construção de novas sentenças a partir de sentenças existentes.
Raciocínio plausível (sound):
garante que as novas sentenças representam fatos que se seguem dos fatos representados pelas sentenças existentes na BC.
implementa a relação de “implicação” entre sentenças
Danielle Rousy & Veronica Teichrieb
 CIn- UFPE
 *
Solucionando o caso do cap. West (em LPO)
 CIn- UFPE
 *
Direções do raciocínio dedutivo
Raciocínio progressivo 
dos dados à conclusão - data-driven inference 
as regras da BC são usadas para gerar informação nova (novos fatos) a partir de um conjunto inicial de dados
os fatos gerados passam a fazer parte da BC
ex.: criminoso(West).
Raciocínio regressivo
da hipótese aos dados - goal-directed inference
usa as regras da BC para responder a perguntas
prova se uma asserção é verdadeira
ex.: criminoso(West)?
só processa as regras relevantes para a pergunta (asserção)
Danielle Rousy & Veronica Teichrieb
 CIn- UFPE
 *
Tipologia de sistemas baseados em conhecimento (LRC+MI)
Danielle Rousy & Veronica Teichrieb
 CIn- UFPE
 *
Implementando Regras
Sistemas de Produção
Restringem a lógica mais do que a programação em lógica, mas são mais eficientes
Geralmente usam Encadeamento Progressivo.
Exemplos: OPS-5, CLIPS, SOLAR.
Linguagens de Programação Lógica
Restringem a lógica, não permitindo o tratamento completo da negação, da disjunção e/ou da igualdade.
Geralmente usam Encadeamento Regressivo.
Exemplos: Prolog, MRS, Life. 
Sistemas de manutenção da verdade
Truth-maintenance systems (TMS)
Mantêm a base de conhecimento consistente.
Danielle Rousy & Veronica Teichrieb
 CIn- UFPE
 *
Implementando Objetos
Sistemas de Redes Semânticas
BC: nós (representando objetos) conectados por arcos (representando a relação binária entre eles).
Exemplos: KRL, SNEPS, NETL, Conceptual Graphs.
Sistemas Frames
Consistem em uma hierarquia de frames (quadros) conectados por atributos, onde os frames representam objetos do mundo e atributos usualmente a relação entre eles.
Exemplos: KRIPTON, OWL, FRAIL, KODIAK.
Linguagens de classes
hierarquia de objetos encapsulando comportamento e estrutura e com comunicação via envio de mensagens
Exemplos: Smalltalk, Lisp-CLOS, Java, ...
Danielle Rousy & Veronica Teichrieb
 CIn- UFPE
 *
Abordagem Híbrida
Sistemas híbridos
combina as vantagens de cada sistema e ainda mais algumas de engenharia de software
Exemplos
eoops: objetos + regras (C++/Clips, Smalltalk/NéOpus, Java/Jeops,...)
lógica + objetos (ObjLog),
lógica + objetos + funções (LIFE), etc...
Danielle Rousy & Veronica Teichrieb
 CIn- UFPE
 *
Critérios de avaliação de LRC
Expressividade: o que é possível dizer facilmente na linguagem? 
Inferência disponível: que tipo de inferência é possível fazer na linguagem?
Corretude: a inferência é plausível (sound)? A semântica é bem definida?
Eficiência: a inferência se realiza em um tempo razoável? 
Modularidade: é fácil identificar e reutilizar partes do conhecimento? 
Legibilidade: é fácil de ler e entender o que está escrito?
Eficiência aquisicional: é fácil adicionar conhecimento?
Danielle Rousy & Veronica Teichrieb