On the Expressiveness of Rule-based Systems for Reasoning with Uncertainty

David Heckerman, Eric HorvitzAAAI 1987 · OpenReview

Abstract

We demonstrate that classes of dependencies among beliefs held with uncertainty cannot be represented in rule-based systems in a natural or efficient manner. We trace these limitations to a fundamental difference between certain and uncertain reasoning. In particular, we show that beliefs held with certainty are more modular than uncertain beliefs. We argue that the limitations of the rule-based approach for expressing dependencies are a consequence of forcing nonmodular knowledge into a representation scheme originally designed to represent modular beliefs. Finally, we describe a representation technique that is related to the rule-based framework yet is not limited in the types of dependencies that it can represent.

Introduction

In the 1970s and 80s, expert systems were primarily built on "IF-THEN" rules. As AI research moved from deterministic logic to domains characterized by uncertainty, such as medical diagnosis, researchers attempted to adapt these systems by attaching "certainty factors" (CFs) to rules. This paper, a seminal work by David Heckerman and Eric Horvitz from AAAI 1987, identifies a fundamental flaw in this approach: the assumption of modularity.

In classical logic, rules are modular; the truth of one rule is independent of others. However, in uncertain reasoning, beliefs are inherently non-modular. A new piece of evidence can drastically alter the significance of existing evidence. Forcing these complex dependencies into a rigid rule-based framework results in systems that are difficult to maintain and "unnatural" in their representation of knowledge.

Analysis of Rule-Based Limitations

The authors focus their critique on the MYCIN certainty factor model, specifically analyzing how uncertainty propagates through "inference nets." They identify two critical structures where rule-based systems struggle:

  1. Parallel Combination: Multiple independent pieces of evidence supporting a single hypothesis.
  2. Divergent Propagation: A single piece of evidence supporting multiple hypotheses.
Figure 5: Parallel combination and divergent propagation in rule-based systems.

In these structures, rule-based systems often assume independence that doesn't exist in reality. For example, in a divergent structure, two hypotheses might be mutually exclusive, but a rule-based system might update them independently, leading to inconsistent global beliefs.

The Modularity Trap and "Explaining Away"

A key insight of the paper is the concept of "explaining away." Consider a house alarm: it might be triggered by a burglary or an earthquake. If the alarm sounds, your belief in both increases. However, if you then learn an earthquake occurred, this "explains away" the alarm, and your belief in a burglary should decrease.

Rule-based systems struggle to represent this interaction without a combinatorial explosion of rules (e.g., "IF alarm AND earthquake THEN NOT burglary"). This is because they lack a mechanism to represent the conditional dependencies between causes of the same effect. The authors use thought experiments like the "Jelly Bean Problem" to illustrate how human intuition naturally handles these dependencies that rules fail to capture.

Belief Networks: A More Expressive Framework

To overcome these limitations, the authors propose Belief Networks (now known as Bayesian Networks). Unlike the flat, often unidirectional structure of inference nets, Belief Networks utilize a two-level representation:

  • Structural Level: A Directed Acyclic Graph (DAG) where nodes represent variables and arcs represent probabilistic dependencies.
  • Numerical Level: Local probability distribution tables for each node, conditioned on its parents.
Figure 2: An example of a complex inference net structure showing multiple paths of dependency.

This framework introduces a "weaker notion of modularity" based on conditional independence. A node only needs to be updated based on its direct predecessors, allowing for local updates that remain globally consistent.

Key Results and Impact

  • Representational Efficiency: Belief Networks can represent complex dependencies linearly or through small local tables, whereas rule-based systems might require an exponential number of rules to achieve the same expressiveness.
  • Knowledge Maintenance: Adding new variables is significantly easier. In a Belief Network, an expert only needs to update the local probability table for the immediate child node. In a rule-based system, one might need to revise every rule that could potentially interact with the new variable.
  • Directional Flexibility: Experts can represent dependencies in the most intuitive direction (e.g., from cause to effect), and the system can still perform inference in the opposite direction (from evidence to hypothesis).

Conclusion

While the authors acknowledge that Belief Networks require more detailed probability assessments and higher computational costs for inference, they argue that the gain in expressiveness and maintainability is essential. This paper successfully predicted the shift in AI from heuristic rule-based systems to the rigorous probabilistic frameworks that underpin modern machine learning and expert systems.

Summary updated

Abstract

We demonstrate that classes of dependencies among beliefs held with uncertainty cannot be represented in rule-based systems in a natural or efficient manner. We trace these limitations to a fundamental difference between certain and uncertain reasoning. In particular, we show that beliefs held with certainty are more modular than uncertain beliefs. We argue that the limitations of the rule-based approach for expressing dependencies are a consequence of forcing nonmodular knowledge into a representation scheme originally designed to represent modular beliefs. Finally, we describe a representation technique that is related, to the rule-based framework yet is not limited in the types of dependencies that it can represent.
BibTeX
@inproceedings{heckerman1987expressiveness,
  author = {David Heckerman and Eric Horvitz},
  title = {{On the Expressiveness of Rule-based Systems for Reasoning with Uncertainty}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1987},
  url = {https://openreview.net/forum?id=r1El9e-OWH},
}
Figure