CIn- UFPE

1

Engenharia do Conhecimento

Conceitos básicos

Etapas de desenvolvimento de Sistemas Baseados em Conhecimento

Aquisição de Conhecimento

Exemplo de construção de base de conhecimento

Ontologias e reuso de conhecimento

Metodologias de aquisição de conhecimento e de construção de ontologias

CIn- UFPE

2

Desenvolver software inteligente

Projeto:• Modelar tarefa em termos de ambiente, percepções, ações,

objetivos e utilidade• Identificar o tipo (complexidade) de ambiente• Identificar a arquitetura de agente adequada ao ambiente e

tarefa

Implementação• Escolher um formalismo de representação do conhecimento• Implementar base de conhecimento do gerador e o simulador

de ambientes• Implementar base de conhecimento de cada componente do

agente (vários tipos de conhecimento)• Testar o desempenho com diferentes instâncias do ambiente

CIn- UFPE

3

Engenharia do Conhecimento

Estuda como construir Sistemas Baseados em Conhecimento (SBC)• Base de Conhecimento• Máquina de Inferência

Engenheiro de conhecimento• Guia a Aquisição do conhecimento sobre o domínio

escolhido e determina quais conceitos são importantes • Cria a Base de Conhecimento

– representações dos conceitos (fatos e regras) em alguma linguagem de Representação do Conhecimento

• É responsável pela Implementação e pelo Refinamento do SBC

CIn- UFPE

4Engenharia do Conhecimento:Etapas de Construção dos SBC

Nível de Conhecimento

Nível Lógico

Nível de Implementação

BC

AQUISIÇÃO

FORMALIZAÇÃO

IMPLEMENTAÇÃO

REFINAMENTO

linguagem natural

linguagem de representação deconhecimento

linguagens de programação

CIn- UFPE

5Engenharia do Conhecimento:Etapas de Construção dos SBC

Vimos um pouco de• Implementação: Regras de produção e Prolog• Formalização: Lógica de Primeira Ordem

Resta-nos ver então as fases de • Aquisição e Organização do conhecimento do domínio

escolhido

CIn- UFPE

6

Aquisição de Conhecimento

Aquisição/Explicitação de conhecimento• Espécie de Engenharia de Requisitos mais complexa

Principais fases da Aquisição:• identificar características do problema• isolar os conceitos principais e suas relações (ontologia)• identificar inferências sobre estes conceitos

Conhecimento pode originar-se de várias fontes: • Entrevistas com especialistas, livros e documentos,

filmes, etc.

CIn- UFPE

7Aquisição: Gargalo na construção de SBCs

Dificuldade de introspecção • O especialista quase nunca está ciente de como usa o

conhecimento e tem dificuldade de verbalizar sob pressão• Algumas soluções são intuitivas ou “compiladas”.

Uso de vocabulário próprio (jargão)

O conhecimento expresso pode ser irrelevante• quantidades enormes de informações supérfluas são

coletadas, para em seguida serem organizadas.

O conhecimento expresso pode ser incompleto, incorreto ou inconsistente

Métodos de aquisição - 3 categorias: • Manual, Semi-automático e Automático

CIn- UFPE

8

Aquisição Manual

Entrevistas • estruturadas ou não estruturadas

Tracking methods • Observação e análise do domínio, leitura de documentos, etc.

especialista

Base de conhecimento

Engenheiro de conhecimento

documentação

codificação

explicitação

CIn- UFPE

9

Aquisição Semi-automática

Ajuda ao engenheiro de conhecimento (editores, documentadores, etc.)

Ajuda ao especialista (grid repertory analysis)

especialista Ferramentas interativas de entrevista

Base de conhecimento

Engenheiro de conhecimento

CIn- UFPE

10

Aquisição Automática

Aprendizagem de Máquina (Machine Learning)

• Algoritmos de aprendizagem automática “induzem”as regras a partir de exemplos do domínio.

• Aqui não há aquisição por parte do Engenheiro de Conhecimento.

Casos e exemplos Indução automática Regras

CIn- UFPE

11

Construindo Bases de Conhecimento

Toda BC tem dois “consumidores”:• usuários• procedimentos de inferência

Uma BC deve:• ser clara e correta • representar apenas objetos e relações relevantes• idealmente, ser codificada separada do procedimento

de inferência (modularidade, reusabilidade)• melhorar a eficiência do processo de inferência

O processo de inferência deve fornecer a mesma resposta, independente de como a base foi codificada

CIn- UFPE

12

Engenharia de Conhecimento

1) Decida sobre o que falar

2) Escolha o vocabulário de predicados, funções e constantes (Ontologia do Domínio)

3) Codifique o conhecimento genérico sobre o domínio (axiomas) x,y,z Americano(x) Arma(y) Nação(z) Hostil(z) Vende(x,z,y)

Criminoso(x)

4) Codifique uma descrição de uma instância específica do problema Nação(Cuba), Nação(USA)

5) Proponha questões para o procedimento de inferência e obtenha respostasWest é criminoso?

CIn- UFPE

13

Um Exemplo: Circuitos Digitais

Objetivo:• determinar se o circuito está de acordo com sua

especificação (o circuito acima é um somador)• responder a perguntas sobre o valor da corrente em

qualquer ponto do circuito

CIn- UFPE

14

Decida sobre o que falar

Para alcançar o objetivo, é relevante falar sobre• circuitos, terminais, sinais nos terminais, conexões entre

terminais

Para determinar quais serão esses sinais, precisamos saber sobre:• portas e tipos de portas: AND, OR, XOR e NOT

Não é relevante falar sobre:• fios, caminhos dos fios, cor e tamanho dos fios, etc.

CIn- UFPE

15

Decida qual vocabulário usar

Nomear os objetos e relações do domínio com funções, predicados e constantes• constantes

– distinguir as portas : X1, X2...– distinguir os tipos de porta: AND, OR, XOR...

• funções e predicados– tipo de uma porta:

Tipo(X1) = XOR, Tipo(X1, XOR), XOR(X1)

– indicar entradas e saídas:Out(1, X1), In(1, X2)

– indicar conectividade entre portas:Conectado(Out(1, X1), In(1, X2))

CIn- UFPE

16

Codifique regras genéricas

(1) (1) Dois terminais conectados têm o mesmo sinal:t1, t2 Conectado(t1, t2) Sinal(t1) = Sinal(t2)

(2) O sinal de um terminal é On ou Off (nunca ambos) t Sinal(t) = On Sinal(t) = Off, On Off

(3) Conectado é um predicado comutativo t1,t 2 Conectado(t1, t2) Conectado(t2, t1)

(4) Uma porta OR está On sse qualquer das suas entradas está On:

g Tipo(g) = OR Sinal(Out(1,g)) = On n Sinal(In(n,g))=On

(5) etc...

CIn- UFPE

17

Codifique a instância específica

Portas:Tipo(X1) = XOR Tipo(X2) = XORTipo(A1) = AND Tipo(A2) = ANDTipo(O1) = OR

Conexões:Conectado(Out(1,X1),In(1,X2))Conectado(Out(1,X1),In(2,A2))Conectado(Out(1,A2),In(1,O1)) . . .

CIn- UFPE

18

Proponha questões ao Procedimento de Inferência

Que entradas causam Out(1,C1) = Off e Out(2, C1) = On?i1, i2, i3 Sinal(In(1,C1)) = i1 Sinal(In(2,C1)) = i2 Sinal(In(3,C1)) = i3 Sinal(Out(1,C1)) = Off Sinal(Out(2,C1) = On

Resposta:(i1 = On i2 = On i3 = Off) (i1 = On i2 = Off i3 = On) (i1 = Off i2 = On i3 = On)

CIn- UFPE

19

O que é uma ontologia?

Definição: especificação (semi-)formal explícita formal explícita de uma concepção compartilhadaconcepção compartilhada• Concepção: Concepção: modelo das entidades, relações, axiomas e

regras de algum domínio• Formal:Formal:

– processável por máquina– permitindo raciocínio automático– com semântica lógica formal

• Compartilhada:Compartilhada: por uma comunidade, permitindo entendimento

Conceitos de computação relacionados:• Base de conhecimento reutilizável• Esquema de banco de dados

CIn- UFPE

20

Elementos de uma ontologia

Hierarquia de conceitos:• entidades

– cada entidade definida por conjunto de pares atributo-valor– correspondem:

– as classes dos modelos orientado a objetos– as entidades do modelo relacional– aos termos do modelo lógico

– atributos propriedades x atributos relações– preenchidos por valores atômicas (tipos primitivos) x por outros

conceitos– Status epistemológico do valor

– Exatamente conhecida, default, probabilista• relações

– sem hierarquia x em hierarquia paralela a hierarquia de entidades

– correspondem:– associações, agregações e atributos dos modelos OO cujos valores

são objetos– as relações do modelo relacional– aos predicados do modelo lógico

CIn- UFPE

21

Elementos de uma ontologia

Restrições:• sobre valores possíveis dos atributos do conceitos• correspondem:

– as assinaturas de classes em modelos OO– as axiomas universalmente quantificados em modelos lógicos– as restrições de integridade nos esquema de BD

Regras dedutivas:• sobre atributos de (conjunto de) conceitos• permitem inferência automática da existência de instâncias

de conceitos a partir da existência de outras instâncias• correspondem:

– as regras dos sistemas especialistas e programação em lógica– aos métodos dos modelos OO– as visões em BD

CIn- UFPE

22

Elementos de uma ontologia

Instâncias de conceitos:• definição de entidade e relações específicos (indivíduos)• correspondem:

– aos fatos de sistemas especialistas e programação em lógica– aos objetos dos modelos OO– aos dados dos BD

Estratégias de resolução de problemas (PSM)• Métodos abstratos para resolver determinadas classes de

problemas• correspondem:

– abstrações de rotinas de máquina de inferência– design patterns para raciocínio automático– meta-dados descrevendo classes de procedimentos– ex, generate and test,

CIn- UFPE

23Exemplo de Estratégia de Resolução de Problema

Estratégia de classificação heurística

observações soluções

abstrair refinar

abstrações deobservações

abstrações desoluções

casamentoheurístico

CIn- UFPE

24Serviços suportados por uma ontologia

Consultas e manipulação:• correspondem:

– métodos de acesso a valor e de reflexão em linguagens OO– consultas de interrogação e manipulação em BD– ask, tell e retract das bases de conhecimento

• sobre conceitos:– Quais são as entidades E relacionadas a entidade e0 via

relações r1, r2?– Quais são as relações R mais gerais que r1?– Definição d de entidade E é consistente com o resto da

ontologia?• sobre instâncias

– um indivíduo I com propriedades P1, ..., Pn é instância de quais conceitos?

Raciocínio automático• geralmente dedutivo

CIn- UFPE

25Origem e motivação para ontologias

Gerenciamentodo Conhecimentoem Organizações

desde 90

Integraçãode Dadosdesde 95

SistemasMulti-agentes

desde 95

Recuperaçãode Informação

na Webdesde 00

PsicologiaCognitivadesde 60

Lingüísticadesde 60

SistemasEspecialistas

desde 80

Processamentode Linguagem

Naturaldesde 80

OntologiasFilosofia

desde 350 A.C.

Engenhariade Software:

requisitos e reusodesde 90

CIn- UFPE

26

Tipologia das ontologias

Especialista:Especialista: modela um domínio particular restrito

Geral:Geral: • modela o conhecimento de senso comum compartilhado por

todos os seres humanos• parte de mais alto nível, reutilizável em vários domínios

Conceitual:Conceitual: fundamentada na capacidade de raciocinar

Lingüística:Lingüística: fundamenta no vocabulário de uma(s) língua(s)

De meta-dados:De meta-dados: “especializada” na descrição de recursos on-line, no entanto sobre qualquer domínio

De tarefas e métodos:De tarefas e métodos: modela procedimentos e comportamentos abstratos no lugar de entidades ou relações

CIn- UFPE

27Sub-problemas de modelagem de uma ontologia geral

Categorias e conjuntos

Medidas

Objetos compostos

Tempo

Espaço

Mudanças

Eventos e processos

Objetos físicos

Substâncias

Objetos mentais e crênças

CIn- UFPE

28Anything

AbstractObjectsEvents

Sets Numbers RepresentationalObjects

Categories

Sentences Measurements

Intervals PlacesPhysicalObjects Processes

MomentsThings Stuff

Animals Agents

Humans

Solid Liquid Gas

CIn- UFPE

29

Ontologias Genéricas: Categorias

Também chamadas de classes, relações, tipos ...• conjuntos de objetos com propriedades comuns• organiza e simplifica a base de conhecimento.

Exemplos de simplificação:• comprar(Maçã123) x comprar(Maçã) - classe-instância• Todo mamífero bebe leite - herança

Taxonomia: • tipo particular de ontologia:

– relações hierárquicas entre classe e sub-classes em forma de árvores

• propriedades discriminantes– ex. biologia sistemática

CIn- UFPE

30

Relações entre Categorias

Disjunção: não há interseção entre as categorias s Disjunção(s)

(c1,c2 c1 s c2 s c1 c2 c1 c2 = ) ex. Disjunção({Animais, Vegetais})

Decomposição exaustivas,c DecomposiçãoExaustiva(s,c) (i. i c c2 c2 s i c2)

ex. DecomposiçãoExaustiva({Americano, Canadense, Mexicano}, Norte-Americano)

Partição: decomposição exaustiva disjuntas,c Partição(s,c) Disjunção(s)

DecomposiçãoExaustiva(s,c)ex.. Partição(({macho, fêmea}), animal)

CIn- UFPE

31Ontologias Genéricas: também podem representar

Medidas• Valores atribuídos às propriedades dos objetos do

mundo real: peso, comprimento, altura, etc...

Objetos compostos• formados por partes que também são objetos: relação

“parte-de”.

Mudanças com eventos• Cálculo de eventos: um fato é verdade em um intervalo

de tempo.

CIn- UFPE

32

Medidas

Valores atribuídos aos objetos do mundo real: servem para descrever objetos• ex. peso, comprimento, altura, diâmetro, ...

Medidas quantitativas são fáceis de representar• ex. Tamanho(L1) = Polegadas(1,5) = Centímetros (3,81)

Medidas qualitativas são mais complicadas • ex. beleza de um poema, dificuldade de um exercício• O importante é ordenar

e1, e2 e1 Exercícios e2 Exercícios Elabora(João,e1) Elabora(Pedro,e2) Dificuldade(e1) < Dificuldade(e2)

CIn- UFPE

33Objetos Compostos

Objetos formados por partes que também são objetos• São caracterizados pela estrutura dos objetos que os

compõem• ex. massa de um carro é a soma das massas de suas

partes(carroceria, motor, pneu, ...)

Para representá-los, usamos a relação ParteDe• e.g., ParteDe(motor, Carro), ParteDe(pneu, Carro)

Exemplo:a Bipede(a)

l1, l2, b Perna(l1) Perna(l2) Corpo(b) ParteDe(l1,a) ParteDe(l2,a)ParteDe(b,a)

Ligado(l1,b) Ligado(l2,b) l1 l2 l3 Perna(l3) ParteDe(l3,a) (l3 = l1 l3 = l2)

CIn- UFPE

34

Objetos Compostos

ParteDe também serve para descrever estrutura de eventos: Script ou Schema• ex. comer no restaurante

Quando se está interessado apenas nas características do conjunto: BunchOf• ex. peso do saco de Maçãs • BunchOf(Maçãs) define um objeto composto formado

pelas Maçãs do saco.

CIn- UFPE

35

Representando Mudanças com Eventos Cálculo de situações:

• adequado quando temos um único agente realizando ações discretas e instantâneas (uma ação por situação).

• inadequado quando:– existem vários agentes no mundo.– o mundo pode mudar espontaneamente.– mudanças ocorrem continuamente.

Cálculo de eventos: versão contínua do calculo de situações• No cálculo de situações, um fato é verdade em uma

situação• No cálculo de eventos, uma coisa é verdade num intervalo

de tempo– ex. SubEvento(BatalhaDaNormandia,SegundaGuerraMundial)

SubEvento(SegundaGuerraMundial, SéculoXX)

CIn- UFPE

36Representando Mudanças com Eventos

CIn- UFPE

37

Tempos, Intervalos e Ações

Meet(i,j)i

j

Before(i,j)After(j,i)

ij

During(i,j)i

j

Overlap(i,j)i

j

CIn- UFPE

38

Cálculo de Eventos: Exemplos

Se duas pessoas ficaram noivas, então em algum intervalo no futuro elas irão se casar ou acabar o noivado:

x,y,i0 T(Noivado(x,y),i0)

i1 (Encontra(i0,i1) Depois(i1,i0))

T(Casamento(x,y) FimNoivado(x,y), i1)

A segunda guerra de Canudos ocorreu na Bahia

no século XIXg g Guerras SubEvento(g,SéculoXIX)

ParteDe(Localização(g),Bahia)

CIn- UFPE

39Problemática geral e questões sobre ontologias

Divisão:• como delimito as classes e os atributos?• quais são as distinções que trazem valor agregado?

Escopo: • qual conhecimento incluir?• qual a fronteira do meu domínio?

Granularidade: • até que nível de detalhe modelar os domínio?• problema da ramificação?

Validação: • como avalio a qualidade do modelo?• como escolho entre várias modelagem alternativas (as vezes

propostas por pessoas diferentes)?]• como identificar aspectos importantes que estão faltando?

CIn- UFPE

40Problemática geral e questões sobre ontologias

Muito difícil responder a essas perguntas porque:• Almejados reuso e relativa independência de aplicação

impedem ser guiado completamente pelos requisitos de uma aplicação restrita

• Para ontologias gerais de senso comum pior devido a imensidão em largura e profundidade do conhecimento a modelar

Metodologias ainda incipientes• Methontology: • Sensus: http://www.isi.edu/natural-language/resources/

sensus.html

No entanto, já existe tentativa de padronização: http://suo.ieee.org/

CIn- UFPE

41

CommonKADS

Pesquisa colaborativa na União Européia (+15 anos)

Utiliza fórmulas e ontologias para representar o conhecimento

Utiliza diagramas baseados em UML• Diagrama de classes• Diagrama de estados• Diagrama de atividades

Possui seis modelos• Modelo organizacional• Modelo de tarefas• Modelo de agentes• Modelos de “expertises” • Modelos de comunicação• Modelo de projeto

CIn- UFPE

42

CommonKADS: Modelos

CIn- UFPE

43

CommonKADS Modelo organizacional: Analisar a organização

Modelo de tarefas• Descreve as tarefas a serem executadas• Distribui as mesmas entre os agentes

Modelo de agentes• É o executor do modelo de tarefas• Descreve as capacidades e características dos agentes

Modelo de Comunicação: Troca de mensagens

Modelo de expertise: É o foco da metodologia• 3 sub-níveis

– Conhecimento do domínio: Conceitos, Propriedades, Relações– Conhecimento da inferência– Conhecimento da tarefa

Modelo de projeto de base de conhecimento• Descreve a arquitetura e o projeto