A Tractable Inference Algorithm for Diagnosing Multiple Diseases

David HeckermanUAI 1989

TL;DR

This paper introduces "Quickscore," a novel algorithm for diagnosing multiple diseases simultaneously using a probabilistic model. It tackles the computational intractability of traditional methods by developing an efficient inference algorithm that scales well with the number of observed symptoms, making it practical for real-world medical diagnosis.

What Problem Does This Paper Address?

Expert systems, like the medical diagnostic system QMR, have historically faced challenges in applying probabilistic reasoning due to the sheer complexity of modeling numerous diseases and their interactions. Traditional probabilistic inference algorithms for such systems often exhibit exponential time complexity with respect to the number of diseases, rendering them impractical for large-scale applications like QMR, which contains over 600 diseases. This paper aims to bridge this gap by proposing a tractable inference algorithm that can efficiently compute disease probabilities given observed findings.

Methods

The paper presents the "Quickscore" algorithm, which operates on a probabilistic model where diseases are marginally independent, and findings are conditionally independent given the presence of diseases. This model uses a "noisy OR-gate" structure to represent how diseases cause findings. The core innovation of Quickscore lies in an algebraic transformation that cleverly rewrites the probability computation. Instead of summing over all possible disease combinations (which is exponential in the number of diseases), Quickscore computes probabilities through a product over diseases, making it exponential only in the number of observed positive findings. This is a significant improvement because, in practice, the number of positive findings is often much smaller than the number of diseases.

Datasets

The paper evaluates Quickscore using a probabilistic version of the Quick Medical Reference (QMR) system. The performance results are based on a library of classic QMR cases, which contain only positive findings.

Key Insights and Ideas

  • The "Noisy OR-Gate" Model: This model provides a structured way to represent how multiple diseases can independently contribute to a single finding, with each disease having a probability of "causing" that finding.
  • Tractability through Algebraic Transformation: The key insight is that the probability of a finding can be computed more efficiently by reformulating the summation over all disease states into a product over individual diseases. This is a crucial step in making the inference tractable.
  • Scalability with Positive Findings: Quickscore's exponential complexity is tied to the number of positive findings, not the number of diseases. This is a critical practical advantage, as patients typically present with a limited set of symptoms.
  • Intermediate Results: The algorithm can provide intermediate results, allowing for graceful degradation of performance under time constraints. This is useful for applications where a quick, approximate answer is better than a delayed exact one.

Key Results

  • Quickscore achieves a time complexity of O(nm⁻²m⁺), where 'n' is the number of diseases and 'm⁺' is the number of positive findings.
  • For a Macintosh II, Quickscore can process cases with nine positive findings in under one minute.
  • In 25% of the tested QMR cases, Quickscore requires 15 minutes or less to score.
  • The algorithm is shown to be useful as a "gold standard" for evaluating approximate inference algorithms in more complex extensions of the QMR-DT model.

Limitations and Future Work

  • Numerical Instability: Quickscore can be numerically unstable when the probability of observations for a given case is very small (e.g., less than 10⁻¹⁹). This typically occurs when the number of positive findings exceeds 15.
  • Model Assumptions: The paper acknowledges that the underlying assumptions of the model (e.g., binary diseases/findings, marginal independence of diseases, causal independence) may not hold in all real-world scenarios.
  • Future Work: The authors suggest extending the model to accommodate multi-valued diseases and findings, causal interactions among diseases, and hidden pathophysiological states. While Quickscore itself might not directly handle these extensions, the paper implies that further research could build upon its foundational work.

Summary updated

BibTeX
@inproceedings{heckerman1989tractable,
  author = {David Heckerman},
  title = {{A Tractable Inference Algorithm for Diagnosing Multiple Diseases}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1989},
}
Figure