Abstract
In the early 1980s, the utility of expert systems was often limited by the inefficiency of their user interfaces, which typically employed rigid, depth-first search strategies. This paper introduces the "merit system," a best-first search control strategy designed to prioritize questions based on their potential to influence the final outcome relative to the cost of obtaining the answer. By treating logical inference as a differentiable function, the authors demonstrate a method for significantly reducing the time required for consultations—a vital advancement for time-sensitive applications such as the Battle weapon-to-target allocation system.
Introduction
The first generation of expert systems, including MYCIN for medical diagnosis and Prospector for mineral exploration, demonstrated the power of rule-based AI. However, these systems shared a common operational bottleneck: they followed a "depth-first" questioning strategy. This approach forced users to answer long sequences of questions to satisfy a single branch of a logic tree, even if those questions had negligible impact on the final conclusion.
While a geologist might have the luxury of time, a military commander using a system like Battle—the primary application discussed in this research—might have only minutes to make critical decisions. The authors identify the need for an "intelligent" control strategy that minimizes user effort and focuses exclusively on the most pertinent information.
The Merit System: A Best-First Approach
The core contribution of this paper is the Merit System, which replaces standard tree-traversal with a global "best-first" search. The system evaluates every possible question (or "askable" proposition) in its network and selects the one with the highest Merit Value. This value is defined by the ratio of the potential change in the top-level goal to the cost of answering the question:
$$\text{Merit} = \frac{|\text{Change in Top-Level Goal Value}|}{\text{Cost of Questioning}}$$
Technical Components
To implement this strategy, the authors developed several key technical mechanisms:
- Edge-Merit: Utilizing the chain rule from calculus, the system calculates the "derivative" of an assignment function. This represents the sensitivity of a high-level conclusion (the consequent) to changes in a low-level piece of data (the antecedent). It essentially measures the "leverage" a specific piece of evidence holds over the final decision.
- Self-Merit: This is a cost-benefit ratio assigned to individual nodes by domain experts. It reflects the inherent difficulty or "cost" of obtaining a specific piece of information (e.g., a simple observation vs. a dangerous scouting mission) compared to how much that information typically shifts the system's confidence.
- Global Search and Cutoffs: Unlike depth-first systems that are locked into a specific sub-problem, the merit system constantly re-evaluates the entire network. Users can also set a merit threshold; if no remaining questions provide a benefit above that threshold, the consultation terminates early, providing the best possible answer within the time constraints.
Evaluation and Results
The authors evaluated the merit system within the context of the Battle system, a consultant developed for the U.S. Marine Corps. They also compared their merit calculations against the logic structures used in MYCIN and Prospector.
Key findings include:
- Superior Prioritization: The merit system more accurately identified the most influential questions compared to existing algorithms like Prospector’s J* algorithm.
- Efficiency Gains: The system successfully focused consultations on a small subset of critical questions, drastically reducing the total number of queries required to reach a stable conclusion.
- Mathematical Versatility: The authors demonstrated that the merit system could be generalized across various inference methods, including logical AND/OR gates and subjective Bayesian assignments.
Discussion and Limitations
While the merit system offers significant gains in efficiency, it introduces a psychological challenge known as the "jumping" problem. Because the system always seeks the highest merit value globally, it may ask about unrelated topics in rapid succession—for example, moving from a question about tank positions to a question about weather conditions. This lack of conversational flow can be disconcerting to human users compared to the thematic consistency of depth-first search.
Furthermore, the system initially relies on "self-merit" values assigned ad-hoc by experts. The authors suggest that future iterations should derive these costs and weights empirically from actual usage data. Finally, while the system saves user time, it increases computational overhead, as the merit of every node must be recalculated after every answer—a trade-off the authors deemed acceptable given the high value of human time in tactical scenarios.
Conclusion
The merit system represents a shift from exhaustive logic to pragmatic, cost-aware inference. By treating the acquisition of knowledge as an optimization problem, the authors provided a framework for expert systems to function effectively in high-stakes, time-limited environments. This work laid the groundwork for more flexible, user-centric AI interfaces that prioritize relevance over completion.
Summary updated