TL;DR
This paper introduces rule-base coverage measures (RBCMs) to address the limitations of traditional expert system evaluation, which often relies solely on test case performance. By analyzing how thoroughly test data exercises the internal logic of a rule-base, RBCMs provide a more robust assessment of system completeness and can guide improvements to both the test suite and the rule-base itself.
What Problem Does This Paper Address?
Evaluating expert systems typically involves running a set of test cases with known outcomes and comparing the system's predictions. While this functional approach can identify errors, it has a critical flaw: it doesn't guarantee that the entire rule-base has been adequately tested. This can lead to a false sense of confidence, where a system performs well on the tested portions but harbors hidden errors in untested logic. The authors argue that this lack of coverage information can result in inaccurate performance predictions and an incomplete understanding of the system's true capabilities. They aim to provide a method to systematically assess and improve this coverage.
Methods
The core of the paper's methodology lies in representing the rule-base as a directed acyclic graph (DAG). This DAG captures the logical relationships between findings, intermediate hypotheses (sub-classes), and final conclusions (classes).
The authors then propose a hierarchy of Rule-Base Coverage Measures (RBCMs), which are assessed by analyzing the execution paths generated by test cases on this DAG:
- Each-class Satisfied: Ensures at least one test path reaches each system class.
- Each-hyp Satisfied: Extends the above to ensure each sub-class is also reached.
- Each-class-every-sub: Verifies that for every possible connection between a sub-class and a class, at least one execution path exists.
- Each-class-every-finding: Similar to the above, but focuses on connections between individual findings and classes.
- All-edges Satisfied: The most stringent measure, ensuring every inference relationship (edge in the DAG) is utilized along some execution path.
Beyond these measures, the paper also introduces:
- A rule-base representation using DAGs that facilitates coverage analysis.
- Heuristics for test data selection that leverage coverage information to build more comprehensive test suites.
- Strategies for rule-base pruning by identifying unused sections.
- A complexity metric for rule-bases based on the number of execution paths.
Datasets
Not discussed in the paper. The authors mention using rule-bases that were prototypes for the AI/RHEUM system for rheumatology diagnosis in their prior work (Barr 1996) to illustrate the utility of their approach, but no specific datasets are detailed for the current paper's evaluation.
Key Insights and Ideas
- Coverage is King: Functional testing alone is insufficient. Understanding how much of the rule-base is exercised by tests is crucial for reliable evaluation.
- DAGs as a Rosetta Stone: Representing rule-bases as DAGs provides a clear, structural view that makes coverage analysis tractable and reveals logical dependencies.
- A Hierarchy of Rigor: The proposed RBCMs offer a graduated approach to coverage, allowing testers to choose a level of rigor appropriate for their needs.
- Testing Informs Improvement: Coverage analysis doesn't just evaluate; it actively guides improvements. It highlights gaps in test data, suggests new test cases, and points to potentially unnecessary rules for pruning.
- Class Dependencies Revealed: The DAG structure naturally reveals how different classes might share underlying logic, which is vital for understanding the impact of changes and for efficient testing.
Key Results
The paper doesn't present quantitative results from a specific experiment in this section. Instead, it focuses on the conceptual framework and the utility of the proposed methods. The key "results" are the introduction and definition of the RBCMs, the DAG representation, and the associated heuristics for test data selection, pruning, and complexity measurement. The authors assert that these methods provide a more objective measure of testing quality and can lead to more robust expert systems. They also highlight that their approach can provide information about rule-base structure and class dependencies without the overhead of executing the rule-base itself, unlike simulation-based methods.
Limitations and Future Work
- Current Focus: The current work is primarily focused on classification systems and propositional rule-bases.
- Dynamic Certainty Factors: The authors acknowledge that systems with dynamic computation of certainty factors would require modifications to the coverage measures and heuristics.
- Bayesian Belief Networks: Extending the approach to analyze Bayesian belief networks is suggested as a future direction, though it's noted that the bi-directional nature of arcs and contextual dependencies would significantly complicate the task.
- Quantitative Performance Prediction: The paper suggests that future work could develop quantitative performance predictions based on test case performance and the degree of rule-base coverage.
- Test Set Representativeness: Further work could also focus on developing measures for the degree to which a test set is representative of the intended application population.
Summary updated