Abstract
This seminal 1986 paper by Peng and Reggia provides a formal mathematical bridge between the intuitive heuristic of "Occam’s Razor" (simplicity) and objective probability in AI diagnostics. By integrating Bayesian likelihood into "Parsimonious Covering Theory," the authors demonstrate the specific conditions under which simpler explanations are mathematically more likely to be true, transforming a subjective preference into a rigorous diagnostic strategy.
Introduction
When an AI system attempts to diagnose a problem—whether in clinical medicine or complex machinery—it frequently encounters a "combinatorial explosion." With dozens of potential disorders and numerous manifestations, the number of possible combinations that could explain a set of symptoms is often astronomical.
Historically, AI researchers relied on "parsimony" to prune these possibilities, focusing on the "simplest" explanations. However, "simplicity" remained a subjective term: was it the fewest number of disorders, or an irredundant set where every disorder is necessary? Peng and Reggia sought to determine if these heuristics were mathematically sound or merely convenient guesswork.
Methods: Parsimonious Covering Theory
The authors utilize Parsimonious Covering Theory, a formal model for diagnostic problem-solving. They define a diagnostic problem as a 4-tuple consisting of:
- D: A set of possible disorders.
- M: A set of possible manifestations (symptoms).
- C: A causal relation (which disorder can cause which symptom).
- M+: The specific symptoms actually observed in a case.
The core innovation is the integration of a Bayesian likelihood measure ($L$) into this symbolic model. Instead of binary causal links, they assign a prior probability to each disorder and a causal strength (the frequency with which a disorder triggers a specific symptom). This allows for the calculation of the relative likelihood of any given set of disorders ($D_I$) being the true cause of the observed symptoms ($M^+$).
As a theoretical work, the paper uses a "tiny abstract diagnostic problem" (a toy model with 4 disorders and 4 manifestations, as illustrated in Figure 1) to provide a proof-of-concept for their mathematical derivations.
Key Insights: Simplicity as a Proxy for Probability
The paper proves that "irrelevant" explanations—those containing disorders that do not cause the observed symptoms—are mathematically much less likely than "relevant" ones, provided the disorders themselves are relatively rare.
The Math Behind Irredundancy
An "irredundant" cover is a set of disorders where removing any one of them would leave at least one symptom unexplained. The authors show that if prior probabilities of disorders are low, the most probable explanation is almost always an irredundant one. This provides a formal justification for one of the most common heuristics in diagnostic AI.
The Trap of "Minimal Cardinality"
Many early AI systems assumed the "best" diagnosis was the one with the fewest number of disorders (minimal cardinality). This paper shows this is a dangerous heuristic. Minimality is only reliable if all disorders have roughly equal, very low probabilities and very high causal strengths. If one disorder is significantly more common than another, a combination of two common disorders might be more likely than a single rare one.
Key Results
The paper provides a formal formula for Relative Likelihood ($L$), decomposed into three primary components:
- Weight of Causation: The probability that the disorders would cause the present symptoms.
- Weight of Absence: A penalty for symptoms that should be present if the disorders were active, but are missing.
- Weight of Prior Expectation: The inherent rarity of the disorders themselves.
Through these formulas, they demonstrate that while "irredundancy" is a strong criterion for plausibility, it is not absolute. They identify "atypical" situations where a redundant explanation (one that explains a symptom twice) might be more probable than a simpler one—specifically when a very common disorder is involved.
Limitations and Future Work
The model assumes that disorders occur independently. In reality, one disease often predisposes a patient to another (e.g., diabetes and heart disease), requiring more complex causal networks. Additionally, while the likelihood calculation is tractable, finding all possible "irredundant covers" remains computationally expensive for large systems. The authors suggest that future work should focus on $A^*$-like search algorithms to navigate the neighborhood of irredundant covers efficiently.
Summary updated