Compiling Bayesian Networks Using Variable Elimination

1 Introduction

Variable elimination [Zhang and Poole, 1996; Dechter, 1996] (VE) is a well-known algorithm for answering probabilistic queries with respect to a Bayesian network. The algorithm runs in time and space exponential in the treewidth of the network. Advantages of VE include its generality and simplicity. In this paper, we consider two aspects of VE. The first is how to effectively utilize local structure in the form of determinism [Jensen and Andersen, 1990] and context-specific independence [Boutilier et al., 1996] to perform inference more efficiently. The second consideration is how to answer multiple queries simultaneously. For example, given particular evidence, we would like to be able to simultaneously compute probability of evidence and a posterior marginal on each network variable. And we would like to be able to repeat this process for many different evidence sets.

Many proposals have been extended to utilize local structure in the context of VE. Although the standard version of the algorithm uses tables to represent factors, the algorithm can sometimes run more efficiently by using a more structured representation like ADDs [R.I. Bahar et al., 1993], affine ADDs [Sanner and McAllester, 2005], representations composed of confactors [Poole and Zhang, 2003], sparse representations [Larkin and Dechter, 2003], and a collection of others. Such a representation makes use of local structure to skip certain arithmetic operations and to represent factors more compactly. However, the effectiveness of these approaches has been sometimes limited in practice, because the overhead they incur may very well outweigh any gains.

∗This work has been partially supported by Air Force grant #FA9550-05-1-0075-P00002 and JPL/NASA grant #1272258.

There has been less work to answer multiple queries simultaneously using VE as is done by the jointree algorithm [Jensen et al., 1990; Lauritzen and Spiegelhalter, 1988]; but see [Cozman, 2000] for an exception. Theoretical results in [Darwiche, 2000] demonstrate that by keeping a trace, one can use VE as a basis for compilation. This algorithm, which we will refer to as tabular compilation, will compile a Bayesian network offline into an arithmetic circuit (AC). Tabular compilation runs in time and space exponential in treewidth; the resulting AC has size exponential in treewidth; and once offline compilation is complete, the AC can be used online to answer many queries simultaneously in time linear in its size. However, the applicability of this approach is limited, because tabular compilation provides no practical advantage over jointree.

An important observation is that when compiling using VE, we need not use tables, but can instead use one of the more structured representations of factors. This observation is seemingly innocent, but it has two critical implications. First, the usual cost incurred when using structured representations gets pushed into the offline phase, where it can be afforded. Second, the usual advantage realized when using more structured representations means that the size of the resulting AC will not necessarily be exponential in treewidth. The smaller AC translates directly into more efficient online inference, where efficiency matters most. We see that the proposed approach is important for four key reasons. First, it exploits local structure much more effectively than previous techniques based on VE. Second, the approach allows any of the many VE variants to compute answers to multiple queries simultaneously. Third, the approach makes a large body of research into more structured representations of factors relevant in many more circumstances than it has been previously. Finally, experimental results demonstrate that on the considered networks, VE can exploit local structure as effectively as state-of-the-art algorithms based on conditioning as applied to a logical encoding of the networks, and can sometimes lead to much faster compilation times.

To demonstrate these ideas, we propose a new method of compiling based on VE and algebraic decision diagrams (ADDs). We will refer to this method of compiling as ADD compilation. It is well known that ADDs can represent the initial conditional probability distributions (factors) of a Bayesian network more compactly than tables. However, it is not clear whether ADDs will retain this advantage when producing intermediate factors during the elimination process, especially in the process of compilation which involves no evidence. Note that the more evidence we have, the smaller the ADDs for intermediate factors.

Experimental results will demonstrate several important points with respect to ADD compilation. The first point deals with AC sizes. ADD elimination (no compilation) can outperform tabular elimination (no compilation) when there are massive amounts of local structure, but can dramatically underperform tabular elimination otherwise. However, ADD compilation produces ACs that are much smaller than those produced by tabular compilation, even in many cases where there are lesser amounts of local structure. Second, because of the smaller AC size, online inference time is capable of outperforming jointree by orders of magnitude. Finally, ADD compilation can be much faster in some cases than a state-ofthe-art compilation technique, which reduces the problem to logical inference [Darwiche, 2002].

This paper is organized as follows. We begin in Section 2 by reviewing VE, elimination using ADDs, and compilation into ACs. Next, Section 3 shows how a trace can be kept during elimination employing ADDs to compile a network into an AC. We then discuss in Section 4 implications for compiling using structured representations of factors. We present experimental results in Section 5 and conclude in Section 6.

2 Background

In this section, we briefly review VE, elimination using ADDs, and compilation into ACs.

2.1 Variable Elimination

Variable elimination is a standard algorithm for computing probability of evidence with respect to a given a Bayesian network [Zhang and Poole, 1996; Dechter, 1996]. For space reasons, we mention only a few points with regard to this algorithm. First, the algorithm acts on a set of factors. Each factor involves a set of variables and maps instantiations of those variables to real-numbers. The initial set of factors are the network's conditional probability distributions (usually tables). Elimination is driven by an ordering on the variables called an elimination order. During the algorithm, two factor operations are performed many times: factors are multiplied and a variable is summed out of a factor. These factor operations reduce to performing many multiplication and addition operations on real-numbers. Although tables are the most common representation for factors, any representation that supports multiplication and summing-out can be used.

2.2 Elimination using ADDs

An ADD is a graph representation of a function that maps instantiations of Boolean variables to real-numbers [R.I. Bahar et al., 1993]. Figure 1 depicts an ADD and the corresponding table (function) it represents. In the worst case, an ADD has the same space complexity as a table representing the same function. Moreover, the factor operations of multiplication and summing-out are implemented on ADDs in polynomial time. There are four points that are important with respect to ADDs. First, because multiplication and summing-out are available for ADDs, we can use ADDs during VE instead of tables. Second, because ADDs can leverage local structure, an ADD can be much smaller than the corresponding table. Third, for the same reason, when applied to ADDs, the factor operations of multiplication and summing-out can result in far fewer arithmetic operations on numbers than the same factor operations acting on tables. Finally, the constants involved in using ADDs are much larger than those involved in using tables, so much so that elimination using ADDs will often take much longer than elimination using tables, even when the ADD performs fewer arithmetic operations on numbers, and so much so that we may run out of memory when using ADDs, even in cases where tabular elimination does not. We will discuss later how we can deal with many-valued variables within an ADD.

2.3 Compiling into ACs

The notion of using arithmetic circuits (ACs) to perform probabilistic inference was introduced in [Darwiche, 2000; 2003]. With each Bayesian network, we associate a corresponding multi-linear function (MLF) that computes the probability of evidence. For example, the network in Figure 2-in which variables A and B are Boolean, and C has three values-induces the following MLF:

The terms in the MLF are in one-to-one correspondence with the rows of the network's joint distribution. Assume that all indicator variables λx have value 1 and all parameter variables θx|u have value Pr(x|u). Each term will then be a product of probabilities which evaluates to the probability of the corresponding row from the joint. The MLF will add all probabilities from the joint, for a sum of 1.0. To compute the probability Pr(e) of evidence e, we need a way to exclude certain terms from the sum. This removal of terms is accomplished by carefully setting certain indicators to 0 instead of 1, according to the evidence.

The fact that a network's MLF computes the probability of evidence is interesting, but the network MLF has exponential size. However, if we can factor the MLF into something small enough to fit within memory, then we can compute Pr(e) in time that is linear in the size of the factorization. The factorization will take the form of an AC, which is a rooted DAG (directed acyclic graph), where an internal node represents the sum or product of its children, and a leaf represents a constant or variable. In this context, those variables will be indicator and parameter variables. An example AC is depicted in Figure 2. We refer to this process of producing an AC from a network as compiling the network.

Once we have an AC for a network, we can compute Pr(e) by assigning appropriate values to leaves and then computing a value for each internal node in bottom-up fashion. The value for the root is then the answer to the query. We can also compute a posterior marginal for each variable in the network by performing a second downward pass [Darwiche, 2003]. Hence, many queries can be computed simultaneously in time linear in the size of the AC. Another main point is that this process may then be repeated for as many evidence sets as desired, without recompiling.

3 ADDCompilation

We have seen how ADDs can be used in place of tables during VE and how compilation produces an AC from a network. In this section, we combine the two methods to compile an AC using a VE algorithm that employs ADDs to represent factors.

The core technique behind our approach is to work with ADDs whose sinks point to ACs (their roots) instead of pointing to constants. We will refer to these ADDs as symbolic ADDs. Given a Bayesian network, we convert each conditional probability table (CPT) into a symbolic ADD called a CPT ADD. To do so, we first convert the CPT into a normal ADD and then replace each constant n within a sink by a pointer to an AC consisting of a single node labeled with con- Algorithm 1 Multiply(α1 : SymADD, α2 : SymADD): returns SymADD.

1: swap α1 and α2 if Pos(α1) > Pos(α2) 2: if cache(α1, α2) ̸= null then 3: return cache(α1, α2) 4: else if α1 and α2 are leaf nodes then 5: α←newADD leaf node 6: Ac(α) ←newAC ∗ node with children Ac(α1) and Ac(α2) 7: else if Pos(α1) = Pos(α2) then 8: α←new internal node 9: V ar(α) ← V ar(α1) 10: Lo(α) ←Multiply(Lo(α1),Lo(α2)) 11: Hi(α) ←Multiply(Hi(α1),Hi(α2)) 12: else 13: α←new internal node 14: V ar(α) ← V ar(α1) 15: Lo(α) ←Multiply(Lo(α1), α2) 16: Hi(α) ←Multiply(Hi(α1), α2) 17: end if 18: cache(α1, α2) ←α 19: return α

stant n. For each variable X in the network, we also construct an indicator ADD, which acts as a placeholder for evidence to be entered during the online inference phase. Assuming that variable X is binary with values x1 and x2, the indicator ADD for X will consist of one internal node, labeled with variable X, and having two sink children. The child corresponding to x1(x2) will be a sink labeled with a pointer to a single-node AC that is itself labeled with indicator λx1 (λx2 ). Figure 3(a) shows a simple Bayesian network and Figure 3(b) shows the corresponding symbolic ADDs.

Working with symbolic ADDs requires a modification to the standard ADD operations, but in a minimal way. We first point out that ADD operations are typically implemented recursively, reducing an operation over two ADDs into operations over smaller ADDs, until we reach boundary conditions: ADDs that correspond to sinks. It is these boundary conditions that need to be modified in order to produce symbolic ADD operations. For example, Algorithm 1 specifies how to multiply two symbolic ADDs. When applied to an internal ADD node, the functions Pos, Lo, and Hi return the position of the variable labeling the node in the ADD variable order, the low-child (corresponding to false), and the high-child (corresponding to true), respectively. When applied to an ADD sink, the functions Pos and Ac return ∞ and a pointer to the AC that labels the sink, respectively. Finally, cache is the standard computed table used in ADD operations. The main observation is that the algorithm is identical to that for multiplying normal ADDs (see [R.I. Bahar et al., 1993]), except for Line 6. When multiplying normal ADDs, this line would label the newly created sink with a constant that is the product of the constants labeling α1 and α2. When multiplying symbolic ADDs, we instead label the new sink with a pointer to an AC that represents an analogous multiplication. This AC will consist of a new multiply node having children that are the ACs pointed to by α1 and α2. The algorithm for summing-out a variable from a symbolic ADD is constructed from the algorithm for summing-out a variable from a normal

Algorithm 2 Compile(N : Bayesian Network): returns AC.

• 2: π ← ordering on the variables (π(i) is ith variable in order)

1: Ψ ← the set of indicator and CPT ADDs for N 3: for i in 1 . . . number of variables in N do 4: P ← {α ∈ Ψ : αmentions variable π(i)} 5: Ψ← (Ψ-P) ∪ {Σπ(i) ∏α∈P α} 6: end for 7: β ← ∏α∈Ψ α 8: return Ac(β)

ADD in an analogous way, by modifying the code that labels newly created sinks. In this case, instead of labeling with a constant representing a sum, we instead label with a pointer to an new addition node.

We now describe the compilation process in Algorithm 2. Line 1 begins by representing the Bayesian network using symbolic ADDs as described previously. We then generate an ordering on the variables using a minfill heuristic on Line 2. Lines 3-7 perform variable elimination in the standard way, using the multiply and sum-out operations of symbolic ADDs. Afterward, we are left with a trivial symbolic ADD: a sink labeled with a pointer to an AC. This AC is a factorization of the network MLF and a compilation of the given network! Each internal node of the AC is labeled with a multiplication or addition operation, and each leaf is labeled with a constant or an indicator variable. The AC represents a history or trace of all arithmetic operations performed during the elimination process.

For the above procedure to scale and produce the results we report later, it has to be augmented by a number of key techniques that we describe next.

ADD variable order: ADDs require a fixed variable order which is independent of the elimination order we have discussed. For that, we use the reverse order used in the elimination process. This ensures that when a variable is eliminated from an ADD, it appears at the bottom of the ADD. The sumout operation on ADDs is known to be much more efficient when the summed out variable appears at the bottom.

Unique table: We maintain a cache, called a unique table in the ADD literature, to ensure that we do not generate redundant AC nodes. Each entry is an AC node that has been constructed, indexed the node's label and its children. Before we ever construct a new AC node, we first consult the unique table to see if a similar node has been constructed before. If this is the case, we simply point to the existing node instead of constructing a duplicate node. As is standard practice, we also use a unique table for the ADD nodes.

Multi-valued variables: When a network variable X has more than two values, we define its ADD variables as follows. For each value xi of X, we create ADD variable Vxi . We translate instantiations of X in the straightforward way. For example, we translate X = x2 as Vx2 = true and Vxi = false for i ̸= 2. Moreover, we construct an ADD over Vxi which enforces the constraint that exactly one Vxi can be true. We multiply this ADD into every CPT and indicator ADD that mentions X. Finally, when eliminating (summing-out) a multi-valued variable X, we sum out all corresponding ADD variables Vxi simultaneously.

Converting a CPT into an ADD: The straightforward way to construct the ADD of a CPT is to construct an ADD for each row of the CPT and then add the resulting ADDs. This method was extremely inefficient for large CPTs (over a thousand parameters). Instead, we construct a tree-structured ADD whose terminals correspond to the CPT rows, and then use the standard reduce operation of ADDs to produce a DAG structure.

Simplifications: In certain cases, simplifications are possible. For example, when multiplying two ADD nodes, if one of the nodes α is a sink labeled with a pointer to an AC node which which is itself labeled constant 0, then we can simply return α without doing more work. Similar simplifications exist for constant 1 and for the summing-out operation.

Figure 4 depicts the elimination process when applied to the symbolic ADDs of Figure 3(b) using elimination order Y,X. The first step is to multiply the set of symbolic ADDs involving Y , which consists of Y 's CPT ADD and Y 's indicator ADD. Figure 4(a) shows the result. Observe that each ADD sink points to an AC that represents the multiplication of two ACs, one pointed to by a sink from Y 's CPT ADD and one pointed to by a sink from Y 's indicator ADD. Also observe that when one of the ACs involved in the multiplication is a sink labeled with 0 or 1, the resulting AC is simplified. Figure 4(b) next shows the result of summing-out Y from the symbolic ADD in Figure 4(a). Here, each ADD node labeled with Y and its children have been replaced with a sink which points to an addition node. A simplification has also occurred. Figure 4(c) shows the result of multiplying symbolic ADDs involving variable X in two steps: first Figure 4(b) by X's indicator ADD and then the result by X's CPT ADD. Finally, Figure 4(d) shows the result of summing-out X from Figure 4(c). At this point, since there is only one remaining symbolic ADD, we have our compilation.

4 Implications

There has been much research into using alternatives to tabular representations of factors in VE. The motivation for such research is that tabular elimination makes use only of global network structure (its topology). It may therefore miss opportunities afforded by local structure to make inference more efficient. Structured representations of factors typically exploit local structure to lessen the space requirements required for inference and to skip arithmetic operations on numbers (multiplications and additions) required for inference. In some cases, structured representations of factors have been successful in performing inference when tabular elimination runs out of memory, and in some cases, structured representations allow for faster inference than tabular elimination. However, the time and space overhead involved in using more structured representations of factors may very well outweigh the benefits. This is particularly true when there are not excessive amounts of local structure present in the network. Table 1 demonstrates the performance of elimination (no compilation) using both tables and ADDs applied to the set of networks we will be considering later in the paper. All ADD operations were performed using the publicly available CUDD ADD package (http://vlsi.colorado.edu/∼fabio/CUDD). We see that in only two cases does ADD elimination outperform tabular elimination. Both of the networks involved, bm-53 and mm-3-8-3, contain massive amounts of determinism. In the remaining cases, ADD elimination is actually slower than tabular elimination, often by an order of magnitude or more. The large number of examples where structured representations of factors are slower than tabular elimination have limited their applicability.

The main observation behind this paper is that even when elimination using a more structured representation of factors is slower than tabular elimination, structured representations become very powerful in the context of compilation. Compilation is an offline process, and so extra time can be afforded. In fact, the combination of structured representations with compilation is ideal, since the very purpose of compilation is to spend time offline in an effort to identify opportunities for savings that can be used repeatedly during online inference. Hence, in the context of compilation, the disadvantages of using structured representations are much less severe (virtually disappearing) and the advantages are retained. 1 Although overhead is incurred during the offline phase, each arithmetic operation saved makes the size of the resulting AC smaller, yielding more efficient online inference. These observations make research into structured representations of factors applicable in many more circumstances than it has been previously. Another major advantage of adding compilation to elimination is that one can compute online answers to many queries simultaneously and very quickly as is done by the jointree algorithm; see [Darwiche, 2003] for details.

1 Note that the use of more structured representations of factors is usually asymptotically no worse than the use of tabular representations, which is particularly true for ADDs.

5 Experimental Results

In this section, we present experimental results of applying ADD compilation and compare ADD compilation to tabular compilation, Ace compilation, and jointree. All ADD operations were performed using the CUDD ADD package (http://vlsi.colorado.edu/∼fabio/CUDD), modified to work with symbolic ADDs. Ace (http://reasoning.cs.ucla.edu/ace) is a state-of-the-art compiler that encodes Bayesian networks as logical knowledge bases and then applies conditioning to the result. Ace has been shown to be extremely effective on networks having large amounts of local structure [Chavira et al., May 2006; 2005], able to compile many networks with treewidths in excess of one-hundred. Ace was also shown in [Chavira and Darwiche, 2005] to perform online inference orders of magnitude more efficiently than jointree when applied to networks having treewidth small enough for jointree to work and having lesser amounts of local structure. On these networks, Ace online inference is very efficient, but some compile times are in excess of one thousand seconds. The networks with which we experimented are a superset of these networks from [Chavira and Darwiche, 2005].

Experiments ran on a 2GHz Core Duo processor with 2GB of memory, using the networks in Table 2. 2 To make the experiments as fair as possible, for each network, we first generated an elimination order π, and all experiments were performed with respect to π. The second column in Table 2 shows the maximum cluster size of a jointree generated from π, which gives an indication of difficulty with respect to structure-based methods. We compiled each network using jointree, Ace 1.2, ADD VE, and tabular VE, in each case driven by π. We evaluate a compilation algorithm based on compilation time, compilation size, and online inference time. We first discuss compilation time, which includes reading the network, compiling, and writing the AC to disk.

2 Because Ace was not available for the test platform, Ace compilation was carried out on a 1.6GHz Pentium M with 2GB of memory.

Columns 3-5 compare Ace compilation time to ADD compilation time. We see that on these networks, neither algorithm dominates the other. Our experiments show that Ace compilation often ran faster than ADD compilation in the following cases: when the networks had very low treewdith (alarm, hailfinder, tcc4f) and when the networks had massive amounts of determinism (bm-5-3, mm-3-8-3, and st-3-2). We also found Ace compilation times to be significantly lower on networks (not shown) having very high treewidth (e.g., the blockmap and mastermind networks from [Chavira et al., May 2006]), many of which ADD compilation could not handle. However, ADD compilation times are significantly more efficient on precisely those networks on which Ace has trouble. In particular, networks with treewidths in the range 1430 having lesser amounts of local structure (barley, diabetes, link, mildew, and the munin networks). On these types of networks, Ace compilation can require thousands of seconds and ADD compilation can run an order of magnitude faster. Perhaps the most striking example is barley, on which Ace required over two hours while ADD compilation required a little over two minutes. Ace compilation also ran out of memory on link, which compiled successfully using ADDs.

We next discuss compilation sizes, which we measure using the number of edges of the AC produced. The AC size is important, because it determines the time and space requirements for online inference, which is linear in this size. The AC size also provides the main indicator for the extent to which local structure was exploited. AC sizes produced using ADDs and using Ace turned out to be very close, showing that both methods seem to exploit local structure to a similar extent. Columns 6-8 compare sizes of ACs that would be produced using tabular compilation to those produced using ADD compilation (the size of the AC embedded in a jointree [Park and Darwiche, 2004] would be about equal to the size of the AC produced by tabular compilation). ADD compilation sizes can be multiple orders of magnitude smaller than those produced by tabular compilation. The difference is most pronounced on networks having massive amounts of local structure (bm-5-3, mm-3-8-3, st-3-2), but is also striking in some other cases. For example, on munin1, munin4, pathfinder, and water, ADD compilation sizes were over 40, 11, 17, and 93 times smaller, respectively. We see here the massive advantage of utilizing more structured representations of factors when compiling via VE.

Because ACs produced using Ace were about the same size as those produced using ADDs, online inference times for the two compilation algorithms were also very similar. The last three columns in Table 2 compare online inference using ADD compilations and jointree (tabular compilation online times would be about equal to jointree online times). For each network, we generated 16 sets of evidence. For each evidence set, we then computed probability of evidence and a posterior marginal on each network variable. Note that answering these queries would be very difficult using standard VE (without compilation), because of the large number of queries involved. Each reported number is the sum of times for all 16 evidence sets. Here we see an online time advantage to ADD compilation about equal to its large space advantage over tabular compilation, which makes sense, since neither tabular compilation nor jointree make use of local structure. Once again we see the massive advantage that can be achieved by utilizing structured representations of factors during compilation.

6 Conclusion

In this paper, we combined three ideas: variable elimination, compilation, and structured representations of factors. The result is an algorithm that retains the advantages of these approaches while minimizing their shortcomings. The approach is important for the following reasons: (1) it utilizes local structure more effectively than previous approaches based on VE; (2) it allows any variant of VE to answer multiple queries simultaneously; (3) it makes a large body of research into structured representations of factors more relevant than it had been previously; and (4) it demonstrates that variable elimination can utilize local structure as effectively as state-ofthe-art approaches based on conditioning (applied to a logical encoding of the Bayesian network), and can sometimes lead to much faster compilation times.