next up previous
Next: Variational Methods Up: Variational Probabilistic Inference and Previous: The QMR-DT Network


Carrying out diagnostic inference in the QMR model involves computing the posterior marginal probabilities of the diseases given a set of observed positive ( tex2html_wrap_inline895 ) and negative ( tex2html_wrap_inline897 ) findings. Note that the set of observed findings is considerably smaller than the set of possible findings; note moreover (from the bi-partite structure of the QMR-DT graph) that unobserved findings have no effect on the posterior probabilities for the diseases. For brevity we adopt a notation in which tex2html_wrap_inline899 corresponds to the event tex2html_wrap_inline895 , and tex2html_wrap_inline903 refers to tex2html_wrap_inline905 (positive and negative findings respectively). Thus the posterior probabilities of interest are tex2html_wrap_inline907 , where tex2html_wrap_inline909 and tex2html_wrap_inline911 are the vectors of positive and negative findings.

The negative findings tex2html_wrap_inline911 are benign with respect to the inference problem--they can be incorporated into the posterior probability in linear time in the number of associated diseases and in the number of negative findings. As we discuss below, this can be seen from the fact that the probability of a negative finding in Eq. (4) is the exponential of an expression that is linear in the tex2html_wrap_inline915 . The positive findings, on the other hand, are more problematic. In the worst case the exact calculation of posterior probabilities is exponentially costly in the number of positive findings (Heckerman, 1989; D'Ambrosio, 1994). Moreover, in practical diagnostic situations the number of positive findings often exceeds the feasible limit for exact calculations.

Let us consider the inference calculations in more detail. To find the posterior probability tex2html_wrap_inline917 , we first absorb the evidence from negative findings, i.e., we compute tex2html_wrap_inline919 . This is just tex2html_wrap_inline921 with normalization. Since both tex2html_wrap_inline923 and P(d) factorize over the diseases (see Eq. (1) and Eq. (2) above), the posterior tex2html_wrap_inline919 must factorize as well. The normalization of tex2html_wrap_inline921 therefore reduces to independent normalizations over each disease and can be carried out in time linear in the number of diseases (or negative findings). In the remainder of the paper, we concentrate solely on the positive findings as they pose the real computational challenge. Unless otherwise stated, we assume that the prior distribution over the diseases already contains the evidence from the negative findings. In other words, we presume that the updates tex2html_wrap_inline931 have already been made.

We now turn to the question of computing tex2html_wrap_inline933 , the posterior marginal probability based on the positive findings. Formally, obtaining such a posterior involves marginalizing tex2html_wrap_inline935 across the remaining diseases:


where the summation is over all the possible configurations of the disease variables other than tex2html_wrap_inline915 (we use the shorthand summation index tex2html_wrap_inline939 for this). In the QMR model tex2html_wrap_inline935 has the form:


which follows from Eq. (4) and the fact that tex2html_wrap_inline943 . To perform the summation in Eq. (5) over the diseases, we would have to multiply out the terms tex2html_wrap_inline945 corresponding to the conditional probabilities for each positive finding. The number of such terms is exponential in the number of positive findings. While algorithms exist that attempt to find and exploit factorizations in this expression, based on the particular pattern of observed evidence (cf. Heckerman, 1989; D'Ambrosio, 1994), these algorithms are limited to roughly 20 positive findings on current computers. It seems unlikely that there is sufficient latent factorization in the QMR-DT model to be able to handle the full CPC corpus, which has a median number of 36 positive findings per case and a maximum number of 61 positive findings.

next up previous
Next: Variational Methods Up: Variational Probabilistic Inference and Previous: The QMR-DT Network

Michael Jordan
Sun May 9 16:22:01 PDT 1999