wolffd@0: function prob = quickscore(fpos, fneg, inhibit, prior, leak)
wolffd@0: % QUICKSCORE Heckerman's algorithm for BN2O networks.
wolffd@0: % prob = quickscore(fpos, fneg, inhibit, prior, leak)
wolffd@0: % 
wolffd@0: % Consider a BN2O (Binary Node 2-layer Noisy-or) network such as QMR with
wolffd@0: % dieases on the top and findings on the bottom. (We assume all findings are observed,
wolffd@0: % since hidden leaves can be marginalized away.)
wolffd@0: % This algorithm takes O(2^|fpos|) time to compute the marginal on all the diseases.
wolffd@0: %
wolffd@0: % Inputs:
wolffd@0: % fpos = the positive findings (a vector of numbers in {1, ..., Nfindings})
wolffd@0: % fneg = the negative findings (a vector of numbers in {1, ..., Nfindings})
wolffd@0: % inhibit(i,j) = inhibition prob. for finding i, disease j, or 1.0 if j is not a parent.
wolffd@0: % prior(j) = prior prob. disease j is ON. We assume prior(off) = 1-prior(on).
wolffd@0: % leak(i) = inhibition prob. for the leak node for finding i
wolffd@0: %
wolffd@0: % Output:
wolffd@0: % prob(d) = Pr(disease d = on | ev)
wolffd@0: %
wolffd@0: % For details, see
wolffd@0: % - Heckerman, "A tractable inference algorithm for diagnosing multiple diseases", UAI89.
wolffd@0: % - Rish and Dechter, "On the impact of causal independence", UCI tech report, 1998.
wolffd@0: %
wolffd@0: % Note that this algorithm is numerically unstable, since it adds a large number of positive and
wolffd@0: % negative terms and hopes that some of them exactly cancel.
wolffd@0: %
wolffd@0: % For matlab experts, use 'mex' to compile C_quickscore, which has identical behavior to this function.
wolffd@0: 
wolffd@0: [nfindings ndiseases] = size(inhibit);
wolffd@0: 
wolffd@0: % make the first disease be always on, for the leak term
wolffd@0: Pon = [1 prior(:)'];
wolffd@0: Poff = 1-Pon;
wolffd@0: Uon = [leak(:) inhibit]; % U(f,d) = Pr(f=0|d=1)
wolffd@0: Uoff = [leak(:) ones(nfindings, ndiseases)]; % Uoff(f,d) = Pr(f=0|d=0)
wolffd@0: ndiseases = ndiseases + 1;
wolffd@0: 
wolffd@0: npos = length(fpos);
wolffd@0: post = zeros(ndiseases, 2);
wolffd@0: % post(d,1) = alpha Pr(d=off), post(d,2) = alpha Pr(d=m)
wolffd@0: 
wolffd@0: FP = length(fpos);
wolffd@0: %allbits = logical(dec2bitv(0:(2^FP - 1), FP));
wolffd@0: allbits = logical(ind2subv(2*ones(1,FP), 1:(2^FP))-1);
wolffd@0: 
wolffd@0: for si=1:2^FP
wolffd@0:   bits = allbits(si,:);
wolffd@0:   fprime = fpos(bits);
wolffd@0:   fmask = zeros(1, nfindings);
wolffd@0:   fmask(fneg)=1;
wolffd@0:   fmask(fprime)=1;
wolffd@0:   fmask = logical(fmask);
wolffd@0:   p = 1;
wolffd@0:   pterm = zeros(1, ndiseases);
wolffd@0:   ptermOff = zeros(1, ndiseases);
wolffd@0:   ptermOn = zeros(1, ndiseases);
wolffd@0:   for d=1:ndiseases
wolffd@0:     ptermOff(d) = prod(Uoff(fmask,d));
wolffd@0:     ptermOn(d) = prod(Uon(fmask,d));
wolffd@0:     pterm(d) = Poff(d)*ptermOff(d) + Pon(d)*ptermOn(d);
wolffd@0:   end
wolffd@0:   p = prod(pterm);
wolffd@0:   sign = (-1)^(length(fprime));
wolffd@0:   for d=1:ndiseases
wolffd@0:     myp = p / pterm(d);
wolffd@0:     post(d,1) = post(d,1) + sign*(myp * ptermOff(d));
wolffd@0:     post(d,2) = post(d,2) + sign*(myp * ptermOn(d));
wolffd@0:   end
wolffd@0: end
wolffd@0: 
wolffd@0: post(:,1) = post(:,1) .* Poff(:);
wolffd@0: post(:,2) = post(:,2) .* Pon(:);
wolffd@0: post = mk_stochastic(post);
wolffd@0: prob = post(2:end,2)'; % skip the leak term
wolffd@0: 
wolffd@0: