Next: Using Abduction for Up: Abduction Previous: Abduction

Bottom-up Abduction

In order to achieve abduction, deduction techniques can be employed in a top-down as well as in a bottom-up manner: with top-down reasoning one skips some subgoals instead of proofing them if they are in the set of abducibles. If the goal only consists of abducibles, top-down reasoning stops. The set of remaining goals is the set of hypotheses explaining the toplevel goal.

On the other hand, there are a number of optimization strategies that allow query answering by bottom-up evaluation. Generalized Magic Sets rewriting is such an optimization technique that has been developed for query answering in deductive databases [\protect\citeauthoryearBeeri and Ramakrishnan1991]. We have adapted this rewriting technique to achieve bottom-up abduction of Horn knowledge bases [\protect\citeauthoryearBurgun and Hinkelmann].

The scheme of our abduction rewriting approach is presented in Fig. 6. Given a theory and a goal we first perform a Generalized Magic Sets rewriting. In a second step we further transform this rulebase with respect to the set of abducibles. Evaluating the resulting abduction rulebase by bottom-up evaluation will compute all abductive solutions.

The transformation can be regarded as a specialization of a partially evaluated upside-down meta-interpreter originally presented by Stickel [\protect\citeauthoryearStickel1991] (see also [\protect\citeauthoryearInoue et al.1993]). Compared to Stickel's approach we have a number of advantages:

-
Only the rules of the knowledge base are transformed; rewriting of the ground facts in the knowledge base is avoided. This is very important when the ground facts change frequently or if they reside on secondary storage like in deductive databases.
-
There is no need for enumeration of all the possible hypotheses. Thus, the approach is applicable if the set of possible hypotheses is infinite.
-
Hypotheses will be derived only if they are not already contained as facts in the knowledge base.
-
By normalization meta predicates are removed, resulting in improved performance.

Most important: this set-oriented approach is usable also for large sets of facts. This is supports our objective to develop techniques suitable not only for toy examples but also for complex real world problems with databases and large knowledge bases.



Next: Using Abduction for Up: Abduction Previous: Abduction


Harold Boley & Stefani Possner (possner@dfki.uni-kl.de)