Description Logic in a nutshell

Description Logic in a nutshell Seminar „Resources for Computational Linguists“ SS 2007 Magdalena Wolska & Michaela Regneri...

0 downloads 229 Views 193KB Size
Description Logic in a nutshell Seminar „Resources for Computational Linguists“ SS 2007 Magdalena Wolska & Michaela Regneri

Motivation • We have seen all those great ontologies - how can we make use of them? • How can we add logic inference to our world knowledge? (Aristotle is a human, humans are mortal -> Aristotle is mortal) • How can we do all that without having to wait for ages?

Resources for Comp‘ Linguists 07

Description Logics

- Michaela Regneri & Magdalena Wolska

2

Outline • Some curses of FOL • Some solutions: Description Logics • Basics and Terms • Reasoning: RACER

Resources for Comp‘ Linguists 07

Description Logics

- Michaela Regneri & Magdalena Wolska

3

Some curses of FOL • FOL is not decidable Provide a system with the following: (The universe shall consist of natural numbers) x y bigger_than(x,y) x y z((bigger_than(x,y)

bigger_than(y,z)) →

bigger_than(x,z))

Finding a prove for the following statement may take forever: x bigger_than(x,x) Resources for Comp‘ Linguists 07

Description Logics

- Michaela Regneri & Magdalena Wolska

4

Some curses of FOL (cont.) • Even if a prover will find a prove, it may take an unreasonable amount of time • How do we encode all the world knowledge with first order logic? • There are some more curses - but this talk won‘t provide any solution for them :-)

Resources for Comp‘ Linguists 07

Description Logics

- Michaela Regneri & Magdalena Wolska

5

Description Logic • A decidable fragment of FOL • efficient reasoners (RACER) exist • some big knowledge bases are already encoded in description logics (like OWL e.g.) • We won‘t look at a special DL now, but introduce some elements they all have in common

Resources for Comp‘ Linguists 07

Description Logics

- Michaela Regneri & Magdalena Wolska

6

Description Logic - basics • Designed for knowledge representations

• allowing to encode general knowledge (as above) as well as world models (with individuals, s.a. john) Resources for Comp‘ Linguists 07

Description Logics

- Michaela Regneri & Magdalena Wolska

7

Description Logic - basics (cont.) • T-Box: The world‘s rules (as described in the knowledge base) man ⊑ person woman ⊑ person city ⊑ location located_in.location ... • A-Box: Relations between and properties of individuals person(mary) person(john) loves(mary, john) loves(john, mary) Resources for Comp‘ Linguists 07

Description Logics

works_for(mary, c1) located_in(NY, c1) woman(mary) man(john) - Michaela Regneri & Magdalena Wolska

8

Description Logic - Terms • (atomic) concepts C denoting sets of individuals (person) ≈ unary predicates in FOL • (atomic) roles R: (loves) ≈ binary predicates in FOL • complex concepts: • conjunction and disjunction of concepts: C1 ⊓ C2 , C1 ⊔ C2 • negation (the complementary concept): ¬C • existential restriction: • value restriction: Resources for Comp‘ Linguists 07

R.C (set of all a having an x s.t. R(a,x) & C(x) )

R.C (set of all a s.t. for all x s.t. R(a,x), C(x) holds)

Description Logics

- Michaela Regneri & Magdalena Wolska

9

Description Logic - Terms (cont.) • inverse roles R-1: loves(john, mary) • the empty concept

loves-1(mary, john)

and the universal concept

• concept equality: C1 ≐ C2 (abbreviates C1 ⊑ C2 C2 ⊑ C1) • ‚at most‘ and ‚at least‘ number restrictions: ≤mR: Set of all a s.t. there are at most m (different) x for which R(a,x) holds Resources for Comp‘ Linguists 07

Description Logics

- Michaela Regneri & Magdalena Wolska

10

Description Logic - Example A-BOX man(john) woman(mary) man(sam) woman(sue)

loves(john,mary) loves(mary,sam) married(sam,sue) happy(sam)

Some assertions...

...and some rules:

T-BOX bachelor ≐ ¬ married.⊤ ⊓ man

„bachelors are unmarried men“

married ≐ married-1 married.⊤ ⊑ happy

(being married to so. is reflexive) „all married people are happy“

2 love

„you can love at most one person“



married.woman ⊑

love.woman

„someone married to a woman also loves a woman“

Resources for Comp‘ Linguists 07

Description Logics

- Michaela Regneri & Magdalena Wolska

11

Description Logic - RACER • a reasoner for description logic • provides reasoning with T-Boxes and (multiple) A-Boxes • performs consistency checks (of A-Boxes, T-Boxes or both) • several retrieval tasks: • all individuals of a concept, all concepts of an individual • check for subsumption („are cities locations?“) Resources for Comp‘ Linguists 07

Description Logics

- Michaela Regneri & Magdalena Wolska

12

Description Logic - RACER (cont.) • several retrieval tasks: • find the parent concepts parents of C are the most specific C‘ s.t. C ⊑ C‘ (children analogously) • find predecessors (successors): predecessors of C are all C‘ s.t. C ⊑* C‘ (successors analogously) • determine domain and fillers of a role: fillers of R are all f s.t. x.R(x,f) (≐ R -1.⊤) domain of R consists of all d s.t. x.R(d,x) (≐ R.⊤) Resources for Comp‘ Linguists 07

Description Logics

- Michaela Regneri & Magdalena Wolska

13

Description Logic - RACER (cont.) A-BOX

• Example queries: Is Sue happy? (Does ‚happy‘ contain Sue?) Can Mary love John? (loves(mary, john) -> consistent?) What properties does Mary have? (Concepts containing mary)

man(john) woman(mary) man(sam) woman(sue)

loves(john,mary) loves(mary,sam) married(sam,sue) happy(sam)

T-BOX bachelor ≐ ¬ married.⊤ ⊓ man married ≐ married-1 married.⊤ ⊑ happy 2 love



married.woman ⊑ Resources for Comp‘ Linguists 07

Description Logics

- Michaela Regneri & Magdalena Wolska

love.woman 14

What about Aristotle? • What‘s needed to answer the question whether or not Aristotle is mortal?

Resources for Comp‘ Linguists 07

Description Logics

- Michaela Regneri & Magdalena Wolska

15

What about Aristotle? • What‘s needed to answer the question whether or not Aristotle is mortal?

A-BOX human(Aristotle)

T-BOX human ⊑ mortal

Aristotle

Resources for Comp‘ Linguists 07

Description Logics

mortal ?

- Michaela Regneri & Magdalena Wolska

15

References • Ian Horrocks and Ulrike Sattler: Tutorial on description logics. Slides: http://www.cs.man.ac.uk/~horrocks/Slides/IJCARtutorial/Display/ • V. Haarslev and R. Möller. RACER System Description. In Proceedings of IJCAR-01, 2001.

Resources for Comp‘ Linguists 07

Description Logics

- Michaela Regneri & Magdalena Wolska

16