Representação de Conhecimento com
Formalismos Orientado a Objetos
Jacques Robin
Cin-UFPE
Roteiro
Histórico
Redes Semânticas
Frames
Lógicas Descritivas
Formalismos híbridos regras + objetos
Formalismos de representação do
conhecimento orientado a objetos
(FRCOO) : histórico
 Redes semânticas aparecem no fim dos anos 70
 Primeiro formalismo de IA estruturando o
conhecimento em uma hierarquia de conceitos (classes)
e instâncias (individuais, objetos) com herança de
propriedades
 Contribui a gênese das linguagens de programação e
engenharia de software orientada a objeto
 Em retrospecto, os diagramas mais utilizados de UML
(classes, objetos) definem uma redes semântica
 Vinham com interpretadores o que os tornavam
linguagem de implementação e não apenas de
especificação
FRCOO: histórico (cont.)
Duas limitações principais das redes semânticas:
1. Computacionalmente incompletos para implementar a maioria
dos sistemas inteligentes
2. Sem semântica declarativa formal bem-definida (atalho entre
nível do conhecimento e nível da implementação sem lógica)
 Frames são sucessores das redes semânticas visando a
superar a 1a limitação
 Lógicas descritivas são sucessores das redes
semânticas visando a superar a 2a limitação
 Atualmente:
 Redes semânticas caíram em desuso para sua função inicial de
formalismo de implementação de BC
 Redes semânticas mais usadas do nunca do que hoje em nova
função de especificação de BC e de software em geral (UML)!
 Emergência proeminente dos FRC híbridos regras + objetos
Redes semânticas
Uma rede semântica é uma representação na qual
existem nós que representam entidades e links (predicados)
que representam relacionamentos entre essas entidades;
cada link conecta um nó origem até um nó destino;
normalmente, os nós e links denotam entidades de domínio
específico.
Exemplo:
Pessoa
Mobília
Ako
Cadeira
é-um
Ana
Dono
é-um
Tem-um
Cadeira-27
Cor
Preto
Couro
Estofamento
Assento
Redes Semânticas
Forma mais flexível e intuitiva de representar
conhecimento.
Suportam herança de propriedades.
Relações
Ako (a-kind-of): relações entre classes
é-um (is-a): relações entre classes e instâncias
uma entidade pertence a uma classe mais alta ou uma categoria de
objetos.
tem-um (has-a): identifica características ou atributos das
entidades
parte-de (part-of): identifica características ou atributos
das entidades
variados: identifica características gerais
Sistemas de Redes Semânticas
Base de conhecimento
nós e links da rede.
Máquina de inferência
busca e casamento de padrões
a busca se dá para frente e para trás através dos links.
A busca pode ser usada de várias maneiras para se
extrair informações
como uma ferramenta explicativa;
para explorar exaustivamente um tópico;
para encontrar o relacionamento entre dois objetos.
Redes semânticas: vantagens
Representação visual fácil de entender.
Flexibilidade na manipulação de nós e links
adição, exclusão, modificação
Economia
herança via relações “é-um” e “ako”.
Capta “senso-comum”
semelhante ao armazenamento de informações no cérebro.
Redes semânticas: limitações
Busca em redes semânticas grandes pode ser muito
ineficiente.
Não há homogeneidade na definição de nós e links.
Hereditariedade pode causar dificuldades no
tratamento de exceções.
Pode haver conflito entre características herdadas.
É difícil representar conhecimento procedimental
seqüenciamento e tempo não estão explícitos.
Menos expressiva que a Lógica de Primeira Ordem
não há quantificadores.
Frames
Um frame é identificado por um nome e descreve um
objeto complexo através de um conjunto de atributos
Um Sistema de Frames é um conjunto de frames
organizados hierarquicamente.
São uma evolução das Redes Semânticas:
nós são substituídos por frames
arcos são substituídos por atributos (slots)
procedimentos podem ser anexados a um frame
Frames: atributos (slots)
Frames
Possuem pelo menos dois atributos:
Nome
Ako ou is-a
A fim de melhorar a estruturação (hierarquia), privilegiam
dois tipos de relações:
ako: relação entre classe e sub-classe
is-a: relação entre classe e instância.
Cada atributo
aponta para um outro frame ou para um tipo primitivo, ex.
string;
consiste em um conjunto de facetas (atributos de
atributos).
Exemplo: Classes e Instâncias
Animal
faz comer
Pássaro
Ako
Babalu
é-um
Comer
Mamífero
Ako
tem
Cão
Ako
Comer
pêlos
Facetas
Descrevem conhecimento ou algum procedimento
relativo ao atributo.
Propriedades
Valor: especifica o único valor possível.
Valor default: especifica o valor assumido pelo atributo caso
não haja nenhuma informação a esse respeito.
Tipo: indica o tipo de dado do valor.
Domínio: descreve os valores possíveis para o atributo.
Procedimentos Demons
como os triggers nos bancos de dados
Uma Representação Abstrata
de um Frame
< Nome do Frame>
< atributo1 >
< faceta1 >: valor
< atributo2 >
< atributo3 >
< faceta1 >: valor
< faceta2 >: valor
< faceta3 >: valor
< faceta1 >: valor
< faceta2 >: valor
< faceta3 >: valor
Os frames integram conhecimento declarativo sobre objetos e
eventos e conhecimento procedimental sobre como recuperar
informações ou calcular valores.
Procedimentos Demons
Definição
São procedimentos anexados aos frames, disparados por
consultas ou atualizações.
Podem inferir valores para atributos a partir de valores de
outros atributos especificados anteriormente em qualquer
frame do sistema.
Procedimentos Demons:
when-requested
quando o valor é pedido mas não existe ainda
when-read
quando valor é lido
when-written
quando valor é modificado
Exemplo: Procedimentos Demons
Ako: Lugar-coberto
Cômodo
Atributo
Default
Tipo
Se-necessário
Nº de paredes
4
número
Formato
retangular símbolo
Altura
3
número
Área
número
número
Volume
Área * Altura
Ako
Sala
Ako: Cômodo
Atributo
Mobiliário
Finalidade
Área
Default
(sofá,mesa,cadeiras)
convivência
25
Tipo
lista de símbolos
símbolo
número
Exemplo de Sistema de Frames
Mobília
...
Cadeira
...
Ana é-um:
...
Pessoa
...
verde é-um:
String
...
Ako: Mobília
Cadeira-27
dono:
cor:
tem-um:
é-um: Cadeira
Assento
estofamento:
tamanho: ...
couro é-um:
Herança de Propriedades
Três tipos de informações podem ser de herdadas
valor (= POO)
procedimento (= POO)
valor default
Idéia: herdar das classes superiores
em caso de conflito, vale a informação mais específica
Existem dois tipos de herança:
Herança simples
existe uma única super-classe para cada classe
Herança múltipla
 uma classe pode ter mais de uma super-classe, podendo
herdar propriedades ao longo de diversos caminhos
diferentes (= o caos)
Sistemas de frames: serviços
Reconhecer que uma dada situação pertence a uma
certa categoria (matching)
ex. reconhecimento visual de uma sala de aula
Interpretar a situação e/ou prever o que surgirá em
termos da categoria reconhecida (matching)
ex. pessoa com revolver (revolver arma -> perigo)
Capturar propriedades de senso comum sobre pessoas,
eventos e ações
foi a primeira tentativa de estruturar conhecimento
declarativo sem usar regras.
Deu origem ao que chamamos hoje de Ontologias!
Sistemas de frames: vantagens e
limitação
 Permite capturar conhecimento terminológico e
procedimental
 Computacionalmente completo via os procedimentos
(implementados em uma linguagem hospede, geralmente
funcional, as vezes imperativa)
 Distingue entre vários tipos de conhecimento (exato,
default, declarativo, procedimental, etc.)
 Demons podem ser usados para as funcionalidade de
interface aquisição de conhecimento e explicação de
raciocínio de um shell de sistemas especialistas
Sistemas de frames: limitações
Conhecimento comportamental não declarativo impede
codificação direita por especialista do domínio que não
é programador
Sem semântica formal
Implementação ad-hoc de dedução e adbução,
geralmente ineficientes
 Não existe máquina de inferência indutivas para
aprendizagem
 Não inclui noções de encapsulamento e componentes
das linguagens de programação OO modernas
 Não escaláveis para grande bases de conhecimento
Lógicas Descritivas (LD): filosofia
Usar lógica para definir formalmente semântica de
formalismos de representação de conhecimento OO.
Estudar computabilidade e complexidade das
linguagens e serviços de inferência antes de
implementá-los.
Limitar expressividade para garantir esses serviços
sejam computacionalmente tratáveis.
SPIV invade a IA.
Lógicas descritivas: conceitos chaves
 Formalismos lógicos para representação das informações sobre
classes de indivíduos e suas descrições.
 Subconjunto da lógica de primeira ordem, trata de:
 Relações unárias (conceitos)
Ex, Student = {x | Student(x)}
 Relações binárias (papéis);
Ex, SUPERVISED = {(x,y) | SUPERVISED(x,y) }
 Possui também:
 Construtores sobre os conceitos (,, outros)
Ex, PdhStudent = Student  SUPERVISED.AcademicStaff
= { x | Student(x)  y.SUPERVISED(x,y)  AcademicStaff(y) }
 Indivíduos, e instâncias dos conceitos
franklin, jacques, thiago;
Student(thiago), PhdStudent(franklin), Researcher(jacques)
 Trade-offs entre expressividade e complexidade computacional
conhecidos.
Lógicas
descritivas:
construtores
Lógicas descritivas: semântica formal
Baseada na teoria dos conjuntos;
Semântica definida por uma interpretação (I,I);
Conjunto não-vazio, domínio I;
Função de interpretação I que mapeia:
Todo conceito em um subconjunto de I;
Todo papel em um subconjunto de I x I;
Unicidade de nome
Se a  b então aI  bI
Um modelo para C é uma interpretação onde CI é nãovazio
Um conceito é satisfiable se ele possui pelo menos um modelo.
LD: semântica dos construtores
Lógicas descritivas:
bases de conhecimento
KB = Tbox + Abox
Tbox (Terminological part) = Descrições
Exemplos:
Student = Person   STUDIESAT.University
PhdStudent  Student  Researcher
Abox (Assertional part) = Instâncias
Exemplos:
PdhStudent (franklin)
STUDIESAT (franklin,UFPE)
Lógicas descritivas:
serviços de inferência
Dada uma base de conhecimento  = <Tbox,Abox>, dois
conceitos C e D, e um indivíduo a, chamamos:
Satisfiability:  |= C  
Verificar se há um modelo I de  tal que CI  
Exemplo: Student  Person ?
Subsumption:  |= C  D
Verificar se C é subsumed por D. CI  DI em todo modelo I de 
Exemplo: Employee  Person  Student ?
Consistência:  |=
Verificar se a própria base tem um modelo.
Exemplo: Student = Person ?
Classificação de instância:  |= C(a)
Verificar se uma dada asserção é válida.
Exemplo: Person(franklin)
LD: raciocínio na Tbox
 Tbox:
 Syntax-based reasoning: Structural Comparison
 Semantic-based reasoning: Constraint Systems
 Expressividade Vs Complexidade
 Expressividade é diretamente proporcional à complexidade computacional.
LD para o exemplo  = <Tbox,Abox>
Tbox – Conceitos
Student  Person
STUDIESAT  Student  University
Student =
Person   STUDIESAT.University
Employee  Person
AFILIATEDTO  Employee  Organization
Employee =
Person   AFILIATEDTO.Organization
AcademicSaff  Employee
SUPERVISES  AcademicStaff  PhdStudent
AcademicSaff =
Employee   SUPERVISES.PdhStudent
Researcher  AcademicStaff
PhdStudent  Student  Researcher
SUPERVISED  PhdStudent  AcademicStaff
PdhStudent =
Student   SUPERVISED.AcademicStaff
Abox – Instâncias
Student(thiago)
STUDIESAT(thiago,UFPE)
PhdStudent(franklin)
STUDIESAT(franklin,UFPE)
Researcher(jacques)
SUPERVISED(franklin,jacques)
AFILIATEDTO(jacques,UFPE)
LD: exemplos de serviços de raciocínio
 |= C  
  |= Student  Person   ?
 Equivalente a:
 Student  Person =  ?
 Se já temos x Student(x)  Person(x)
 x Student(x)  Person(x)  x Person(x)  Person(x) que é impossível.
 Logo o conjunto formado pela conjunção Student  Person é . Não satisfiable.
Person
e1
e2
Student
e5
...
en
e14
LD: exemplos de serviços de raciocínio
 |= C  D
 |= AcademicStaff  Researcher ?
AcademicStaff  Researcher
Equivalente a: x Researcher(x)  AcademicStaff(x)
O conjunto de indivíduos do tipo Researcher está
contido no do conjunto de AcademicStaff.
AcademicStaff
e1
e2
Research
e5
...
en
e14
LD: exemplos de serviços de raciocínio
 |= 
 A base contém asserções/definições contraditórias?
 Adicionando Person(franklin) mantém a base consistente ?
Raciocinando com as instâncias da Abox e conceitos da
Tbox, temos:
 PhdStudent(franklin)
: Abox
 Student(franklin) : Regra PhdStudent  Student da Tbox
 Person(franklin)
: Regra Person  Student da Tbox
 Ao término das expansões da Abox temos:
 Abox = Abox0 , Student(franklin), Person(franklin)
 Ao adicionarmos Person(franklin) teríamos uma KB com contradições,

isto é, inconsistente onde franklin é Student e franklin não é Student.
Conclusão:
 Uma KB que possua a Tbox anterior, não pode ter Abox com asserções do tipo
PhdStudent(franklin) e Person(franklin) pois se torna uma base
inconsistente.
LD: exemplos de serviços de raciocínio
 |= C(a)
 |= Person(franklin) ?
Raciocínio sobre a hierarquia definida na Tbox, gera:
Student(franklin)
Person(franklin)
Assim, Person(franklin) pode ser deduzido como uma
instância válida dentro da KB.