Inferential Complexity Control for Model-Based Abduction

Gregory Provan

We describe a technique for speeding up inference for model-based abduction tasks that trades off inference time and/or space for the fraction of queries correctly answered. We compile a knowledge base (for which inference may be intractable) into a set of rules that cover the most likely queries using simple criteria that do not entail extensive knowledge engineering effort, such as subset-minimal or most probable query-responses. We demonstrate this approach on the abduction task of model-based diagnosis, and show that this approach can predictably produce order-of-magnitude reductions in time and memory requirements for abductive tasks in which the queries have skewed distributions; for example, in diagnosis the faults are skewed towards being highly unlikely.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.