Formalismos de Representação
de Conhecimento
Prof. Fred Freitas
Centro de Informática - CIn
Universidade Federal de Pernambuco - UFPE
Roteiro
•
•
•
•
•
•
•
Controvérsia declarativo-procedural
Formalismos orientados à resolução de problemas
Formalismos orientados a domínios
Redes semânticas
Frames (Molduras)
Lógica de descrições
Analise de SBCs
Controvérsia DeclarativoProcedimental
• Abordagem procedimental
– Descreve o funcionamento de processos passo-a-passo
– Código compilado, mais rápido, simples, controlável e
popular
– Metáfora do “como”
• Abordagem declarativa
– Descreve um domínio com suas entidades e
características, através de “fatos” declarativos que não
estão dentro dos programas
– Motores de inferência deduzem novos fatos a partir dos
existentes
– Metáfora do “o quê”
Sistemas Baseados em
Conhecimento
• Criar sistemas diretamente a partir do conhecimento
• Separação entre o conhecimento e o processo
dedutivo ou inferência
• Conhecimento sobre o domínio e sobre processos
são dados (fatos), que podem ficar fora do
programa
• A concepção passa por 3 especificações
consecutivas:
– O nível de conhecimento ou epistemológico
– O nível lógico
– O nível de implementação
Formalismos de Representação
de Conhecimento
• Prover teorias - fundamentadas em lógica
matemática - e sistemas para expressar e
manipular conhecimento declarativo de forma
tratável e eficiente computacionalmente
• Um formalismo deve prover:
– Acesso aos fatos (conhecimento)
– Mecanismo de inferência (ou estratégia de resolução)
– Estratégias de controle e escalonamento da inferência
Tipos de formalismos
em relação ao foco
• Formalismos orientados à resolução de problemas:
regras de produção e programação em lógica
– Pioneiros
– Foco no processo, funcionamento
• Formalismos orientados a domínios: frames, redes
semânticas, lógica de descrições
– Classes, relações e restrições
– Facilitam a estruturação de conhecimento sobre um
domínio de aplicação
Formalismos orientados a
domínios
Redes Semânticas
• Proposta por Quillian [68] a partir da modelagem
da memória semântica humana
• Nós (objetos) conectados por arcos (relações
binárias)
• Arcos típicos: é-um (is-a), é-parte
• Muito utilizadas em Processamento de Linguagem
Natural
– Ontologias linguísticas (Ex: WordNet)
Redes Semânticas
pessoa
nome
cônjuge
id
primeiro
último
string
string
último
nome
pessoa
id
X: pessoa ( nome => id ( primeiro => string, último => Y: string ),
Cônjuge => pessoa ( nome => id ( último => Y),Cônjuge => X))
Correspondência com a LPO
• Uma rede semântica pode ser mapeada em uma
representação na LPO (Lógica da Primeira Ordem):
nós
retas
termos
relações
• Não é definido um conjunto específico de relações. As
relações mais usadas:
• is-a (é-um)
Permite agrupar objetos na mesma classe (Instanciação)
• ako (a-kind-of: tipo-de)
Refinamento de um conceito em um mais específico (Sub-classe)
• part-of (parte-de)
(relação de: pertence a ...)
Inferência sobre Redes Semânticas
• Busca e casamento de padrões
• Pode ser a partir de um nó ou arco, para frente
e/ou para trás através dos links
• Usos:
– Explicações
– Inferência sobre subsunção (herança)
– Consultar toda a informação possível sobre um nó ou
arco
– ...
Exemplo de ontologias
em redes semânticas
faz
Animal
Ako
Pássaro
Comer
Ako
Mamífero
tem
Pêlos
Ako
Cão
Is-a
Fido
(instanciação)
Busca como
Ferramenta Explicativa
• Para provar a declaração “Cães comem”
– pode-se supor que cães comem, e usar busca sobre a rede
para provar a hipótese.
• Buscando a partir do nó “Cão”, temos:
– “Cão é-um mamífero”
– “Mamífero é-um animal”
– “Animal faz comer”
– Isto é uma prova para “Cães comem”
Explorar exaustivamente
um tópico
• Para derivar todo o conhecimento sobre “cães”,
usa-se Busca em Largura a partir do nó “Cão”
– “Cães são Mamíferos”
– “Cães têm Pêlos”
– “Cães são Animais”
– “Cães Comem”
Relacionando tópicos
• Para verificar se “Cães” e “Pássaros” estão
relacionados, pode-se executar, a partir de ambos
os nós, uma Busca em Largura.
• A interseção entre os nós visitados nos dá uma
pista sobre o relacionamento entre os nós iniciais.
• Isto é chamado ativação distribuída ou interseção
de busca.
Problemas de redes semânticas
•
•
•
•
Muitos nós para representar pouca coisa
Muita repetição de nós
Não há distinção entre classes e objetos
Não podemos falar sobre as relações
– Dizer por exemplo que é de 1:1 ou 1:n
– A não ser reificando-as ...
• ...
Frames (Quadros)
• Base: modelos mentais de psicologia cognitiva
usados na resolução de problemas [Bartlett 32]
– Esquemas: estruturas de conhecimento (estereótipos)
armazenadas na memória duradoura, baseadas em
experiências passadas, a serem adaptadas
• Proposta por M. Minsky [75]
• Precursores declarativos dos objetos
procedimentais
Animais
Frames
Vivo:
V
Voa:
F
[Figueira 98]
Pássaros
Mamíferos
Pernas:
2
Voa:
V
Subconjunto
Pernas:
Subconjunto
Canários
Gatos
Amigo:
Piu-piu
Humanos
Frajola
Nome:
Amigo:
2
Membro
Membro
Piu-piu
Nome:
Subconjunto
Pernas:
Amarelo
Membro
Cor:
4
Frajola
Fred
Nome:
Fred
Expressividade dos Frames
• Classes
– Herança múltipla
– Instâncias
• Atributos (slots)
– Slots podem ser instâncias de outras classes (relações)
– Slots inversos:
• Ex: Slot Orientados da classe Professor é inverso do slot
Orientador da classe Aluno
• Ao preencher um o outro é preenchido automaticamente
• Facetas
– Restrições sobre os slots
• Inferência por meio de herança e restrições
Definindo classes e instâncias
(defclass City "Cities are part of countries or states."
(is-a Location)
(multislot is-Part-Of
(type INSTANCE)
(allowed-classes Country State)
(inverse-slot has-Parts)
(cardinality 1 ?VARIABLE))
(single-slot name
(type STRING)
(cardinality 1 1)))
([Locations_00427] of City
(is-Part-Of [WA])
(name "Washington"))
Facetas mais comuns em
sistemas de Frames
• São elas que diferenciam os frames de redes
semânticas!
• Valor default
• Valores permitidos (allowed-values)
• Domínio
– Ex: 1..100
• Cardinalidade máxima e mínima
• Tipo: inteiro, string, booleano, float, símbolo, instância
• Classes permitidas (allowed-classes): válida apenas
para slots do tipo instância
Frames x Objetos procedimentais
[Farquhar 97]
• Semelhança apenas aparente
• Frames modelam aspectos de um domínio real
• Objetos e suas classes visam modelar estruturas de
dados e reusar código
• Às vezes frames e objetos se parecem
• Às vezes objetos violam o engajamento ontológico
Class circulo
altura}
{int x,y; int
Class elipse extends circulo
{int largura}
Frames x Objetos procedimentais
(cont.)
• Também não é necessária em frames a inclusão de
detalhes de implementação, como tamanho de
strings, etc
• Frames não possuem métodos nem information
hiding, desnecessária para a declaratividade
• Objetos não possuem facetas
• Frames têm sua parte procedimental
– Daemons: procedimentos executados quando um valor
é lido, incluído ou modificado num slot
Herança
• Forma usual de poupar
redescrever cada objeto
– Na herança as relações são
transitivas
• Redes de Herança
– Em árvore
– Em reticulados
• Herança estrita
– Uma só classe é herdada
– Em árvore (vide ao lado)
– Tudo o que é alcançável a
partir de um nó é herdado
Herança Múltipla
• Representa “IS-NOT”
• Pode haver conflitos...
Herança mutável
• Como em frames
• Lemos que Clyde é um
elefante mas não é cinza
• Porém a rede pode ser
ambígüa ...
• Nixon é pacifista ou não??
• Como decidir?
isa
pacificist
Quaker
is-not
Republican
isa Nixon
isa
Heurística do menor caminho
• Para decidir a polaridade (positiva ou negativa)
• Alguns argumentos são tomados de antemão (preventivos)
• Os que não são preventivos, são admissíveis
Problemas com herança mutável
• Redundância
– Nó q
– Pior, Clyde agora é cinza!
• Mesmo usando o menor
caminho...
• Se colocarmos 2 arcos no
lado esquerdo, a conclusão
muda...
Formalizando redes de herança
• Uma rede de herança G={V,N} é um DAG (grafo
acíclico direcionado) com arcos positivos (a.x) e
negativos (a.¬x)
– V = conjunto de vértices e E = conjunto de arcos
• Um caminho positivo só tem arcos positivos
– (a. ... .x), significando que “a é-um x”
• Um caminho negativo só tem arcos positivos
seguidos por um arco negativo
– (a. ... .v.¬x), significando que “a não é-um x”
– O número de positivos aqui pode ser 0
• Uma conclusão continua podendo ser amparda por
vários argumentos (caminhos) diferentes...
Amparo e admissibilidade
• Então quais argumentos devem prevalecer??
• G ampara um caminho a.s1. ... .sn.¬x se o conjunto de
arcos está em N e o caminho é admissível
• A hierarquia ampara a conclusão que a é-um x (ou a não
é-um x) se existir este caminho em G
• Um caminho é admissível se seus arcos são admissíveis
• Um nó v.x (ou v.¬x) é admissível em G sobre a se
– existe um caminho positivo a. ... .v em N
– cada arco deste caminho é admissível
– não há arcos redundantes nem preventivos no caminho
Arcos preventivos e redundantes
• Um arco y sobre um caminho a. ... .y. ... .v previne o arco v.x
sobre a se y.¬x pertence a N
• Um arco b.w (ou b.¬w) é redundante em G sobre a se há um
caminho positivo admissível e nao há um caminho negativo
admissível no meio (q sobre BlueWhale, na figura)
Extensões e extensões crédulas
• Extensão = conjunto de fatos tomados por verdade numa rede
• G é a-conectada sse para todo nó x (ou ¬x), há um caminho
positvo entre a e v
• G é ambígüa sobre a se existem os caminhos a. ... .x e a. ... .¬x
• Uma extensão crédula de G sobre a é a hierarquia não-ambígüa
a-conectada de maior tamanho de G sobre a (1 e 2)
Extensões preponderantes
• Como escolher entre as 2 extensões?
– Usando a admissibilidade
• Se X e Y são extensões crédulas de G sobre a
• X prepondera sobre Y sse possui arcos v e x em que
– X e Y possuem os mesmos arcos que precedem v
– Existe um arco v.x (ou v.¬x) inadmissível em Y mas não em X
Tipos de raciocínio de subsunção
• Raciocínio crédulo: escolhe a extensão
preponderante, talvez aleatoriamente, e aceita
todas as conclusões derivadas dela
• Raciocínio cético: aceita as conclusões derivadas
das extensões preponderantes
• Raciocínio cético ideal: raciocínio cético em que
as conclusões devem ser amparadas por caminhos
distintos