Abstract
Traditional rule-based systems often operate under the "closed-world assumption," where any information not explicitly known is treated as false. This paper presents an alternative framework that treats knowledge acquisition as a resource-allocation problem. By integrating reasoning with a cost-benefit analysis of acquiring missing information, the proposed architecture allows AI systems to navigate environments with limited time, computational power, and human attention.
1. Introduction
In the early development of artificial intelligence, production systems typically occupied two extremes when faced with incomplete data. Some, like MYCIN, utilized backward chaining to perform exhaustive searches regardless of cost. Others simply ignored missing information, potentially leading to incorrect or suboptimal conclusions.
Mark S. Fox of Carnegie-Mellon University argues that neither approach is suitable for real-world, resource-constrained environments. In practice, evaluating a rule involves varying costs: a memory lookup is inexpensive, a database search is moderately costly, and querying a human expert is highly expensive due to "user annoyance." This paper introduces a system capable of reasoning about its own ignorance and deciding whether the cost of acquiring new knowledge is justified by its potential utility.
2. System Architecture: The Department Model
Inspired by the Hearsay-II speech-understanding system, Fox proposes an architecture organized like a functional department. This structure consists of a Manager and several Employee Knowledge Sources (KSs) that interact via a shared blackboard.
2.1 Meta-Evaluation
The core innovation is the concept of "meta-evaluation." In this framework, a rule antecedent does not merely return a Boolean value (True or False). Instead, it returns a triplet: True, False, or an Expected Resource Cost required to determine the answer. This allows the system to weigh the difficulty of finding an answer against the importance of the rule.
2.2 Function Flavors
To facilitate cost estimation, functions within rules are categorized into three distinct types:
- Low-cost Functions: These have fast, bounded execution times, such as direct string matching or local variable lookups.
- Variable-cost Functions: These involve potentially unbounded searches, such as existential quantifiers ("Does there exist an X such that...").
- Multifunctions: These represent tasks that can be solved through multiple methods of varying costs. For example, checking set membership might involve a quick cache check, followed by a hierarchical search, and finally a query to the user.
3. Knowledge Acquisition as Reasoning
When a promising rule cannot be fully evaluated due to missing data, the system does not fail. Instead, it "suspends" the current Knowledge Source and posts the missing information as a "Goal" on the blackboard.
The Manager KS then acts as a resource allocator. It examines the posted goals and determines which Employee KS to activate—such as INTROSPEC for internal inference or QUESTASK to query the user—based on the goal's utility and the remaining resource budget.
3.1 The "Annoyance" Cost
A significant insight in Fox's work is the treatment of human interaction as a nonreplenishable resource. The system explicitly factors in "user annoyance," reasoning that excessive questioning leads to a degradation in the quality of human-provided data. By quantifying this cost, the system ensures it only interrupts a human expert when the potential gain in reasoning accuracy is high.
4. Qualitative Results and Discussion
As a conceptual and architectural study, the paper demonstrates the system's logic through biological classification examples (e.g., determining if a "Lion" is a "Vertebrate"). The results show that the system can prioritize specific, complex rules even if they are initially incomplete, provided the Manager deems the cost of completion to be worth the gain in specificity.
Fox notes that the overhead of meta-evaluation is negligible if functional schemata are represented for direct execution. However, the paper acknowledges that as systems scale, the rules governing the Manager's resource assignment become increasingly complex.
5. Conclusion and Future Work
This framework moves AI toward "graceful degradation," where systems can prioritize low-cost inferences and only expend heavy resources when necessary. Future research directions include handling uncertainty and noise in perceptual data, as well as developing mechanisms for hypothesis generation—where the system "assumes" a value when resources run out, requiring sophisticated dependency tracking to manage potential contradictions.
Summary updated