Finding optimal derivation strategies in redundant knowledge bases

✍ Scribed by Russell Greiner

• Publisher: Elsevier Science
• Year: 1991
• Tongue: English
• Weight: 1014 KB
• Volume: 50
• Category: Article
• ISSN: 0004-3702
• DOI: 10.1016/0004-3702(91)90092-x

✦ Synopsis

Greiner, R., Finding optimal derivation strategies in redundant knowledge bases (Research Note), Artificial Intelligence 50 (1991) 95-115.

A backward chaining process uses a collection of rules to reduce a given goal to a sequence of database retrievals. A "derivation strategy" is an ordering on these steps, specifying when to use each rule and when to perform each retrieval. Given the costs of reductions and retrievals, and the a priori likelihood that each particular retrieval will succeed, one can compute the expected cost of any strategy, for answering a specific query from a given knowledge base. Smith [19] presents an algorithm that finds the minimal cost strategy in time (essentially) linear in the number of rules, for any disjunctive, irredundant knowledge base. This paper proves that the addition of redundancies renders this task NP-hard. Many Explanation-Based Learning systems work by adding in redundancies; this shows the complexities inherent in their task.