doc logica 1274183227

Prévia do material em texto

*
*
Ensino Superior
6 – Introdução aos Sistemas Especialistas
Amintas Paiva Afonso
Lógica Matemática e Computacional
*
*
Inteligência Artificial
O campo da Inteligência Artificial (IA) tenta compreender as entidades inteligentes para construir entidades inteligentes. 
Construir máquinas (computadores) com um nível de inteligência igual ou superior aos humanos! 
As abordagens de IA podem organizar-se em 4 categorias:
*
*
Inteligência Artificial
Raciocínio/
Pensamento
Comportamento
Modelação do Ser Humano
Outros Modelos
Sistemas que pensam como os Humanos
Foco de Interesse
Sistemas que pensam Racionalmente
Sistemas que agem como os Humanos
Sistemas que agem Racionalmente
*
*
IA Simbólica
Fundamenta-se em:
Representação do conhecimento; e 
Métodos de Busca.
*
*
IA Simbólica
Representação do conhecimento:
Lógica proposicional e predicativa;
Regras de produção;
Redes semânticas;
Frames e scripts;
...
*
*
IA Simbólica
Métodos de Busca:
Espaço de estados;
Busca em profundidade;
Busca em largura;
Busca heurística (A*);
Busca em feixe;
Têmpera simulada;
...
*
*
Exemplo: um pequeno jogo...
Estado inicial: <XX_YY>
Estado objetivo: <YY_XX>
Ações (operações):
X_ => _X 	e	_Y => Y_
XX_ => _XX	e	_YY => YY_
XY_ => _YX	e	 _XY => YX_
*
*
Exemplo: uma solução
<XX_YY> (estado inicial)
<X_XYY> (ação 1a)
<XYX_Y> (ação 2b)
<XYXY_> (ação 1b)
<XY_YX> (ação 3a)
<_YXYX> (ação 3a)
<Y_XYX> (ação 1b)
<YYX_X> (ação 3b) 
<YY_XX> (ação 1a)
*
*
Exemplo: uma falha
<XX_YY> (estado inicial)
<X_XYY> (ação 1a)
<XYX_Y> (ação 2b)
<XYXY_> (ação 1b)
<XY_YX> (ação 3a)
<XYY_X> (ação 1b) Falha !!!!
*
*
Exemplo: árvore de busca
<XX_YY> (estado inicial)
<X_XYY> (ação 1a) OU
<XXY_Y> (ação 1b) OU
<_XXYY> (ação 2a) OU
<XXYY_> (ação 2b)
Qual escolher ? (heurística ?)
*
*
Sistemas Especialistas
Os especialistas humanos são capazes de atingir um alto desempenho na medida em conhecem muito bem as suas áreas de especialização;
Um Sistema Especialista (SE) é um programa de computador que utiliza conhecimento específico do domínio de um problema e emula a metodologia e desempenho de um especialista para obter soluções de problemas neste domínio. 
*
*
Sistemas Especialistas
O conhecimento inerente a um Sistema Especialista é um ponto chave na sua construção, e é normalmente definido por engenheiros do conhecimento;
Para tal são consultados especialistas no domínio do problema e tenta-se codificar numa linguagem formal todo o conhecimento que estes adquiriam ao longo da sua experiência, nomeadamente heurísticas e truques.
*
*
Sistemas Especialistas
Os Sistemas Especialistas não imitam necessariamente a estrutura da mente humana, nem os mecanismos da inteligência; 
São programas práticos que usam estratégias heurísticas desenvolvidas por humanos na resolução de classes específicas de problemas;
São uma classe de programas na área da Inteligência Artificial, e têm contribuído para o sucesso desta área através de vários produtos comerciais desenvolvidos e aplicações.
*
*
Sistemas Especialistas
		
		Programa
		Sistema Especialista
		Representação do Conhecimento
		Implícita
		Explicita
		Realidade expressa em termos de
		Modelos Matemáticos
		Modelos Cognitivos
		Conhecimento traduzido em
		Algoritmos
		Estruturas hierárquicas
Redes Semânticas Regras
Árvores de decisão
Tabelas de decisão
Redes de Inferência
		O computador executa
		Processamento numérico (cálculos)
		Processamento simbólico (inferências)
		Tipo de Resultados
		Numéricos
		Conhecimento
*
*
Categorias dos Problemas
Interpretação: formar conclusões a partir de dados;
Predição: projetar consequências de situações;
Diagnóstico e reparo : determinar a causa de maus funcionamentos, e prescrever e implementar soluções; 
Projeto: configurar componentes de forma a atingir um objetivo;
Planejamento: obter a sequência de passos para atingir um objetivo;
Monitoração: comparar o comportamento de um sistema com aquilo que seria de esperar;
Tutoriais: detectar e corrigir deficiências, e auxiliar processos de aprendizagem;
Controle: governar o comportamento de um sistema.
*
*
Tecnologia dos Sistemas Especialistas
Arquitetura
BASE DE CONHECIMENTO
DADOS ESPECÍFICOS DO CASO
MOTOR DE INFERÊNCIA
INTERFACE COM USUÁRIO:
PERGUNTA/RESPOSTA
ORIENTADO POR MENUS
LINGUAGEM NATURAL
GRÁFICO
APRENDIZAGEM
EXPLANAÇÃO
ESPECIALISTA/
ENG. CONHECIMENTO/
PROGRAMADOR
SHELL
USUÁRIO
*
*
Quando desenvolver um SE
O problema justifica o custo e esforço de construção do SE; 
Não existem especialistas disponíveis (no local) para resolver diretamente o problema; 
Existem especialistas para cooperarem na construção do SE;
O problema pode ser solucionado através de raciocínio simbólico (próximo dos humanos);
O problema não requer “senso comum”;
O problema não pode ser resolvido através de métodos computacionais tradicionais;
O problema não é demasiado grande nem demasiado genérico.
*
*
Desenvolvimento de SE
Envolve o Engenheiro de Conhecimento, o Especialista do domínio do problema e o Usuário final;
Criação Rápida de Protótipos:
Metodologia Centrada no Cliente;
Sucessivas iterações nas quais as possibilidades são postas à prova pelos futuros usuários.
Correção
Programação
Modelagem 
do Sistema
Aquisição do Conhecimento
*
*
Criação de SE
Linguagens de Programação: C++, LISP, PROLOG
Shells:
Acadêmicos: MYCIN - EMYCIN, CLIPS, GUIDON, TEIRESIAS, VM, CENTAUR...
Comerciais: Deciding Factor, Exsys, M-1, Savoir, Expert-	Ease, Guru, Crystal...
Ambientes de Programação (de IA):
	ILOG...
Aplicações:
	Business Insight...
*
*
Raciocínio Baseado em Regras
Representação do conhecimento para a resolução do problema através de regras do tipo “se...então...” (regras de produção)
Exemplo:	
	Se 	(Qualifica = SIM) e
		(Média < 3,5) e
		(Experiência >= 2)
	Então
		(Posição = engenheiro de serviço)
*
*
Arquitetura Clássica de um SE
Base de Conhecimento
Regras
Fatos
Memória 
de Trabalho
Motor de 
Inferência:
Controle e 
Inferência
Subsistema de 
aquisição de 
conhecimento
Subsistema de 
explanação
Interface 
com o usuário
Especialista / Eng. Conhecimento
Usuário
*
*
Motor de Inferência
Regras (MR)
Fatos (MF)
Motor de 
Inferência:
Controle e 
Inferência
Conjunto de conflitos (CC)
Pattern Matching
Resolução de conflitos
Regra (s) escolhida(s)
Disparo da(s) regra(s)
Alterações em MF (MR)
*
*
Exemplo: um pequeno SE
Problema:
Oferta de emprego a um candidato em uma empresa.
Variáveis de entrada: Descoberta (Sim / Não), Diploma (Sim / Não), Experiência (em anos), Média (nota média do histórico);
Variáveis de saída: Posição (Nenhuma / Pesquisa / Eng. De Serviço / Eng. De Produto), Qualifica (Sim / Não).
*
*
Exemplo: um pequeno SE
Variáveis:
Descoberta: o candidato fez alguma descoberta?
Diploma: o candidato tem curso superior ?
Experiência: quantos anos de experiência tem o candidato ?
Média: qual a nota média do candidato em seu curso superior ?
Posição:que posição deve ser oferecida ao candidato ?
Qualifica: o candidato se qualifica para uma posição ?
*
*
Exemplo: um pequeno SE
Regras:
R1: SE (Diploma = Não) 
		ENTÃO (Posição =Nenhuma);
R2: SE (Diploma = Sim) 
		ENTÃO (Qualifica = Sim);
R3: SE (Diploma = Sim) E 
		 (Descoberta = Sim) 
		ENTÃO (Posição = Pesquisa);
*
*
Exemplo: um pequeno SE
R4: SE (Qualifica = Sim) E
		 (Média <= 7,0 ) E 
		 (Experiência >= 2)
		ENTÃO (Posição = Eng. De Serviço);
R5: SE (Qualifica = Sim) E
		 (Média < 7,0) E
		 (Experiência < 2) 
		ENTÃO (Posição = Não);
*
*
Exemplo: um pequeno SE
R6: SE (Qualifica = Sim) E 
		 (Média > 7,0) 
		ENTÃO (Posição =Eng. de Produto);
*
*
Encadeamento para frente
Procedimento básico:
Até que a solução pertença a MF faça:
Compare a MF e MR e obtenha o CC;
Escolha uma (várias) regra(s) no CC (resolução de conflitos);
Dispare a(s) regra(s) escolhida(s)
	(acrescenta / retira fatos da MT).
*
*
Encadeamento para frente
Fatos iniciais (M0):
F0: (Diploma = Sim);
F1: (Experiência = 1,5);
F2: (Média = 8,0);
F3: (Descoberta = Não).
Inferência 1: Dispara R2;
F4: (Qualifica = Sim);
*
*
Encadeamento para frente
Fatos atuais (M1):
F0: (Diploma = Sim);
F1: (Experiência = 1,5);
F2: (Média = 8,0);
F3: (Descoberta = Não).
F4: (Qualifica = Sim);
Inferência 2: Dispara R6;
F5: (Posição = Eng. De Produto).
*
*
Encadeamento para frente
Fatos atuais (M2):
F0: (Diploma = Sim);
F1: (Experiência = 1,5);
F3: (Média = 8,0);
F4: (Descoberta = Não).
F5: (Qualifica = Sim);
F6: (Posição = Eng. De Produto).
Não há mais regra a disparar.
*
*
Encadeamento para trás
Procedimento básico:
Escolha uma hipótese H da Pilha de Hipóteses;
Até que a hipótese seja comprovada (pertença a MF):
Escolha uma regra R cuja conclusão seja H;
Tente provar as premissas de R (recursivamente);
Se não for possível , escolha outra hipótese.
*
*
Encadeamento para trás
Fatos iniciais (M0):
F0: (Diploma = Sim);
F1: (Experiência = 1,5);
F2: (Média = 8,0);
F3: (Descoberta = Não).
*
*
Encadeamento para trás
Possui Pilha de Hipóteses a serem provadas / negadas.
Hipótese:
H0: (Posição = Nenhuma);
Pela regra R1, substituída por:
H1: (Diploma = Não), é negada por M0;
A hipótese é descartada.
*
*
Encadeamento para trás
Nova hipótese:
H2: (Posição = Pesquisa);
Pela regra R3, substituída por (H3) e (H4):
H3: (Diploma = Sim), e
H4: (Descoberta = Sim).
H3 confirmada por M0, H4 não;
Não há regra cuja conclusão seja H4, logo H4 e H2 são descartadas.
*
*
Encadeamento para trás
Nova hipótese:
H5: (Posição = Eng. De Serviço);
Pela regra R4, substituída por (H6), (H7) e (H8):
H6: (Qualifica = Sim);
H7: (Média < 7,0);
H8: (Experiência >= 2).
H7 negada por M0, (como também H8), H5 descartada.
*
*
Encadeamento para trás
Nova hipótese:
H9: (Posição = Eng. De Produto);
Pela regra R6, substituída por (H10) e (H11):
H10: (Qualifica = Sim);
H11: (Média > 7,0).
H10 e H11 confirmadas por M0, H9 confirmada.
*
*
Encadeamento para trás
Outra possibilidade: inquisição do usuário a cada passo:
Caso não haja regra cuja conclusão confirme a hipótese, uma pergunta é feita ao usuário para se obter o valor da variável.
*
*
Raciocínio Baseado em Modelos
Em vez de se utilizarem heurísticas na resolução de um problema;
A análise é fundamentada diretamente na especificação e funcionalidade do sistema físico (um modelo do sistema);
Normalmente aplica-se no diagnóstico;
O sistema é simulado assim como a estrutura e funcionamento das suas componentes;
Exemplo de um circuito de somadores e multiplicadores.
*
*
Raciocínio Baseado em Casos
Regras heurísticas e modelos teóricos são dois tipos de informação que os especialistas humanos utilizam para resolver problemas;
Outra estratégia utilizada é o raciocínio baseado em casos (Case-Based Reasoning - CBR);
Utiliza uma base de dados com soluções de problemas para resolver novas situações;
Exemplos: medicina, justiça, programação de computadores, arquitetura, história...
*
*
Algoritmo de inferência
1. Procurar casos similares na memória,
	aqueles cuja solução pode ser aplicada à 
	nova situação (características comuns)
2. Modificar um desses casos para aplicar à 
	situação nova (alterar sequência dos passos 
	que levam de um estado inicial a um estado 
	final)
3. Aplicar o caso transformado ao novo problema
4. Guardar a solução com uma medida do sucesso ou insucesso para uso futuro.
*
*
Raciocínio Baseado em Regras
vantagens:			
modo direto
modular
desempenho
facilidades de explanação
as regras encaixam-se naturalmente na procura num espaço de estados
o processo de inferência é fácil de seguir e depurar
os passos para a solução do problema são facilmente inspecionáveis
separação do controle e do conhecimento
*
*
Raciocínio Baseado em Regras
desvantagens:			
regras altamente heurísticas, falta de profundidade
não manuseiam falta de informação ou valores inesperados 
a explicação baseia-se na prova e não nas bases teóricas
muito específico na aplicação
*
*
Raciocínio Baseado em Casos
vantagens:			
codificação direta de conhecimento histórico (e.g. reparações)
permite obter a solução a partir de um caso apropriado não necessitando de todo o processo de resolução do problema
evita erros do passado e explora os sucessos (aprendizagem)
*
*
Raciocínio Baseado em Casos
vantagens:			
não é necessária uma análise extensiva do domínio do conhecimento
aquisição de conhecimento e sua codificação relativamente fáceis
*
*
Raciocínio Baseado em Casos
desvantagens:			
explanação difícil
desempenho computacional (bases de dados extensas)
difícil definir critérios de similaridade
*
*
Raciocínio Baseado em Modelos
vantagens:			
uso de conhecimento funcional/estrutural
robustez (ao contrário do baseado em regras)
algum conhecimento é transferível entre tarefas (teorias genéricas...)
explicação causal
*
*
Raciocínio Baseado em Modelos
desvantagens:			
falta de conhecimento heurístico
requer um modelo explícito do domínio (nem sempre é possível (e.g. finanças)
complexidade
situações excepcionais (um componente avariado)
*
*
Outras possibilidades
Raciocínio Baseado em Representações Híbridas
regras+casos
regras+modelos
modelos+casos
Raciocínio com Incerteza ou Informação Incompleta:
Probabilidades
Fatores de certeza
Sistemas difusos
*
*
Referências
Sobre IA em geral:
S.J. Russel; P. Norvig. Artificial Intelligence. Prentice Hall, 1995, http://aima.cs.berkeley.edu/. 
E. Rich; K. Knight. Inteligência Artificial. Makron Books, 1994, http://www.cs.utexas.edu/users/ear/ e http://www.isi.edu/natural-language/people/knight.html .
*
*
Referências
Sobre SE:
M. Stefik. “Introduction to Knowledge Systems”, Morgan Kaufmann, 1995.
P. Harmon, D. King. “Expert Systems: AI in Business”, John Wiley & Sons, 1985.
K. Parsaye, M. Chignell. “Expert Systems for Experts”, John Wiley & Sons, 1988.
*
*