RepCon-OO

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

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:
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
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 
Os frames integram conhecimento declarativo sobre objetos e eventos e conhecimento procedimental sobre como recuperar informações ou calcular valores.
 
< Nome do Frame>
< atributo1 >
< faceta1 >: valor
< atributo2 >
< faceta1 >: valor
< faceta2 >: valor
< faceta3 >: valor
< atributo3 >
< faceta1 >: valor
< faceta2 >: valor
< faceta3 >: valor
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 
Cômodo
Ako: Lugar-coberto
Atributo
Default
Tipo
Se-necessário
Nº de paredes
Formato
Altura
Área
Volume
número
número
número
número
símbolo
4
retangular
3
Área * Altura
Sala
Ako: Cômodo
Atributo
Default
Tipo
Mobiliário
Finalidade
Área
lista de símbolos
símbolo
número
convivência
25 
(sofá,mesa,cadeiras)
Ako
Exemplo de Sistema de Frames
Mobília
...
Cadeira
...
Ako: Mobília
Cadeira-27
dono:
cor:
tem-um:
é-um: Cadeira
Ana
...
é-um:
String
...
Assento
estofamento:
tamanho: ...
Pessoa
...
verde
é-um:
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ão-vazio
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
Student
e1
e2
e5
e14
en
...
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
Research
e1
e2
e5
e14
en
...
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.
Motivação e objetivos da lógica descritiva. 
Dizer o que é SPIV.
	S- Specify;
	P- Prove;
	I- Implement;
	V- Verify
Explicar os construtures usados nos exemplos.
Apresentação opcional
Apresentação Opcional.
Mostrar semântica dos exemplos;
Convenção de nomes AL[c][u][r]...;
Equivalências ALEU = AUCN.