PPT - Franco Salvetti

download report

Transcript PPT - Franco Salvetti

Non-Monotonic Reasoning
for the Semantic Web
Agenda
 Default
reasoning
 Closed
World Assumption
 Belief
vs truth
 A possible
 Different
non-monotonic Semantic Web
semantics for rdf:type
 Results
 Unique
Name Assumption (the names problem)
Bertino, Provetti, Salvetti
Bertino, Provetti & Salvetti, AGP03
Non-Monotonic Reasoning for the Semantic Web
AGP03, pag. 2
Semantic Web
“The Semantic Web is not a Web of documents, but a
Web of relations between resources denoting real
world objects, i.e., objects such as people, places
and events.” - (Guha, McCool, Miller)
Bertino, Provetti & Salvetti, AGP03
A modern Semantic Network
Franco Salvetti
Bertino, Provetti & Salvetti, AGP03
Non-Monotonic Reasoning for the Semantic Web
University of Colorado at Boulder
15, August 2003 - HP Lab, pag. 4
Semantic Web =? Semantic Network
 Yes/No...
Maybe
 Semantic
Network introduced few years later the
Peano’s work for First Order Logic (Peirce 1882)
 FOL
=? Semantic Networks
 DAML-OIL
Franco Salvetti
 FOL (KSL, Stanford 2001)
Bertino, Provetti & Salvetti, AGP03
Non-Monotonic Reasoning for the Semantic Web
University of Colorado at Boulder
15, August 2003 - HP Lab, pag. 5
Knowledge Base
 We
want to describe the world using RDF
assertions (Subject, Predicate, Object)
 RDF
does not have inference, yet a descriptionlogic semantics is available (Horrocks et al.)
 RDF
assertions can be seen as equivalent to facts:
– triple(”subject”,”predicate”,”object”).
 We
can translate DAML-OIL to LP/ASP
Franco Salvetti
Bertino, Provetti & Salvetti, AGP03
Non-Monotonic Reasoning for the Semantic Web
University of Colorado at Boulder
15, August 2003 - HP Lab, pag. 6
An RDF assertion
triple(“http://example.org/LCWA”,
“http://example.org/author”,
“Ale”).
http://example.org/LCWA
http://example.org/author
Ale
<?xml version="1.0"?>
<rdf:RDF xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#”
xmlns:example="http://example.org/">
<rdf:Description rdf:about="http://example.org/paper_LCWA">
<example:author>
Ale
</example:author>
</rdf:Description>
</rdf:RDF>
Franco Salvetti
Bertino, Provetti & Salvetti, AGP03
Non-Monotonic Reasoning for the Semantic Web
University of Colorado at Boulder
15, August 2003 - HP Lab, pag. 7
Why rules and inference?
 Rules
are a compact way to describe the world
 Inference
is the formal mechanism for passing from
facts and rules to new facts
 We
need inference if we want to use rules to
describe in a compact way our domain
Franco Salvetti
Bertino, Provetti & Salvetti, AGP03
Non-Monotonic Reasoning for the Semantic Web
University of Colorado at Boulder
15, August 2003 - HP Lab, pag. 8
Why default reasoning?
 “Any
classification of the world has exceptions.”
 Default
 If
rules are a way to deal with exceptions
 is true and we can assume , we can believe 
– If there is a proof for  and there is no proof of  we
can believe in 
Franco Salvetti
Bertino, Provetti & Salvetti, AGP03
Non-Monotonic Reasoning for the Semantic Web
University of Colorado at Boulder
15, August 2003 - HP Lab, pag. 9
Example of a default rules
 “Normally
skiers”.
Swedish people are pale unless they are
swedish : skier
pale
pale :- swedish, not skier.
:- pale, n_pale.
is consistent assuming that you are skier if
there is no proof that you are a skier
 It
Franco Salvetti
Bertino, Provetti & Salvetti, AGP03
Non-Monotonic Reasoning for the Semantic Web
University of Colorado at Boulder
15, August 2003 - HP Lab, pag. 10
…and the inference?
admit contraddiction, swedish is pale (from
inference) and swedish is tanned for a fact: she
lives in ski resort the whole year.
 we
default reasoning consider pale as a belief
and tanned a truth, therefore there is no
contraddiction
 The
Franco Salvetti
Bertino, Provetti & Salvetti, AGP03
Non-Monotonic Reasoning for the Semantic Web
University of Colorado at Boulder
15, August 2003 - HP Lab, pag. 11
Stable Models and ASP

capture maximal consistent sets of beliefs
(Gelfond & Lifschitz 1991)
 Anwer
Set Programming is the confluence of
Deductive Database and Logic Programming
 DATALOG
with negation and negation as failure
 Big
difference between “the train is not coming”
and “I do not have a proof that the train is coming”
 In
the SW provability is an issue.
Franco Salvetti
Bertino, Provetti & Salvetti, AGP03
Non-Monotonic Reasoning for the Semantic Web
University of Colorado at Boulder
15, August 2003 - HP Lab, pag. 12
Negation as failure and CWA
 The
negation as failure, used in a default rule to
produce a beleif is based on the CWA
 CWA:
“everything that does not have a formal proof
is false”
 We
think that the truth of things relevant for our
reasoning is captured in the KB
Franco Salvetti
Bertino, Provetti & Salvetti, AGP03
Non-Monotonic Reasoning for the Semantic Web
University of Colorado at Boulder
15, August 2003 - HP Lab, pag. 13
Can we rely on CWA for the SW?
 NO
 We
cannot make inference on the whole Web
 Do
two agents need to reason on the whole Web?
 NO
 Can
they define their world?
 YES
 They
Franco Salvetti
can declare which “pages” are relevant
Bertino, Provetti & Salvetti, AGP03
Non-Monotonic Reasoning for the Semantic Web
University of Colorado at Boulder
15, August 2003 - HP Lab, pag. 14
All together!
 We
want to do default reasoning because is
compact way to dealt with exceptions in
classification
 Default
 We
rules are good candidates
need negation as failure
 Negation
 We
as failure needs CWA
introduce a Local CWA for the Web
Franco Salvetti
Bertino, Provetti & Salvetti, AGP03
Non-Monotonic Reasoning for the Semantic Web
University of Colorado at Boulder
15, August 2003 - HP Lab, pag. 15
rdf:type and rdfs:subClassOf
 rdf:type
is monotonic, it means that if we say that B
is a rdfs:subClassOf A and x is rdf:type B we can
infer that x is rdf:type of A
 however,
any system of classification sooner or
later fails due to exceptions
transform rdf:type into its non monotonic
version
 Idea:
Franco Salvetti
Bertino, Provetti & Salvetti, AGP03
Non-Monotonic Reasoning for the Semantic Web
University of Colorado at Boulder
15, August 2003 - HP Lab, pag. 16
some new knowledge arrives
 rdf:type
is monotonic, it means that if we say that B
is a rdfs:subClassOf A and x is rdf:type B we can
infer that x is rdf:type of A
 Here
we have made an implicit inference
 Now
we discover that x is rdf:type of C and C is
daml:complementOf A
x
is, not A and A... This is really bad!!!
Franco Salvetti
Bertino, Provetti & Salvetti, AGP03
Non-Monotonic Reasoning for the Semantic Web
University of Colorado at Boulder
15, August 2003 - HP Lab, pag. 17
Does it happen?
 YES
 Do
you know Pingu? (Minsky, McCarthy)
 “Normally
birds fly”
 “Penguins
rdfs:subClassOf Birds”
 “Penguins
do not fly!”
 “Magic
is a magic Penguin that flies!”
 “Pingu
is a Penguin”
Franco Salvetti
Bertino, Provetti & Salvetti, AGP03
Non-Monotonic Reasoning for the Semantic Web
University of Colorado at Boulder
15, August 2003 - HP Lab, pag. 18
Flying, in RDF
triple(S, "rdfs:subClassOf", O) :d(S),
d(O),
d(B),
d(C),
triple(S, "rdfs:subClassOf", B),
triple(B, "rdfs:subClassOf", O),
not cannotBeSubClassOf(S,O).
cannotBeSubClassOf(X,C) :d(X),
d(C),
d(A),
triple(X, "rdfs:subClassOf", A),
triple(A, "daml:complementOf", C).
triple(S, "rdf:type", O) :d(S),
d(C),
d(B),
d(O),
triple(S, "rdf:type", B),
triple(B, "rdfs:subClassOf", O),
not cannotBeTypeOf(S,O).
cannotBeTypeOf(X,C) :d(X),
d(C),
d(A),
triple(X, "rdf:type", A),
triple(A, "daml:complementOf", C).
Franco Salvetti
Bertino, Provetti & Salvetti, AGP03
Non-Monotonic Reasoning for the Semantic Web
University of Colorado at Boulder
15, August 2003 - HP Lab, pag. 19
Two consistent s-models
Answer: 1
Stable Model:
type("magic","Flying")
type("pingu","Flying")
type("magic","Penguin")
type("pingu","Penguin")
type("magic","Bird")
type("pingu","Bird")
subClassOf("Bird","Flying")
subClassOf("Penguin","n_Flying")
subClassOf("Penguin","Bird")
Answer: 2
Stable Model:
type("magic","Flying")
type("pingu","n_Flying")
type("magic","Penguin")
type("pingu","Penguin")
type("magic","Bird")
type("pingu","Bird")
subClassOf("Bird","Flying")
subClassOf("Penguin","n_Flying")
subClassOf("Penguin","Bird")
Franco Salvetti
Bertino, Provetti & Salvetti, AGP03
Non-Monotonic Reasoning for the Semantic Web
University of Colorado at Boulder
15, August 2003 - HP Lab, pag. 20
An explicit semantics in ASP
q
p
triple(S,Super,O) :d(S),
d(Super),
d(O),
d(Son),
triple(Son, "rdfs:subPropertyOf", Super),
triple(S, Son, O).
Franco Salvetti
Bertino, Provetti & Salvetti, AGP03
Non-Monotonic Reasoning for the Semantic Web
University of Colorado at Boulder
15, August 2003 - HP Lab, pag. 21
Results
 Using
the LCWA we can use the negation as failure
for the SW
 with
negation as failure we can do default
reasoning
 We
can discover alternative interpretations of our
knowledge
 ASP
Franco Salvetti
inference engines, e.g., smodels can do that
Bertino, Provetti & Salvetti, AGP03
Non-Monotonic Reasoning for the Semantic Web
University of Colorado at Boulder
15, August 2003 - HP Lab, pag. 22
Is the CWA the only assumption?
 NO
 The
Unique Names Assumption (UNA) is normally
used in logic programming
 Can
we rely on that in the Semantic Web?
 Yes/No...
 Maybe
Maybe
No!
 No!
Franco Salvetti
Bertino, Provetti & Salvetti, AGP03
Non-Monotonic Reasoning for the Semantic Web
University of Colorado at Boulder
15, August 2003 - HP Lab, pag. 23
Towards ontology/schema integration?
“How many people have written an
ontology with a resource named
student?”
Franco Salvetti
Bertino, Provetti & Salvetti, AGP03
Non-Monotonic Reasoning for the Semantic Web
University of Colorado at Boulder
15, August 2003 - HP Lab, pag. 24
Is there a solution?
 The
problem of schema or ontology integration is
an open, maybe unsolvable problem
 Do
we hope in Darwin?
 Is
there a cooperative way to build ontologies?
 Is
Linux a good example?
 Reintroducing
Franco Salvetti
names is stupid!
Bertino, Provetti & Salvetti, AGP03
Non-Monotonic Reasoning for the Semantic Web
University of Colorado at Boulder
15, August 2003 - HP Lab, pag. 25
Conclusions
 A non
monotonic semantic for RDF is needed for
capturing an environment, the Web, that is not
monotonic
 W3C
semantics for RDF is monotonic, the Web
ain’t
 Default
and ASP are a possible practical solution
 LCWA is
a must
 A different
Franco Salvetti
way to build ontologies has to be found
Bertino, Provetti & Salvetti, AGP03
Non-Monotonic Reasoning for the Semantic Web
University of Colorado at Boulder
15, August 2003 - HP Lab, pag. 26
Acknowledgments
 S.
McIlraith (Stanford University)
 R.
King (Univerity of Colorado at Boulder)
 B.
Burg (HP Lab)
Franco Salvetti
Bertino, Provetti & Salvetti, AGP03
Non-Monotonic Reasoning for the Semantic Web
University of Colorado at Boulder
15, August 2003 - HP Lab, pag. 27
Non-Monotonic Reasoning
for the Semantic Web
questions…
Non-Monotonic Reasoning
for the Semantic Web
thank you