1

Inteligência Artificial

Aula 6

2

Regras de produção

• Exemplo de sistema de representação procedimental , baseado na lógica de primeira ordem (prolog constitui um exemplo desta abordagem);

• especialistas tendem a expressar suas técnicas de solução de problemas em termos de conjuntos de regras situação-ação;

• regras de produção = conhecimento é representado como uma coleção de regras do tipo se condição então ação;

3

– A ação corresponde a algum procedimento que acarreta uma conclusão ou mudança no estado corrente;

– o conjunto de regras de produção é visto como uma representação de conhecimento procedimental, baseada em lógica de primeira ordem;

• este esquema representa um dos melhores meios disponíveis para codificação da experiência de especialistas, na resolução de problemas;

• regra de produção apresentam um estilo estímulo-resposta na representação ;

4

• Principais propriedades das regras de produção:– incorporam conhecimento prático (heurístico) em regras se-

então;– sua habilidade cresce em uma taxa proporcional ao crescimento

da base de conhecimento (crescimento incremental);– pode resolver um grande intervalo de problemas possivelmente

complexos utilizando regras relativamente simples e combinando os resultados de maneira apropriada;

– podem explicar suas conclusões refazendo suas linhas de raciocínio e traduzindo a lógica de cada regra empregada em linguagem natural;

5

• Cada regra aproxima um fragmento independente do conhecimento (conhecimento refinado com a adição de nova regra);

• as regras de produção descrevem as relações entre os objetos do domínio ( se... então...);– os objetos tem diversos atributos ligados a ele;

• cada condição da regra representa uma informação na forma objeto-atributo-valor ou objeto-atributo:– exemplo retirado do MYCIN ( programa de

diagnóstico de doenças infecciosas)

6

– Se local da cultura for o sangue e a morfologia do organismo for bastonete e a mancha de gram do organismo for gram-positiva e o doente estiver em perigo então existe evidência de que a identidade do organismo é Pseudomonas-aeruginosa (regra102);

• mostrando objeto-atributo valor da regra;

Objeto Atributo Valor

cultura local sangue

organismo morfologia bastonete

organismo mancha de gram gram-positiva

doente comprometimento verdade

organismo identidade Pseudomonas-aeruginosa

7

• Um sistema típico de regras de produção é formado por:– uma base de conhecimento;– memória de trabalho;– máquina de inferências;

• linguagens como Prolog e Lisp já incorporam a memória de trabalho e a máquina de inferências:– o que não ocorre em linguagens tradicionais

como C e Java onde há necessidade de implementar estes mecanismos;

8

– existem shells (programas específicos para implementação de regras) que já incorporam a memória de trabalho,a máquina de inferências e as rotinas de interface com o usuário, tornado muito mais fácil o trabalho sendo que o desenvolvedor precisa apenas codificar o conhecimento ;

– shells = pseudo linguagens interpretadas, não gera executável;

• base de conhecimento:base de conhecimento:– composta por regras e fatos;– regras: declaração sobre classes e objetos:

• SE condição (antecedente) ENTÂO ação (consequente);

– fatos: declarações sobre objetos específicos;

9

• Memória de trabalho:Memória de trabalho:– representa o estado do problema em um dado

instante (permite comunicação entre regras);– possui dados dinâmicos de curta duração que

existem enquanto uma regra estiver sendo interpretada;

• com a especificação do estado meta do problema, a máquina de inferência é ativada:– responsável pela execução das regras,

determinando quais são relevantes, de acordo com a configuração da memória de trabalho e pela escolha de quais aplicar;

– isto acontece em ciclos;

10

– em cada ciclo:• as regras são examinadas buscando as que são apropriadas para ativação;

– um ciclo pode ser dividido nem três fases:– Seleção de regras;– resolução de conflitos;– ação;– se o desenvolvedor estiver utilizando Prolog, Lisp ou uma shell

não terá como interferir nestas fases;

• Seleção de regras ou matching:Seleção de regras ou matching:– objetivo é encontrar todas as regras que são satisfeitas pelo

conteúdo da memória de trabalho;

11

– tarefa de “casar” as regras com os dados da memória de trabalho gerando um conjunto de conflito;

– conjunto de conflito= regras que satisfazem as “condições de casamento”, ou seja, regras passíveis de serem executadas;

• as estratégias mais utilizadas para este casamento são:– raciocínio para frente (raciocínio dirigido por

regras);– raciocínio para trás (raciocínio orientado por

metas);

12

• Raciocínio para Frente:– dirigido por dados, antecedente, progressivo,

“foward-chaining” ou bottom-up”;– os dados da memória de trabalho são “casados”

com as condições das regras;– o programa inicia do estado inicial e gera

estados intermediários através da execução das ações das regras;

– a meta permanece a mesma durante todo o processo de solução do problema;

– quando um destes estados alcançáveis casar com a meta, o problema está resolvido;

13

• Raciocínio para trás:– dirigido por metas, conseqüente, regressivo,

“top-down” ou “backward-chining”;– o programa inicia com a configuração objetivo

final = meta;– seleciona uma ou mais regras, cuja ação casa

com o objetivo em alguma extensão;;– o lado esquerdo das regras selecionadas é

utilizado para gerar novos objetivos a serem atingidos e o processo continua até que um deles seja casado com o estado inicial;

14

• Veja o exemplo:– possuímos a seguinte base de conhecimento:

fatos regras

Marcos é homem. SE x é homem

César é homem. ENTÃO x é pessoa.

– A meta é responder a questão

– Estado meta: “ Existe x que é pessoa ?”

– Estado inicial: fatos

15

– Com a estratégia raciocínio para frente o nó raiz conterá o estado inicial (conjunto de fatos) e a meta será encontrar uma pessoa;

– como o antecedente da regra 1 casa com o estado inicial, o segundo nível será composto do nó “ Marcos é pessoa” ;

– o processo de inferência é encerrado porque houve o casamento com a meta, através da substituição da variável x por Marcos;

– o sistema responde com “ sim, x= Marcos”;

homem(Marcos)

homem(César)

pessoa(Marcos)

16

– Com a estratégia raciocínio para trás o nó raiz conterá a meta;

– o próximo nível é formado pelo antecedente da regra 1, isto é “ x é homem”, pois o seu conseqüente casa com a raiz;

– analogamente o segundo nível é formado por “ Marcos é homem” e a inferência é interrompida pois se atingiu um estado inicial;

– o sistema responde com “ sim, x=Marcos”;

pessoa(x)

homem(x)

homem(Marcos)

17

• Utilizado em sistemas especialistas, mesclando de acordo com a situação o raciocínio para frente e o raciocínio para trás;

• exemplo:

Objetivo: escolher um vinho;

Fatos: dados de entrada;

Regras:

Regra 1Se tem molho

e molho = apimentado

então melhorcorpo = encorpado

18

Regra2 Se sabor = delicado

então melhorcorpo = leve

Regra3Se pratoprincipal = peixe

então melhorcor = branco

Regra4

Se pratoprincipal <> peixee tem molho

e molho = tomate

então melhorcor = tinto

19

Regra5Se cor recomendada = branco

e corpo recomendado = leve

e suavidade recomendada = medio

então vinho = chenin blanc

Regra5Se cor recomendada = tinto

e corpo recomendado = medio

e suavidade recomendada = medio

então vinho = Pinot Noir

20

Prolog

• É uma linguagem que utiliza o paradigma de programação em lógica;

• representamos conhecimento positivos;• hipótese do mundo fechado=as declarações relevantes

e verdadeiras estão contidas na base de conhecimento ou podem ser derivadas ( método de inferência);

• negação = ausência da declaração;• resolução por refutação = P é consistente se falha ao

tentar provar ¬P;

21

• definições lógicas em programas Prolog constituem cláusulas de Horn;

• Cláusulas de Horn:– tem no máximo um literal positivo;– qualquer fbf (fórmula bem formada) de uma lógica de primeira ordem

pode ser representada na forma clausal;– não possui conectivo ;– quantificadores universais () é aplicado a predicados conectados por ;

• Prolog:– os quantificadores não são explicitados;– o conectivo é representado por vírgula;

22

– As implicações do tipo p q são representados invertidos como q:-p ;

– as disjunções são representadas por uma lista de declarações alternativas representadas por ; ;

– os comandos são finalizados com um ponto;– cabeças de regra no Prolog são as conseqüentes

nas regras de produção (então);– cada cabeça de regra representa uma ação (se

condição e condição e ... então ação);– variáveis iniciam com letras maiúsculas;– constantes iniciam com letras minúsculas;– predicados iniciam com letras minúsculas;

23

• Os fatos das cláusulas de Horn são decidíveis:– há garantias de parar quando a cláusula que

tiver de se demonstrada não for dedutível a partir dos fatos e regras conhecidos;

• a base de conhecimento é expressa por conhecimento codificado como cláusulas de Horn transformadas, ou seja, cláusulas prolog;

• a máquina de inferência do Prolog é composto do procedimento de inferência e de uma estratégia de busca;

24

• usa resolução e raciocínio para trás e estratégia de busca em profundidade, analisando as regras da esquerda para a direita e de cima para baixo;

• Exemplo de programas em Prolog

1.amigo(joao,jose).

amigo(joao,jorge).

amigo(joao,jaco).

amigo(pedro,paulo).

amigo(pedro,julio).

Tem_amigos(X):-amigo(X,_).

25

female(pam).

male(tom).

Male(bob).

female(liz).

female(pat).

female(ann).

male(jim).

parent(tom,liz).

parent(pam,bob).

parent(tom,bob).

parent(bob,ann).

parent(bob,pat).

parent(pat,jim).

offspring(Y,X):-parent(X,Y).

father(X,Y):-male(X),parent(X,Y).mother(X,Y):-female(X),parent(X,Y).grandparent(X,Y):-parent(Z,Y),parent(X,Z).sister(X,Y):-female(X),parent(Z,X),parent(Z,Y).hasachild(X):-parent(X,Y).happy(X):-hasachild(X).hastwochildren(X):-parent(X,Y),sister(Y,Z).grandchild(X,Z):-parent(Y,X),parent(Z,Y).aunt(X,Y):-parent(Z,Y),sister(X,Z),not(mother(X,Y)).

Exemplo 2

26

Vantagens:

• Ampla expressividade;

• representação de associações empíricas (heurísticas) em domínios não estruturados;

• codificação da experiência de especialistas na resolução de problemas;

• possui sintaxe e semântica simples;

• aplicação: sistemas de diagnóstico;

• prototipação: crescimento incremental da base de conhecimento;

27

Desvantagens• Falta de estruturação da base de conhecimento dificulta:

– introduzir modificações na base;– localizar informações desejadas;– representar estruturas inerentes ao domínio:

• taxonomia de classes;• relações temporais;• relações estruturais;• herança de atributos;

• não facilita a distinção semântica entre propriedades essenciais e propriedades complementares dos objetos;