Representação de Conhecimento com Formalismos Orientado a

Objetos

Jacques RobinCin-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:

Cadeira-27

Mobília

Cadeira

Preto

Couro

AssentoAna

Pessoa

é-um

Ako

é-um Tem-um

CorDono

Estofamento

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).

Animalfaz comer

Pássaro Ako Comer

Mamífero Ako tem

Comer

Cão Ako

Babalu é-um

pêlos

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

< Nome do Frame> < atributo1 >

< faceta1 >: valor

< atributo2 >

< faceta1 >: valor< faceta2 >: valor< faceta3 >: valor

< atributo3 >

< faceta1 >: valor< faceta2 >: valor< faceta3 >: valor

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.

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

Cômodo Ako: Lugar-coberto

Atributo Default Tipo Se-necessário

Nº de paredesFormato

Altura

Área

Volume

número

número

número

número

símbolo4

retangular

3

Área * Altura

Sala Ako: Cômodo

Atributo Default Tipo

MobiliárioFinalidadeÁrea

lista de símbolossímbolonúmero

convivência25

(sofá,mesa,cadeiras)

Ako

Exemplo: Procedimentos Demons

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)

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)

Lógicas descritivas: serviços de inferência

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 – ConceitosStudent PersonSTUDIESAT Student UniversityStudent =

Person STUDIESAT.UniversityEmployee PersonAFILIATEDTO Employee OrganizationEmployee =

Person AFILIATEDTO.OrganizationAcademicSaff EmployeeSUPERVISES AcademicStaff PhdStudentAcademicSaff =

Employee SUPERVISES.PdhStudentResearcher AcademicStaffPhdStudent Student ResearcherSUPERVISED PhdStudent AcademicStaffPdhStudent =

Student SUPERVISED.AcademicStaff

Abox – InstânciasStudent(thiago)STUDIESAT(thiago,UFPE)

PhdStudent(franklin)STUDIESAT(franklin,UFPE)

Researcher(jacques)SUPERVISED(franklin,jacqu

es)

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

e5e14

en...

AcademicStaff

Research

e1 e2

e5e14

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.

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.