This classic 1986 paper from the Stanford Medical Computer Science Group bridges the gap between the "rules of thumb" used in early Artificial Intelligence and the rigorous mathematical framework of Decision Theory. It provides a formal method for knowledge engineers to justify, evaluate, and understand the limitations of the heuristics that power expert systems.
The Problem: "Compiled" Knowledge
In the 1980s, expert systems like MYCIN were built using heuristics: situation-to-action rules provided by human experts (e.g., "If the patient is under 8, don't use tetracycline"). While effective, these rules were "compiled" knowledge—they didn't explicitly state the tradeoffs involved, such as the risk of tooth staining versus the effectiveness of the drug.
The authors identify a major gap in knowledge engineering: there was no formal way to assess the merit of an individual rule. Without a formal model, it was impossible to know how often a heuristic might be wrong, how much it actually improved system performance, or how to justify it beyond "the expert said so."
Methodology: Formalizing Tradeoffs
The authors propose applying Expected Utility Theory to individual heuristics. Their approach involves three main steps:
- Problem Formulation: Converting a rule into a decision tree that includes alternative actions, potential outcomes (chance nodes), and the desirability of those outcomes (utilities).
- Expected Utility (EU) Calculation: Calculating the value of a plan by multiplying the probability of each outcome by its utility: $Expected Utility = \sum p(O_i) \times U(O_i)$.
- Sensitivity Analysis:
- One-way Sensitivity Analysis: Varying a single parameter to find the "threshold value" where the recommended action would change.
- Monte Carlo Simulation: Randomly sampling all parameters simultaneously from their probability distributions to estimate the "error rate" of the heuristic—the percentage of cases where the rule's recommendation is sub-optimal.
Case Study: Tetracycline vs. Erythromycin
The paper uses a case study based on a real-world rule from the MYCIN system. The case involves an 8-year-old male with a suspected infection where the choice is between Tetracycline (highly effective but causes tooth staining) and Erythromycin (slightly less effective but safer). The probabilities and utilities used in the model were assessed from a physician.
Key Results and Insights
The analysis provided a rigorous quantitative justification for the heuristic.
- Quantitative Justification: In the tetracycline case study, the expected utility of using the alternative drug (erythromycin) was 0.83, while tetracycline was 0.63, formally justifying the MYCIN rule to avoid tetracycline.
- Threshold Discovery: One-way sensitivity analysis revealed that the probability of dental staining would have to drop from the estimated 0.3 to below 0.025 before tetracycline became the better choice.
- Error Rate Estimation: Using Monte Carlo simulation, the authors found that the probability of the tetracycline heuristic being "wrong" for a patient was less than 1 in 100,000, providing a rigorous metric for the rule's reliability.
Heuristics as Compiled Plans
A heuristic isn't just a fact; it's a pre-calculated decision that balances risks and benefits. Formalizing it reveals the "hidden" logic of the expert. The authors define the "power" of a heuristic by its error rate. If a Monte Carlo simulation shows a rule is optimal in 99.9% of cases, it is a "powerful" heuristic.
Limitations and Future Work
While powerful, this approach has drawbacks:
- Computational Expense: Performing a full decision-theoretic analysis for every rule in a large expert system is "expensive and difficult."
- Knowledge Acquisition Burden: The method requires experts to provide precise numerical probabilities and utilities, which can be difficult and prone to human bias.
- Modularity Issues: Decision theory shows that rules are often interconnected, and violating independence assumptions can lead to performance issues.
The authors envision a hybrid system where heuristics provide computational economy for standard cases, while decision theory is used to justify those rules or handle complex, unusual tradeoffs.
Summary updated