Domain Structure and the Complexity of Diagnostic Problem Solving

Thomas D. WuAAAI 1991

Introduction

In the field of artificial intelligence, a long-standing principle has been that "in the knowledge lies the power." However, for decades, the specific relationship between the organization of that knowledge and the efficiency of problem-solving algorithms remained largely unquantified. Diagnostic problem solving—the task of identifying which diseases best explain a set of observed symptoms—is a prime example of a domain where complexity can easily spiral out of control. As the number of symptoms increases, the number of potential disease combinations grows exponentially.

This paper investigates the "modularity hypothesis": the idea that real-world diagnostic domains are not uniform but are composed of discrete modules where specific groups of causes lead to specific groups of effects. By quantifying this "lumpy" structure, we can demonstrate how inherent domain organization drastically reduces computational complexity, even when not explicitly programmed into a system.

The Diagnostic Challenge

At its core, diagnostic reasoning involves mapping observable symptoms back to their underlying causes.

Figure 1: Conceptual model of diagnostic problem solving, where observable symptoms are linked to a target disorder and various competing disorders.

The difficulty lies in the "competing disorders" shown in Figure 1. A single symptom might be explained by dozens of different diseases. When a patient presents with multiple symptoms, the search space for the "best" set of explanatory disorders becomes massive.

Quantifying Domain Structure: Explanatory Power

To study this phenomenon, we introduce the concept of Explanatory Power. This is defined as the fraction of a patient's symptoms that a single disorder can explain. In a perfectly uniform, structureless domain, most disorders would have similar explanatory power. However, real-world medical data tells a different story.

Figure 4: Distribution of Explanatory Power in a medical database. The non-Gaussian "lumpy" distribution indicates that a few disorders explain many symptoms, while most explain very few.

As seen in Figure 4, the distribution of explanatory power in the Quick Medical Reference (QMR) database is highly skewed. This "lumpiness" is the mathematical signature of domain structure. Most disorders explain very little, but a significant few explain a large portion of the symptoms. This clustering suggests that symptoms are not independent but are tied to specific modular disease processes.

Methodology: Testing the Modularity Hypothesis

To isolate the effect of this structure, the study employed Domain Randomization. A "control" version of a medical subdomain (specifically prerenal azotemia) was created by randomizing the links between disorders and symptoms while maintaining the total number of links. This effectively "smoothed out" the natural clusters, creating a structureless baseline.

The paper then compares two algorithmic approaches:

  1. Candidate Generation: A traditional method that attempts to find all minimal sets of disorders explaining all symptoms.
  2. Symptom Clustering: A newer approach that partitions symptoms into groups, where each group is explained by a single differential diagnosis. This creates a more compact, "factored" representation of the problem.

Key Results and Insights

The experiments revealed that domain structure is a massive hidden asset for diagnostic efficiency.

  • Exponential Speedup: In structured domains, the space complexity of symptom clustering was approximately the fifth-root of the complexity required by traditional candidate generation.
  • The Impact of Randomization: When the inherent structure was removed through randomization, complexity skyrocketed for both algorithms. For candidate generation, the natural structure was found to reduce complexity by a factor of 9.
  • Superiority of Factored Representations: Symptom clustering consistently outperformed candidate generation, even in randomized domains. This suggests that representing combinations of diseases implicitly (as a Cartesian product of sets) is fundamentally more efficient than listing every possible combination.

Conclusion

The efficiency of diagnostic programs is not merely a product of the facts they contain, but of the underlying modularity of the world they model. Real-world knowledge is "lumpy," and algorithms that can exploit this natural clustering—like symptom clustering—can achieve performance gains of several orders of magnitude. This research underscores that understanding the structural attributes of a domain is as critical as the knowledge itself for building scalable AI systems.

Summary updated

BibTeX
@inproceedings{wu1991domain,
  author = {Thomas D. Wu},
  title = {{Domain Structure and the Complexity of Diagnostic Problem Solving}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1991},
}
Figure