A New Inference Method for Frame-Based Expert Systems

James A. Reggia, Dana S. Nau, Pearl Y. WangAAAI 1983

In the early 1980s, diagnostic expert systems—such as those used in medicine or circuit repair—faced significant hurdles. Most relied on production rules ("If X, then Y") or statistical pattern matching, which often failed when a patient suffered from multiple simultaneous disorders. Furthermore, these "ad hoc" systems lacked a rigorous theoretical foundation. This 1983 paper from the AAAI proceedings introduces the Generalized Set Covering (GSC) model, a formal mathematical framework for diagnostic reasoning that addresses these limitations by adapting the classic "set covering problem" from mathematics.

The Generalized Set Covering (GSC) Model

The GSC model moves away from simple rule-based logic toward abductive inference—reasoning from effects back to causes. The authors define a diagnostic problem as a formal 4-tuple: $<D, M, C, M^+>$.

  • $D$: The set of all possible disorders.
  • $M$: The set of all possible manifestations (symptoms).
  • $C$: The causal relation, mapping which disorders in $D$ cause which manifestations in $M$.
  • $M^+$: The specific subset of symptoms observed in a particular case.

An explanation in this model is a set of disorders that "covers" (accounts for) all observed symptoms $M^+$. To ensure the diagnosis remains practical, the model adheres to the Principle of Parsimony (Ockham’s Razor), seeking the "minimal" set of disorders—the smallest number of causes that can explain all observed effects.

Conceptual mapping between disorders (D) and manifestations (M) in the GSC model.

Sequential Diagnostic Reasoning

Diagnostic reasoning is rarely a one-step process; data is typically discovered over time. To handle this, the authors developed a sequential algorithm that updates three primary data structures as new information arrives:

  1. MANIFS: The set of symptoms currently known to be present.
  2. SCOPE: The set of all disorders that could potentially explain at least one symptom in MANIFS.
  3. FOCUS: The current "differential diagnosis," which represents all possible minimal explanations.

To maintain efficiency, the FOCUS is stored using generators—compact representations (often Cartesian products) that allow the system to track multiple complex explanations without exhausting memory resources.

The sequential update process of MANIFS, SCOPE, and FOCUS as symptoms are discovered.

Key Insights and Results

The GSC model represents a shift toward breadth-first reasoning. Unlike systems that attempt to confirm one disease at a time (depth-first), GSC maintains all possible minimal explanations simultaneously.

Testing on specialized knowledge bases—specifically a Dizziness Knowledge Base (50 disorders) and a Peroneal Muscular Atrophy domain—demonstrated that the model could successfully identify multiple simultaneous disorders. This was a significant advancement over contemporary systems that struggled with co-occurring diseases. The use of generators proved highly effective, allowing the system to represent complex differential diagnoses in a very small memory footprint.

Limitations and Future Directions

While the GSC model provided a rigorous foundation, the authors identified several areas for refinement:

  • Independence Assumption: The model assumes disorders occur independently. In clinical reality, one disease often predisposes a patient to another, suggesting the "minimal cardinality" rule may need adjustment for dependent disorders.
  • Probabilistic Ranking: While the model finds all possible minimal explanations, it initially lacked a method to rank them by likelihood. The authors proposed using "symbolic probabilities" (e.g., High, Low) to refine the FOCUS.
  • Computational Complexity: Set covering is an NP-hard problem. While the prototypes functioned well, the authors noted that as knowledge bases scale to thousands of disorders, the search for minimal covers could become computationally expensive.

By formalizing the logic of "explanation," this work bridged the gap between intuitive AI design and domain-independent mathematical theory, setting a new standard for diagnostic inference in expert systems.

Summary updated

BibTeX
@inproceedings{reggia1983new,
  author = {James A. Reggia and Dana S. Nau and Pearl Y. Wang},
  title = {{A New Inference Method for Frame-Based Expert Systems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1983},
}
Figure