An Exact Algorithm for Computing the Same-Decision Probability

When using graphical models for decision making, the presence of unobserved variables  may hinder our ability to reach the correct decision.  A fundamental question here is whether or not  one is ready to make a decision (stopping criteria), and if not, what additional  observations should be made in order to better prepare for a decision  (selection criteria).  A recently introduced notion, the Same-Decision Probability (SDP), has been shown to be useful  as both a stopping and a selection criteria.  This query has been shown to be highly intractable,  being PP^PP-complete, and is exemplary of a class of queries which correspond to the computation of certain expectations.  We propose the first exact algorithm for computing the SDP in this paper, and demonstrate its effectiveness on several real and synthetic networks.  We also present a new complexity result for computing the SDP on models with a Naive Bayes structure.