Page1

DAS-5341: Sistemas Especialistas

Prof. Eduardo Camponogara

Page2

Agenda• Técnicas e metodologias utilizadas em

sistemas especialistas– Sistemas de produção– Sistemas especialistas– Aquisição de conhecimento– Métodos de representação do conhecimento

• Lógica, redes semânticas, quadros, etc.– Ferramentas para construção de SE’s– Exemplos de sistemas especialistas

Page3

Sistemas de Produção• Sistema de produção é um nome genérico

para todos os sistemas baseados em regras de produção, isto é, pares de expressões consistindo em uma condição e uma ação

– (condição) -> (ação)

Page4

Sistemas de Produção• Na sua forma mais simples, um sistema de

produção apresenta dois componentes passivos1) Conjunto de regras

• Conjunto de pares ordenados (LHS, RHS), onde LHS e RHS são cadeias de caracteres

2) Memória de trabalho• Uma seqüência de caracteres

• O modelo apresenta também um componente ativo, o interpretador

Page5

Sistemas de Produção• O interpretador segue o procedimento:

– Para cada regra (LHS,RHS), se a seqüência de caracteres LHS está contida na memória de trabalho, então substituir os caracteres LHS na memória pelos caracteres de RHS;

– Caso contrário, continuar na próxima regra

Page6

Exemplo• Exemplo de sistema de produção

– Um sistema capaz de multiplicar dois números em notação unária (na qual o número n é representado por uma seqüência de n algarismos 1), pode ser especificado através de um conjunto de regras

1) x1* B* 6) 2B B12) 1x11 1Ax1 7) *A *3) 1A A21 8) *B *4) 2A A25) 1B B1

Page7

Sistemas de Produção: Exemplo• Exemplo: multiplicar *11x11*

*11x11* *11Ax1* *1A21x1*

*1A21B* *A2121B* *A212B1*

*A21B11* *A2B111* *AB1111*

*B1111* *1111*

2 3 1

1 3 5

6 5 5 7

6

7 8

Page8

Sistemas de Produção• Os sistemas de produção foram utilizados

nos anos 70 como uma ferramenta para modelagem de todos os comportamentos baseados em pares estímulo-resposta

• O sistemas especialistas utilizam o formato de regras de produção como método de representação do conhecimento– SE’s são concebidos para reproduzir o

comportamento de especialistas humanos na resolução de problemas do mundo real, mas o domínio destes problemas é altamente restrito

Page9

Sistemas Especialista• Exemplos de sistemas especialistas

encontrados no mundo real– Sistema Dendral:

• Capaz de inferir a estrutura molecular de compostos desconhecidos a partir de dados espectrais de massa e de resposta magnética nuclear

– Sistema Mycin:• Auxilia médicos na escolha de uma

terapia de antibióticos para pacientes com certas doenças

Page10

Arquitetura de Sistema Especialista

Base de Conhecimento

Memória deTrabalho

Base de Regras

Motor de Inferência

Page11

Sistemas Especialistas• Conforme a figura anterior, um SE apresenta

três módulos:– Memória de trabalho– Base de regras– Motor inferência

• Memória de Trabalho– No modelo simples, consiste em seq.

caracteres– Pode conter qualquer estrutura de dados– A memória deve respeitar o método de

representação do conhecimento

Page12

Sistemas Especialistas• Método de representação do

conhecimento– Uma linguagem formal e– Uma descrição do seu significado

• Exemplo de método: • lógica de primeira ordem

Page13

Sistemas Especialistas• Base de regras

– Contém condições que representam “perguntas” à representação do conhecimento

– Estas perguntas, no modelo simples, eram limitadas à comparação de símbolos

– Em geral, elas podem envolver variáveis a serem instanciadas

– A sintaxe das regras varia: • lógica proposicional, lógica de primeira

ordem, linguagem natural, etc.

Page14

Sistemas Especialistas• Motor de inferência

– O motor de inferência controla a atividade do sistema

– Esta atividade ocorre em ciclos, cada ciclo consistindo em três fases1) correspondência de dados

– Seleciona as regras que satisfazem a situação atual

2) resolução de conflitos3) ação

Page15

Sistemas Especialistas Vantagens• Modularidade• Uniformidade• Naturalidade

Desvantagens• Influência em tempo

de execução• Complexidade do

fluxo de controle

Domínios adequados para SE’s•Fatos parcialmente independentes•Ações independentes•Nítida separação entre conhecimento e ação

Page16

Sistemas Especialistas• A chave para o sucesso de um SE está no

conhecimento armazenado e em sua memória de trabalho

• Este conhecimento deve:1) ser obtido de um especialista humano

do domínio, 2) depois representado de acordo com as

regras formais, e 3) codificado em regras de produção

Page17

Sistemas Especialistas

Ferramenta deProgramação

Conhecimentodo Domínio

•Formato do conhecimento•Regras•Aspectos operacionais

Page18

Exemplo• Exemplo implementado no sistema FASE

(Ferramenta para a construção de Arcabouços e Sistemas Especialistas)

• FASE foi implementado em Common-Lisp

• O sistema consiste em um conjunto de bibliotecas de funções com as seguintes funcionalidades– Representação do conhecimento:– Estratégias de controle– Resolução de conflito

Page19

FASE• A modularidade do ambiente é decorrência

dos conceitos de padrão e instância

– Padrão (pattern) é uma representação genérica de um conjunto de fragmentos de conhecimento, geralmente envolvendo variáveis

– Instância é uma representação específica de um fragmento de conhecimento

Page20

Padrão/Instância• Intuitivamente, um padrão pode ser interpretado

como “uma pergunta” à memória de trabalho, e uma instância, como uma resposta a esta pergunta

Padrão Instância

? Resposta

Page21

Regras FASE• As regras utilizadas no ambiente FASE têm a

seguinte sintaxe

<rule> ::= (<name> <alpha> ({pattern}) ({pattern}))

• <name> é um símbolo correspondente ao nome da regra

• <alpha> é o valor numérico associado ao coeficiente de certeza da regra

• <pattern> depende do método de representação

Page22

Regras FASE: Exemplo• (nota-4 0.9 ((logic (nota ?x matematica muito-

bom) (nota ?x fisica bom))) ((logic (performance ?x

computacao))) )name

alpha pattern

Page23

Aquisição de Conhecimento• É uma das partes mais sensíveis

– Não basta adicionar elementos de conhecimento à base;

– É necessário integrar o novo conhecimento ao já disponível

• Outro ponto importante na aquisição de conhecimento é o tratamento de incoerências– Erros podem resultar da própria natureza do

conhecimento– Erros da interface homem/máquina

Page24

Aquisição de Conhecimento• Verificação periódica de inconsistências

– Linguagens de representação expressivas não contam com procedimentos completos de verificação

– Problemas NP-Difíceis no sentido forte

Page25

Métodos de Representação• A parte mais importante no projeto de

um sistema SE é a escolha do método de representação de conhecimento– A linguagem associada ao método deve ser

suficientemente expressiva– Em tese, uma representação em lógica seria

suficiente

Page26

Lógica• A lógica é a base para a maioria dos

formalismos de representação do conhecimento

• Tipicamente, as regras podem ser representadas como proposições ou predicados lógicos

Page27

Exemplo: Sistema FASE• FASE dispõe de um módulo de representação do

conhecimento baseado na lógica de primeira ordem

• Primitivas– Store: armazena um fragmento de

conhecimento na base– Query: obter instâncias que satisfazem às

restrições especificadas através de variáveis que ocorrem em seu argumento

– List: que permite examinar o conteúdo da base

Page28

FASE: Linguagem de Acesso• <command> ::= (logic-query <query>) |

(logic-store <store>) | (logic-list)

• <query> ::= (<predicate> {<term>})• <store> ::= (<predicate> {<closed term>}) |

(off <predicate> {<closed term>})• <closed-term> ::= <constant> |

(<function> {<closed-term>})• <term> ::= <constant> |

<variable> |(<function> {<term>})

Page29

FASE: Exemplo• Base de conhecimento

– Progenitor(Boris, Jane)– Progenitor(Boris, Marcia)– Progenitor(Adelia, Jane)– Progenitor(Jane, Tiago)

• Codificando o conhecimento em FASE– > (logic-store (progenitor Boris Jane))– > (logic-store (progenitor Boris Marcia))– > (logic-store (progenitor Adelia Jane))– > (logic-store (progenitor Adelia Marcia))– > (logic-store (progenitor Jane Tiago))

Page30

FASE: Fazendo consulta• Uma vez armazenadas as informações, a base

de conhecimento pode ser consultada através do comando query

• > (logic-query (progenitor x Tiago))( [Substituicao : (x . Jane))] )

• > (logic-query (progenitor Boris y))( [Substituicao : (y . Marcia))] )( [Substituicao : (y . Jane))] )

Page31

FASE: Fazendo consulta• Introduzindo regras mais complexas

– > (logic (progenitor x y) (progenitor y Tiago))

– ( [Substituindo : ((x . Boris) (y . Jane))] )– ( [Substituindo : ( (x . Adelia) (y . Jane))] )

Page32

Redes Semânticas• Rede semântica é um nome utilizado para

definir um conjunto heterogêneo de sistemas– Um grafo, cujos nós modelam sistemas e

cujos arcos indicam as relações binárias

• Nós– Objetos– Predicados– Classes– Palavras de uma linguagem

Page33

Redes Semânticas• Redes semânticas foram propostas por Quillian

como um formalismo computacional da memória humana

Page34

Redes SemânticasMobilia

Preto

Cadeira Assento

Cadeira-27Ana

Pessoa

Couro

é-um

é-um

estofamento

parte-de

cor

é-um

dono

Page35

Redes Semânticas• Nos anos 60, redes semânticas foram usadas

na implementação de sistemas de processamento de linguagem natural

Page36

Desenvolvimentos Seguintes• Marvin Minsky (1975)

– Introduziu a noção de estrutura interna, criando outra estrutura chamada de quadros

• Woods– Sugeriu a fundamentação teórica com

ênfase em lógica

Page37

Herança de Propriedades• Herança é formada por caminhos do grafo

• Permite que propriedades de um nodo sejam especificadas apenas uma vez

• Herança é simplificada se a rede formar uma árvore (mais complexa no caso de herança múltipla)

Page38

Exemplo

Clyde

Elefante real

elefante

Cinza

é-um

é-umé-um

não-é-um

Page39

Quadros• Quadros foram introduzidos para permitir a

expressão das estruturas dos objetos, mantendo a propriedade de representar herança como as redes semânticas

• Os quadros foram introduzidos por Marvin Minsky– “A Framework to Represent Knowledge”

• O método de quadros dá origem às idéias que levaram à concepção das linguagens de programação orientadas a objetos

Page40

ExemploSuper-Frame: Lugar-CobertoFrame: Comodo

Tipo

Número de Paredes

Default Atributo Se-necessário

Formato

Altura

4

retangular

3

número

símbolo

Número (m)

Super-Frame: ComodoFrame: Sala

É-um

Page41

Sistemas Híbridos• Os problemas de eficiência, associados aos

métodos gerais de representação do conhecimento, baseados nos formalismos lógicos, e a dificuldade em representar certos tipos de conhecimento (e.g., fatos negativos, disjunções e asserções quantificadas) utilizando quadros e redes semânticas levaram às idéias de representação múltipla

Page42

Sistemas Híbridos• O sistemas de representação do

conhecimento atuais fornecem a seus usuários mais de um formalismo de representação

– Devemos utilizar os formalismos simultaneamente?

– Que pontos devem ser integrados?

Page43

Sistemas Híbridos• Em arcabouços para SE´s, a tarefa é

deixada para o usuário:– Cada formalismo é independente um do

outro– Facilidade de programação (+)– Dificuldade de manter consistência (-)

• Mais recentemente, teorias e sistemas foram propostos para integração de formalismos (e.g., Krypton)– O subsistema tem a semântica integrada

Page44

Ferramentas para Construção de SEs

• As ferramentas variam quanto:– A interface com o usuário– Interface de desenvolvimento– Interface com o S.O.– Motor de inferência

Page45

Construção de SE´s• Interface com o usuário final

– Tipicamente gráfica– Uso de janelas e recursos gráficos– Diferentes níveis de usuário (iniciante,

avançado)

• Interface de desenvolvimento– Facilidade para manipulação da base de

dados– Tratamento de erros e verificação– Facilidade para documentação

Page46

Construção de SE´s• Interface com o sistema operacional

– Ferramentas disponíveis para várias plataformas• Mainframes e microcomputadores

– Linguagens de programação• C/C++• Common Lisp

– Facilidade de comunicação com bancos de dados

– Grau de segurança

Page47

Construção de SE´s• Motor de Inferência

– Características relevantes• Modo de raciocínio• Estratégia de busca• Resolução de conflito• Representação de incerteza• Representação de conhecimento

Page48

Construção de SE´s• Motor de Inferência

– Modo de raciocínio• Encadeamento progressivo ou

encadeamento para trás• Problema de planejamento: encadeamento

progressivo• Problema de diagnóstico: encadeamento

regressivo– Estratégia de busca

• Guiar a pesquisa na memória de trabalho e base de regras

• Equivalente a algoritmos de busca em grafos

Page49

Construção de SE´s• Motor de Inferência

– Resolução de conflito• Regras para seleção de regras

sensibilizadas• Regras: prioridade, etc.

– Representação de incerteza• Área de pesquisa

– Teoria nebulosa– Teoria de probabilidades (redes Bayesianas)

• SE´s atribuem um número à regra que caracteriza o grau de confiança da regra

Page50

Referências• Guilherme Bittencourt, Inteligência Artificial:

Ferramentas e Teorias, Editora da UFSC, 1998.

Page51

Fim• Obrigado pela presença!