Differential Semantics of Intervention in Bayesian Networks

1 Introduction

Bayesian networks capture uncertain knowledge naturally and efficiently, and belong to the family of probabilistic graphical models. They are widely used in various fields such as signal processing, information retrieval, sensornets and pervasive computing, natural language processing, and computer vision.

Causal Bayesian networks are another kind of directed acyclic graph, which conveys causal information as well as the traditional conditional independencies, and permits one to infer the causal effects. In causal Bayesian networks, interventions are usually interpreted as an external agent setting a variable to a certain value, which contrasts with an agent just passively observing variables' values. Goldszmidt and Pearl [Goldszmidt and Pearl, 1992] denoted the intervention of a variable in a causal Bayesian network as do(Vi = vk i ), or do(vk i ) for short.

In this paper, we will use capital letters (e.g. A) for network parameters, lowercase letters (a) for any values taken by the corresponding network parameters, and lowercase letters with superscripts (ak ) as generic symbols for specific values taken by the corresponding network parameters. For ease of illustration, we also denote |Vi| as the number of possible values for a network parameter Vi. Thus Vi has |Vi| atomic interventions do(vk i ) (k = 1, . . . , |Vi|). Each such intervention do(vk i ) is called an action.

Pearl [Pearl, 2009b] introduced two methods to represent the intervention in causal Bayesian networks. One is a mutilated graph, which is obtained by deleting all links from its parent nodes to the intervention node Vi (Figure 2(a)). The other is an augmented network, which is obtained by adding a hypothetical intervention link Fi → Vi in the network(Figure 2(b)). Using the mutilated graph, for the Bayesian network shown in Figure 1, P(d|do(B = 1)) can be computed as follows.

The prediction P(d|B = 1) can be computed by using classical methods like variable elimination. A Bayesian network consists of two parts, the network structure and the conditional probability tables (CPTs). Pearl changed the network structure to represent the external intervention. In this paper, we encode the external intervention from another perspective by replacing CPTs with partial intervention tables without changing the network structure. For an action do(vk i ), we set P (vk i |u) = 1 and P(vl i |u) = 0 for l ̸= k, and the CPT of Vi becomes a partial intervention table. We will give formal definition for this concept in Section 3.

Pearl's method computes Vi's atomic interventions do(vk i ) (k = 1, · · · , |Vi|) by inferring the Bayesian network |Vi| times. Using the partial intervention table, we can compute all these atomic interventions by inferring the Bayesian network only once. Assume that all variables in the Bayesian network shown in Figure 1 are binary. If one intervenes and assigns a value to B, he has to, according to Pearl's method, use two probabilistic inferences for do(B = 1) and do(B = 0). However, we can employ only one Bayesian network inference to simultaneously compute both do(B = 1) and do(B = 0). The combination of do(B = 1) and do(B = 0) together is called a full atomic intervention, whose definition is given in Section 3. Our first main contribution is to propose a new representation model of the intervention by using the partial intervention tables, and design a novel and efficient approach to calculating interventions based on this new representation model.

Bayesian networks have two classical inference methods, i.e. variable elimination and jointree. Let e denote the evidence. We propose a jointree based algorithm to compute the full intervention for all network parameters with respect to P(e). This is our second main contribution.

Differentiation is one of inference methods in Bayesian networks and is conducted on a multi-linear function f called network polynomial, which has the property that f(e) = P(e) for each given evidence e [Darwiche, 2003]. The calculation of the differentiation of f is similar to how we obtain partial derivatives in classical mathematics. Darwiche [Darwiche, 2003] proposes an efficient framework for computing the first derivatives with respect to all network parameters. Moreover, the partial derivative has applications to sensitivity analysis [Chan and Darwiche, 2002; 2004], by identifying the minimal changes of parameters in order to satisfy probabilistic query constraints. It can be also applied in the learning of network parameters from data. The details will be reviewed in Section 2.

The first derivative ∂P(d) ∂P(b|a) can be computed over the Bayesian network in Figure 1 as follows.

We find Eq. (1) can be derived from Eq. (2). Thus action is computed from the derivative function while prediction is inferred from the original function, and action and prediction can be regarded as velocity and displacement, respectively. Usually, velocity is more stable than displacement. Similarly, Pearl [Pearl, 2009b] found causal relationship is more stable than probabilistic relationship. However, if the intervention variables cannot reach the evidence variables, the distribution of evidence variables is independent of the intervention variables. We find the causal influence cannot be derived from the differentiation in this case. For example, ∂P(c) ∂P(b|a) can be computed by using Park and Darwiche's method [Park and Darwiche, 2004] as follows.

However, we observe that ∂P(c) ∂P(b|a) = 0 while P(c|do(B = 1)) = ∑a P(a)P(c|a). So we show that the output of Park and Darwiche's jointree algorithm is not the differentiation but the intervention of Bayesian networks in this case. Our third contribution is to reveal the connection between the intervention and the differentiation.

The rest of this paper is organized as follows. We outline Bayesian networks, their differential semantics and interventions in Section 2. We introduce a new approach to represent intervention in Section 3 and discover its differential semantics in Section 4. Experimental results are reported in Section 5. The related work is discussed in Section 6, and we conclude our work in Section 7.

2 Preliminaries

In this section, we first outline the differentiation of Bayesian networks and next briefly survey the intervention of Bayesian networks.

2.1 The differentiation of Bayesian networks

A Bayesian network is defined as a pair BN = (G, Θ). Here, G = (V, E) is a directed acyclic graph, called the network structure, where V denotes all nodes in G and an edge in E denotes conditional dependence relationships between two nodes. Θ is a set of CPTs, and one CPT is for each node in G, called the network parameter. Moreover, a Bayesian network implicitly represents the joint probability distribution of its set of variables V. In Bayesian networks, every variable is conditionally independent of its nondescendants given its parents. Using the conditional independence property, the joint probability distribution of a Bayesian network can be simplified. For example, Figure 1 shows a Bayesian network with five nodes V = {A,B,C,D,E}. P(v) can be computed as shown below.

Here, ui is the parent of vi. Darwiche [Darwiche, 2003] defined for each Bayesian network a unique multilinear function, denoted by f, over a set of evidence indicators λv and a set of parameters P(v|u). Each term of f corresponds to an instantiation of the network variables. Therefore, f has an exponential number of terms. The term corresponding to instantiation v is the product of all evidence indicators and network parameters that are compatible with the instantiation. The network polynomial of a BN is defined as follows:

where ∼ denotes the compatibility relation among instantiations (that is, vu ∼ v says that instantiations vu and v agree on values of their common variables). The value of network polynomial f at evidence e, denoted by f(e), is the result of replacing each evidence indicator λv in f with 1 if v is consistent with e, and with 0 otherwise. In order to differentiate Bayesian networks, Darwiche [Darwiche, 2003] compiled the network polynomial into an arithmetic circuit. The circuit is a rooted, directed acyclic graph with two types of leaf nodes, λv and P(v|u), and its other nodes are multiplication and addition operations. Parameter variables are set according to the network CPTs while indicator variables are set according to the given evidence. Once the circuit inputs are set, it can be evaluated using a bottom-up pass, which proceeds from the circuit inputs to its output. Moreover, it can be differentiated using a top-down pass, which computes the first derivative of the circuit output with respect to every circuit input. Since f(e) = P(e), Darwiche proved that the first derivatives with respect to network parameters can be calculated below.

A jointree [Shenoy and Shafer, 1986; Jensen and Andersen, 1990] for BN is a pair (T ,C), where T is a tree and C is a function that maps each node i in the tree T into a label Ci, which is called a cluster. A jointree must satisfy three properties: (1) the cluster Ci is a set of nodes from the BN; (2) each family in the BN must appear in some cluster Cj; (3) if a node appears in two clusters Ci and Cj , it must also appear in every cluster Ck on the path between Ci and Cj . The edges of a jointree are called separators, which is denoted by Sij and defined as Ci ∩ Cj . The width of a jointree is defined as the size of its largest cluster minus one. Given some evidence e, a jointree algorithm [Pearl, 1988; Shenoy and Shafer, 1986; Jensen and Andersen, 1990] propagates messages between clusters. After passing an inward and an outward messages for each cluster Ci, one can compute its marginal P(Ci, e).

Park and Darwiche [Park and Darwiche, 2004] further proposed a differential semantics for jointree algorithms and computed the first derivative with respect to P(v|u) in the jointree. A jointree can implicitly encode an arithmetic circuit. Inward message propagation evaluates the circuit while outward message propagation differentiates it. Suppose that CPTΘXj|Uj is assigned to cluster Ci which has variables Ci. Then:

where P (vk|uk) ranges over all evidences and CPTs assigned to cluster Ci andMji denotes the message fromCj to Ci.

2.2 The intervention of Bayesian networks

The simplest type of external intervention is one in which a single variable, say Vi, is forced to take on some fixed value vk i . Such an intervention is called atomic intervention. Pearl [Pearl, 2009b] introduced two techniques to denote the intervention in a Bayesian network. One is to describe an intervention by a mutilated graph derived from the original Bayesian network by removing all the incoming arcs to Vi and setting the CPT of Vi as P(Vi = vk i ) = 1. In this case, intervention essentially separates Vi from its direct causes and Vi becomes a root node. For example, if we want to compute the intervention do(B = 1) in the Bayesian networks shown in Figure 1, we should first delete the link A → B and then assign P(B = 1) = 1. The graph resulting from this operation is shown in Figure 2(a), and the resulting joint distribution on the remaining variables will be

Using the mutilated graph, Pearl [Pearl, 2009a] revealed that the distribution generated by an intervention do(Vi = vk i ) on a set V is given by the truncated factorization

where P(vj|uj) are the pre-intervention conditional probabilities. Thus the distribution of evidence e given the intervention can be computed by

An alternative way is to encode an intervention by an augmented network [Pearl, 1993] which is generated by adding to BN a link Fi → Vi. For example, if we want to compute the intervention do(B = 1) in the Bayesian networks shown in Figure 1, we should add a link Fi → B in the network. The augmented network is shown in Figure 2(b), where Fi is a new variable taking values in {do(va i ),idle}, va i can be any value of Vi and "idle" denotes no intervention. Thus, the new parent set of Vi in the augmented network is Uai = Ui ∪{Fi}, and it is related to Vi by the following conditional probability

Then the causal effect of the intervention do(va i ) can be given by

where Pa is the distribution specified by the augmented network BN a = BN ∪ {Fi → Vi} and P (vi|uai ), with an arbitrary prior distribution on Fi.

3 A novel approach to computing the intervention

In this section, we introduce a newmodel to represent the intervention without changing the network structure, and propose a jointree based approach to calculating the intervention by using this novel representation model. We first give the following definition.

Definition 3.1 Given an intervention do(vk i ), the partial intervention table (PIT in short) of Vi demonstrates the intervention probability, P ′ (vk i |ui), w.r.t do(vk i ), which is calculated as below.

For example, if we want to compute the action do(B = 1) in the Bayesian networks shown in Figure 1, then P(B = 1) = 1 and P(B = 0) = 0. Thus we can change ΘB to Θ′B (B = 1) as shown below.

Θ′B (B = 1)

A PIT representation of an intervention is obtained by simply replacing the CPT of each intervention variable by its corresponding PIT without any changes to the network structure.

Theorem 3.1 The PIT representation is correct in terms of calculating the intervention.

Proof. We prove this by showing that the causal effect, P (e|do(vk i )), will be the same when calculated by using the CPTs of the mutilated-graph representation and the PITs of the PIT representation respectively. Using Pearl's mutilated graph, we get the following causal effect.

Using our partial intervention table, we compute the following causal effect.

Since P ′ (vi|u) = 1, P1(e|do(vk i )) = P2(e|do(vk i )). Thus the theorem is proved. □

For example, if one intervenes and sets B = 1, then we can derive by using P ′ (B = 1|a) = 1 as follows.

So we can get the same result as Pearl's method. Next, we give the following definition for the full atomic intervention.

Definition 3.2 A full atomic intervention of Vi consists of all atomic interventions of Vi each of which is w.r.t a possible value of Vi. It is denoted as do(Vi) and contains do(v1 i ), . . . , do(v|Vi| i ).

For example, if one wants to compute the interventions do(B = 1) and do(B = 0) in Figure 1, he has to compute P(a, c, d, e|do(B = 1)) and P(a, c, d, e|do(B = 0)) one by one according to Pearl's method. However, we can simultaneously compute do(B = 1) and do(B = 0) using the following technique. First, since P(B = 1) = 1 and P(B = 0) = 1, we change ΘB to a full intervention table Θ′B (B) as shown below.

We next compute P(a, c, d, e|do(B)) as follows.

Since we compute the post-intervention distribution of a full atomic intervention, we should make a distinction between do(B = 1) and do(B = 0). Thus we should keep the intervention variable and its parent variables in the result. Let Vars(ΘVi ) denote all network variables in ΘVi . Since {A, B} ⊂ Vars(ΘA ∪ ΘC ∪ ΘD ∪ ΘE) and P ′ (b|a) = 1, it can yield

Using the PIT presentation, we can compute each full atomic intervention by one Bayesian network inference, e.g, Eq. (8). While using Pearl's methods, a full atomic intervention for node Vi requires |Vi| Bayesian network inferences.

The jointree algorithm is widely utilized for performing Bayesian network inferences. The following theorem illustrates a method to compute the full atomic intervention by using the jointree algorithm.

Theorem 3.2 In a jointree constructed over G, the full atomic intervention of every node Vi with respect to P(e) in cluster Cl can be computed below.

Proof. 1. If node Vi can reach e, we can use the jointree algorithm to compute the full intervention as follows.

Here, C ′ l denotes {Cl, e}.

1. If node Vi cannot reach e, we can use the jointree algorithm to compute the full intervention as shown below.

The proof is then done. □

Using Theorem 3.2, we propose Algorithm 1 to compute the full atomic intervention of all nodes w.r.t evidence in Bayesian networks. We now explain the main aspects of the algorithm. We first compile a jointree by the network structure and P(e). Then the jointree passes messages toward its root. According to Theorem 3.2, we can use a cached factor Φi to compute the full atomic interventions of all nodes in cluster Ci with respect to P(e) in some order πi if a cluster Ci has received messages from all its neighbors in the outward phase. After computing the full atomic intervention of a node Vj, our algorithm updates Φi. In this way, we need not compute the full atomic intervention of its next node from scratch but from the cached factor each time. All clusters can compute the full atomic interventions in parallel to accelerate the process.

Algorithm 1 FullDo

Input: e: a set of evidences

Output: the full atomic intervention of all network variables

• 1: compile the jointree;
• 2: messages are passed toward the root;
• 3: messages are passed away from the root;
• 4: for (each cluster Ci) do
• 5: receive messages from its all neighbors;
• 6: select an intervention order πi in the cluster;
• 7: for (each node Vj ∈ πi) do
• 8: if (Vj is the first node) Φi = ∅;
• 9: use Theorem 3.2 and Φi to compute P(e|do(Vj));
• 10: update Φi;
• 11: end for;
• 12: end for;
• 13: return (the full atomic interventions of all variables);

The time complexity of our algorithm for computing the full intervention in Bayesian networks is O(n · exp(w)+n21 · l · exp(w1)), where n is the number of network variables, w is the network treewidth, n1 is the number of network variables in the biggest cluster, l is the number of clusters for the jointree and w1 is the biggest network treewidth of all clusters. Using Pearl's Eq. (6), we implement a jointree algorithm called Do to compute the causal effect of the full atomic interventions of all nodes in a Bayesian network. The time complexity of Do is O(n · exp(w)+m· n21 · l · exp(w1)), where m is the maximum value of |Vi| (i = 1, · · · , |V|).

4 The differential semantics of intervention

We recompute ∂P(c) ∂P(b|a) shown in Eq. (3). We call node B as differential node and first compute P(c) as shown below.

This is because first ∑e P (e|c) = 1, next ∑d P (d|b, c) = 1 and finally ∑b P(b|a) = 1. Since P(c) = ∑a P(a)P(c|a), ∂P(c) ∂P(b|a) = ∂ ∑a P(a)P(c|a) ∂P(b|a) = 0. Thus P(e|c), P(b|a) and P(d|b, c) have no contribution to ∂P(c) ∂P (b|a) . We observe that nodes E,B and D cannot reach node C. From this finding, we give the following theorem.

Theorem 4.1 If a differential node Vi cannot reach any one of the evidence nodes e, then ∂P(e) ∂P(vi|ui) = 0.

Proof. Shachter [Shachter, 1986] had proved that any node which cannot reach any one of the evidence nodes e has no contribution to the marginal probability in a Bayesian network. Thus ∂P(e) ∂P(vi|ui) = 0. □

So the outputs of the jointree algorithm [Park and Darwiche, 2004] is not differentiation of Bayesian networks in this case. We then reveal the differential semantics of intervention in Bayesian networks and begin with the differentiation of P(e) with respect to a differential node Vi.

Lemma 4.1 If Vi can reach e in a Bayesian network, we can compute the first derivative of P(e) with respect to P(vi|ui) using the following formula:

Proof. We prove the theorem as follows.

Hence the lemma is proved. □

We reveal the following connection between the first derivative and atomic intervention of Bayesian networks.

Theorem 4.2 In Bayesian networks, a full intervention has the following differential semantics.

Proof. 1. From Lemma 4.1, we know if Vi can reach e, ∂P (e) ∂P (vi|ui) = ∑v\{vi,ui,e} P ′ (vi|ui) ∏j̸=i P (vj |uj ) Next we can derive P(e|do(Vi)) as follows.

2. According to Shachter [Shachter, 1986] theorem, if node Vi which cannot reach any one of the evidence nodes, then Vi has no contribution to the marginal probability of e in a Bayesian network. Thus P(e|vi) = P(e) whenever P(vi) > 0. If we intervene on node Vi, we change its CPT into a PIT. Since we do not change the network structure, P(e|vi) = P(e) whenever P(vi) > 0. □

Using Theorem 4.2, we can derive the following Corollary.

Corollary 4.1 In Bayesian networks, an atomic intervention has the following differential semantics.

Let Vi = vk i . Corollary 4.1 directly follows from Theorem 4.2.

So far we highlight the relationship between atomic interventions and first derivatives. Intuitively, there should be similar relationship between multiple interventions and higherorder derivatives. For example, if both B and C are intervention variables, the post-intervention distribution would be

On the other hand, the corresponding second derivative ∂ 2P (d,e) ∂P(b|a)∂P(c|a) = P(a)P(d|b, c)P(e|c). We can see that the two also have similar connections. Due to space limitation, we do not include the discussions in this paper.

5 Experiments

To test our algorithm, we study its performance in real Bayesian networks. We implement our FullDo and Do based on BNJ [kdd, 2006]. The experiments were conducted on a PC with Intel core2, 1.8GHz, 4.0G memory and Linux. We compute the full atomic intervention of the real world Bayesian networks, which are selected from the benchmark [ace, 2003]. The statistics of these networks are summarized in Table 1, where ∑ |Vi| denotes the number of values for all network variables in a Bayesian network and | ¯m| represents the average number of values for each network variable.

Since both FullDo and Do are based on the jointree algorithm, we first compile the jointree for them and use Compile to denote the compilation phase of FullDo and Do. We next compute the full atomic intervention of all nodes with respect to evidence variables and use FullDo-I and Do-I to represent the time for computing the full atomic intervention of all nodes in the outward phase by using our method and Pearl's method respectively. From Table 2, we can see that FullDo performs better than Do for all Bayesian networks. This is because our FullDo computes the full atomic intervention of each node by a single Bayesian network inference while Do computes each atomic intervention by one Bayesian network inference. In order to compute the full atomic intervention of each node Vi, Do has to employ |Vi| Bayesian network inferences. Comparing | ¯m| in Table 1 with the ratio of FullDo-I to Do-I in Table 2, we further observe that the speedup ratio is positively correlated with | ¯m| but less than | ¯m|. The reasons are as follows. Since it can independently compute every atomic intervention of a node, Do computes each full atomic intervention in a parallel way. Moreover, the intermediate results of our algorithm are larger than those of Do.

6 RelatedWork

Differentiation and evaluation are two inference methods in Bayesian networks. Evaluation is widely studied in Bayesian networks. Russell et al. [Russell et al., 1995] originally studied the derivatives with respect to network parameters. Castillo et al. [Castillo et al., 1997] initially introduced the network polynomial to denote the Bayesian networks. After compiling the network polynomial into arithmetic circuits, Darwiche [Darwiche, 2003] performed inference in Bayesian networks by evaluating the circuits in a bottom-up manner and computed the first derivatives with respect to network parameters by differentiating the circuits in a top-down manner. Park and Darwiche [Park and Darwiche, 2004] further introduce a jointree algorithm to compute the first derivatives and studied the relationship between circuit propagation and jointree propagation. They found that an arithmetic circuit is implicitly encoded in a jointree. However, we find that the outputs of their jointree algorithm [Park and Darwiche, 2004] are not the differentiation but the intervention of the Bayesian networks if a differential node Vi cannot reach the set of evidence nodes e. Accordingly, the output of arithmetic circuit is not the differentiation but the intervention of a Bayesian network in this case In causal networks, there are two ways to represent the intervention. One is graphs as models of intervention and the other is interventions as variables [Pearl, 1993]. The do(x) was first used in Goldszmidt and Pearl [Goldszmidt and Pearl, 1992] and has become popular. Pearl [Pearl, 2009b] encoded the intervention by changing the network structure. In this paper, we study the intervention in two novel ways. One way is that we encode an atomic intervention as changing a CPT into a partial intervention table. The other way is that we reveal the connection between the differentiation and intervention. Pearl [Pearl, 2009b] discovered that statisticians read structural equations as statements about E(Y |x) while economists read them as E(Y |do(x)). We find that statisticians directly compute the result from the observation while economists compute the result by differentiating the observation. Thus, statisticians and economists use the observation from different perspectives.

7 Conclusions

Bayesian networks are a very general tool that can be used for a large number of artificial intelligence problems: reasoning, learning, planning, perception and etc. Causal Bayesian networks can represent and respond to external or spontaneous changes. Any local reconfiguration of the mechanisms in the environment can be translated, with only minor modification, into an isomorphic reconfiguration of the network topology. In this paper, we show that action is the derivative of the observation while prediction directly computes from the observation. Thus, there is one step between causal effect and prediction just like the relationship between velocity and displacement. Moreover, there are two ways to encode intervention. One is Pearl's method to change the network structure, and the other is our technique to alter the network parameters (CPTs). As a future work, we will reveal the relationship between multiple interventions and higher-order derivative of Bayesian networks.

Acknowledgment

This work is partially funded by the National Natural Science Foundation of China under Grant No. 61170012 and the National Basic Research Program of China (973 Program) under Grant No. 2012CB316205