Collaboration of KIF, SUMM, and CG developers
sowa <sowa@turing.pacss.binghamton.edu>
Date: Wed, 10 Feb 93 15:20:08 EST
From: sowa <sowa@turing.pacss.binghamton.edu>
Message-id: <9302102020.AA19296@turing.pacss.binghamton.edu>
To: interlingua@ISI.EDU, srkb@ISI.EDU, kr-advisory@ISI.EDU, cg@cs.umn.edu
Subject: Collaboration of KIF, SUMM, and CG developers
Cc: fikes@sumex-aim.stanford.edu, mrg@cs.stanford.edu, jfulton@atc.boeing.com,
neches@ISI.EDU, sowa@turing.pacss.binghamton.edu
During the past few years, three logic-based formalisms have been proposed for
overlapping purposes:
1. KIF (Knowledge Interchange Format) has been developed by the Interlingua
Committee of the DARPA-sponsored Knowledge Sharing Effort (KSE). The
principal designers of KIF are Michael Genesereth and Richard Fikes of
Stanford.
2. SUMM (Semantic Unification Meta-Model) was developed for the PDES
Committee (Product Data Exchange using STEP) and its international affiliate,
ISO Technical Committee 184, SC 4. The principal designer of SUMM is James
Fulton of Boeing.
3. CGs (Conceptual Graphs) have been proposed as the initial normative
language for the IRDS Conceptual Schema by the ANSI X3H4 Committee on IRDS
(Information Resource Dictionary Systems). The principal designer of CGs is
John Sowa, formerly of IBM, now at the State University of New York at
Binghamton.
These three formalisms have overlapping scope and expressive power:
First-order logic with sets, metalanguage facilities, and the ability to
express modal, intensional, and temporal statements. Because of the
similarities, the designers of all three formalisms have been considering the
possibility of combining forces instead of competing. Yet the chief designers
of the three formalisms had never had a chance to get together in one room at
the same time. Finally, during the week of January 18, 1993, we were able to
get Fikes, Genesereth, Fulton, and Sowa together for a meeting at Stanford.
Bob Neches from ISI served as the KSE observer, moderator, and referee for the
first two days.
The first point that emerged from our discussions was that the three systems
were designed for different purposes and their strengths are complementary to
one another:
1. KIF, as its name implies, is intended primarily as an interchange format
between heterogeneous knowledge base and data base systems.
2. SUMM, as its name implies, is intended as an ontology for a metalanguage
to unify formal modeling languages.
3. Conceptual graphs were designed as a graphic formalism of logic for
representing natural language semantics.
All three formalisms have a model-theoretic semantics, but the KIF semantics
is the simplest of the three, since it avoids some of the modal features of
SUMM and the natural language features of CGs. Because of its greater
simplicity, it seemed best to take the KIF semantics as primitive and define
the SUMM and CG semantics in terms of KIF. The SUMM metalanguge primitives,
which were developed for representing the PDES Express language and other
modeling languages, provide an ontology that can also be used to define much
of the semantics of KIF and CGs. Conceptual graphs have a highly readable
graphic notation and a direct mapping to natural language syntax that can help
to make knowledge representations more readable and easier to map to natural
language text for help and explanations. These three systems therefore have
complementary strengths, and future developments should take advantage of
those strengths. To do that, we recommend the following approach:
1. Define the SUMM metalanguage ontology in terms of the KIF semantics by
using the KIF definition sublanguage to define SUMM as a KIF ontology.
2. Describe both the KIF and CG languages using the SUMM ontology as
defined in KIF.
3. Define the syntactic mappings between KIF and CGs so that anything
expressed in either one can automatically be translated into the other while
preserving the native semantics of both.
4. Verify that the mappings defined in Point #3 preserve the equivalence
implied by the definitions in Point #2.
We propose to continue this work under the auspices of the DARPA sponsored
Knowledge Sharing Effort as well as the ANSI and ISO standards projects.
Following are some of the issues we considered and possible ways of dealing
with them:
a) Conceptual graphs have been evolving in parallel with research in
linguistics and related areas of cognitive science. To avoid restraining that
evolution, we propose two distinct, but overlapping dialects of conceptual
graphs: The standardized version, called IRDS-CG, would be exactly equivalent
in semantics to KIF. The research version, called NL-CG, would include most,
if not all of IRDS-CG, but would allow any extensions or modifications that
anyone might find useful for representing natural language and other areas
of cognitive science. Innovations in NL-CG that prove useful could later be
incorporated in future versions of IRDS-CG, and they might also lead to
extensions of KIF.
b) One example where the SUMM and CG semantics differ from KIF is in the
handling of necessary or mandatory associations. An instance of selling, for
example, cannot occur without a seller. The SUMM "occurrences" and the CG
"canonical graphs" were designed to ensure that such associations could not be
broken. In KIF, an instance of selling might occur without a seller; in SUMM,
such an occurrence would not be permitted, and in CGs it could be stated, but
would be considered "noncanonical". The truth-functional denotations,
however, would not be affected: every permissible occurrence in SUMM would be
canonical in conceptual graphs and would have the same truth value as in KIF;
some nonpermissible occurrences in SUMM that were statable in KIF could also
be stated in CGs as noncanonical graphs, and they would have the same truth
values in KIF and CGs. Therefore, the KIF semantics would be adequate to
define the truth conditions for both CGs and SUMM, although CGs and SUMM might
generate "warning messages" for certain noncanonical statements that might be
permissible in KIF.
Another difference is that the SUMM semantics allows predicates with different
canonical structures in their home languages to be semantically mapped to the
same ontological association. For example, a two-placed predicate 'x met y'
in language L1 could be mapped to the same association as the three-placed
predicate 'x met y at z' in language L2, as long as the users of L1 agreed
that the 'in' role was meaningful but uninteresting to them, while the users
of L2 agreed that the 'in' role was optional. This would allow the
communication of information about meetings between the two languages. In KIF
and CGs, this communication might be handled by a translation axiom such as:
L1 satisfies "Tom met Betty" if and only if L2 satisfies
"Tom met Betty somewhere".
Such variation in the details of permissible roles is likely across multiple
languages. Although KIF semantics and SUMM semantics would assign the same
truth value to both forms, the SUMM semantics provides at least a rudimentary
"explanation" of the truth of this axiom.
c) SUMM uses modal logic to represent constraints and mandatory
associations. Conceptual graphs also have monadic relations such as PSBL
(possible) and NECS (necessary) that apply to contexts. Although KIF
semantics is purely first-order, it appears to be possible to define such
modal operators at the metalevel using the metalanguage capabilities of KIF.
At the metalevel, it would be possible to designate certain propositions as
"laws"; then any proposition entailed by the laws would be defined as
"necessary", and any proposition consistent with the laws would be "possible".
At the object level, however, the laws would be syntactically
indistinguishable from any other propositions.
d) An ongoing issue has been the representation of types or sorts in KIF. As
an example, the sentence "Every cat is on a mat" could be represented by the
following conceptual graph:
[CAT: @every]->(ON)->[MAT].
In this graph, the universal quantifier @every (also representable by an
upside-down "A") has precedence over (i.e., includes within its scope) the
implicit existential quantifier for the mat. That graph would be translated
to the following formula in the current version of KIF:
(=> (cat ?x) (exists ?y (and (mat ?y) (on ?x ?y)))).
If this formula is translated back to a conceptual graph in the most direct
way, a more complex graph is obtained, even though it is provably equivalent
to the original:
[IF: (CAT)->[*x] [THEN: [*x]->(ON)->[*y]<-(MAT) ]].
In this form, the cat and the mat are represented by monadic relations
(CAT)-> and (MAT)-> instead of type labels, and an additional IF-THEN
construction has been inserted. If KIF would show types syntactically, as in
the following formula, then the original graph could be derived from it:
(forall (?x cat) (exists (?y mat) (on ?x ?y))).
This form is arguably a more readable version of KIF, and it allows a more
direct mapping to and from CGs. Mike Genesereth's earlier reluctance to
introduce types into KIF resulted from semantic concerns about how types would
interact with sets. However, if we treated this notation as a purely
syntactic extension that would not affect the KIF semantics, then he would be
willing to accept it.
This syntactic approach treats types as a notational variant of monadic
predicates. However, it cannot directly handle generalized quantifiers such
as "most", whose semantics depend on the type. For the sentence "Most cats
are on a mat", the corresponding conceptual graph [CAT: {*}@most]->(ON)->[MAT]
would have to be translated to a KIF paraphrase about the cardinality of the
set of cats compared to the cardinality of cats on mats. This compromise
should be adequate for the current ANSI standards, and it does not preclude
future extensions to support types and generalized quantifiers semantically.
e) Another ongoing issue has been the representation of contexts, as
defined by John McCarthy and implemented in Cyc by Guha. Last October,
McCarthy, Genesereth, and Sowa met to discuss the treatment of contexts in KIF
and CGs. Genesereth and Sowa came to an agreement that the KIF quoting and
metalanguage capabilities should be adequate to define the CG contexts and
that the CG contexts together with McCarthy's axioms should be able to support
the mechanisms that Guha and others are using. This belief, however, must be
verified by further work to specify the actual mappings in detail and test
them on examples from Cyc and similar applications. Some of this work may be
done by Sasa Buvac, a Ph.D. student at Stanford who is doing further work on
formalizing and applying contexts under the supervision of McCarthy and Fikes.
f) We believe that issues (a) through (e) do not deal with unsolved research
problems, and that they can be settled within the scope of the ANSI, ISO, and
KSE projects. There are, however, many research problems in nonstandard
logics and natural language semantics that are not likely to be solved in time
for the standards efforts. These include issues in situation semantics,
discourse representation theory, game-theoretical semantics, mereology,
multivalued and fuzzy logics, nonmonotonic logics, and belief revision. The
definitional and metalanguage features of KIF and CGs appear to be general
enough to provide researchers with a foundation on which to build formalisms
that address many of these issues. In any case, ANSI and ISO standards are
always evolving, and anyone who finds anything that cannot be accommodated by
the current semantic base can and should propose new extensions for the
future.
In summary, KIF, CGs, and SUMM are complementary. The definition of the
mappings between them will require some careful work for the formal
specifications, but there appear to be no major technical obstacles in doing
so. It should be possible to do that work within the framework of the
Knowledge Sharing Effort and the ANSI and ISO projects.
Signed,
Richard Fikes (fikes@ksl.stanford.edu)
James Fulton (jfulton@atc.boeing.com)
Michael Genesereth (mrg@cs.stanford.edu)
Robert Neches (neches@isi.edu)
John Sowa (sowa@turing.pacss.binghamton.edu)
_________________________________________________________________________
BIBLIOGRAPHY:
KIF:
1. M. R. Genesereth & R. E. Fikes; "Knowledge Interchange Format, Version
3.0 Reference Manual"; Report Logic-92-1, Computer Science Department,
Stanford University; June 1992. (Copies available by request to Jeanne
Beharry, Jeanne@isi.edu)
2. R. Patil, R. Fikes, P. Patel-Schneider, D. Mckay, T. Finin, T. Gruber, R.
Neches; "The DARPA Knowledge Sharing Effort: a Progress Report"; in
Proceedings of the Third International Conference on Principles of Knowledge
Representation and Reasoning; Cambridge, Massachusetts; October 25-29, 1992.
SUMM:
1. Technical Report on the Semantic Unification Meta-Model: Volume 1 --
Semantic Unification of Static Models. ISO TC184/SC4/WG3 N175. October 1992.
(Copies available from James Fulton, jfulton@atc.boeing.com)
2. "Enterprise Integration Using Semantic Unification." Proceedings of the
First International Conference on Enterprise Integration. MIT Press. October
1992. (Copies available from James Fulton, jfulton@atc.boeing.com)
Conceptual Graphs:
1. John F. Sowa, _Conceptual Structures: Information Processing in Mind and
Machine_, Addison-Wesley, Reading, MA, 1984
2. John F. Sowa, "Towards the expressive power of natural languages," in J.
F. Sowa, ed., _Principles of Semantic Networks_, Morgan Kaufmann Publishers,
San Mateo, CA, 1991, pp. 157-189.
3. T. E. Nagle, J. A. Nagle, L. L. Gerholz, & P. W. Eklund, eds.,
_Conceptual Structures: Current Research and Practice_, Ellis Horwood,
New York, 1992.