Funções da representação de conhecimento:
Conhecimento
•Informação armazenada (Dados)
•Modelos usados para interpretar, predizer e responder ao ambiente
Razões para se representar o conhecimento
•Função Dedutiva:
•Obtenção de novos resultados a partir de dados existentes
•Função Consultiva:
•Grandes quantidades de informação podem gerar dificuldades
no cruzamento delas.
•Função Organizacional:
•Organização dos dados facilita a computação.
Recuperação
Raciocínio
•Função Interpretativa:
•Permite a interpretação através de comparações com modelos
pré-estabelecidos e armazenados previamente.
Aquisição de novos conhecimentos
Características desejadas em uma representação:
•
Coleta de informação deve seguir os objetivos desejados.
•
Explicitar o que é importante (Não deve haver informação
implícita nas representações).
•
Revelar restrições naturais, facilitando algumas classes de
computações.
•
Ser completa (procurar dizer tudo que pode).
•
Ser concisa (necessidade de poucos recursos e mostrar eficiência
nas inferências).
•
•
Facilitar a computação (armazenamento e recuperação da
informação).
•
Suprir pormenores e informações raras
•
Ser computável.
•
Permitir fácil aquisição do conhecimento e ser legível.
•
Permitir a aplicação de mecanismos de inferência.
•
Apresentar acesso rápido e fácil ao conhecimento.
•
Manter o conhecimento coerente.
Ser transparente (sem criptografia)
1
Representação do conhecimento
Sistemas de Produção
(Tecnologias de representação do conhecimento)
•Base para os sistemas especialistas.
•Sistemas (regras) de produção
•Redes semânticas
•Quadros e roteiros
•Lógica
•Emil Post (1943) –
•modelo computacional geral de solução de problemas (um
procedimento calculável pode ser modelado como um sistema
de produção).
•Nos anos 50 e 60 –
•usados para representar a forma humana de resolver
problemas (xadrez e criptoaritmética).
•Nos anos 70 –
•usados para representar modelos mentais.
=> atualmente descrevem uma família de sistemas constituídos de
regras (condições e ações).
Exemplos:
•Condição (lado esquerdo, antecedente, premissa, padrão) determina a aplicabilidade da regras
•Condição
•(lado esquerdo, antecedente, premissa, padrão) - determina a
aplicabilidade da regras
•Ação
•Ação (lado direito ou consequente) - o que deve ser realizado se a
regra é aplicável
Regra: Farol vermelho
IF o farol está vermelho THEN pare
Regra: Farol verde
IF o farol está verde THEN atravesse
•(lado direito ou consequente) - o que deve ser realizado se a
regra é aplicável
Obs.: Cada regra é identificada por um nome
2
•Sistema de produção - formado por uma ou mais bases de regras,
separadas por conveniência computacional.
•Sistema de produção - formado por uma ou mais bases de regras,
separadas por conveniência computacional.
•Exemplo:
•Exemplo (MYCIN):
Regra: 1
IF faixa da esquerda está muito a esquerda
AND faixa da direita está muito a esquerda
THEN saída é muito a esquerda
Regra: 2
IF faixa da esquerda está médio a esquerda
AND faixa da direita está médio a esquerda
THEN saída é médio a esquerda
Regra: 3
IF faixa da esquerda está pouco a esquerda
AND faixa da direita está pouco a esquerda
THEN saída é pouco a esquerda
•Exemplo:
•B3:
B3:
IF the step is packpack-largelarge-items
AND there is a large item to be packed
AND there is a large bottle to be packed
AND there is a bag with < 6 large items
THEN put the bottle into the bag
•B4:
B4:
IF the step is packpack-largelarge-items
AND there is a large item to be packed
AND there is a bag with < 6 large items
THEN put the large item into the bag
•B5:
B5:
IF the step is packpack-largelarge-items
AND there is a large item to be packed
THEN get a new bag http://www.cse.unsw.edu.au/~billw/cs9414/notes/kr/rules/rules.html
IF the identity of the germ is not known with certainty
AND the germ is gramgram-positive
AND the morphology of the organism is "rod
"rod"
rod"
AND the germ is aerobic
THEN there is a strong probability (0.8) that the germ is of
type enterobacteriacae
http://www.ecs.soton.ac.uk/~phl/ctit/ho1/node2.html
Máquina de inferência determina que antecedentes de que regras são
satisfeitas pelos fatos.
Métodos de inferência:
•Encadeamento para frente (forward chaining)
•Raciocínio dos fatos para as conclusões
•Ex.: IF está chovendo THEN leve o guarda-chuva.
(fato, premissa)
(conclusão, ação)
3
•Encadeamento para frente (forward chaining)
•Encadeamento para trás (backward chaining)
•Raciocínio a partir da conclusão (tomada como hipótese),
tentando-se encontrar os fatos que suportam a hipótese.
FATO 1
FATO 2
AND
DECISÃO 1
FATO 3
FATO 4
AND
OR
DECISÃO 2
AND
DECISÃO 3
DECISÃO 4
•Exemplo:
FATO 5
FATO 6
FATO 7
AND
DECISÃO 5
FATO 8
•sua hipótese é que está chovendo
•Encadeamento para trás (backward chaining)
•O tipo de mecanismo de inferência depende da aplicação.
•Problemas de diagnósticos - backward chaining.
FATO 1
FATO 2
AND
DECISÃO 1
FATO 3
FATO 4
•Problemas de monitoramento e controle - forward chaining.
AND
OR
DECISÃO 4
DECISÃO 2
•A regra é ativada ou instanciada se todos os padrões (premissas)
forem satisfeitas.
FATO 5
FATO 6
FATO 7
FATO 8
•Se você não sai na rua, mas
•alguém entra na sua casa com os sapatos e o guarda-chuva
molhados,
AND
DECISÃO 3
AND
DECISÃO 5
•Se várias regras são ativadas, o mecanismo de inferência deve
escolher uma regra para ativar.
4
•A máquina de inferência opera em ciclos:
Vantagens:
•ciclo de reconhecer-agir
•ciclo de selecionar-executar
•Modularidade (independência das regras, fácil de
encapsular e expandir incrementalmente)
•ciclo de situar-responder
•Naturalidade (próximo do pensamento)
•ciclo de situar-agir
•Uniformidade (mesmo padrão de escrita)
•Máquina de inferência executa repetidamente um grupo de tarefas
até um certo critério de parada.
Desvantagens:
•Opacidade (difícil verificar completude)
•Ineficiência
•número de regras a combinar
•esforço para o casamento (matching- verificação de regras
que se aplicam)
Domínios de aplicação
•Conhecimento difuso, com muitos fatos
•Processos que podem ser representados como conjunto de ações
independentes.
•Conhecimento fácil de separar de sua forma de uso
=> pode ser resolvida com ordenação
5
Restrições para aplicação de Sistemas de Produção:
•Não aprendem
•Não raciocinam em níveis
•Não vêm os problemas de perspectivas diferentes
•Não usam modelos revelados por restrições
•Não sabem como e quando violam suas próprias regras
•Não têm acesso ao raciocínio que está por trás das regras
Tarefa:
(Escolher um dos itens)
1. Escrever um sistema de produção para representar o
conhecimento que um especialista em redes usa, para
diagnosticar um defeito de acesso à internet em um computador.
2. Escrever um sistema de produção para um sistema automático de
revisão de artigos científicos para verificação de plágio através da
comparação de artigos.
3. Escrever um sistema de produção para representar o
conhecimento (básico) que um gerente de banco usa para aprovar
um empréstimo.
4. (Propostas de implementação)
PROLOG
PROLOG (PROgramming in LOGic)
•Desenvolvida nos anos 70
•Primeiro PROLOG - Universidade de Edimburgo, Escócia
•Fama - japoneses utilizaram como a linguagem para a quinta
ATOMO - tipo e palavra mais comum em prolog.
lapis, carro, maria, livro
PREDICADO - construção usada para declarar algo sobre objetos
(declaração - representada por átomos e seguida por objetos que
devem ser separados por vírgulas)
geração de computadores.
•Linguagem declarativa orientada para o processamento simbólico.
robo(joao)
•Difere das linguagens tradicionais.
construiu(silva,joao)
•Possui uma teoria matemática - Lógica dos predicados.
•Programação envolve aspectos declarativos e procedimentais.
pai(silva,jose)
•Predicado pode representar relação entre os objetos ou nomear uma
ação da qual eles participam.
6
FRASES
•Frases podem ser usadas para perguntar algo ao computador
(interrogativas).
•Constituídas por um único predicado
•Quando dizem alguma coisa elas são afirmativas e terminam com
ponto final (.)
•Começam com um ponto de interrogação seguido do sinal de
menos (-)
robo(joao). (joao é um robô)
?- robo(joao).
yes
construiu(silva,joao).
pai(silva,jose).
homem(silva).
?- robo(silva).
no
Variáveis Existenciais
Variável Universal
Usadas para se referir a objetos desconhecidos (quando é preciso
perguntar sobre objetos cuja identidade nada se conhece - quando se
usa os pronomes “qual” e “quem”).
•Representa um objeto qualquer
São diferenciadas pela letra maiúscula inicial.
igual(X,X).
•Análoga a palavras como “qualquer”, “tudo”, etc.
- Significa tudo é igual a tudo.
Ex.:
Uso de variáveis universais não é exclusivo do PROLOG
?-homem(Pessoa).
Pessoa =silva ;
no
•Se uma pessoa P pede emprestado uma quantia de N a 5% ao
mês, depois de um mês estará devendo N+5*N/100.
7
Frases Compostas (no PROLOG)
Frases Compostas
Simbologia
Ex.: (Primeira lei da robótica)
proibido_fazer(R,B):-robo(R),
capaz_de_fazer(R,B),
machuca(B,H),
humano(H).
:- IF
, AND
Frase 1:
R está proibido de fazer um ato B se R for um robô e R for
capaz de fazer B e B machucar H e H for humano.
; OR
Ex.: (Segunda Lei da robótica)
obrigado_a_fazer(R,B):-robo(R),
capaz_de_fazer(R,B),
oferece_perigo(C,para,H),
humano(H),
afasta(B,C).
deve_fazer(R,Ato):-robo(R),
capaz_de_fazer(R,Ato),
mandou_fazer(H,Ato),
humano(H),
not proibido_fazer(R,Ato).
Frase:
Frase 2:
R é obrigado a fazer um ato B se R for um robô e R for
capaz de fazer B e C oferece perigo para H e H é humano e
o ato B afasta o perigo C.
R deve fazer um Ato se R for um robô e R for capaz de
fazer o Ato e H mandou R fazer este Ato e H é humano e R
não está proibido de fazer o ato pela primeira lei da
robótica.
Obs.: Operador “not” antes do predicado negação do predicado.
8
Estruturas
Palavras usadas para se referir a objetos com partes que devem ser
nomeadas individualmente.
Ex. (estrutura):
machuca(derrubar(H),H):-animal(H).
•As estruturas possuem componentes:
•O objeto do predicado machuca é a estrutura derrubar(H).
•Funtor - átomo que identifica a estrutura
•O funtor da estrutura é derrubar e
•Argumentos
•Nomeiam as partes do objeto composto
(constantes, variáveis, números ou outras estruturas).
•O único argumento é H.
•Colocados entre parênteses e separados por vírgula
=> as estruturas têm a mesma forma que os predicados.
Perguntas sobre a primeira lei da robótica:
?-proibido_fazer(piter,O_que).
O_que = derrubar(silvestre) ;
O_que = derrubar(hadar) ;
O_que = derrubar(nadia);
no
Para a segunda lei da robótica
Estruturas e Predicados
•Predicados são estruturas que declaram coisas que são
verdadeiras ou falsas
•Todo predicado é uma estrutura, mas nem toda estrutura é um
predicado. (Ex.: Estruturas que nomeiam objetos)
•Predicados são componentes principais das frases em PROLOG
e são ligados pelo símbolo ( :- ) ou por vírgulas (,)
?-obrigado_a_fazer(piter, O_que).
O_que = derrubar(monstro_verde).
yes
9
Estruturas e Predicados
aniversario(nadia,data(3,marco,1986)).
Programas
Seja a frase:
Definindo o signo de Nadia:
humano(H):-homem(H).
signo(Pessoa,aquario):aniversario(Pessoa,data(Dia,janeiro,_)),
Dia > 20.
Cabeça
Corpo
signo(Pessoa,aquario):aniversario(Pessoa,data(Dia,fevereiro,_)),
Dia =<18.
“_” significa não importa, ou seja, o computador não leva o ano em
conta.
Aridade
Conceito de Definição
•Número de objetos em um predicado ou o número de argumentos
em uma estrutura.
•Um conjunto de frases é denominado uma definição, se os
predicados cabeça são os mesmos e se tiverem a mesma aridade.
humano(H):-homem(H).
Exemplos:
humano(M):-mulher(M).
humano(H) -> aridade 1.
•Várias definições juntas para realizar uma tarefa formam um
programa.
data(15,marco,1986) -> aridade 3.
10
Listas
Listas
•Sequências de elementos colocados entre colchetes e separados por
vírgula.
•Usadas (em geral) como objetos de predicados.
Exemplo:
•[rosa,cravo,violeta]
(os elementos são constantes)
•[laranja,X,abacate]
(o segundo elemento é variável)
•[data(3,marco,1986),data(1,abril,1952)]
(os elementos são estruturas)
•[[1,2],[4,5]]
(lista constituída de outras listas)
partes(manipulador,[braco,punho,efetuador]).
1o argumento: manipulador – usado pelo robô para realizar trabalho.
2o argumento: lista com as partes de um manipulador.
•Usa-se variáveis para representar elementos desconhecidos ou
genéricos.
[P,A,piter]
P e A – são genéricos ou desconhecidos.
Listas
Exemplos:
•Número indeterminado de elementos genéricos na cauda de uma
lista é representado por uma barra vertical.
[ana] é a mesma coisa que [ana|Y] sendo Y a lista vazia.
Programa para verificar se um elementos pertence a uma lista:
[rosa,cravo | X]
Barra vertical significa o resto dos elementos.
Um tipo especial de lista é aquele em que o primeiro elemento e o
resto dos elementos são representados por variáveis.
[X | Y]
[Primeiro | Cauda]
[Topo | Cauda]
pertence(X,[X|Y]).
pertence(X,[P|R]):-pertence(X,R).
?- pertence(a,[b,c,d,a,g]).
yes
?- pertence(ana,[cravo,rosa,violea]).
no
?- pertence(E,[a,b,c,d]).
E=a;
E=b;
E=c;
E=d;
no
11
Aritmética
Aritmética
Exemplo:
Exemplo: Cálculo do número de elementos de uma lista.
numero_de_elementos([],0).
?- X is 2+5*9.0/4.
numero_de_elementos([X|Y],N):numero_de_elementos(Y,NY),
N is 1+NY.
X = 13.25 ;
no
?Teste:
?- numero_de_elementos([a,b,c],Num_elms).
Num_elms = 3 .
yes
?-
Aritmética
Aritmética
Exemplo de uma função de somatoria.
Exemplo de uma função de calculo de media.
somatoria([],0).
media(Lista,Med):numero_de_elementos(Lista,Num_de_elems),
somatoria(Lista,S),
Med is S/Num_de_elems.
somatoria([X|Y],S):somatoria(Y,SY),
S is X+SY.
Teste:
Teste:
?- somatoria([1,2,3],S).
?- media([5,4.0,9,4],Media).
S=6.
yes
?-
Media = 5.5 .
yes
?-
12
Prioridade
Prioridade
É possível representar um funtor em forma infix (entre os
argumentos) => usa-se o comando interno “op” com 3 argumentos
(op/3) onde:
Argumento 1 - precedência;
Argumento 2 - associatividade;
Argumento 3 - nome do operador
-Prioridade e hierarquias:
:-op(500,yfx,+).
-Observações: Estruturas de menor prioridade são objetos
(argumentos) de estruturas de maior prioridade, se não existir
parênteses.
Exemplos: (Considerando as definições anteriores)
:-op(500, yfx, +).
:-op(400, yfx, *)
:-op(400,yfx,*)
2*3 é argumento de “+” na estrutura 4+2*3
-y e x são os argumentos
-f é o funtor
-Os números 500 e 400 são prioridade e estabelecem hierarquias
entre estruturas (precedência varia entre 1 e 1200).
Mas
Associatividade
Associatividade
- Seja a expressão: 4 + 6 + 9
-Na transformação a seguir o funtor “,” tem associatividade direita.
(4+2) é argumento de “*” na estrutura (4+2)*3
Deve-se decidir se “4+6” é argumento do segundo “+” ou se “6+9” é
argumento do primeiro “+”.
:-op(1000,xfy,”,”)
?- homem(hadar),mulher(nadia),robo(piter).
- Pela transformação a seguir, o “+” foi transformado em funtor infix
por meio de um “yfx” possuindo associatividade esquerda.
yes
?- homem(hadar),(mulher(nadia),robo(piter)).
:-op(500,yfx,+).
Portanto, “4+6” é argumento do segundo “+”
yes
?-
(4+6)+9 é equivalente a 4+6+9
13
Associatividade
Associatividade
-Há funtores que não admitem encadeamento com outros de igual
prioridade.
-Regra para associatividade de um funtor infix:
-Se usar “yfx” => associatividade esquerda
-Para torná-los infix usa-se a declaração “xfx”
-Se usar “xfy” => associatividade direita
:-op(700, xfx, [=, <, >]).
-Se usar “xfx” => não há associatividade
Pode-se instalar uma lista [=, <, >] de funtores infix se todos tem a
mesma prioridade.
Operadores
Operadores => Clareza
-São funtores que não precedem argumentos colocados em
parênteses.
-O uso de operadores transformam frases em Prolog em frases
familiares aumentando a clareza dos programas.
Exemplos:
-Funtores infix são operadores ( “+” e o “*”).
-Operador prefixo “not” precede seu argumento único e não exige
parênteses.
:-op(900,fy,not).
:-op(30,yf,eh).
:-op(35,yf,[homem,mulher,robo]).
piter eh robo.
joao eh homem.
silvestre eh homem.
hadar eh homem.
nadia eh mulher.
maria eh mulher.
14
Operadores => Clareza
:-op(35,xfx,[pai, construiu, ama]).
:-op(30,fx,de).
silvestre eh pai de nadia.
silvestre construiu piter.
nadia ama hadar.
hadar ama nadia.
?- nadia ama piter.
no
?- nadia ama hadar.
yes
Operadores => Clareza
?- Quem eh homem.
Quem = joao ;
Quem = silvestre ;
Quem = hadar ;
no
?- Alguem eh robo.
Alguem = piter ;
no
?-
Operadores e Listas
Operadores e Listas
-
-Para evitar a representação entre colchetes pode-se instalar o
operador “ponto”.
Listas são transformadas em estruturas da seguinte forma:
.(X,Y)
X é o primeiro argumento do “ponto”;
Y representa o segundo argumento do “ponto” (o resto da lista).
:-op(800,xfy,dot).
As estruturas abaixo são equivalentes:
[rosa, cravo, violeta]
Exemplos:
1) [ana] => .(ana,[])
2) [vera, ana] => .(vera, .(ana,[]))
3) [magda, vera, ana] => .(magda, .(vera, .(ana,[])))
rosa dot cravo dot violeta dot []
dot(rosa, dot(cravo, dot(violeta,[])))
[X | Y]
X dot Y
dot(X,Y)
15
Operadores e Listas
Tarefas:
-Exemplo:
1) Pesquisar mais detalhes e enriquecer esta base de dados para
permitir novas conclusões.
:-op(850,xfx,pertence).
:-op(830,fx,a).
X pertence a X dot Y.
X pertence a Y dot Z :- X pertence a Z.
2) Fazer uma pesquisa sobre o uso da linguagem PROLOG em
aplicações comerciais no mundo. Fazer uma pequena
monografia.
?- w pertence a w dot k dot [].
yes
?- rosa pertence a cravo dot orquidea dot rosa dot violeta dot [].
yes
?-
www.amzi.com
16