Inferential Complexity Control for Model-Based Abduction

Principles of Knowledge Representation and Reasoning: Proceedings of the Ninth International Conference (KR2004)

Volume

No

Principles of Knowledge Representation and Reasoning: Proceedings of the Ninth International Conference (KR2004)

Contents

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.