CIn- UFPE

1

Engenharia do Conhecimento

Conceitos básicos

Etapas de desenvolvimento de Sistemas Baseados em Conhecimento

Aquisição de Conhecimento

Ontologias

Exemplos de construção de sistemas BC

CIn- UFPE

2

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

3Engenharia 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

4Engenharia 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

5

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

6Aquisiçã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

7

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

8

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

9

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

10

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

11Organizando o Conhecimento Adqurido:Ontologias

Em Filosofia:• estudo do que existe no mundo

Em IA:• especificação das classes, objetos e relações da realidade

Usadas para: • organizar a BC, separando conceitos (objetos) das regras• aumentar a reusabilidade

Ontologias Genéricas (Gerais)• usadas para representar grandes conjuntos de objetos e

relações• representam senso comum - conhecimento enciclopédico• codificadas usando algum formalismo (ex. LPO)

CIn- UFPE

12Ontologias Genéricas

Maior tempo de construção do que ontologias especializadas, porém mais vantajosas:• unificam diferentes áreas de conhecimento, porque o

raciocínio e a resolução de problemas pode envolver várias áreas simultaneamente.

• aplicáveis a domínios específicos, com a adição de axiomas específicos desse domínio

Senso Comum (ontologia genérica)

Domínios Especializados

Ontologia do Universo

QualquerCoisa

ObjetosAbstratos Eventos

Conjuntos Números ObjetosRepresentativos

Intervalos LugaresObjetosFísicos

Categorias Sentenças Medidas Momentos Coisas Matéria

Tempos Pesos Animais Agentes Sólido Líquido Gasoso

Processos

Humanos

CIn- UFPE

14

Estratégias de Construção de Ontologias

Abordagem Top-Down:• começa definindo os conceitos do senso comum,

depois agrega o conhecimento especializado.

Abordagem Bottom-Up:• começa com N bases especializadas, depois integra os

conceitos mais gerais.

Qualquer ontologia específica pode ser modificada a fim de se tornar mais genérica.

CIn- UFPE

15

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çã3) x comprar(Maçã) - instância x classe• 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

• Representa propriedades discriminantes– ex. biologia sistemática

CIn- UFPE

16

Exemplos de Categorias Um objeto é membro de uma categoria:

Maçã3 Maçãs

Uma categoria pode ser subclasse de outra categoria:

Maçãs Frutas

Todos os membros de uma categoria têm alguma propriedade em comum:

x. x Maçãs Vermelho(x) Arredondado(x)

Membros de uma categoria podem ser reconhecidos por algumas propriedades:

x. Vermelho(Interior(x)) Verde(Exterior(x)) x Melões x Melancias

CIn- UFPE

17

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

18Ontologias 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

19

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

20Objetos 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

21

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

22

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

23

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

24

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

25

Uma vez concluída uma versão preliminar de aquisição...

é só formalizar e implementar!

CIn- UFPE

26Engenharia 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

27

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

28

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

29

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

30

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

31

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

32

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

33

Ferramentas para Implementação de SBC

Três opções:• Shells - é a mais utilizada

– Expert Sintta, OPS, KAS, ...• Elementos “embutíveis”

– regras + objetos (CLIPS, JESS, NeOpus, JEOPS, etc.)• Linguagens de programação de alto nível

– Prolog, Lisp. OOP

Critérios de escolha• Facilidade de uso • Flexibilidade• Interface com sistema • Desempenho• Portabilidade

CIn- UFPE

34

Sistemas Especialistas

Definições

Histórico

Sistemas Especialistas de Segunda geração

Áreas de Aplicação e Classes de tarefas

CIn- UFPE

351960s: General-purpose Problem Solver (GPSs)

Motivação: • leis do pensamento + máquinas poderosas

Funcionamento: planejamento + sub-goaling

– ex. estou com fome => comer => pedir pizza => telefonar => ir para a sala => sair do quarto...

O Logic Theorist deu certo mas.... em geral, GPSs não funcionam• fraca representação de conhecimento• humanos são bons só em domínios restritos

Solução => Sistemas Especialistas!!!

CIn- UFPE

36

Sistemas Especialistas (SEs) Definição

• Um tipo de Sistema Baseado em Conhecimento (knowledge-based system)

• Sistemas que empregam o conhecimento humano para resolver problemas que requererem a presença de um especialista

• Área de aplicação de mais sucesso da IA

Utilidade• capacitar não-especialistas• servir de assistente a especialistas• servir de repositório de conhecimento “valioso” para a

empresa• etc.

CIn- UFPE

37

1960s-1970s: Primeiros Sistemas Especialistas

DENDRAL • Inferir estrutura molecular de componentes

desconhecidos dadas a massa espectral e a resposta nuclear magnética

• Conhecimento especializado poda a busca por possíveis estruturas moleculares

• Fez sucesso: publicações científicas• Representação procedimental de conhecimento

CIn- UFPE

38

1960s-1970s: Primeiros SEs MYCIN

• Diagnosticar rapidamente meningite e outras infecções bacterianas, e prescrever tratamento

• Representação de conhecimento baseada em regras probabilísticas (em torno de 500)

• Fez sucesso: acima de 90% de acerto• introduziu explicação e boa interface com usuário

Exemplo de regraifthe infection is meningitis and

the type of infection is bacterial andthe patient has undergone surgery andthe patient has under gone neurosurgery andthe neurosurgery-time was < 2 months ago andthe patient got a ventricular-urethral-shunt

then infection = e.coli(.8) or klebsiella(.75)

CIn- UFPE

39

1980: Grande Boom dos SEs Problema da General Electric:

• Aposentadoria de David Smith: engenheiro especialista em falhas de motores elétrico-diesel de locomotivas

• Custo deste tipo de engenheiro

Solução convencional• Treinamento de engenheiros novatos

1980: Construção de CATS-1 (DELTA)• Meses de entrevista, 3 anos p/ primeiro protótipo• Permite diagnostico em poucos minutos• Existe um em cada oficina• Dá treinamento: é amigável e explica decisões

CIn- UFPE

40

1970s & 1980s: Avanços em SBCs

1970s: Esforço para desenvolver melhores (e mais especializadas)• Linguagens de representação de conhecimento• Mecanismos de inferência

Conclusões• O poder de um sistema é derivado do conhecimento

específico que ele possui, e não de esquemas de inferências e formalismo particular que ele emprega

• As linguagens existentes já bastam

CIn- UFPE

41

SEs: Conceitos Básicos Expertise

• conhecimento especializado adquirido por longo treinamento, leitura e experiência

Especialista• Quem possui o conhecimento, experiência, métodos e a

habilidade de aplicá-los para dar conselhos e resolver problemas.

Engenheiro de conhecimento• Guia a aquisição, representação do conhecimento

especializado, bem como a implementação e refinamento do SE.

Engenheiro de Conhecimento

Ferramentas,Linguagens

SistemaEspecialista

Construtor deFerramentas

Construtordo

sistema

Especialista Equipe deSuporte

UsuárioFinal

ConhecimentoDocumentado Adquire

Conhecimento

Testa

Constrói

Constrói

Conecta

Coopera

ForneceSuporte

UsaUsa

Usa

Constrói

Personagens de um SE

CIn- UFPE

43Sistemas Especialistas de Segunda Geração

Abandonaram a hipótese da transferência de conhecimento (i.e., Aquisição)• o especialista valida o modelo computacional proposto

Aquisição guiada por modelos: reuso de ontologias e estruturas de inferência1) Decomposição de tarefas2) Caracterização das (sub)tarefas3) Busca de um modelo em uma biblioteca (ex. KADS -

http://www.commonkads.uva.nl/)modelo = ontologia do domínio + estrutura de inferência

4) entrevista estruturada

CIn- UFPE

44

Defeitos do Equipamento de Áudio

diagnóstico ação

recofigurar consertar

(1) Decomposição de tarefas

Exemplo: Falhas em equipamentos de áudio

Interpretação Inferindo descrições das situações por observações

Predição Inferindo prováveis conseqüência de dadas situações

Diagnóstico Inferência de mal-funcionamento do sistema por observações

Projeto Configurando objetos sob restrição

Planejamento Desenvolvimento de plano(s) para realização de objetivo(s), meta(s)

Monitoração Comparando observações para planos, detectando exceções

ETC…

Categoria Problemas Abordados

(2) Caracterização da tarefa

system’s structure

given(analysis)

modified(transformation)

constructed(synthesis)

solution type

sequence of steps(planning)

structure(design)

solution type

states(predict)

category(identification)

category type

discrepancy(monitoring)

faulty category(diagnosis)

decisionclass

(assessment)model type

correct model(systematic diagnosis)

fault model(heuristic classification or

cover & differentiate)

(3) Hierarquização das categorias de tarefas(biblioteca KADS)

is-acomponent

audiosystem

tapedeck

speakersystem

...

Modelo: Ontologia do domínio de áudio

Prorpiedades dos componentes• deck: function (stop, play, rew, ff, pause)• deck: power (on,off)• amplifier: power (on,off)• amplifier: input-signal (deck, turner, CD, VCR, Aux)• ...

Testes com os componentes• deck-power-switch (preessed, not pressed)• input-selector (deck, turner, ...)

audio system

amplifier tapedeck

speakersystem

...

leftspeaker

rightspeaker

part-of

CIn- UFPE

48

Modelo: Ontologia do domínio de áudio

Causa (regras causais)• deck: power = on and deck: function = play and

cable-connection: deck amplifier = presentCAUSESamplifier: input-signal = deck

• amplifier: input-signal = deck and amplifier: input-selector = deckCAUSESamplifier: output-signal = deck

Indica• deck-power-switch = pressed

INDICATESdeck-power = on

• input-selector = XINDICATES amplifier: input-signal = X

CIn- UFPE

Reclamação

Seleciona

Modelo do sistema

Decompõe

hipótesesObservação

Seleciona

descoberta

Especifica

normaCompara

diferença

Fonte de conhecimento Meta-classe

Modelo: Estrutura de inferência (raciocínio)

entrevistas

CIn- UFPE

50

Classes de Tarefas dos SEs

CIn- UFPE

51

Áreas de Aplicação dos SEs

CIn- UFPE

52

Evolução do mercado de SEs

CIn- UFPE

53

Benefícios e Limitações dos SEs

Pontos positivos:• Criam repositórios de conhecimento • Forneem de treinamento • Aumentam a produtividade e a qualidade• Têm a habilidade de resolver problemas complexos• Apresentam Flexibilidade e modularidade• Operam em ambientes arriscados • Trabalham com informações incompletas ou incertas

Pontos negativos:• Transferência de conhecimento está sujeita a um

grande número de problemas• Avaliação de desempenho difícil• Só trabalham bem em domínios estreitos• Engenheiros de Conhecimento são raros e caros

CIn- UFPE

54

Últimos desenvolvimentos

Aquisição de conhecimento:• SEs de 2ª geração & aprendizagem

Ferramentas de desenvolvimento + OOP

Integração com outros sistemas• ex. banco de dados e sistemas de suporte à decisão

Tratamento de incerteza