TL;DR
This paper introduces a novel approach for rule-based systems to reason effectively even when faced with incomplete information and limited computational resources. It achieves this by integrating reasoning with dynamic knowledge acquisition, allowing the system to intelligently decide how and when to acquire missing information, rather than simply failing or making assumptions.
What Problem Does This Paper Address?
Traditional rule-based systems often struggle when their knowledge bases are incomplete. When a rule's antecedent (the "IF" part) cannot be fully evaluated because some information is missing, systems typically face a dilemma: either expend potentially vast resources to acquire the missing information, or ignore the rule and risk an incomplete or incorrect conclusion. This paper addresses the challenge of reasoning in "resource-limited environments" where such exhaustive searches are infeasible. The core problem is how to gracefully handle missing information by making intelligent decisions about resource allocation for knowledge acquisition, rather than treating missing information as a simple "false" or an insurmountable obstacle.
Methods
The paper proposes a "Hearsay-II-like" system architecture where knowledge is organized into "knowledge sources" (KS), each acting as a production system. The key innovation lies in the meta-evaluation process for rule antecedents. Instead of a binary true/false evaluation, antecedents are evaluated using minimal resources first. If this fails, the system doesn't immediately give up. Instead, it estimates the expected resource cost to acquire the necessary information.
If a rule's antecedent is only partially evaluated or requires further information, the system posts a goal for that missing information. This goal is then managed by a manager KS, which has a global view of the system's resources and other KS capabilities. The manager decides:
- Whether the goal is worth pursuing.
- How many resources to allocate.
- Which KS is best suited to acquire the information.
- When to abandon the pursuit.
This allows for a dynamic and intelligent integration of reasoning and knowledge acquisition, where the system reasons about the acquisition process itself.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Reasoning about Resource Constraints: The most significant insight is the shift from simply executing rules to reasoning about the cost and feasibility of evaluating them. This meta-level reasoning is crucial for resource-limited environments.
- Intelligent Knowledge Acquisition: The system doesn't just acquire knowledge; it intelligently decides what knowledge to acquire, how to acquire it (e.g., through inference, asking the user), and when to stop trying.
- Managerial Control: The introduction of a manager KS provides a centralized point for resource allocation and task delegation, enabling more strategic decision-making than decentralized approaches.
- Hypothesis Generation: The ability to assume a condition is true and later retract it if inconsistencies arise is a powerful mechanism for dealing with uncertainty and incomplete information.
- Cognitive Economy: The paper implicitly advocates for "cognitive economy," a principle of efficiently using limited cognitive resources, by prioritizing actions based on estimated costs and benefits.
Key Results
The paper describes the system's behavior through an example involving classifying a "Lion" as a "Vertebrata."
* When evaluating the rule (X € VERTEBRATA), the system first tries low-cost methods (equality check, shallow ISA hierarchy search).
* When these fail, it assigns an expected cost of 30 seconds to evaluate the € function.
* The conflict resolution mechanism chooses a more specific rule (R2) over a general one (R1) because it has more subparts matched and is more specific.
* If a rule's antecedent cannot be evaluated, the system suspends the KS and posts a goal. For example, the €-GOAL is posted with an expected cost of 30 seconds and a budget of 50 seconds.
* The manager KS then assigns this goal to either INTROSPEC (which uses a rule matching approach with a cost of 25 seconds) or QUESTASK (which asks the user with a cost of 5 questions). The manager chooses based on available resources and the cost of each approach.
Limitations and Future Work
- Meta-evaluation Overhead: The paper acknowledges that the meta-evaluation process itself incurs a cost (interpreting function schemata). However, it notes that in their KS system, this overhead is minimized by making functional schemas directly executable.
- Manager Complexity: The increased complexity of the manager's rules to handle task selection, employee selection, and resource assignment is noted as a necessary expense, drawing parallels to complex perceptual systems like Hearsay-II.
- Future Work: The paper suggests that the manager can postpone evaluating antecedents to focus on more important problems, implying a need for sophisticated prioritization mechanisms. It also touches upon the need for dependency analysis capabilities when hypotheses are formed.
Summary updated