Episodic Logic &
EPILOG
Episodic Logic is a knowledge representation developed for use as a
semantic theory for natural language understanding.
EPILOG is the computational system for Episodic
Logic (EL). It is a powerful knowledge management and
inference system. The EPILOG family has been
under development at the University of Alberta and University of
Rochester for over twenty years, with the financial support from the
Boeing Co. in Seattle during 1987–1992. (The first delivery of the
EPILOG system was in 1990.)
EPILOG is now available for download.
Authors:
- Lenhart K.
Schubert
- Stephanie Schaeffer (developed most of the EPILOG code and documentation)
- Chung Hee Hwang (developed much of EL and contributed to EPILOG)
- Johannes de Haan (contributed to EPILOG
and the documentation)
- Aaron Kaplan (contributed to EPILOG
and the documentation)
- Fabrizio Morbini
(currently handling bug registry and repairs)
For further information please email to:
epilog AT
cs DOT rochester DOT edu
Episodic Logic (EL)
The knowledge representation
Episodic Logic
(
EL) was developed for use as a semantic representation
for natural language understanding, supporting general inference. It was
designed to meet the following requirements:
- Expressive adequacy: The representation language should be
powerful enough to allow us to represent various kinds of constructs
found in English, as well as the nuances in naturally occurring
sentences.
- Derivational adequacy: The representation language should
support a simple, systematic derivation of meaning from English surface
structures.
- Semantic adequacy: The meaning of the representation language
itself should be precisely defined, i.e., it should have a denotational
semantics.
- Inferential adequacy: The inference mechanisms should enable at
least those inferences that people make without conscious mental
effort, including uncertain inferences.
Recently, KRS (knowledge representation systems)
seem headed for greater expressiveness and generality, coming closer to
matching the resources of NL (natural language). In
part this is driven by the growing emphasis on sharing ontologies and
KBs (knowledge bases). It is also driven by the growing
emphasis on access to KBs via natural,
discourse-like interaction. EL is “natural” in the sense that it
allows direct expression of many NL constructs. This makes it
relatively easy to map NL to EL and vice versa, to browse a KB, and to
formulate commonsense inferences.
The development of EL was influenced by Montague-style logical
form, Turner and Chierchia’s type theory, Barwise and Perry’s situation
theory, and Kamp and Heim’s discourse representation theory
(DRT),
among others. More particularly, EL is a first-order intensional logic
featuring
- explicit episodes associated with arbitrary sentences (wffs)
- general restricted quantifiers
- lambda abstraction
- sentence and predicate modifiers (similar to adjectives and
adverbials)
- sentence and predicate nominalization (i.e., reification)
operators
- a DRT/DPL-like mechanism for making referential connections
- statistical conditionals and epistemic probabilities
The most distinctive aspect of EL is its use of episodes, which are
similar to situations in situation semantics. However, while the latter
are often thought of in terms of the information (infons) they carry,
episodes are thought of as entities existing in the world, as real as
cats, clouds, or corporations and describable in an unlimited variety
of ways, either as a whole or in part. The notion of an episode
subsumes the notion of events that is used in many representations
based on Davidson, because an event is a particular kind of episode.
The EL representation has been successfully used in various domains:
fairy tale and other kinds of narrative domains. It was also used in TRAINS-93 (an
interactive, conversational planning assistant developed at the
University of Rochester 1990–1994), and proved well-suited to this
domain despite the obvious differences from the narrative domains it
was originally developed for.
Contrary to a widespread myth that a rich syntax is an impediment
to effective inference, EL readily lends itself to inference. The
successful implementation of EL in the EPILOG system
proves this. Restricted representations with efficient proof methods
are used extensively by EPILOG as
“subroutines” (specialists), but not
as the central representation for NL content or commonsense knowledge.
To become a basis for well-founded implementations, EL still needs a
lot of further refinement—especially in the model theories and proof
theories—but our success to date has convinced us that we are on the
right track.
The EPILOG System
EPILOG is the computational system developed
for Episodic Logic (EL), a
very expressive, NL-like logic. EPILOG is a powerful
knowledge management and inference system allowing data-driven
inference, goal-driven inference, and featuring integration with about
a dozen specialist modules for accelerating temporal, taxonomic,
partonomic, set-theoretic, numeric, and other special types of
inference. Its goals are to support NLU (natural language
understanding) and commonsense reasoning using large KBs of commonsense
knowledge. EPILOG is fully implemented, and
has been demonstrated for story fragments, terrorist stories, aircraft
maintenance reports, and the notorious Steamroller theorem proving problem
(see EPILOG Sample
Output).
EPILOG uses input-driven inference for
understanding and goal-driven inference for question answering and
problem solving. Both modes are based chiefly on replacing positively
embedded subformulas by their consequences, and negatively embedded
formulas by their anticonsequences (this subsumes resolution, but is
not based on skolemization). Forward inference termination is by probability
threshold and “interestingness”. General inference is supported
by efficient, uniformly integrated specialists for time, taxonomies,
parts, colors, episodes, sets, numbers, strings, schematic axioms, etc.
These perform simplification, factoring, and the equivalent of narrow
theory resolution. The key to scalable knowledge access and inference
is an indexing scheme based on topic (predicate), participant type,
role-triples, plus mechanisms for “hierarchy climbing”
and modal embedding.
The KRS design was inspired originally by the semantic net
literature (Quillian, Shapiro, Rumelhart, etc.) The inference
techniques were originally resolution-based, but were subsequently
influenced by natural deduction techniques (e.g., a la F. J.
Pelletier). However, our style of “polarity-based” inference
could be said to hark back to pre-Fregean “natural logic”
(see van Benthem’s discussion in his Essays in Logical Semantics).
The integration of the specialists benefited from early work on
procedural attachment, and later from Stickel’s notion of theory
resolution. Probability chaining is based on work on probabilistic logics
(Bacchus, Halpern, etc.); evidence combination is Bayesian at times, and
more ad hoc at other times. The knowledge accessing structure was inspired
by the semantic net literature; the notion of “topic
hierarchies” used in accessing turns out to be similar to
Pustejowsky’s more recent notion of “qualia”.
We see general-purpose KRSs as providing the “commonsense
core” of various application systems, containing the knowledge
essential to natural interaction with computers, regardless of the
application. The core KRS could mediate access to many special-purpose
applications packages, based on knowledge about the functionality of
these packages and about the goals of the user. Some of the most urgently
needed research concerns the interface between KRSs and the user/world.
A KRS, no matter how elegant and powerful its mechanisms may be, is useless
if it is hard to build up a substantial knowledge base, and hard to
communicate with the system. Thus we need research on how KRSs can
learn from large text corpora and “by being told” (and by making
generalizations, etc.), so that we can begin to break through the
knowledge bottleneck. And we need research on more effective, natural
interaction with KRSs. Both goals require good ways of transducing
between the KR and ordinary language (as well as other media—graphics,
menus, gestures, etc.)
Important research topics in inference include
- Better-founded, more complete, incremental methods of
“adjudicative inference”: computing propositional probabilities or
probability bounds for arbitrary wffs in the light of various lines of
uncertain inference supporting that wff, or its negation;
- More general, more effective methods of planning (and plan
recognition); planning should be probabilistic and incremental. This is
crucial not only for systems specifically designed to help with
planning, but any intelligent system that can communicate naturally
with a user;
- Better-founded, more complete methods of predicting
propositional attitudes (beliefs, plans, desires, etc.) of other agents
who “think like us” based on what we know they know, and on what we
know they find out (through perception, being told, etc.);
- Further development of “general-purpose specialists”
(e.g., for
envisioning dynamic, interacting objects) and integration with general
reasoners; the completeness problems that arise for hybrid systems are
very hard.
The most important development goals for EPILOG, over the next few
years, are
- the addition of incremental, probabilistic planning
capabilities, based in part on stored plans that are represented and
indexed much like facts (with goals providing indexing keys), and on
methods for synthesizing, modifying, and combining plans;
- developing more complete, better-founded (Bayesian-network-like,
or entropy-maximizing) probabilistic inference methods; and
- building sufficiently large core KBs to allow knowledge
bootstrapping via NL.
EPILOG Sample Output
Some sample sessions with EPILOG are
available below: two from the NLU domain and one from a problem solving domain.
Each sample consists of the input and output files to and from
EPILOG. The input file contains, among other things, meta knowledge
(about predicates, ontology, grammar, etc.), meaning postulates, world
knowledge, and a story fragment or problem in Episodic Logic form,
followed by optional questions. (The software for translating English
to EL has been partially developed but not been connected to EPILOG
yet.)
The output shows how EPILOG processes the story, especially, what
kind of forward inference (spontaneous inference) it makes. The
inferred formulas have probabilities attached. They are the lower bound
on the epistemic probability; i.e., EPILOG’s degree of belief in the
formula it has inferred. EPILOG is capable of saying what it “hears” or
“infers” in English (in a somewhat crude way). So after reading each
world knowledge or story sentence, as well as after inferring a
formula, EPILOG makes an attempt to say it in English. In case the
input file contains questions, the reasoning process of EPILOG to
answer them is also shown in the output file.
- Excerpt from LRRH: This example shows how EPILOG
“understands”, or “makes sense of”, the following
sentence from the Little Red Riding Hood story:
- The wolf would have very much liked to eat her [Little
Red Riding Hood], but he dared not do so on account of some woodcutters
nearby.
- Terrorist story: In this example, EPILOG reads the
following mini-story from the Wall Street Journal, and answers
the questions posed to it (both Yes/No and Wh-), demonstrating that it
actually "understood" the story.
- A bomb exploded in the office of an [Afghan] guerrilla
group in a crowded Shiite Moslem neighborhood in Beirut.
- Steamroller problem: In this example, EPILOG solves Schubert’s infamous Steamroller problem described below. Even
though EPILOG was not developed as a general problem solver, it turned
out to be a fairly good one.
- Wolves, foxes, birds, caterpillars, and snails are
animals, and there are some of each. Also there are some grains, and
grains are plants.
- Every animal either likes to eat all plants or all
animals much smaller than itself that like to eat some plants.
- Caterpillars and snails are much smaller than birds,
which are much smaller than foxes, which in turn are much smaller than
wolves. Wolves do not like to eat foxes or grains, while birds like to
eat caterpillars but not snails. Caterpillars and snails like to eat
some plants.
- Is there an animal that likes to eat a grain-eating
animal?
Downloading EPILOG
EPILOG, a program maintained in Allegro
Common Lisp, is now available for download. After unpacking the
tarred, gzipped file, read the README file for pointers to
documentation on compiling and running the system.
EPILOG’s time specialist, TG-I, is
not currently available in stand-alone form, but there is a stand-alone
version of TG-II,
a newer time specialist also based on timegraphs, but intended for
non-incremental use and lacking the ability to handle metric bounds on
times and durations. On the other hand, TG-II builds quasi-optimal
graphs, is faster, and handles time point relations of form x ≠ y,
point-interval exclusion and interval disjointness relations, in
addition to strict and nonstrict time-point ordering (with assurance of
completeness). See the readme
file for that package.
Please send correspondence regarding EPILOG to epilog AT
cs DOT rochester DOT edu.
Related Publications
- C. H. Hwang, A Logical Approach to Narrative Understanding.
Ph.D. thesis, U. of Alberta, 1992.
- L. K. Schubert and C. H. Hwang,
“Episodic Logic meets Little Red Riding Hood: A comprehensive, natural
representation for language understanding”, in L. Iwanska and S. C.
Shapiro (eds.), Natural Language Processing and Knowledge
Representation: Language for Knowledge and Knowledge for Language,
MIT/AAAI Press, Menlo Park, CA, and Cambridge, MA, 2000, 111–174. See MIT
Press website for the book.
- L. K. Schubert, “Some knowledge
representation and reasoning requirements for self-awareness”,
2005 AAAI Spring Symposium on Metacognition in Computation,
Stanford Univ., March 21–23, 2005.
- David Ahn, The Role of Situations and Presuppositions in
Restricting Adverbial Quantification, Ph.D. thesis, Department
of Computer Science, Univ. of Rochester, Rochester, NY, March 2004.
- D. Ahn and L. K. Schubert, “A binary modality for reasoning about
conjoined situations in a hybrid logic”, Proc. of the Workshop on
Methods for Modalities 3 (M4M 3), LORIA (INRIA Lorraine), Nancy,
France, Sept. 22–23, 2003.
- David Ahn, “A dynamic situation logic”, in Harry Bunt,
Ielka van der Sluis, and Roser Morante, editors, Proceedings of
IWCS-5, 2003.
- L. K. Schubert,
“The situations we talk about”, in J. Minker (ed.),
Logic-Based Artificial Intelligence, Kluwer, Dortrecht,
2000, 407–439.
- A. N. Kaplan, “Reason maintenance in a hybrid reasoning
system.” Journal of Language and Computation,
1(2): 227–240, 2000.
- A. N. Kaplan, A
Computational Model of Belief. Ph.D. thesis, University of
Rochester, 2000.
- D. R. Traum, L. K. Schubert, M. Poesio, N. G. Martin, M. Light,
C. H. Hwang, P. Heeman, G. Ferguson, and J. F. Allen. “Knowledge
representation in the TRAINS-93 conversation system.”
Internat. J. of Expert Systems, Special Issue on Knowledge
Representation and Inference for Natural Language Processing, v. 9
(1996).
- J. F. Allen, L. K. Schubert, G. Ferguson, P. Heeman, C. H.
Hwang, T. Kato, M. Light, N. G. Martin, B. W. Miller, M. Poesio,
and D. R. Traum. “The TRAINS Project: A case
study in building a conversational planning agent.” J. of
Experimental & Theoretical AI, v. 7 (1995): 7–48.
- C. H. Hwang and L. K. Schubert. “Interpreting tense,
aspect and time adverbials: A compositional, unified approach.”
Proceedings, 1st Internat. Conference on Temporal Logic (ICTL
94), July 11–14, 1994, Bonn, Germany. pp. 238–264.
- M. Poesio, J. F. Allen, G. Ferguson, P. Heeman, C. H.
Hwang, T. Kato, N. Martin, L. K. Schubert, and D. R. Traum.
“Knowledge Representation in the TRAINS System.”
AAAI 1994 Fall Symposium on Knowledge Representation for Natural
Language Processing in Implemented Systems, New Orleans, LA, November
4–6, 1994.
- C. H. Hwang and L. K. Schubert. “Episodic Logic: A
comprehensive, natural representation for language understanding.”
Minds & Machines, v. 3 (1993): 381–419.
- C. H. Hwang and L. K. Schubert. “Episodic Logic: A
situational logic for natural language processing.” Situation
Theory and its Applications, v. 3 (edited by P. Aczel, D. Israel, Y.
Katagiri, and S. Peters). CSLI, Stanford, CA. 1993. pp. 303–338.
- C. H. Hwang and L. K. Schubert.
“Meeting the interlocking needs of LF-computation, deindexing, and
inference: An organic approach to general NLU”. Proceedings,
13th Internat. Joint Conference on Artificial Intelligence (IJCAI 93),
August 29–September 3, 1993, Chambery, France. pp. 1297–1302.
- C. H. Hwang and L. K. Schubert.
“EL: A formal, yet natural, comprehensive knowledge
representation”. Proceedings, 11th National Conference on
Artificial Intelligence (AAAI-93), July 11–15, 1993,
Washington, DC. pp. 676–682.
- S. Schaeffer, C. H. Hwang, J. de Haan, and L. K. Schubert.
The User’s Guide to EPILOG
(Prepared for the Boeing Co., Seattle), U. of Alberta, Canada, 1993.
- A. Namioka, C. H. Hwang, and S. Schaeffer. “Using the inference
tool EPILOG for a message processing
application.” Internat. J. of Expert Systems, v. 5 (1992):
55–82.
- C. H. Hwang and L. K. Schubert.
“Tense trees as the ‘fine structure’ of discourse”.
Proceedings, 30th Annual Meeting of the ACL, June 29–July 2,
1992, Newark, DE. pp. 232–240.
- L. K. Schubert and C. H. Hwang. “Picking reference
events from tense trees: A formal, implementable theory of English
tense-aspect semantics.” Proceedings, DARPA Workshop on Speech
and Natural Language, June 24–27, 1990, Hidden Valley, PA.
pp. 34–41.
- L. K. Schubert and C. H. Hwang. “An Episodic knowledge
representation for narrative texts.” Proceedings, 1st Internat.
Conference on Principles of Knowledge Representation and Reasoning (KR
’89), May 15–18, 1989, Toronto, Canada.
pp. 444–458.
- L. K. Schubert, S. Miller, and C. H. Hwang. The
User’s Guide to ECOLOGIC (Prepared for the Boeing Co.,
Seattle), U. of Alberta, Canada, 1989.
For more publications, see Lenhart Schubert’s
homepage.
Last modified: 2010-02-17 by J. Gordon.
Realized on November 9, 2000 by A. Kaplan and updated on January
23, 2005 by L. K. Schubert