Source-linked AI summary
A Tractable Inference Algorithm for Diagnosing Multiple Diseases
David Heckerman
TL;DR
Probabilistic diagnosis in large disease models was computationally intractable under existing methods. The paper introduces quickscore within a QMR probabilistic model, using independence assumptions and a noisy OR-gate, and shows that its finding-dependent complexity can support practical inference in many cases.
Problem
Existing probabilistic inference for QMR was exponential in the number of diseases, O(2^n), making diagnosis intractable for a knowledge base with over 600 diseases.
Method
Quickscore computes disease probabilities from positive and negative findings under a model with marginally independent diseases, conditionally independent findings, and independently acting disease causes.
Results
O(nm−2m+) time complexity makes quickscore useful when positive findings are much fewer than diseases; many realistic cases ran in under 1 minute on a Macintosh II.
Takeaways & Limitations
Quickscore provided a practical inference tool and gold standards for evaluating Monte Carlo approximation algorithms within the current QMR-DT model.
Takeaways & Limitations
Inference is unreliable when p(F+, F−) is below approximately 10−19, typically when current QMR-DT cases exceed 15 positive findings.
Abstract
from arXiv · showhide
We examine a probabilistic model for the diagnosis of multiple diseases. In the model, diseases and findings are represented as binary variables. Also, diseases are marginally independent, features are conditionally independent given disease instances, and diseases interact to produce findings via a noisy OR-gate. An algorithm for computing the posterior probability of each disease, given a set of observed findings, called quickscore, is presented. The time complexity of the algorithm is O(nm-2m+), where n is the number of diseases, m+ is the number of positive findings and m- is the number of negative findings. Although the time complexity of quickscore i5 exponential in the number of positive findings, the algorithm is useful in practice because the number of observed positive findings is usually far less than the number of diseases under consideration. Performance results for quickscore applied to a probabilistic version of Quick Medical Reference (QMR) are provided.
1 Introduction
The paper addresses the intractability of probabilistic diagnosis in large disease models by introducing quickscore, whose complexity depends exponentially on positive findings rather than diseases. This makes inference practical when observed positive findings are relatively few.
- Probabilistic inference in QMR was exponential in the number of diseases, O(2^n), making known algorithms intractable for its over 600 diseases.The problem is also known to be NP-hard.
- Quickscore has time complexity O(nm−2m+), exponential in the number of positive findings rather than diseases.Here, m+ counts positive findings and m− counts negative findings.
- Quickscore is useful in practice because observed positive findings are often far fewer than the diseases under consideration.For many realistic patient cases, a Macintosh II produced an answer in less than 1 minute.
2 The QMR model
QMR-DT represents diseases and findings as binary variables in a belief network with independence assumptions. A noisy OR-gate models how independently acting diseases combine to produce findings, enabling tractable probabilistic computation.
- QMR-DT contains n disease nodes and m finding nodes, and computes each disease's probability from observed positive and negative findings.Findings may be present, absent, or unobserved.
- The model assumes diseases are marginally independent and findings are conditionally independent given any disease instance.A disease instance assigns each disease in a set as present or absent.
- Under causal independence, diseases act independently to cause a given finding, and the finding is present if at least one disease causes it.The noisy OR-gate represents this combination of independent causal influences.
- The noisy OR-gate computes a finding's probability from disease-specific causal probabilities rather than enumerating all 2^n disease instances.For n potential causes, each p_i is the probability that disease d_i causes the finding.
3 The Quickscore Algorithm
Quickscore computes disease posteriors by exploiting independence and noisy-OR assumptions to replace an exponential disease-instance sum with tractable products and sums. Its runtime remains exponential in positive findings, but it can provide intermediate results as findings are processed.
- 3 The Quickscore Algorithm: Quickscore computes each disease's posterior probability given positive and negative findings under the model's independence and noisy-OR assumptions.The algorithm first computes the observation probability, then recomputes the conditional probability with each disease set present.
- 3 The Quickscore Algorithm: The noisy-OR transformation converts a sum over 2^n disease instances into a linear product over n sums.This equivalence is the source of quickscore's speed.
- 3 The Quickscore Algorithm: Quickscore combines positive and negative findings by expanding the joint probability and evaluating the resulting power-set terms.The positive-findings case is introduced with two findings before being generalized to mixed observations.
- 3 The Quickscore Algorithm: The algorithm can recover disease probabilities after the first j positive findings, with computation time exponential in j.This permits intermediate results and may support graceful degradation under time constraints.
- 3 The Quickscore Algorithm: Nine positive findings can typically be scored in less than 1 minute on a Macintosh II implementation.The runtime plot relates quickscore's execution time to the number of positive findings.
4 Run-Time Performance of Quickscore
Quickscore was evaluated on 400 classic QMR cases using a Macintosh II implementation. Nine positive findings were typically scored in under one minute, while 25% of cases required 15 minutes or less.
- 4 Run-Time Performance of Quickscore: Nine findings can typically be scored in less than 1 minute in the QMR case library.The cases contained only positive findings and were drawn from classic cases used to test QMR diagnostic accuracy.
- 4 Run-Time Performance of Quickscore: 25 percent of the 400 cases required 15 minutes or less to score each case.Quickscore was implemented in Lightspeed Pascal on a Macintosh II.
5 Weaknesses of the Algorithm
The diagnostic model relies on assumptions that may not suit many domains, and quickscore has important limits in extending the model and handling very small observation probabilities.
- Model assumptions: The model assumes binary diseases and findings, marginally independent diseases, and conditionally independent findings, assumptions that may be inappropriate in many domains.Examples include severity differences, causal disease relationships, and dependencies among findings.
- Extension limits: Quickscore cannot be extended in a straightforward manner to accommodate the model extensions discussed in the paper.These extensions address multiple-valued variables, causal interactions among diseases, and dependencies among findings.
- Numerical stability: 10^-19 is the approximate lower bound for reliable inference when hardware provides about 19 decimal places of precision.The instability arises when p(F +, F −) is small; in the current QMR-DT model, it typically occurs when positive findings exceed 15.
6 Conclusion
Despite its shortcomings, quickscore supported development of QMR-DT by providing exact reference results for evaluating approximate inference methods. The paper therefore presents it as a useful tool for developing decision-theoretic expert systems.
- 6 Conclusion: Quickscore provided gold standards for evaluating convergence properties of Monte-Carlo inference algorithms in the current QMR-DT model.Those approximation algorithms target extensions of QMR-DT, but their convergence properties are not well characterized.
- 6 Conclusion: Quickscore is likely to be useful to knowledge engineers developing decision-theoretic expert systems.This conclusion is stated despite the algorithm's shortcomings.
- 6 Conclusion: Monte-Carlo approximation algorithms were suited to model extensions, whereas quickscore supplied the reference standard within the current model.The comparison concerns the roles of the two approaches rather than a claim that quickscore handles the extensions directly.