Aprendizado Exato de Ontologias em Lógica Descritiva

•

Humanas / Sociais

0

Aprendendo com resumos

21/03/2023

E aí, curtiu este material?

Ajude a incentivar outros estudantes a melhorar o conteúdo

Gostou desse material? Compartilhe! 🧡

Trabalho de Conclusão de Curso - TCC

95.981 Materiais compartilhados

Baixe o app para aproveitar ainda mais

Leia os materiais offline, sem usar a internet. Além de vários outros recursos!

Prévia do material em texto

Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
Aprendizado Exato de Ontologias
em Lógica Descritiva
16 de junho de 2016
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
OUTLINE
Introdução
Modelo de Comunicação
Aprendizado Exato
Nossos Resultados
Conclusão
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
INTRODUÇÃO
I Ontologias em Lógica Descritiva (LD)
I Formalismo para representação de conhecimento baseado
em lógica.
I Usadas para descrever um domı́nio em termos de
conceitos (predicado unário) e papéis (predicado binário).
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
INTRODUÇÃO
Exemplo:
I Vocabulário:
I Conceitos: Acadêmico
I Papéis: temOrientador
I Ontologia em Lógica Descritiva:
I Acadêmico v ∃ temOrientador.Acadêmico
I Tradução:
∀x(Acadêmico(x)→ ∃y(temOrientador(x, y) ∧Acadêmico(y)))
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
EXEMPLOS DE ONTOLOGIAS
I Nomenclatura Sistematizada de Medicina, Termos Clı́nicos
(SNOMED CT): 500.000 conceitos [Ruch et al., 2008]
I Enciclopédia do Instituto Nacional de Câncer (NCI) dos
Estados Unidos: 50.000 conceitos [Golbeck et al., 2011]
I Genética: 25.000 conceitos [Consortium et al., 2013]
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
SNOMED CT
Exemplo de um axioma definindo o termo Tuberculose
Pulmonar em SNOMED CT (sintaxe LD):
PulmonaryTuberculosis ≡ Disease u
∃causativeAgent.MycobacteriumTuberculosisComplex u
∃findingSite.LungStructure
Tradução para Lógica de Primeira Ordem:
∀(x)(PulmonaryTuberculosis(x) ↔ (Disease(x) ∧ ∃y1(causativeAgent(x, y1)∧
MycobacteriumTuberculosisComplex(y1)) ∧
∃y2(findingSite(x, y2) ∧ LungStructure(y2))))
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
CONSTRUÇÃO DE ONTOLOGIAS
I O processo de construção de ontologias de grande porte é
altamente complexo.
I Engenheiro de Ontologia - Não conhece o domı́nio
I Especialista no Domı́nio - Não conhece as linguagens
usadas para construção de ontologias
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
CONSTRUÇÃO DE ONTOLOGIAS
I Neste trabalho, consideramos um modelo simples do
processo de comunicação e analisamos, dentro do modelo,
a complexidade computacional de construir uma
ontologia.
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
OUTLINE
Introdução
Modelo de Comunicação
Aprendizado Exato
Nossos Resultados
Conclusão
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
MODELO DE COMUNICAÇÃO
I Premissas:
I o especialista no domı́nio conhece o domı́nio e seu
vocabulário sem saber como formalizá-lo como uma
ontologia;
I o especialista no domı́nio informa ao engenheiro de
ontologia os termos relevantes do domı́nio, o vocabulário.
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
MODELO DE COMUNICAÇÃO
I O engenheiro de ontologia pode perguntar se um
conhecimento conceitual é verdadeiro no domı́nio.
Em sı́mbolos: T |= C v D?
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
MODELO DE COMUNICAÇÃO
I O engenheiro de ontologia também precisa saber se a
ontologia construı́da está completa e, se não estiver, o
engenheiro pede um contraexemplo.
Em sı́mbolos: H ≡ T ?
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
ENUNCIADO DO PROBLEMA
Dado esse modelo, onde se assume que o vocabulário e a
linguagem da lógica descritiva são conhecidos:
I Pode o engenheiro de ontologia construir uma ontologia
que reflita o conhecimento do especialista no domı́nio?
I Quantas perguntas são necessárias para isso?
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
OUTLINE
Introdução
Modelo de Comunicação
Aprendizado Exato
Nossos Resultados
Conclusão
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
APRENDIZADO EXATO (ANGLUIN)
I Um algoritmo aprende exatamente um conjunto alvo L∗ se
sempre termina e retorna uma hipótese Lh tal que Lh = L∗.
I Pergunta de Pertinência: x ∈ L∗ ? Sim/Não
I Pergunta de Equivalência: Lh = L∗ ? Sim/Não e x ∈ Lh ⊕ L∗
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
APRENDIZADO EXATO
I Pergunta de Pertinência: x ∈ L∗ ? Sim/Não
I Pergunta de Equivalência: Lh = L∗ ? Sim/Não e x ∈ Lh⊕ L∗
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
APRENDIZADO EXATO
I Pergunta de Pertinência: x ∈ L∗ ? Sim/Não
I Pergunta de Equivalência: Lh = L∗ ? Sim/Não e x ∈ Lh⊕ L∗
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
APRENDIZADO EXATO
I Pergunta de Pertinência: x ∈ L∗ ? Sim/Não
I Pergunta de Equivalência: Lh = L∗ ? Sim/Não e x ∈ Lh⊕ L∗
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
APRENDIZADO EXATO
I Pergunta de Pertinência: x ∈ L∗ ? Sim/Não
I Pergunta de Equivalência: Lh = L∗ ? Sim/Não e x ∈ Lh⊕ L∗
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
APRENDIZADO EXATO
I Pergunta de Pertinência: x ∈ L∗ ? Sim/Não
I Pergunta de Equivalência: Lh = L∗ ? Sim/Não e x ∈ Lh⊕ L∗
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
APRENDIZADO EXATO
I Pergunta de Pertinência: x ∈ L∗ ? Sim/Não
I Pergunta de Equivalência: Lh = L∗ ? Sim/Não e x ∈ Lh⊕ L∗
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
EXACT LEARNING
I Membership query: x ∈ L∗ ? Yes/No
I Equivalence query: Lh = L∗ ? Yes/No and x ∈ Lh ⊕ L∗
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
APRENDIZADO EXATO
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
APRENDIZADO EXATO DE ONTOLOGIAS EM LD
I Elementos de conjuntos
I Pergunta de Pertinência: x ∈ L∗ ? Sim/Não
I Pergunta de Equivalência: Lh = L∗ ? Sim/Não e x ∈ Lh ⊕ L∗
I Inclusão de conceitos
I Pergunta de Pertinência: T |= C v D? Sim/Não
I Pergunta de Equivalência: H ≡ T ? Sim/Não e o oráculo
retorna C v D tal que T |= C v D eH 6|= C v D (um
contraexemplo positivo), ou vice versa (um contraexemplo
negativo).
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
APRENDIZADO EXATO
I Aprendizado em tempo polinomial:
I Polinomial no tamanho do alvo de aprendizado e do maior
contraexemplo visto até o momento.
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
APRENDIZADO EXATO
I Aprendizado em tempo polinomial:
I Linguagens Regulares [Angluin, 1987],
I Horn Proposicional [Angluin et al., 1992],
I Horn de Primeira Ordem Não-Recursivo
[Reddy and Tadepalli, 1999],
I Mapeamentos de Schemas de Banco de Dados
[ten Cate et al., 2012].
I Em aberto:
I FNC e FND Booleano,
I Horn de Primeira Ordem (brecha entre ‘lower bound’ e
melhor algoritmo conhecido).
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
OUTLINE
Introdução
Modelo de Comunicação
Aprendizado Exato
Nossos Resultados
Conclusão
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
LINGUAGENS DA LÓGICA DESCRITIVA
CA vC v AC v D
ELrhsELlhsEL
∃r.A′ v A∃r.A v ∃s.A′ A v ∃r.A′
I Expressões de conceitos em EL:
I C,D := A | > | C uD | ∃r.C
I Problema SAT é trivial.
I Problema T |= C v D é polinomial.
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
PRIMEIRAS OBSERVAÇÕES DO PROBLEMA
CA vC v AC v D
ELrhsELlhsEL
∃r.A′ v A∃r.A v ∃s.A′ A v ∃r.A′
I Expressões de conceitos em EL:
I C,D:= A | > | C uD | ∃r.C
1. Com um mesmo vocabulário pode-se criar expressões de
conceitos de tamanho arbitrário.
2. Seria inviável perguntar todos os axiomas possiveis em
uma das linguagens, mesmo conhecendo o vocabulário.
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
PRIMEIRAS OBSERVAÇÕES DO PROBLEMA
I Suponha que estejamos tentando aprender a seguinte
ontologia formulada em ELlhs.
I T = {∃r.A v A}
O seguinte algoritmo poderia não terminar.
inicio
H = ∅
enquantoH 6≡ T faça
Seja C v A o contraexemplo (positivo)
H := H ∪ {C v A}
fim
fin
retornaH
O oráculo pode retornar uma sequencia infinita de
contraexemplos ∃rn.A v A, sendo n um número primo.
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
NOSSOS RESULTADOS
CA vC v AC v D
ELrhsELlhsEL
∃r.A′ v A∃r.A v ∃s.A′ A v ∃r.A′
I ELlhs e ELrhs: é possı́vel aprender em tempo polinomial.
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
NOSSOS RESULTADOS
I ELlhs e ELrhs: é possı́vel aprender em tempo polinomial.
inicio
H = ∅
enquantoH 6≡ T faça
Refina o contraexemplo C v D com perguntas
AtualizeH com o contraexemplo refinado
fim
fin
retornaH
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
NOSSOS RESULTADOS
CA vC v AC v D
ELrhsELlhsEL
∃r.A′ v A∃r.A v ∃s.A′ A v ∃r.A′
I EL: não é possı́vel aprender em tempo polinomial.
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
OUTLINE
Introdução
Modelo de Comunicação
Aprendizado Exato
Nossos Resultados
Conclusão
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
CONCLUSÃO
I Neste trabalho, tratamos o problem de construir uma
ontologia como um problema de aprendizado.
I Investigamos a complexidade de aprender ontologias em
diversas linguagens da lógica descritiva.
I Classificação:
I ELlhs: 3
I ELrhs: 3
I EL: 7
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
TRABALHOS PUBLICADOS
Tese de Doutorado:
I Exact Learning of Lightweight Description Logic
Ontologies - KR 2014;
I Exact Learning Description Logic Ontologies from Data
Retrieval Examples - DL Workshop 2015;
I A Model for Learning Description Logic Ontologies Based
on Exact Learning - AAAI 2016.
Outros Projetos:
I Exact Learning of Multivalued Dependencies - ALT 2015;
I On Metric Temporal Description Logics - ECAI 2016.
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
OUTROS PROJETOS
Em andamento:
I Metric Temporal Logic Translations;
I Rewritability in Modal Logic.
Futuros:
I Projeto Posdoc: Dimensão Vapnik-Chervonenkis de
Ontologias em Lógica Descritiva;
I ?
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
PERGUNTAS
Obrigada!
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
QUAL É A ‘COMPLEXIDADE’ DE APRENDER
ONTOLOGIAS EM LÓGICA DESCRITIVA?
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
Angluin, D. (1987).
Learning regular sets from queries and counterexamples.
Inf. Comput., 75(2):87–106.
Angluin, D., Frazier, M., and Pitt, L. (1992).
Learning conjunctions of Horn clauses.
Machine Learning, 9:147–164.
Consortium, G. O. et al. (2013).
Gene ontology annotations and resources.
Nucleic acids research, 41(D1):D530–D535.
Golbeck, J., Fragoso, G., Hartel, F., Hendler, J., Oberthaler,
J., and Parsia, B. (2011).
The national cancer institute’s thesaurus and ontology.
Web Semantics: Science, Services and Agents on the World Wide
Web, 1(1).
Reddy, C. and Tadepalli, P. (1999).
Introdução Modelo de Comunicação Aprendizado Exato Nossos Resultados Conclusão
Learning Horn definitions: Theory and an application to
planning.
New Generation Comput., 17(1):77–98.
Ruch, P., Gobeill, J., Lovis, C., and Geissbühler, A. (2008).
Automatic medical encoding with snomed categories.
BMC medical informatics and decision making, 8(1):1.
ten Cate, B., Dalmau, V., and Kolaitis, P. G. (2012).
Learning schema mappings.
In ICDT, pages 182–195.
	Introdução
	Modelo de Comunicação
	Aprendizado Exato
	Nossos Resultados
	Conclusão