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 Contents

  1. Episodic Logic
  2. The EPILOG System
  3. EPILOG Sample Output
  4. Download EPILOG
  5. Publications

See Also

Authors

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:

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

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., à 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

The most important development goals for EPILOG, over the next few years, are

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.

  1. 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.
  2. 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.
  3. 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 available for download (last updated 2005-06-22). 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.

Epilog 2 (as presented in recent work by Morbini & Schubert) is not available for public download currently.

Publications

A good introduction to Epilog is:

Other publications about Epilog and Episodic Logic include:

2011

2010

2009

2008

2007

2005

2004

2003

2000

1996

1995

1994

1993

1992

1990

1989

For more publications, see Lenhart Schubert’s homepage.

Website created by Aaron Kaplan in 2000. Last updated by Jonathan Gordon, 2013-01-03.