Semana de Cursos e Palestras da Computação (SECCOM) 04 a 08 de outubro de 2004 CTC-UFSC Representação de Conhecimento e Ontologias Guilherme Bittencourt

Semana de Cursos e Palestras da Computação (SECCOM)

04 a 08 de outubro de 2004CTC-UFSC

Representação de Conhecimento e Ontologias

Guilherme Bittencourt

Departamento de Automação e SistemasUniversidade Federal de Santa Catarina

Brasil

SECCOM - 07/10/ 2004 - [email protected] - www.das.ufsc.br/~gb

2

Sumário

• Computação• Representação de conhecimento• Ontologias

– Ferramentas– Construção– Aplicações

• Conclusões

Computação


4

Computação

F = m a

Modelo

Predição

« Nous devons […] envisager l’état présent de l’univers comme l’effet de son état antérieur et comme la cause de celui qui va suivre. Une intelligence qui pour un instant donné connaîtrait toutes les forces dont la nature est animée et la situation respective des êtres qui la composent, si d’ailleurs elle était assez vaste pour soumettre ces données à l’analyse, embrasserait dans la même formule les mouvements des plus grands corps de l’univers et ceux du plus léger atome : rien ne serait incertain pour elle, et l’avenir, comme le passé, serait présent à ses yeux ». Pierre Simon Laplace (1825)

Computação

• Kurt Gödel (Czech): Aritmética (e portanto toda a Matemática) é indicidível, 1931

• Lambda Calculus: Alonso Church, Princeton, United States, Abril 1936.

• Turing Machine: Alan Mathison Turing (1912-1954), King's College, England, Agosto 1936.

• Sistemas de Produção: Emil Post (Polish), Cidade College, United States, Outubro 1936.


6

Computação

• II Guerra Mundial

• Criptografia

• Balística

• Bomba atômica


7

Inteligência Artificial

"I propose to consider the question, 'Can machines think?' This should beginwith definitions of the meaning of the terms'machine' e 'think' ".

A.M. Turing, Computing Machinery e Intelligence, 1950.


8

Além da Computação

• Rosa

• r (uma constante)

conjunto

Linguagem natural:

Lógica:

What´s in a name? that which we call a rose by any other name would smell as sweet.Romeo e Juliet, Act 2, Scene 2, William Shakespeare

Representação de conhecimento


10

Representação de Conhecimento

• Sistemas computacionais e formalismos matemáticos para expressar e manipular conhecimento declarativo de forma tratável e computacionalmente eficiente

• Um formalismo deve prover:– Linguagem de representação de conhecimento– Mecanismo de inferência– Estratégias de controle da inferência


11

Representação de conhecimento

• Lógica: base matemática para todos os mecanismos de representação.– Teoria dos modelos– Teoria da prova– Implementável computacionalmente


12

Lógica

• Kurt Gödel e Jacques Herbrand (1930): existem sistemas lógicos nos quais toda fórmula verdadeira pode ser provada (completude)

• Alfred Tarski (1934): definição formal da semântica da lógica

• Alonzo Church, Alan Turing, Post (1936): indecidibilidade


13

Semântica de Tarski

Linguagem natural:

Cochabamba é uma Cidade.

Lógica:

Cidade(cochabamba)

Coisas

Cidades


14

Exemplo

Bolívia

América do Sul


15

Exemplo

Regiao(planicie)Regiao(vales)Regiao(altiplano)

Cidade(Cobija)Cidade(Trinidad)Cidade(La_Paz)Cidade(Oruro)Cidade(Santa_Cruz)Cidade(Sucre)Cidade(Potosi)Cidade(Tarija)Cidade(Cochabamba)

Clima(planicie,tropical)Clima(vales,temperado)Clima(altiplano,frio)

Altitude(Cobija,240)Altitude(Trinidad,250)Altitude(La_Paz,3200)Altitude(Oruro,4000)Altitude(Santa_Cruz,200)Altitude(Sucre,2800)Altitude(Potosi,3000)Altitude(Tarija,2500)Altitude(Cochabamba,2700)

Local(Cobija,planicie)Local(Trinidad,planicie)Local(La_Paz,altiplano)Local(Oruro,altiplano)Local(Santa_Cruz,planicie)Local(Sucre,vales)Local(Potosi,altiplano)Local(Tarija,vales)Local(Cochabamba,vales)

Voltagem(Cobija,220)Voltagem(Trinidad,220)Voltagem(La_Paz,110)Voltagem(Oruro,220)Voltagem(Santa_Cruz,220)Voltagem(Sucre,220)Voltagem(Potosi,220)Voltagem(Tarija,220)Voltagem(Cochabamba,220)

Representação lógica:


16

Redes semânticas

• Propostas por Quillian (1968) como modelo da memória associativa humana.

• Nodos (objetos, conceitos) conectados por arcos (relações binárias).

• Arcos: is a, is part (herança), outros (propriedades)

• Aplicações: processamento de linguagem natural


17

Exemplo

220

Rede semântica:Cidade

cochabamba

Regiao

Clima

Local

Altitude

Voltagem

is a

temperado

2700

vales

is a


18

Frames

• Marvin Minsky (A framework to represent knowledge, 1975).

• Frame (objetos ou conceitos)• Slots (nomes de propriedades) com valores• Herança (só arcos is a e is part)• Valores default e facetas• Ligação procedural


19

Exemplo

Frames:

is part

is a

RegiaoVoltagem: 220

Planicie

Clima: tropical

Vales

Clima: temperado

Altiplano

Clima: frio

Cochabamba

Altitude: 2700

Tarija

Altitude: 2500

Sucre

Altitude: 2800

Oruro

Altitude: 4000

La Paz

Altitude: 3200

Voltagem:110

Santa Cruz

Altitude: 200

Trinidad

Altitude: 250

Cobicha

Altitude: 240

Potosi

Altitude: 3000

is part

is a

is part is part


20

Lógica de descrição• Descendente das linguagens terminológicas (KL-ONE) e

das redes semânticas.• Baseada em conceitos (classes) e papéis

– conceitos (classes): conjuntos de objetos– papéis: relações binárias entre objetos

• Construtores permitem a definição de conceitos e papéis complexos a partir de primitivos

• Fragmento decidível da lógica de primeira ordem• Relacionada com a Lógica Modal• Propriedades principais:

– Semântica bem definida– Inferência decidível e (as vezes) tratável


21

Lógica de descrição

Tbox (schema)

(def man (and human male))

(def happy-father (and man (exist has-child female) …)

Abox (data)

(is-a John happy-father)

(has-child John Mary)

Knowledge Base

Sistema

de inferência

Interface


22

Sistemas de Produção• Origiem: Post (1936), regras para a especificação

sintática de transformações em cadeias de caracteres. Método completo de computação.

• Componentes:– Conjunto de regras: pares ordenados (LH, RH), onde LH e

RH são cadeias de caracteres.– Memória de trabalho: cadeia de caracteres– Motor de inferência: para cada regra (LE,LD), se a

seqüência de caracteres LE estiver contida na memória de trabalho, substitui os caracteres LE na memória de trabalho pelos caracteres de LD. O interpretador continua na próxima regra, e ao final volta à primeira, até que não existam mais regras aplicáveis.


23

Sistemas de Produção

1 : _ (blank) +2 : § (new line) +3 : . (point) +4 : ++ +

Regras: Memória de trabalho:Tudo_ _vale_a_pena §Se_a_alma_não_é_pequena.

Tudo_ _vale_a_pena § Se_a_alma_não_é_pequena. 1 Tudo+_vale_a_pena § Se_a_alma_não_é_pequena. 2 Tudo+_vale_a_pena+Se_a_alma_não_é_pequena. 3 Tudo+_vale_a_pena+Se_a_alma_não_é_pequena+ 1 Tudo++vale_a_pena+Se_a_alma_não_é_pequena+ 4 Tudo+vale_a_pena+Se_a_alma_não_é_pequena+ 1 Tudo+vale+a_pena+Se_a_alma_não_é_pequena+ 1 Tudo+vale+a+pena+Se_a_alma_não_é_pequena+ 1 Tudo+vale+a+pena+Se+a_alma_não_é_pequena+ 1 Tudo+vale+a+pena+Se+a+alma_não_é_pequena+ 1 Tudo+vale+a+pena+Se+a+alma+não_é_pequena+ 1 Tudo+vale+a+pena+Se+a+alma+não+é_pequena+ 1 Tudo+vale+a+pena+Se+a+alma+não+é+pequena+

Execução:


24

História• Clássica (1956-1970)}

– Objetivo: simular a inteligência humana

– Métodos: solucionadores gerais de problemas e lógica

– Limitação: subestimação da complexidade computacional dos problemas

• Romântica (1970-1980)– Objetivo: simular a inteligência

humana em situações pré-determinadas.

– Métodos: formalismos de representação de conhecimento.

– Limitação: subestimação da quantidade de conhecimento necessária.

• Moderna (1980-1990)

– Objetivo: simular o comportamento de um especialista humano ao resolver problemas em um domínio específico.

– Métodos: Sistemas de regras, representação da incerteza.

– Limitação: subestimação da complexidade do problema de aquisição de conhecimento.

• Contemporânea (1990-hoje)

– Objetivo: aplicações reais (Internet)

– Métodos: Ontologias (?)

Ontologias


26

Internet

• Grande volume de informações desestruturadas adequadas apenas ao entendimento humano (as vezes... )

• HTTP e HTML asseguram apenas navegação e apresentação• Solução procedimental: Engenhos de busca

– Análise apenas em nível léxico– Falta de precisão e muitos resultados irrelevantes,

• Principais ausências– Falta de contexto – Falta de semântica na definição das páginas


27

Soluções possíveis para o tratamento de informação na Web

• Dotar os sistemas de inteligência– Agentes inteligentes– Manipulação cooperativa de informação: distribuição,

cooperação e comunicação sobre a semântica das páginas– Restrição de domínios

• Dotar a Internet de inteligência: a Web Semântica– Linguagens e padrões para definir páginas com uma semântica

clara e definida formalmente– Os agentes poderão raciocinar e “conversar” no contexto desta

semântica

=> Ontologias desempenham um papel fundamental em ambas as soluções!


28

Motivações de Ontologias

• Permitir reuso entre formalismos de representação diferentes

• Servir como vocabulário compartilhado de comunicação entre agentes

• Unidade básica de representação: Frames• Define um domínio, visando maximizar o reuso

destas definições• Idealmente não deve refletir nenhum formalismo


29

Definições de ontologia

• Ontologia: Especificação de uma conceitualização• Hierarquia de conceitos (classes) com suas relações,

restrições, axiomas e terminologia associada

Id Modelo

Xy 777

Agente da Cia. Aérea

Ont. de Meios de Transporte

Trem Avião Barco

Transporte Carreira Caça

Avião

Meu agente

777[é-um 777]

Id Modelo

Xy 777

Agente da Cia. Aérea

Ont. de Meios de Transporte

Trem Avião Barco

Transporte Carreira Caça

Avião

Meu agente

777[é-um 777]


30

Definições de ontologia (cont.)• “Uma ontologia é uma especificação explícita e formal de uma

conceitualização compartilhada” [Studer et al 98]• Especificação explícita: definições declarativas de conceitos,

instâncias, relações, restrições e axiomas• Formal: declarativamente definida, sendo compreensível e

manipulável para agentes e sistemas• Conceitualização: modelo abstrato de uma área de conhecimento ou

de um universo limitado de discurso• Compartilhada: conhecimento consensual, seja uma terminologia

comum da área modelada, ou acordada entre os desenvolvedores dos agentes que se comunicam


31

Ontologias são hierarquias...


32

...mas também relações Ontologias


33

Tipos de Ontologias• Ontologias de Representação: definem as primitivas

de representação - como frames, axiomas, atributos e outros – de forma declarativa.

• Ontologias Gerais (ou de topo): contêm definições abstratas necessárias para a compreensão de aspectos do mundo, como tempo, processos, papéis, espaço, seres, coisas, etc.

• Ontologias centrais ou genéricas de domínio (core ontologies): descrevem ramos de estudo de uma área e seus conceitos mais genéricos e abstratos.

• Ontologias de domínio e de aplicação: tratam de um domínio específico de uma área genérica de conhecimento, como direito tributário, microbiologia, etc.


34

Vantagens das ontologias

• Reuso massivo de conhecimento

– Incorporação de conhecimento é facilitada, inclusive de linguagem natural

• Facilidades de acesso a conhecimento

– Via browser

– Servidores

• Interoperabilidade entre formalismos

– Tradução

– Mapeamento

• Comunicação em nível de conhecimento

Ferramentas para ontologias


36

Knowledge Sharing Effort (KSE)Knowledge Sharing Effort (KSE)

• O KSE produziu inicialmente quatro ferramentas :– Ambiente de edição, manipulação e

acesso de ontologias: Ontolingua

– Tradução: Linguagem KIF

– Comunicação entre agentes: Linguagem KQML

– Conectividade/ Interoperabilidade: OKBC


37

Editor da Ontolingua


38

Tradução na Ontolingua• Tradução intermediária para a interlingua KIF

(Knowledge Interchange Format) – No. de tradutores cai de (n-1)² para 2n

• KIF foi feita para ser usada com a Frame-Ontology

Ontologias“de prateleira”

Ontolingua

LOOMOntol.

“T-box”

EpikitAxiomas

ExpressModeloInform.

PrologRegras backwarchaining”

CLIPSRegrasforward chaining

CORBAIDL

KIFLógica

predic.1ª

ordem

Ontologias“de prateleira”

Ontolingua

LOOMOntol.

“T-box”

EpikitAxiomas

ExpressModeloInform.

PrologRegras backwarchaining”

CLIPSRegrasforward chaining

CORBAIDL

KIFLógica

predic.1ª

ordem


39

Uso da Ontolingua Remote collaborators

Writers

Readers

Remote Applications

DB

Aplic. GUI

Stand-alone applications

Aplic.

BC

KQML

NGFP

Ontology Server/Editor

Editor

Server

HTTP

NGFP

Translators:LOOM,IDL,CLIPS...

Library

File transfer (Batch)


40

Ontologias disponíveis na Ontolingua

• Normalmente mantidas por grupos de pesquisa

• Metadados de imagens de satélites

• Metadados para integração de bases de dados de genoma

• Catálogos de produtos• Osciloscópios• Robótica

• Semicondutores• Modelagem de sólidos• Matemática• Engenharia• Drogas• Terminologia medica• Padrão IEEE para

interconexões entre ferramentas


41

Problemas da Ontolingua

• As ontologias criadas na Ontolingua ficam complexas porque devem referenciar a Frame-Ontology

• Falta um motor de inferência para KIF– Falta de integração: nenhum teste com ontologias

e inferência pode ser rodado• Falta à Ontolingua uma interface para estações de

trabalho que permita a manipulacao de ontologias, sem estar acessando a Internet

• Extensibilidade: Como incluir novas funcionalidades?– O gerador de gráficos não é configurável


42

Protégé• Ferramenta desktop criada pelo Depto. de Informática Médica da

Univ. Stanford– Milhares de usuários

• Flexibilidade:– Editor de ontologias com interface gráfica

• Cria formulários para entrada de instâncias– Integração de Componentes

• Ex: Componentes gráficos, como OntoViz, Jambalaya– Plugin OKBC: acesso remoto à Ontolingua– Modelo de conhecimento: classes primitivas (metaclasses)

podem ser redefinidas• CLIPS, Jess, F-Logic, Prolog, RDF, OIL, XML, Topic Maps


43

Plugin OKBC acessando a Ontolingua


44

Importando BCs via OKBC


45

Ferramentas do KAON e da Ontoprise

• Desenvolvidas em Karlsruhe, Alemanha • 1o. protótipo do que viria a ser a Web semântica, o

Ontobroker • O KAON (the KArlsruhe ONtology e semântica web tool

suite) engloba ferramentas para: – edição de ontologias (OntoEdit)– disponibilizar ontologias num servidor baseado em BDs– criação de ontologias a partir de texto (Text-to-Onto)– busca baseada em ontologias sobre bases de texto

(SemânticaMiner)– anotação semi-automática de referências a ontologias

em páginas para a Web– agrupamento de textos baseados em ontologias


46

Requisitos para ferramentas de ontologias

• facilidades de uso• entendimento intuitivo da interface • interface gráfica• visibilidade gradativa• conexão a repositórios• portabilidade• interoperabilidade• organização dos arquivos gerados• documentação de alterações• suporte a trabalho cooperativo• estensibilidade (capacidade de inclusão de componentes)• ferramentas de apoio

Construção de ontologias


48

Princípios de construção

• Clareza

• Legibilidade

• Coerência

• Extensibilidade

• Mínima codificação

• Mínimo compromisso ontológico


49

Metodologias de desenvolvimento

• Processo iterativo, com revisões constantes• Nas metodologias propostas, são considerados

passos similares aos de engenharia de software:– Especificação– Conceitualização– Implementação

• Atividades de suporte são executadas concomitantemente com o desenvolvimento– Aquisição– Avaliação– Documentação– Integração com ontologias existentes


50

Especificação

• Determina o propósito e escopo da ontologia • Deve incluir uma análise para decidir se é possível,

necessário ou adequado o reuso de ontologias• Sugere-se elaborar uma lista de questões de

competência:– Servirão para a avaliação da ontologia durante o

desenvolvimento – Ex: “Jornais científicos são considerados eventos

científicos?”


51

Conceitualização • Fase crítica, nela ocorrem a maior parte das atividades de suporte

de aquisição e avaliação • Passos e dicas:

– Enumerar os termos do domínio– Definir as classes - não confundir nomes de um conceito com o

próprio conceito– Definir a hierarquia das classes - passo capcioso– Definir os slots e facetas de cada classe, interagindo com os

dois passos anteriores– Criar as instâncias - Se elas não possuem uma hierarquia

natural, é preciso revisar a hierarquia das classes– Usar convenções de nomes e nomes facilmente

compreensíveis


52

Implementação e Avaliação

• Objetivo: transformar a ontologia em algo computável• Na fase de implementação, a ontologia é escrita

numa linguagem de representação de conhecimento• Na fase de avaliação, são executados testes para

verificar se a ontologia atende aos requisitos especificados na fase de especificação

• Testes freqüentemente provocam mudanças na implementação

Aplicações de Ontologias


54

Ramos de aplicação

• Comércio eletrônico

• Gestão de conhecimento

• Workflow

• Tratamento inteligente de informação

• Web semântica


55

MASTER-Web

• Multi-Agent Sytem for Text Extraction, classeification e Retrieval over the Web

• Manipulação integrada de informação usando ontologias

• Objetivo: recuperar, classificar e extrair dados de páginas pertencentes às classes a um grupo

• EX:o grupo científico, com classes como artigos científicos, eventos, pesquisadores, etc

• Cada agente trata uma classe• Os agentes cooperam sugerindo links entre as classe

– Beneficiam-se dos relacionamentos entre as classes

[Freitas & Bittencourt 2003]


56

Arquitetura do MASTER-Web

URLs, fatos &

conhecimento

Sistema Multiagente

WEB

Infoseek

Excite

...

.

Meta-robô

Ontologias, Categorias & Dicionários

Novo Agente

DB

URLs & páginas

Mediador

Usuários

Agentes


57

Experimentos do MASTER-Web• Instanciado para o meio científico

– Ontologia de Ciência – Agente CFP: eventos científicos– Agente PPR: artigos científicos

• As páginas são classificadas em subclasses dentro da ontologia– Ex: o agente CFP as classifica em Conferência,

Workshop, Jornal, Revista, Evento-Genérico-ao-Vivo, Evento-Genérico-de-Publicação e Edição-Especial-de-Jornal e de Revista

• Taxa de acerto no reconhecimento e classificação: +80% em todos os testes


58

Uso de ontologias no MASTER-Web

• Generalidade da solução:– Para tratar páginas de outro grupo, basta criar

uma ontologia de seu domínio• Vocabulário de comunicação entre agentes• Definição e organização do conhecimento• A ontologia do domínio deve ser bastante detalhada

para garantir precisão no reconhecimento e classificação

• Ganho de expressividade e flexibilidade– O conhecimento sobre uma classe não se

circunscreve a termos e palavras-chaves, mas a qualquer fato que diga respeito às páginas, como estrutura, regiões, conceitos, etc

Conclusões


60

Conclusões

• Ontologias revigoraram o paradigma declarativo• Materialização do nível de conhecimento• Possibilitaram um modelo de comunicação

expressivo e intencional para agentes cognitivos• Área promissora, de pesquisa ativa• Aplicável principalmente em:

– Gestão de Conhecimento– Web semântica– e-commerce: muitas soluções com comunicação

baseadas em ontologias


61

Conclusões (cont.)

• Ontologias são o elemento estruturador da Web semântica

• Padrões ainda em processo de maturação• A Web semântica promete oferecer um tratamento

melhor da informação• As ontologias já começam a desempenhar o papel

de conhecimento estruturado disponível em larga escala, reusável por sistemas e programas

Documents

Semana de Cursos e Palestras da Computação (SECCOM) 04 a 08 de outubro de 2004 CTC-UFSC Representação de Conhecimento e Ontologias Guilherme Bittencourt