Interlingua Nonmon Proposal and Meeting Agenda Items
Richard Fikes <fikes@sumex-aim.stanford.edu>
Full-Name: Richard Fikes
Date: Thu, 21 Mar 1991 14:02:10 PST
From: Richard Fikes <fikes@sumex-aim.stanford.edu>
Subject: Interlingua Nonmon Proposal and Meeting Agenda Items
To: interlingua-admin@vaxa.isi.edu, kr-advisory@isi.edu, grosof@ibm.com,
nado@tc.pw.com
Cc: fikes@sumex-aim.stanford.edu
Message-id: <MacMS.28002.31327.fikes@sumex-aim.stanford.edu>
Folks,
Our meeting next Thursday will be focused on four items as follows:
Presentation and review of a proposal by Vladimir Lifschitz for language
extensions to support representation of nonmonotonic knowledge.
Presentation of a proposal by Mike Genesereth and Reed Letsinger for
extending the interlingua to nth order.
Report by Ramesh Patil and myself on the status and plans for building
translators into and out of the interlingua.
Discussion of next steps for the working group.
Benjamin Grosof from IBM Watson Research and Bob Nado from Price Waterhouse
will be joining us and providing initial reviews of the nonmon proposal. The
proposal itself is appended to this message as a Tex file. I encourage you to
read and think about it before the meeting (its short).
The following is my current attendees status list:
Richard Fikes (yes)
Mike Genesereth (yes)
Danny Bobrow (yes)
Piero Bonissone (?)
Ron Brachman (no)
Ramanathan Guha (yes)
Reed Letsinger (yes)
Vladimir Lifschitz (yes)
Bob MacGregor (yes)
John McCarthy (?)
Peter Norvig (yes)
Ramesh Patil (yes)
Len Schubert (yes)
Benjamin Grosof (yes)
Bob Nado (yes)
Bob Neches (?)
Peter Patel-Schneider (yes)
Bill Swartout (?)
Gio Wiederhold (no)
Tim Finin (?)
Tom Gruber (yes)
Marty Tenenbaum (?)
Mike and I look forward to seeing you all next Thursday at 4:00 and to having a
productive meeting. Location information for the meeting to follow.
Richard
P.S. Vladimir's nonmon proposal:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%%% Macros
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
\font\eightrm=cmr10 scaled 800
\font\twelverm=cmr10 scaled \magstep1
\font\twelvebf=cmbx10 scaled \magstep1
\font\fourteenrm=cmr10 scaled \magstep2
\font\fourteenbf=cmbx10 scaled \magstep2
\countdef\sectioncount=11
\countdef\subsectioncount=13
\countdef\subsubsectioncount=15
\sectioncount=0
\subsectioncount=0
\subsubsectioncount=0
\def\sect#1{\advance\sectioncount by1\subsectioncount=0
\nobreak\bigskip\noindent{\bf\the\sectioncount. #1}\par\medskip}
\def\subsect#1{\advance\subsectioncount by 1\subsubsectioncount=0
\bigskip\noindent{\bf\the\sectioncount.\the\subsectioncount\ #1}\par
\nobreak\medskip}
\def\subsubsect#1{\advance\subsubsectioncount by 1
\bigskip\noindent
{\bf\the\sectioncount.\the\subsectioncount.\the\subsubsectioncount\ #1}\par
\nobreak\medskip}
\def\nosect#1{\bigskip\noindent{\bf#1}\par\nobreak\medskip}
\def\uncatcodespecials{\def\do##1{\catcode`##1=12}\dospecials}
\def\setupverbatim{\tt\def\par{\leavevmode\endgraf}\catcode`\`=\active
\obeylines\uncatcodespecials\obeyspaces}
{\catcode`\`=\active \gdef`{\relax\lq}}
{\obeyspaces\global\let =\ }{\obeylines\global\let^^M=\par}
\def\beginverbatim{\par\begingroup\setupverbatim\doverbatim}
{\catcode`|=0 \catcode`\\=12
|obeylines|gdef|doverbatim^^M#1\endverbatim{#1|endgroup}}
\def\bibitem#1#2{\medskip\noindent}
\def\cite#1{[#1]}
\def\begconcept{\bigskip\hrule\par\nobreak
\noindent\vrule height3pt\hfill\vrule height3pt\par\nobreak}
\def\midconcept{\nobreak\medskip\hrule\medskip\par}
\def\defconcept#1#2{\noindent{\tt #1}\hfill{\it #2}\par\nobreak}
\def\difconcept#1#2{\noindent{\tt #1}\hfill{\it #2}\par\medskip}
\def\endconcept{\nobreak\noindent\vrule height3pt\hfill\vrule height3pt\par
\nobreak\hrule\bigskip}
\countdef\eqcount=17
\eqcount=1
\def\eqn{\the\eqcount\advance\eqcount by1}
\sect{Nonmonotonicity}
Many knowlege representation and reasoning systems are capable of drawing
conclusions based on the absence of knowedge from a database. This is
nonmonotonic reasoning. The addition of new sentences to the database
may be cause for the system to retract earlier conclusions.
In some systems, the exact policy for deriving nonmonotonic conclusions is
built into the system. In other systems, the policy can be modified
by its user, though rarely within the system's knowledge representation
language (e.g. by selecting which predicates to circumscribe). Since KIF
is a knowledge representation language and not a system, it is necessary
to provide means for its user to express his nomonotonic reasoning policy
within the language itself.
To this end, we define a new type of legal list expressions---{\it default
rules}. The syntax of defaults rules is described by the following modified
BNF:
\medskip
\beginverbatim
<defrule> ::= <sentence> | (<<= <sentence> <premise>*)
<premise> ::= <sentence> | (consis <sentence>)
\endverbatim
\medskip
The sentence that follows {\tt <<=} is the {\it consequent} of the rule;
the premises that are sentences are its {\sl prerequisites}, and the
premises that have the form {\tt (consis $\phi$)} are its {\it justifications}.
Notice that every sentence $\phi$ is also a default rule. The consequent
of this default is $\phi$ itself.
For instance, the default rule
\medskip
\beginverbatim
(<<= (flies $x) (bird $x) (consis (flies $x)))
\endverbatim
\medskip
\noindent
expresses that an object can be assumed to fly if this object is known to be
a bird and it is consistent to assume that it flies.
A {\it nonmonotonic database} is a set of default rules. Since every
sentence is a default rule, every database (i.e. set of sentences) is a
nonmonotonic database. The semantics of default rules described at the end
of this section extends the notion of a model to nonmonotonic databases. We
say that a nonmonotonic database $\Delta$ {\it (nonmonotonically) entails}
a sentence $\phi$ if every model of $\Delta$ is also a model of $\phi$.
We will see that the definition of a model for nonmonotonic databases is
``nonlocal'': One cannot check whether an interpretation $i$ is a model by
looking at each default rule in isolation. This feature of the definition is
responsible for the nonmonotonic character of the new notion of entailment.
The use of {\tt consis} is the only source of nonmonotonicity in KIF.
Accordingly, a rule without justifications will be called
{\it monotonic}. This particularly simple case will be discussed first.
\subsect{Monotonic Rules}
It is clear that a monotonic rule is either a sentence or an expression of
the form
$$(\hbox{\tt <<= $\phi$ $\phi_1$ $\dots$ $\phi_n$}),$$
where $\phi$, $\phi_1,\dots,\phi_n$ are sentences. Such an expression should
be distinguished from the implication
$$(\hbox{\tt <= $\phi$ $\phi_1$ $\dots$ $\phi_n$}).$$
Monotonic rules are not sentences; they are similar to {\it inference rules},
familiar from elementary
logic. If, for instance, $\Delta$ consists of some sentences
$\Delta_0$ and one rule ({\tt <<=} $\psi$ $\phi$),
where $\phi$ and $\psi$ are sentences without free variables, then the set
of sentences entailed by $\Delta$ is the smallest set of
sentences which (i) contains $\Delta_0$, (ii) is closed
under logical entailment, and (iii) contains $\psi$ provided that it
contains $\phi$.
It is not generally true that this set contains the implication
({\tt <=} $\psi$ $\phi$).
The rationale for using monotonic rules in knowledge representation,
instead of implications, is twofold. On the one hand, the ``directed''
character of rules can simplify the task of developing efficient inference
procedures. On the other hand, in some cases, replacing {\tt <==} by
{\tt <=} would be semantically unacceptable. For instance, the rules
\medskip
\beginverbatim
(<<= (status-known $x) (citizen $x))
(<<= (status-known $x) (not (citizen $x)))
\endverbatim
\medskip
\noindent
allow us to infer {\tt (status-known Joe)} only if one of the sentences
\medskip
\beginverbatim
(citizen Joe), (not (citizen Joe))
\endverbatim
\medskip
\noindent
can be inferred.
Replacing the rules by implications would make {\tt (citizen \$x)}
identically true.
\subsect{Logic Programs}
A pure Prolog rule
$$\phi\hbox{\tt :-}\phi_1,\dots,\phi_n$$
where $\phi,\phi_1,\dots,\phi_n$ are atoms,
can be viewed as a syntactic variant of the monotonic rule
$$(\hbox{\tt <<= $\phi$ $\phi_1$ $\dots$ $\phi_n$})$$
except for two important details. First, the declarative semantics of
Prolog applies the {\it unique names assumption} to its ground
terms. If, for example, the program contains no function constants, then this
assumption can be expressed by the sentences
$$(\hbox{\tt not ($=$ $\sigma_1$ $\sigma_2$))}$$
for all distinct object constants $\sigma_1$, $\sigma_2$ in the language
of the program. Second, this semantics
applies the {\it closed world assumption} to each relation. For
a relation constant $\sigma$, this assumption can be expressed by the rule
$$(\hbox{\tt <<= (not ($\sigma$ $\nu$)) (consis (not ($\sigma$ $\nu$)))}),$$
where $\nu$ is a sequence variable. A pure Prolog program can be translated
into KIF by appending to it (i) the sentences expressing the unique names
assumption, and (ii) the default rules expressing the closed world assumption.
This method can be easily extended to programs with negation as failure.
A negative subgoal {\tt not}$\,\phi$ is represented in KIF by the premise
{\tt (consis (not $\phi$))}. (Adding {\tt consis} is necessary because,
in KIF, {\tt not} represents classical negation, rather than negation as
failure.)
\subsect{Circumscribing Abnormality}
Extending a set of sentences by the closed world assumption for some relation
constant $\sigma$, expressed by a default rule as shown above,
has the same effect as circumscribing $\sigma$ (with all object, function
and relation constants varied). In particular, circumscribing
abnormality can be expressed by the default rule
$$\hbox{\tt (<<= (not (ab }\nu\hbox{\tt )) (consis (not (ab }\nu\hbox{))))}.$$
Consider, for instance, the nonmonotonic database that contains, in addition
to this standard default, two facts: {\tt (bird tweety)} and
\medskip
\beginverbatim
(<= (flies $x) (bird $x) (not (ab aspect1 $x)))
\endverbatim
\medskip
\noindent
(birds fly unless they are abnormal in {\tt aspect1}).
This database nonmonotonically entails the conclusion
that everything is {\it not} abnormal, including {\tt tweety}:
\medskip
\beginverbatim
(not (ab $x))
\endverbatim
\medskip
>From this, we can conclude that {\tt tweety} flies.
Suppose, on the other hand, that our database includes also the fact
that {\tt tweety} is abnormal in {\tt aspect1}:
\medskip
\beginverbatim
(ab aspect1 Tweety)
\endverbatim
\medskip
In this case, we can no longer infer that {\tt tweety} is not abnormal, and,
therefore, we cannot conclude that {\tt tweety} is a flier. Note, however,
that we have {\it not} asserted that {\tt tweety} cannot fly; we have only
prevented the default rule from taking effect in this case.
\subsect{Semantics of Default Rules}
Recall that the truth value of a sentence is defined relative to an
interpretation $i$ and a variable assignment $v$. To define the truth
value of a premise in a default rule, we need to
select, instead of a single interpretation $i$, a {\it set} of
interpretations---the interpretations that are considered ``possible.''
In the following definition, $I$ is a set of interpretations which all have
the same universe of discourse $O$, and $v$ is a variable assignment with
this universe. We consider prerequisites and justifications separately.
\begconcept
\defconcept{\tt $\phi$}{premise}
The truth value of a prerequisite is {\it true}
if and only if it is true for at every ``possible'' intepretation.
$$t_{Iv}(\phi)=\cases{
true&$\forall i\in I\;t_{iv}(\phi)=true$\cr false&otherwise\cr}$$
\midconcept
\defconcept{\tt (consis $\phi$)}{premise}
The truth value of a justification is {\it true}
if and only if its second term is true for at least one ``possible''
intepretation.
$$t_{Iv}(\hbox{\tt (consis $\phi_i$)})=\cases{
true&$\exists i\in I\;t_{iv}(\phi)=true$\cr false&otherwise\cr}$$
\endconcept
Let $\Delta$ be a nonmonotonic database. We define when a set $I$ of
interpretations is ``a set of possible worlds'' for $\Delta$, by means
of the following fixpont construction. Consider a universe of discourse $O$;
by a {\it world} we understand an interpretation with the universe $O$.
Let $I$ be a set of worlds. Consider the largest set $I'$ of worlds such
that, for each default $\delta\in\Delta$ and each variable assignment $v$ with
the universe $O$, the following condition holds:
If the truth value of every prerequisite of $\delta$ for $I'$ and $v$ is
$true$, and the truth value of every justification of $\delta$ for $I$ and
$v$ is true, then the truth value of the consequent of $\delta$ for
$I'$ and $v$ is $true$. (This $I'$ always exists.) If $I'=I$, then we say
that $I$ is {\it a set of possible worlds} for $\Delta$. Typically, a
nonmonotonic database has many sets of possible worlds; it is clear, for
instance, that any two interpretations with different universes cannot
belong to the same set of possible worlds.
An interpretation $i$ is a {\it model} of $\Delta$ if it belongs to some set of
possible worlds for $\Delta$.
-------