Transcript S-Match ESWS

Web Explanations for
Semantic Heterogeneity Discovery
Pavel Shvaiko
work in collaboration with
Fausto Giunchiglia, Paulo Pinheiro da Silva and
Deborah L. McGuinness
2nd European Semantic Web Conference (ESWC),
1 June 2005, Crete, Greece
2
Outline
Introduction
Semantic Matching
Inference Web (IW) Framework
Explaining Semantic Matching using IW
Experimental Study
Conclusions
ESWC, June 1, 2005, Crete, Greece
3
Introduction
Information sources (e.g., database schemas,
classifications or ontologies) can be viewed as graph-like
structures containing terms and their inter-relationships
Matching is one of the key operations for enabling the
Semantic Web since it takes two graph-like structures and
produces a mapping between the nodes of the graphs
that correspond semantically to each other
Matching, however, requires explanations because
mappings between terms are not always intuitively
obvious to human users
ESWC, June 1, 2005, Crete, Greece
4
Semantic Matching
ESWC, June 1, 2005, Crete, Greece
5
Semantic Matching
Semantic Matching: Given two graphs G1 and G2, for any node n1i  G1,
find the strongest semantic relation R’ holding with node n2j  G2
Computed R’s, listed in the decreasing binding strength order:
equivalence { = };
more general/specific { , };
disjointness {  }
We compute semantic relations by analyzing the meaning (concepts, not
labels) which is codified in the elements and the structures of
schemas/classifications
Technically, labels at nodes written in natural language are
translated into propositional logical formulas which explicitly
codify the label’s intended meaning. This allows us to codify the
matching problem into a propositional validity problem
ESWC, June 1, 2005, Crete, Greece
6
Example: Two simple classifications
A1
Images
Computers
and
Internet
D.E.
Europe
Europe
Trento
=
?
Italy
Pictures
A2
Cyberspace
and
Virtual Reality
Italy
Axioms  rel (Context1, Context2)
(Images1Pictures2)  (Europe1Europe2)  (Images1  Europe1)  (Europe2 Pictures2)
Axioms
ESWC, June 1, 2005, Crete, Greece
Context1
Context2
7
S-Match
Expl.
ESWC, June 1, 2005, Crete, Greece
8
Inference Web (IW) Framework
ESWC, June 1, 2005, Crete, Greece
9
The IW Framework Overview
Inference Web is a framework enabling applications to
generate portable and distributed explanations for their
answers
ESWC, June 1, 2005, Crete, Greece
10
Explaining Semantic Matching
using IW
ESWC, June 1, 2005, Crete, Greece
11
Producing Explanations
In order to explain mappings produced by S-Match and
thereby increase the trust level of its users, we need to
provide information about:
•
•
background theories (e.g., WordNet)
WordNet
JSAT manipulations of propositional formulas
ESWC, June 1, 2005, Crete, Greece
12
Default Explanation
A default explanation of mappings the S-Match system produces is
a short, natural language, high-level explanation without any
technical details. It is designed to be intuitive and understandable
by ordinary users
Query: find "European pictures"
Query
ESWC, June 1, 2005, Crete, Greece
13
Explaining Background Knowledge
Suppose that the agent still does not trust the answer and may
want to see the sources of metadata information behind the
mapping
ESWC, June 1, 2005, Crete, Greece
14
Explaining Logical Reasoning
If the mappings derivation process needs to be explained, using
the JSAT SAT engine, S-Match produces a trace of the DPLL
procedure
ESWC, June 1, 2005, Crete, Greece
15
Experimental Study
ESWC, June 1, 2005, Crete, Greece
16
Preliminary Results
Goal: to obtain a vision of how the S-Match explanations
potentially scale to requirements of the Semantic Web
ESWC, June 1, 2005, Crete, Greece
17
Conclusions
We use the Proof Mark-up Language for representing
S-Match proofs, thus facilitating interoperability
We use meaningful terms rather than numbers in the
DIMACS format, thus facilitating understandability
We use the IW tools, thus facilitating customizable,
interactive proof and explanation presentation and
abstraction
Our solution is potentially scalable to the Semantic Web
requirements
ESWC, June 1, 2005, Crete, Greece
18
Future Work
Developing an environment, which efficiently exploits the
IW proofs and explanations, in order to make the S-Match
matching process (fully-fledged) interactive and iterative
Improving the S-Match proofs and explanations by using
abstraction techniques more extensively
Conducting a user satisfaction study of the explanations
Extending explanations to other SAT engines as well as
to other non-SAT DPLL-based inference engines
ESWC, June 1, 2005, Crete, Greece
19
References
Project website at DIT - ACCORD: http://www.dit.unitn.it/~accord/
Project website at KSL - IW: http://iw.stanford.edu/
F. Giunchiglia, P. Shvaiko: Semantic matching. The Knowledge
Engineering Review Journal, 18(3):265-280, 2003.
F. Giunchiglia, P. Shvaiko, M. Yatskevich: S-Match: an algorithm
and an implementation of semantic matching. In Proceedings of
ESWS, pages 61-75, 2004.
D. McGuinness, P. Pinheiro da Silva: Explaining Answers from
the Semantic Web: The Inference Web Approach. Journal of Web
Semantics, 1(4): 397- 413, 2004.
ESWC, June 1, 2005, Crete, Greece
20
Thank you!
ESWC, June 1, 2005, Crete, Greece