An Exact Algorithm for Computing the Same-Decision Probability

1 Introduction

When making any kind of decision under uncertainty, information gathering is crucial. Consider for example a physician who is examining an ill patient. The physician may perform a few tests and then strongly believe that the patient is suffering from substance-abuse induced depression. However, by not gathering more information in the form of further testing, the doctor could unwittingly be making a grave misdiagnosis. After all, 41% to 83% of patients being treated for psychiatric disorders, including depression, have been misdiagnosed and have an unresolved physical ailment that ranges from hypothyroidism to cancer [Klonoff and Landrine, 1997]. If the patient, say, was actually suffering from hypothyroidism, this misdiagnosis could have been prevented quite easily if the doctor had either checked the patient's neck carefully or performed a blood test. This example can also be seen as a warning to not make decisions that could easily change given some new information (i.e., decisions that may not be robust).

This paper is dedicated to the computation of a new probabilistic notion, called the Same-Decision Probability (SDP), which is mainly concerned with quantifying the robustness of a decision with respect to some hidden information. Intuitively, the SDP is the probability that one would make the same decision, had one observed the values of some hidden variables of interest.

The SDP is formulated in the context of probabilistic graphical models, which have often been used to model a variety of decision problems, e.g., in medical diagnosis [van der Gaag and Coup´e, 1999], troubleshooting [Heckerman et al., 1995], and in classification [Friedman et al., 1997]. In these applications, there is often some unobservable variable, such as the state of a patient's health. There are also often some hidden variables which could influence our belief on this variable of interest. Before making a decision, there are two fundamental questions. The first question is whether, given the current observations, the decision maker is ready to commit to a decision. We will refer to this as the stopping criteria for making a decision. 1 Assuming the stopping criteria is not met, the second question is what additional observations should be made before the decision maker is ready to make a decision. This typically requires a selection criteria based on some measure for quantifying an observation's value of information (VOI).

The literature contains a number of proposals for both stopping and selection criteria. For stopping criteria, one may commit to a decision once the belief about a certain event crosses some threshold, as in [Pauker and Kassirer, 1980; Lu and Przytula, 2006]. Alternatively, we may simply perform as many observations as our budget allows, as in [Greiner et al., 1996; Krause and Guestrin, 2009]. As for selection criteria, different observations may have different value of information (VOI) with respect to the decision we are interested in making. The value of an observation may depend upon how much it minimizes our expected uncertainty about an event, or it may depend on how much it raises the expected utility. Researchers have explored how to compute myopic VOI [Dittmer and Jensen, 1997] as well as nonmyopic VOI [Heckerman et al., 1993; Krause and Guestrin, 2009]. Additionally, [Bilgic and Getoor, 2011] have developed the Value of Information Lattice (VOILA), a framework in which all subsets of hidden variables are examined, and the most cost-efficient subset of features can be found.

1 [van der Gaag and Bodlaender, 2011] pose the STOP problem that asks whether or not the present evidence gathered is sufficient for diagnosis, or if there exists further relevant evidence that can and should be gathered.

The Same-Decision Probability (SDP) has been introduced recently and shown to be an effective stopping and selection criteria [Darwiche and Choi, 2010; Chen et al., 2012]. The SDP is defined as a measure of potential stability in a decision given further observations of some set of hidden variables. In short, the SDP is the probability that we would have made the same decision, had we known the states of variables that have not yet been observed. Compared to calculating a low SDP, calculating a high SDP would indicate a higher degree of readiness to make a decision, as the chances of the decision changing post observation would be lower.

The SDP is hard to compute. For example, we show in this paper that computing the SDP is NP-hard even in Naive Bayes networks. In [Choi et al., 2012], computing the SDP is shown to be generally PPPP-complete. The PPPP class can be thought of as a counting variant of the NPPP class, for which the MAP problem is complete [Park and Darwiche, 2004]. Non-myopic value of information (VOI) is a similar query that is shown to be PPPP-complete as well in [Chen et al., 2012]. These problems are not only closely related in terms of complexity, but also, they both involve computing the expectation over some unobserved variables. Existing algorithms for computing the non-myopic VOI are either approximate algorithms [Heckerman et al., 1993; Liao and Ji, 2008] or brute-force algorithms that are restricted to tree networks with few leaf variables [Krause and Guestrin, 2009].

The main contribution of this paper is in presenting the first exact algorithm for computing the SDP, which is based on a novel combination of branch-and-bound search with classical inference techniques for graphical models. As non-myopic VOI is in the same complexity class as SDP, our proposed algorithm can then serve as an example for developing similar exact algorithms for non-myopic VOI as well as other problems that are complete for PPPP.

This paper is structured as follows. Section 2 provides a formal definition of the SDP and some background knowledge. Section 3 presents our algorithm and discusses its complexity. Section 4 exhibits empirical results. Section 5 closes with some concluding remarks.

2 Background

We use standard notation for variables and their instantiations, where variables are denoted by upper case letters X and their instantiations by lower case letters x. Sets of variables are then denoted by bold upper case letters X and their instantiations by bold lower case letters x.

We will consistently use X to denote all variables in our model, E ✓ X to denote evidence variables (i.e., observed ones), and U ✓ X to denote the set of all hidden variables (i.e., unobserved ones). Hence, E \ U = ; and E [ U = X. We will also use D 2 U to denote a binary hypothesis variable with states d and d, which is sometimes referred to as the decision variable.

Given some evidence e, we assume that a decision will be made depending on whether Pr(d ♣ e) ≥ T , for some threshold T . We are particularly interested in measuring the stability of this decision with respect to the state of some variables

- - 0.90

- - 0.70

H ✓ U ∩ D, which are called query variables.

The Same-Decision Probability (SDP) is defined in [Darwiche and Choi, 2010] for this purpose.

Definition 1. Given hypothesis variable D, evidence e, unobserved variables H, and threshold T , suppose we are making a decision that is confirmed by Pr(d ♣ e) ≥ T. The samedecision probability (SDP) is defined as

where [Pr(d ♣ h↪ e) ≥ T] is an indicator function that = 1 when Pr (d ♣ h↪ e) ≥ T and = 0 otherwise.

In other words, SDP is the probability that we would have made the same decision had we known the variables H.

Consider the simple Naive Bayes network presented in Figure 1, which will serve as a running example through this paper. We will make a decision here if Pr(d ♣ e) ≥ T, where d is the event D = + and T is 0▷50. For example, we would make this decision under evidence E1 = +, since Pr(D = + ♣ E1 = +) ≥ 0▷5. Our goal now is to quantify the robustness of this decision with respect to hidden variables H = ¶H1↪H2↪H3♦. That is, we wish to compute the probability that we would still make the same decision after having observed H.

Consider Table 2 which enumerates all possible instantiations h. We see that in 5 of the 8 cases, Pr(d ♣ h↪ e) ≥ 0▷50. We take the sum of the probability of those instantiations and we find that SDP(d↪ ¶H1↪H2↪H3♦↪ ¶E1♦↪ 0▷50) = 0▷5395. Hence, according to this example, there is a good chance that we would make a different decision after having observed H.

Computing the SDP helps us in quantifying how ready we are to make a decision, and can also help us decide which variables to observe next. There is an in-depth discussion of how SDP is useful as a stopping criteria and as a selection criteria in [Chen et al., 2012]. In particular, the SDP is contrasted with classical notions such as entropy and value of information and is shown to be a useful decision-making tool that can quantify the robustness of a decision in ways that are not evident when we consider beliefs and utilities alone.

3 Computing the SDP Exactly

Computing the SDP involves computing an expectation over the hidden variables H. The naive brute-force algorithm

Table 2: Scenarios h for the network in Figure 1. The cases where Pr (d ♣ h↪ e) ≥ 0▷5 are bolded.

- - - 0.2295

would enumerate and check whether Pr(d ♣ h↪ e) ≥ T for all instantiations H. We now present an algorithm that can save us the need to explore every possible instantiation of h. To make the algorithm easier to understand, we will first describe how to compute the SDP in a Naive Bayes network, which we also show to be NP-hard. We then generalize our algorithm to arbitrary networks.

3.1 Computing the SDP in Naive Bayes Networks

We will find it more convenient to implement the test Pr(d ♣ h↪ e) ≥ T in the log-odds domain, where:

We then define the log-odds threshold as λ = log T 1-T and, equivalently, test logO(d ♣ h↪ e) ≥ λ.

In a Naive Bayes network with D as the class variable, H and E as the leaf variables, and Q ✓ H, the posterior logodds after observing a partial instantiation q = ¶h1↪ ▷ ▷ ▷ ↪ hj♦ can be written as:

where whi is the weight of evidence hi and defined as:

The weight of evidence whi is then the contribution of evidence hi to the quantity logO(d ♣ q↪ e) [Chan and Darwiche, 2003]. Note that all weights can be computed in time and space linear in ♣H♣. Table 3 depicts the weights of evidence for the network in Figure 1.

One can then compute the SDP by enumerating the instantiations of variables H and then using Equation 3 to test whether logO(d ♣ h↪ e) ≥ λ. Figure 2 depicts a search tree for the Naive Bayes network in Figure 1, which can be used

0.27 -2▷17 -2▷17 -4▷61

Figure 2: The search tree for the network of Figure 1. A solid line indicates + and a dashed line indicates -. The quantity logO(d ♣ q↪ e) is displayed next to each node q in the tree. Nodes with log O(d ♣ q↪ e) ≥ λ = 0 are shown in bold.

for this purpose. The leaves of this tree correspond to instantiations h of variables H. More generally, every node in the tree corresponds to an instantiation q, where Q ✓ H.

A brute-force computation of the SDP would then entail: 1.) Initializing the total SDP to 0, 2.) Visiting every leaf node h in the search tree, 3.) Checking whether logO(d ♣ h↪ e) ≥ λ, and if so, adding Pr(h ♣ e) to the total SDP. Figure 2 depicts the quantity logO(d ♣ q↪ e) for each node q in the tree, indicating that five leaf nodes (i.e., five instantiations of variables H) will indeed contribute to the SDP.

We now state the key observation underlying our proposed algorithm. Consider the node corresponding to instantiation H1 = + in the search tree, with log O(d ♣ H1 = +↪ e) = 3▷0. All four completions h of this instantiation (i.e., the four leaf nodes below it) are such that logO(d ♣ h↪ e) ≥ λ = 0. Hence, we really do not need to visit all such leaves and add their contributions Pr(h♣e) individually to the SDP. Instead, we can simply add Pr(H1 = +♣e) to the SDP, which equals the sum of Pr(h♣e) for these leaves. More importantly, we can detect that all such leaves will contribute to the SDP by computing a lower bound using the weights depicted in Table 3. That is, there are two weights for variable H2, the minimum of which is -1▷22. Moreover, there are two weights for variable H3, the minimum of which -1▷22. Hence, the lowest contribution to the log-odds made by any leaf below node H1 = + will be -1▷22 - 1▷22 = -2▷44. Adding this contribution to the current log-odds of 3▷0 will lead to a log-odds of ▷56, which still passes the given threshold.

A similar technique can be used to compute upper bounds, allowing us to detect nodes in the search tree where no leaf below them will contribute to the SDP. Consider for example the node corresponding to instantiation H1 = -↪H2 = -, with logO(d ♣ H1 = -↪H2 = -↪ e) = -3▷39. Neither of the leaves below this node will contribute to the SDP as their log-odds do not pass the threshold. This can be detected by considering the weights of evidence for variable H3 and computing the maximum of these weights (1▷22). Adding this to the current log-odds of -3▷39 gives -2▷17, which is still below the threshold. Hence, no leaf node below H1 = -↪ H2 = - will contribute to the SDP and this part of the search tree can also be pruned.

If we apply this pruning technique based on lower and upper bounds, we will actually end up exploring only the partition of the tree shown in Figure 3. The pseudocode of our

0.27 -2▷17

Figure 3: The reduced search tree for the network of Figure 2.

Algorithm 1 Computing the SDP in a Naive Bayes network.

Note: For q = ¶h1↪ ▷ ▷ ▷ ↪ hj♦, wq is defined as Pji=1 whi . input: N: Naive Bayes network with class variable D H: attributes ¶H1↪ ▷ ▷ ▷ ↪Hk♦ λ: log-odds threshold e: evidence output: Same-Decision Probability p main: p 0▷0 (initial probability) q φ (initial instantiation) DFS SDP(q, H, 0) return p 1: procedure DFS SDP(q, H, d) 2: if (logO(d ♣ e) + wq + Pki=d+1 maxhi whi ) < λ then return 3: else if (log O(d ♣ e)+wq+ Pki=d+1 minhi whi ) ≥ λ then 4: add Pr(q ♣ e) to p, return 5: else 6: if d < k then 7: for each value hd+1 of attribute Hd+1 do 8: DFS SDP(qhd+1,H ∩ Hd+1,d + 1)

final algorithm is shown in Algorithm 1. 2

3.2 The SDP for Naive Bayes is Hard

SDP is known to be PPPP-complete [Choi et al., 2012]. We now show that SDP remains hard for Naive Bayes networks.

Theorem 1. Computing the Same-Decision Probability in a Naive Bayes network is NP-hard.

Proof. We reduce the number partition problem [Karp, 1972] to computing the SDP in a Naive Bayes model. Suppose we are given a set of positive integers c1↪ ▷ ▷ ▷ ↪ cn, and we wish to determine whether there exists I ✓ ¶1↪ ▷ ▷ ▷ ↪ n♦ such that Pj2I ci = Pj62I cj. We can solve this by considering a Naive Bayes network with a binary class variable D having uniform probability, and binary attributes H1↪ ▷ ▷ ▷ ↪Hn having CPTs leading to weights of evidence wHi=T = ci and wHi=F = -ci. In particular, the set of integers can be partitioned if there is an instantiation h = ¶h1↪ ▷ ▷ ▷ ↪ hn♦ with Pni=1 whi = 0 since I would then include all indices i with hi = T in this case.

2 The specific ordering of H in which the search tree is constructed is directly linked to the amount of pruning. We use an ordering heuristic that ranks each query variable Hi by the difference of its corresponding upper and lower bound - H is then ordered from greatest difference to lowest difference.

Consider now the following SDP (the last step below is based on the above properties):

The Naive Bayes network satisfies a number of properties that we shall use next. First, Pni=1 whi is either 0, ≥ 1, or  -1 since all weights whi are integers. Next, if Pni=1 whi = c, then Pni=1 wh0i = -c where h0i 6= hi. Finally, Pr(h1↪ ▷ ▷ ▷ ↪ hn) = Pr(h01 ↪ ▷ ▷ ▷ ↪ h0n ) when h0i 6= hi.

We then have Pni=1 whi = 0 for some instantiation h1↪ ▷ ▷ ▷ ↪ hn iff Ph1↪▷▷▷↪hn [Pni=1 whi 6= 0] Pr(h1↪ ▷ ▷ ▷ ↪ hn) < 1. Hence, the partitioning problem can be solved iff SDP (D = T↪ ¶H1↪ ▷ ▷ ▷ ↪ Hn♦↪ ¶♦↪ 2◁3) < 1◁2.

3.3 Computing the SDP in Arbitrary Networks

We will generalize our algorithm to arbitrary networks by viewing such networks as Naive Bayes networks but with aggregate attributes. For this, we first need the following notion.

Definition 2. A partition of H given D and E is a set S1↪ ▷ ▷ ▷ ↪ Sk such that: Si ✓ H; Si \Sj = ;; S1 [ ▷ ▷ ▷ [Sk = H; and Si is independent from Sj , i 6= j, given D and E.

Figure 4 depicts an example partition.

The intuition behind a partition is that it allows us to view an arbitrary network as a Naive Bayes network, with class variable D and aggregate attributes S1↪ ▷ ▷ ▷ ↪ Sk. That is, each aggregate attribute Si is viewed as a variable with states si, allowing us to view each instantiation h as a set of values s1↪ ▷ ▷ ▷ ↪ sk. We now have:

where

Since Equations 5 and 6 are analogous to Equations 3 and 4, we can now use Algorithm 1 on an arbitrary network. This usage, however, requires some auxiliary computations that were not needed or were readily available for Naive Bayes networks. We discuss these computations next.

Finding a Partition

We first need to compute a partition S1↪ ▷ ▷ ▷ ↪ Sk, which is done by pruning the network structure as follows: we delete edges outgoing from nodes in evidence E and hypothesis D, and delete (successively) all leaf nodes that are neither in H, E or D. We then identify the components X1↪ ▷ ▷ ▷ ↪Xk of the resulting network and define each nonempty Si = H \ Xi as an element of the partition. This guarantees that in the original network structure, Si is dseparated from Sj by D and E for i 6= j (see [Darwiche, 2009]). In Figure 4, network pruning leads to the components X1 = ¶X1↪ X2↪ E2↪ H1↪ H2↪ H3♦, X2 = ¶D↪ E1↪ H4♦ and X3 = ¶X3↪ H5↪ H6♦.

These quantities, which are referenced on Lines 2-4 of the algorithm, have simple closed forms in Naive Bayes networks. For arbitrary networks, however, computing these quantities requires inference which we do using the algorithm of variable elimination as described in [Darwiche, 2009]. Note that network pruning, as discussed above, guarantees that each factor used by variable elimination will have all its variables in some component Xi. Hence, variable elimination can be applied to each component Xi in isolation, which is sufficient to obtain all needed quantities. We omit the details of these computations, however, for space limitations.

Computing the Min and Max of Evidence Weights

We finally show how to compute maxsi wsi and minsi wsi , which are referenced on Lines 2 and 3 of the algorithm. These quantities can also be computed using variable elimination, applied to each component Xi in isolation. In this case, however, we must eliminate variables Xi ∩ Si first and then variables Si. Moreover, the first set of variables is summed-out, while the second set of variables is max'd-out or min'd-out, depending on whether we need maxsi wsi or minsi wsi . Finally, this elimination process is applied twice, once with evidence d↪ e and a second time with evidence d↪ e. Again, we leave out the details of this computation for space limitations.

3.4 Complexity Analysis

Let n be the number of variables in the network, h = ♣H♣, and w = maxi wi, where wi is the width of constrained elimination order used on component Xi. The best-case time complexity of our algorithm is then O(n exp w) and the worst-case time complexity is O(nexp (w+h)). The intuition behind these bounds is that computing the maximum and minimum weights for each aggregate attribute takes time O(nexpw). This also bounds the complexity of computing O(d♣e), Pr(q♣e) and corresponding weights wsi . Moreover, depending on the weights and the threshold T, traversing the search tree can take anywhere from constant time to O(exph). Since depth-first search can be implemented with linear space, the space complexity is O(nexpw).

4 Experimental Results

We performed several experiments on both real and synthetic networks to test the performance of our algorithm across a wide variety of network structures, ranging from simple Naive Bayes networks to highly connected networks. Real networks were either learned from datasets provided by the UCI Machine Learning Repository or provided by HRL Laboratories and CRESST. 3 For the majority of the real networks, it was clear which variable should be selected as the decision variable. For the unclear cases, the decision variable was picked at random. Query and evidence variables were selected at random for all real networks.

Besides this algorithm, there are two other options available to compute the SDP: 1. the naive method to brute-force the computation by enumerating over all possible instantiations or 2. the approximate algorithm developed by [Choi et al., 2012]. To compare our algorithm with these two other approaches, we compute the SDP over the real networks. For each network we selected at least 80% of the total network variables to be query variables so that we could emphasize how the size of the query set greatly influences the computation time. Each computation was given 20 minutes to complete. As we believe that the value of the threshold can greatly affect running time, we computed the SDP with thresholds T = [0▷01↪ 0▷1↪ 0▷2↪ ▷ ▷ ▷ ↪ 0▷8↪ 0▷9↪ 0▷99] and took the worst-case time. The results of our experiments with the three algorithms are shown in Table 4. Note that ♣H♣ is the number of query variables and ♣h♣ is the number of instantiations the naive algorithm must enumerate over. Moreover, φ indicates that the computation did not complete in the 20 minute time limit and * indicates that there was not sufficient memory to complete the computation. The networks ¶car,ttt,voting,nav,chess♦ are Naive Bayes networks whereas the others are polytree networks.

Given the real networks that we tested our algorithm on, it is clear that the algorithm outperforms both the naive implementation and the approximate algorithm for both Naive Bayes networks and polytree networks. Note that the approximation algorithm is based on variable elimination but can only use certain constrained orders. For a Naive Bayes network with hypothesis D being the root, the approximation algorithm will be forced to use a particularly poor ordering, which explains its failure on the chess network.

3 http://www.cse.ucla.edu/

To analyze how a more general network structure and the selected threshold affects the performance of our algorithm, we generated synthetic networks with 100 variables and varying treewidth using BNGenerator [Ide et al., 2004]. For each network, we randomly selected the decision variable, 25 query variables, and evidence variables. 4 We then generated a partition for each network and grouped the networks by the size of obtained partition (k). Our goal was to test how our algorithm's running time and ability to prune the searchspace depends on k. The average time and average number of instantiations explored are shown in Figure 5.

In general, we can see that as k increases, the number of instantiations explored by the algorithm decreases and its runtime improves. The network becomes more similar to a Naive Bayes structure with increasing k. Moreover, the larger k is, the more levels there are in the search tree, which means that our algorithm will have more opportunities to prune. In the worst case, a network may be unable to be disconnected at all (k = 1). However, even in this case our algorithm is still, on average, more efficient compared to the brute-force implementation as for some cases, after computing the maximum and minimum weight of observing H, it will find that there does not exist any h that will change the decision. We found that, given a time limit of 2 hours, the brute-force algorithm could not solve any synthetic networks whereas our approach solved greater than 70% of such networks.

4 As the synthetic networks are binary, a brute-force approach would need to explore 225 instantiations.

We also test how the threshold affects computation time. Here, we calculate the posterior probability of the decision variable and then run repeatedly our algorithm with thresholds that are varying increments away. The average running time for all increments can be seen in Figure 6. It is evident that when the threshold is set to be further away from the initial posterior probability, the algorithm finishes much faster, which is perhaps expected since the usage of more extreme thresholds would allow for more search space pruning.

Overall, our experimental results show that our algorithm is able to solve many SDP problems that are out of reach of existing methods. We also confirm that our algorithm completes much faster when the network can be disconnected or when the threshold is far away from the initial posterior probability of the decision variable.

5 Conclusion

We have introduced the first exact algorithm for computing the SDP. Experimental results show that this algorithm has comparable running time to the previous approximate algorithm and is also much faster than the naive brute-force algorithm. Our algorithm is able to compute the SDP for query sets that previous algorithms are unable to solve.

Acknowledgements

This work has been partially supported by ONR grant #N00014-12-1-0423, NSF grant #IIS-1118122, and NSF grant #IIS-0916161.