Abstract: This paper, originally presented at the 1988 AAAI proceedings, addresses the historical divide between symbolic reasoning and numeric probability in Artificial Intelligence. Laskey and Lehner propose a unified framework—the Belief Maintenance System (BMS)—which integrates Assumption-based Truth Maintenance Systems (ATMS) with Shafer-Dempster belief theory. By treating probabilistic weights as "belief tokens" within a logical framework, the authors demonstrate a mathematically consistent method for handling both non-monotonic reasoning and degrees of certainty.
Introduction: The Symbolic-Numeric Schism
In the late 1980s, AI research was largely bifurcated. The Symbolic Camp utilized Truth Maintenance Systems (TMS) to manage default reasoning (e.g., "Birds fly, unless they are penguins"), allowing for the retraction of conclusions when new information arrived. However, these systems lacked the ability to quantify uncertainty. Conversely, the Numeric Camp employed probability or belief functions like Shafer-Dempster to grade uncertainty but struggled with the computational overhead and the structural flexibility required to change underlying assumptions once mathematical models were established.
Laskey and Lehner argue that a comprehensive inference strategy requires both: the efficiency of symbolic logic and the nuanced grading of numeric probability.
The Belief Maintenance System (BMS)
The core innovation of this work is the mapping of Shafer-Dempster belief functions onto the architecture of an ATMS. The authors introduce several key mechanisms to achieve this integration:
- Belief Tokens: Unlike standard logical assumptions that are strictly true or false, belief tokens carry an attached probability.
- "Noisy" Rules: Uncertain rules (e.g., "If it is cloudy, it might rain") are represented by adding a validity token ($V$) to the logical antecedent. If $V$ is treated as a default, the system functions as a logic engine; if $V$ is assigned a probability, the system calculates a Shafer-Dempster belief value.
- The BMS Algorithm: The authors provide a six-step algorithm to compute the probability of a proposition's "label" (the set of environments in which it is true). This process involves conditioning the probability on current defaults and removing "nogoods" (logical contradictions).
Theoretical Unification and Results
The primary contribution of the paper is the mathematical proof that an ATMS extended with probabilistic assumptions is formally equivalent to the Shafer-Dempster theory of evidence. The belief in a proposition is defined as the conditional probability of its ATMS label, given the current defaults and the absence of contradictions:
$$Bel(node) = P(label | defaults, \neg nogoods)$$
Key Insights
- Automatic Dependency Tracking: Because the ATMS tracks the "lineage" of every conclusion via labels, the BMS automatically accounts for non-independencies, preventing the "double counting" of evidence common in other numeric systems.
- Conflict as a Diagnostic: In this system, the prior probability of a "nogood" environment serves as a quantitative measure of conflict. A high value signals that the system's default assumptions are likely incorrect and require revision.
- Efficiency via Defaults: By allowing the system to treat certain belief tokens as temporarily certain (probability of 1.0), the BMS can prune search spaces that would otherwise be computationally prohibitive for pure numeric calculus.
Limitations and Future Work
While the BMS offers a powerful theoretical bridge, the authors acknowledge significant hurdles. The algorithm's complexity is exponential relative to the number of hypothesis sets, making large-scale belief networks a challenge. Furthermore, while the system can use defaults to speed up reasoning, the paper notes that a robust theory for when to convert a probability into a default assumption remains a subject for future research. At the time of publication, the implementation was limited to small-scale problems to demonstrate formal equivalence.
Summary updated