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.
Page content:
- Episodic Logic
- EPILOG System
- EPILOG Sample Output
- Download EPILOG
- Publications
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.
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 the
infamous Schubert's 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.
Last modified: Wednesday, 17-Oct-2007 08:19:42 EDT
Realized on November 9, 2000 by A. Kaplan and updated on January
23, 2005 by L.K.Schubert