Knowledge Compilation
Starting with Lipski's ideas about reasoning with deductive databases,
there has been a growing trend aimed at addressing the inherent
computational complexity of many reasoning problems by compiling
knowledge bases and/or queries into restricted forms where
query-answering is easier than in the original language. In this way,
computational effort at compile time (presumably at the system's
leisure) can be traded for quick response at query time. In general,
these approaches also involve some form(s) of approximation,
because the target language for the compilation is less expressive
than the original language of the knowledge base.
CIRL
Etherington (CIRL) and Dalal (i2/Columbia U.) have developed a general
framework for approximating logical deduction that admits the development
of well behaved, tractable approximations. Theories and queries are
compiled into theories in limited vocabularies for which the deduction
problem may be easier. The resulting theories may be stronger or weaker
than the original, providing bounds on answers to queries. A range of
mechanisms is provided, allowing tradeoffs between computational effort
and accuracy, as well as control of the direction of error (i.e.,
conclusions that are too strong or too weak). By allowing for the
possibility of hierarchies of target vocabularies, we provide for the
possibility of anytime approximations, in the sense that additional
effort can be expended at query time (as time is available) to provide
better answers.
Pointers
-
Hierarchical Knowledge Bases and Efficient Disjunctive Reasoning
- This article describes a method for doing approximate reasoning
efficiently on restricted types of information. Written by Alex
Borgida and David Etherington, appeared in Proc. KR in 1989.
Compressed postscript document.
-
Tractable Approximate Deduction Using Limited Vocabularies
-
This article presents a comprehensive theoretical framework for
approximate reasoning. Written by Mukesh Dalal and David
Etherington, appeared in Proc. of the Ninth Canadian
Conference on AI, 1992. Compressed postscript document.
- List of
papers by Henry Kautz and Bart Selman
- The authors, working
at AT&T Labs, have written a number of papers on knowledge
compilation.
- Parent areas:
- Tractable Reasoning
- Subareas:
- Polytime Simplification
Back to the CIRL Overview Page.