Finding Optimal Derivation Strategies in Redundant Knowledge Bases
- Russ Greiner, Dept of Computing Science; PI of AICML
A backward chaining process uses a collection of rules to reduce a given goal to a sequence of data-base 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 cite{ControlBC} 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.
Citation
R. Greiner. "Finding Optimal Derivation Strategies in Redundant Knowledge Bases". Artificial Intelligence (AIJ), 50(1), pp 95--115, August 1991.| Keywords: | Redundant, Knowledge Bases, EBL, machine learning |
| Category: | In Journal |
BibTeX
@article{Greiner:AIJ91,
author = {Russ Greiner},
title = {Finding Optimal Derivation Strategies in Redundant Knowledge Bases},
Volume = "50",
Number = "1",
Pages = {95--115},
journal = {Artificial Intelligence (AIJ)},
year = 1991,
}Last Updated: April 24, 2007Submitted by Russ Greiner
