TCS -TR-A-06-18

TCS Technical ReportCompiling Bayesian Networks by Symbolic Probability
Calculation Using Zero-suppressed BDDs
by

Shin-ichi Minato, Ken Satoh, and Taisuke Sato

Division of Computer Science
Report Series A
July 3, 2006

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

minato@ist.hokudai.ac.jp

Phone:+81-011-706-7682

Fax:+81-011-706-7682

Compiling Bayesian Networks by Symbolic Probability Calculation
Using Zero-suppressed BDDs
Shin-ichi Minato

Ken Satoh

Taisuke Sato

Hokkaido University
North 14, West 9
Sapporo 060-0814, Japan

National Institute of Informatics
Chiyoda-ku, 2-1-2, Hitotsubashi
Tokyo 101-8430, JapanTokyo Institute of Technology
2-12-1 Ookayama, Meguro-ku
Tokyo 152-8550, Japan

July 3, 2006
(Abstract) Compiling Bayesian networks (BNs)is one of the hot topics in the area of probabilistic
modeling and processing. In this paper, we propose a new method of compiling BNs into multilinear functions (MLFs) based on Zero-suppressed
BDDs (ZBDDs), which are the graph-based representation of combinatorial item sets. Our method
is diﬀerent from the original approach of Darwiche
et. al which encodes BNs into Conjunctive Normal Forms (CNFs) and then translates CNFs into
factored MLFs. Our approach directly translates a
BN into a set of factored MLFs using ZBDD-based
symbolic probability calculation. The MLF may
have an exponential size, but our ZBDD-based data
structure provides a compact factored form of the
MLF, and arithmetic operations can be executed ina time almost linear to the ZBDD size. Our method
is not necessary to generate the MLF for the wholenetwork, but we can extract MLFs for only a partof network related to the query, to avoid unnecessary calculation of redundant terms of MLFs. We
show experimental results for some typical benchmark examples. Although our algorithm is simply
based on the mathematical deﬁnition of probability calculation, the performance is competitive tothe existing state-of-the-art method.

1

for accelerating probability computation for BNs.
Darwiche et. al[6, 2] have shown an eﬃcient methodof compiling BNs into the factored forms of MultiLinear Functions (MLFs), whose evaluation anddiﬀerentiation solves the exact inference problem.
In their method, at ﬁrst a given BN structure is encoded to a Conjunctive Normal Form (CNF) to beprocessed in Boolean domain, and then the CNFs
are factored under Boolean algebra. The compilation procedure generates a kind of decision diagram representing a compact Arithmetic Circuit(AC) with the symbolic parameters.
In this paper, we propose a new methodof compiling BNs into factored MLFs based on
Zero-suppressed BDDs (ZBDDs)[7], which are thegraph-based representation at ﬁrst proposed for
VLSI logic design applications. Our method isbased on a similar MLF modeling with symbolic
parameters as well as Darwiche’s approach. However, our method does not use CNF representation
but directly translates a BN into a set of factored
MLFs. Our ZBDD manipulator can generate a
new ZBDD as the result of addition/multiplication
operations between a pair of ZBDDs. Using suchinter-ZBDD operations with a bottom-up manneraccording to the BN structure, we can produce a
set of ZBDDs each of which represents the MLF
of each BN nodes. We can see an important property that the total product of the ZBDDs for all
BN nodes corresponds to the factored MLF which
is basically equivalent to the Darwiche’s result. In
addition, our method is not necessary to calculate
the MLF for the whole network, but we can ex-

Introduction

Compiling Bayesian Networks (BNs) is one of the
hot topics in the area of probabilistic modeling andprocessing. Recently, the data structures of decision diagrams[9, 4, 5, 6, 2, 10] are eﬀectively used1

2

Shin-ichi Minato, Ken Satoh, and Taisuke Sato

tract MLFs for only a part of network related tothe query, to avoid unnecessary calculation of redundant terms of MLFs.
In this paper, we show experimental results
for some typical benchmark examples. Although
our algorithm is simply based on the mathematical deﬁnition of probability calculation, the performance is competitive to the existing state-of-theart method.
Our ZBDD-based method can also be comparedwith the recent work by Sanner and McAllester[10],computing BN probabilities using Aﬃne Algebraic
DDs (AADDs). Their method generates AADDs
as the results of inter-AADD operations for a given
BN and an inference query. This is somehow a similar manner to us, but the semantics of decision diagrams are quite diﬀerent. We discuss the diﬀerence
in a later section.
In the following sections, we describe the basic
concept of BN compilation and existing method in
Section 2. We then show the data structure of ZBDDs for representing MLFs in Section 3. In section
4, we describe the procedure of ZBDD generationand online inference. Experimental result is shownin Section 5, followed by conclusion.

2

Preliminary

Here we brieﬂy review the method of compiling
BNs.

A
a1
a2
AB
a1 b1
a1 b2
a2 b1
a2 b2

Prb(A)
θa1 = 0.4
θa2 = 0.6
Prb(B|A)θb1 |a1 = 0.2
θb2 |a1 = 0.8
θb1 |a2 = 0.8
θb2 |a2 = 0.2

AC
a1 c1
a1 c2
a2 c1
a2 c2

Prb(C|A)θc1 |a1 = 0.5
θc2 |a1 = 0.5
θc1 |a2 = 0.5
θc2 |a2 = 0.5

BC D
b1 c1 d1
b1 c1 d2
b1 c1 d3
b1 c2 d1
b1 c2 d2
b1 c2 d3
b2 c1 d1
b2 c1 d2
b2 c1 d3
b2 c2 d1
b2 c2 d2
b2 c2 d3

Prb(D|B, C)
θd1 |b1 c1 = 0.0
θd2 |b1 c1 = 0.5
θd3 |b1 c1 = 0.5
θd1 |b1 c2 = 0.2
θd2 |b1 c2 = 0.3
θd3 |b1 c2 = 0.5
θd1 |b2 c1 = 0.0
θd2 |b2 c1 = 0.0
θd3 |b2 c1 = 1.0
θd1 |b2 c2 = 0.2
θd2 |b2 c2 = 0.3
θd3 |b2 c2 = 0.5

Figure 1: An example of BN.

a term for each instantiation of the BN variables,
and the term is the product of all indicators andparameters that are consistent with the instantiation. For the example in Fig. 1, the MLF has thefollowing forms.
λa1 λb1 λc1 λd1 θa1 θb1 |a1 θc1|a1 θd1 |b1 c1+ λa1 λb1 λc1 λd2 θa1 θb1 |a1 θc1|a1 θd2 |b1 c1+ λa1 λb1 λc1 λd3 θa1 θb1 |a1 θc1|a1 θd3 |b1 c1+ λa1 λb1 λc2 λd1 θa1 θb1 |a1 θc2|a1 θd3 |b1 c2
+ ...

2.1

Bayesian networks and MLFs

A Bayesian network (BN) is a directed acyclic
graph. Each BN node has a network variable X
whose domain is a discrete set of values. Each
BN node also has a Conditional Probability Table(CPT) to describe the conditional probabilities ofthe variable X to be respective values for respective conditions of the parent BN nodes. Figure 1
shows a small example of BN with CPTs.
The Multi-Linear Function (MLF)[5] consists of
two types of variables, indicator variable λx foreach value X = x, and parameter variable θx|u
for each parameter Prb(x|u). The MLF contains+ λa2 λb2 λc2 λd3 θa2 θb2 |a2 θc2|a2 θd3 |b2 c2
Once we have generated the MLF for a given
BN, the probability of evidence e can be calculated by setting indicators that contradict e to 0
and other indicators to 1. Namely, we can calculate the probability in a linear time to the size of
MLF. Obviously the MLF has an exponential size,
so the computation requires exponential time andspace. The MLF can be factored into an Arithmetic
Circuit (AC) whose size may not be exponential. If
we can generate a compact AC for a given BN, theprobability calculation can greatly be accelerated.
This means compiling BNs based on MLFs.

Compiling Bayesian Networks by Symbolic Probability Calculation Using Zero-suppressed BDDs

F1
a

F2
1

0

0

b
0

0

1

a

F3
1

F4

0

1

b
0

1

3

a
1

F 1 = a∧b
F 2 = a⊕b
F3 = b
F 4 = a∨b

Figure 2: Shared multiple BDDs.
Figure 3: A Boolean function and a combinatorial
item set.

2.2

Compiling BNs based on CNFs

Darwiche et. al[6] have shown an eﬃcient method
for generating compact ACs without processing an
exponential size of MLFs. In their method, at ﬁrst
a given BN structure is encoded to a Conjunctive
Normal Form (CNF) to be processed in Boolean
domain. The CNF is factored by all variables one
by one based on Boolean algebra, and a kind ofdecision diagram is obtained. The result of diagram
has a special property called smooth deterministic
Decomposable Negational Normal Form (smooth dDNNF)[4], so it can directly be converted to the AC
for probability calculation.
In addition, the following two techniques areused in variable encoding:• If a parameter is deterministic (θx|u = 1 or 0),
we do not assign a parameter variable and justreduce the CNF.
• The diﬀerent parameter variables related tothe same BN node do not coexist at the same
term of MLF. Therefore, if a CPT contains a
number of parameters with a same probability, we do not have to distinguish them andwe may assign only one parameter variable toshare those. This technique sometimes greatly
reduces the CNF.
The experimental results reported that their
method succeeded in compiling large-scale benchmark networks, such as “pathﬁnder” and “Diabetes,” with a practical computation time andspace. The BN compilation method is one of the
hot topics on probabilistic modeling and inference
for practical problems.

3

Zero-suppressed BDDs

In this paper, we present a new method of manipulating MLFs using Zero-suppressed BDDs (ZBDDs). Here we describe our data structure.

3.1

ZBDDs and combinatorial item sets

Reduced Ordered BDD (ROBDD)[1] is a compact
graph representation of the Boolean function. It isderived by reducing a binary tree graph representing recursive Shannon’s expansion. ROBDDs provide canonical forms for Boolean functions whenthe variable order is ﬁxed. (In the following sections, we basically omit “RO” from BDDs.) As
shown in Fig. 2, a set of multiple BDDs can beshared each other under the same ﬁxed variable
ordering. In this way, we can handle a number ofBoolean functions simultaneously in a monolithic
memory space.
A conventional BDD package supports a set ofbasic logic operations (i.e. AND, OR, XOR) for
given a pair of operand BDDs. Those operation algorithms are based on hash table techniques, andthe computation time is almost linear to the data
size unless the data overﬂows the main memory.
By using those inter-BDD operations, we can generate BDDs for given Boolean expressions or logic
circuits.
BDDs are originally developed for handling
Boolean function data, however, they can also be
used for implicit representation of combinatorial
item sets. A combinatorial item set consists of theelements each of which is a combination of a number of items. There are 2n combinations chosen

4Shin-ichi Minato, Ken Satoh, and Taisuke Sato

• Share equivalent nodes as well as ordinary
BDDs.

Figure 4: An example of ZBDD.

0

f

x

Jump

1

0

f

Figure 5: ZBDD reduction rule.

nfrom n items, so we have 22 variations of combinatorial item sets. For example, for a domain ofﬁve items a, b, c, d, and e, we can show examples ofcombinatorial item sets as:{ab, e}, {abc, cde, bd, acde, e}, {1, cd}, 0.
Here “1” denotes a combination of null items, and0 means an empty set. Combinatorial item sets are
one of the basic data structure for various problems
in computer science.
A combinatorial item set can be mapped into
Boolean space of n input variables. For example,
Fig. 3 shows a truth table of Boolean function:
F = (a b c) ∨ (b c), but also represents a combinatorial item set S = {ab, ac, c}. Using BDDs for thecorresponding Boolean functions, we can implicitly
represent and manipulate combinatorial item set.
Zero-suppressed BDD (ZBDD)[7] is a variant of
BDDs for eﬃcient manipulation of combinatorial
item sets. An example of ZBDD is shown in Fig. 4.
ZBDDs are based on the following special reduction
rules.
• Delete all nodes whose 1-edge directly points
to the 0-terminal node, and jump through to
the 0-edge’s destination, as shown in Fig. 5.

The zero-suppressed deletion rule is asymmetric forthe two edges, as we do not delete the nodes whose
0-edge points to a terminal node. It is proved thatZBDDs are also gives canonical forms as well as ordinary BDDs under a ﬁxed variable ordering. Here
we summarize the properties of ZBDDs.
• The nodes of irrelevant items (never chosen in
any combination) are automatically deleted by
ZBDD reduction rule.
• Each path from the root node to the 1-terminal
node corresponds to each combination in theset. Namely, the number of such paths in the
ZBDD equals to the number of combinationsin the set.
• When many similar ZBDDs are generated,their ZBDD nodes are eﬀectively shared intoa monolithic multi-rooted graph, so the memory requirement is much less than storing each
ZBDD separately.
Table 1 shows the most of primitive operationsof ZBDDs. In these operations, ∅, 1, P.top are executed in a constant time, and the others are almost
linear to the size of graph. We can describe various
processing on sets of combinations by composing ofthese primitive operations.

3.2

MLF representation using ZBDDs

An MLF is a polynomial formula of indicator andparameter variables. It can be regarded as a combinatorial item set, since each term is just a combination of variables. For example, the MLF at Node
B in Fig. 1 can be written as follows.
MLF(B) = λa1 λb1 θa1 θb1 |a1 + λa1 λb2 θa1 θb2 |a1+λa2 λb1 θa2 θb1 |a2 + λa2 λb2 θa2 θb2 |a2
Here, we rename the parameter variables to sharethe same probabilities.
MLF(B) = λa1 λb1 θa(0.4) θb(0.2) + λa1 λb2 θa(0.4) θb(0.8)+λa2 λb1 θa(0.6) θb(0.8) + λa2 λb2 θa(0.6) θb(0.2)

Compiling Bayesian Networks by Symbolic Probability Calculation Using Zero-suppressed BDDs“∅”
“1”
P .top
P .factor0(v)P .factor1(v)P .attach(v)
P ∪Q
P ∩Q
P −Q
P .count

5

Table 1: Primitive ZBDD operations.
Returns empty set. (0-termial node)
Returns the set of only null-combination. (1-terminal node)
Returns the item-ID at the root node of P .
Subset of combinations not including item v.
Gets P − P .factor0(v) and then deletes v from each combination.
Attaches v to all combinations in P .
Returns union set.
Returns intersection set.
Returns diﬀerence set. (in P but not in Q.)
Counts number of combinations.

Then, we show an example of ZBDD for MLF(B)in Fig. 6. In this example, there are four paths
from the root node to the 1-terminal node, each ofwhich corresponds to a term in the MLF. Namely,
it is an implicit representation of the MLF. At thesame time, the structure of ZBDD also represents acompact factored form of MLF. As shown in Fig. 7,
each ZBDD decision node can be interpreted as afew AC nodes with the simple mapping rule. Thismeans that a compact AC is quite easily obtained
when we have generated a ZBDD for MLF.
We can see an important property that our
ZBDD representation for an MLF is basicallyequivalent to a smooth d-DNNF, obtained by Darwiche’s CNF-based method[6, 2]. In the following
sections, we show our new method for generating
ACs without CNFs but only using ZBDD operations.

3.3

Comparison to AADDs

Sanner and McAllester[10] presented Aﬃne Algebraic Decision Diagrams (AADDs), another variant of decision diagram, for computing BN probabilities. AADD is a factored form of ADD, whichcontains indicator variables for splitting conditions,and the results of respective conditional probabilities are written in the leaves of the graph. This issomehow similar to our approach since they generate AADDs as the result of algebraic operationsof AADDs. The most diﬀerent point is that they
numerically calculate the probability values witha ﬂoating-point data format, not using symbolic

Figure 6: An example of ZBDD for MLF(B).

probability parameters as our MLFs. It is an interesting open problem which is more eﬃcient tohandle probabilities in symbolic or numerical. It
may depend on the instances of probability values
written in CPTs.

4

ZBDD-based MLF calculation

4.1

ZBDD construction procedure

BDDs are originally developed for VLSI logic circuit design[1], and the basic technique of BDD construction is shown in Fig. 8. First we make trivial
BDDs for the primary inputs F1 and F2 , and then6Shin-ichi Minato, Ken Satoh, and Taisuke Sato

Figure 7: Mapping from a ZBDD node to an ACnode.

we apply the inter-BDD logic operations according
to the data ﬂow, to generate BDDs for F3 to F7 .
After that, all the BDDs are shared into a monolithic multi-rooted graph. This procedure is called
symbolic simulation for the logic circuit.

Figure 8: Conventional BDD construction procedure.

Our ZBDD construction procedure for the MLF
is based on a similar manner to the symbolic simulation of logic circuit. The diﬀerent points are:• BNs do not only assume binary values. The
MLF uses multiple variables at each node forrespective values.
• The BN node is not a logic gate. The functionof each node is speciﬁed by a CPT.
As shown in Fig. 9, we ﬁrst make MLF(A), andthen we generate MLF(B) and MLF(C) using theresult of MLF(A). Finally we generate MLF(D) using the results for the node B and C. After the construction procedure, all MLFs for respective nodes
are compactly represented by the shared ZBDDs.
On each BN node X, the MLF is calculated by
the following operations using the MLFs at the parent nodes of X.
MLF(Xi ) = λxi ·u∈CPT(X)θx(Pu ) ·


Yv ∈u



MLF(Yv )Here MLF(Xi ) denotes the MLF for the node Xto be a value xi . Namely, MLF(X) = MLF(Xi ).
When calculating this expression using the
ZBDD operations, we have to consider the diﬀerences between the arithmetic algebra and combinatorial set algebra. For considering arithmetic sum,
we may use union operation to perform arithmetic
sum, because the MLF does not contain the same

Figure 9: ZBDD construction procedure for BN.

term more than once. We should be more careful for arithmetic product operation. Product of
two MLFs produces all possible combinations of
two terms from the respective MLFs. Here, probabilistic algebra does not produces x2 for duplicate
variables, but just returns x. In addition, λxi andλxj (same node but diﬀerent values) cannot coexist
in one term since at least either becomes zero.

4.2

Multi-valuedrithm

multiplicationalgo-

The multiplication algorithm is a key technique inour compiling method. The conventional algorithm
for product of two ZBDDs has been presented in
the article[8]. The sketch of the algorithm is shownin Fig. 10. This algorithm is based on a divide-andconquer manner, with the two recursive calls forthe sub-graphs obtained by assigning 0 and 1 into
the top variable. It also uses a hash-based cachetechnique to avoid duplicated recursive calls. The

Compiling Bayesian Networks by Symbolic Probability Calculation Using Zero-suppressed BDDs

computation time is almost linear to the ZBDD
size.
Unfortunately, the conventional algorithm does
not consider multi-valued variable encoding, so theresult of ZBDD may contain redundant terms, suchas one both λxi and λxj coexist. Such redundant
MLFs are still correct expressions for probability
calculation, however, the redundant terms cause asigniﬁcant overhead of computation time. For example, we analyzed our MLF construction for a BN
in the benchmark set. It is a typical case that wehave the two ZBDDs F and G each of which has
about 1,000 decision nodes, and the product (F ·G)
grows as much as 200,000 nodes of ZBDD, but it
can be reduced to only 400 nodes after eliminating redundant terms. This observation indicates
that, the redundant terms consume 500 times ofoverhead time and space in this case.
To address this problem, we implemented an
improved multiplication algorithm devoted to themulti-valued variable encoding. Figure 11 showsa sketch of new algorithm. Here we assume thatthe indicator variables for a same BN node havethe consecutive positions in the ZBDD variable ordering. This algorithm does not produce any redundant terms in the recursive procedure, and we
can calculate MLFs without any overhead related
to the multi-valued encoding.

4.3

Online inference based on ZBDDs

After the compilation procedure, each BN node has
its own ZBDD for the MLF. The MLF(X) on anode X contains only the variables at the ancestor
nodes of X, since the other variables are irrelevantto the probabilities on X.
Here we describe the online inference method
based on ZBDDs. To obtain the joint probability for evidence e, we ﬁrst compute the productof MLF(Xv ) for all Xv ∈ e by the ZBDD multiplication operation. The contradicting terms areautomatically eliminated by our multiplication algorithm, so the result of ZBDD contains only thevariables related to the joint probability computation. We then set all indicators to 1 and calculate
the AC directly converted from the ZBDD.

7

For example, to compute Prb(b1 , c2 ) for the BN
of Fig. 1, the two MLFs are the follows:
MLF(B1 ) = λa1 λb1 θa(0.4) θb(0.2) +λa2 λb1 θa(0.6) θb(0.8) ,MLF(C2 ) = λa1 λc2 θa(0.4) θc(0.5) +λa2 λc2 θa(0.6) θc(0.5) ,and then
MLF(B1 ) · MLF(C2 ) = λa1 λb1 λc2 θa(0.4) θb(0.2) θc(0.5)+λa2 λb1 λc2 θa(0.6) θb(0.8) θc(0.5) .
Finally we can obtain the probability as: 0.4×0.2×
0.5 + 0.6 × 0.8 × 0.5.
In our method, each multiplication requires atime almost linear to the ZBDD size, however, theZBDD size may not glow larger in repeating multiplications for the inference, because many of terms
contradict the evidence and they are eliminated.
Therefore, the computation cost for the inference
will be much smaller than the cost for compilation.
An interesting point is that the above MLF forPrb(b1 , c2 ) does not contain the variables at thenode D since they are irrelevant to the joint probability. In other word, our inference method provides dependency checking for a given query.
As another strategy, we can generate the MLF
for the whole networks by performing product of all
MLF(X). Such a global MLF is basically equivalent to the result of Darwiche’s compilation[2]. After generating the global MLF, we do not have toperform product of MLFs any more. However, theMLF contains the parameters of all the BN nodes,
and we should sum up the parameters even if they
are irrelevant to the query. Having a set of local
MLFs will be more eﬃcient than the global one
since we can avoid unnecessary calculation of parameters not related to the query.
Finally we note that our method can save theresult of partial product of MLFs in the shared
ZBDD environment, so we do not have to recompute ZBDDs for the same evidence set.

5

Experimental Results

For evaluating our method, we implemented a
BN compiler based on our own ZBDD package.
We used a Pentium-4 PC, 800MHz, 1.5GB ofmain memory, with SuSE Linux 9 and gnu C++
compiler. In this platform, we can manipulate up
to 40,000,000 nodes of ZBDDs with up to 65,000

8Shin-ichi Minato, Ken Satoh, and Taisuke Sato

procedure(F · G)
{ if (F.top < G.top) return (G · F ) ;if (G = 0) return 0 ;if (G = 1) return F ;H ← cache(“F · G”) ;if (H exists) return H ;v ← F.top ; /* the highest item in F */(F0 , F1 ) ← factors of F by v ;(G0 , G1 ) ← factors of G by v ;H ← ((F1 · G1 ) ∪ (F1 · G0 ) ∪ (F0 · G1 )).attach(v) ∪ (F0 · G0 ) ;cache(“F · G”) ← H ;return H ;}Figure 10: Conventional multiplication algorithm.
procedure(F · G)
{ if (F.top < G.top) return (G · F ) ;if (G = 0) return 0 ;if (G = 1) return F ;H ← cache(“F · G”) ;if (H exists) return H ;v ← F.top ; /* the highest item in F */(F0 , F1 ) ← factors of F by v ;(G0 , G1 ) ← factors of G by v ;FZ ← F0 ; GZ ← G0 ;while(FZ .top and v conﬂict) FZ ← FZ .factor0(FZ .top) ;while(GZ .top and v conﬂict) GZ ← GZ .factor0(GZ .top) ;H ← ((F1 · G1 ) ∪ (F1 · GZ ) ∪ (FZ · G1 )).attach(v) ∪ (F0 · G0 ) ;cache(“F · G”) ← H ;return H ;}Figure 11: Improved multiplication algorithm.

diﬀerent variables. We applied our method tothe practical size of BN examples provided at
http://www.cs.huji.ac.il/labs/compbio/Repository.
The experimental results are shown in Table 2.
In this table, the ﬁrst four columns shows the network speciﬁcations, such as BN name, the numberof BN nodes, the indicator variables, and the parameter variables to be used in the MLF. The next
three columns present the results of our compiling
method. “|ZBDDs|(total)” shows the number ofdecision nodes in the multi-rooted shared ZBDDs
representing the set of MLFs. “|ZBDD|(a node)”is the average size of ZBDD on each BN node. Notice that the total ZBDD size is usually much lessthan numerical product of each ZBDD size because
their sub-graphs are shared each other.
After compilation, we evaluated the performance of online inference. In our experiment, we
randomly select a pair of BN nodes with random

values (xi , yj ), then generate a ZBDD as the product of the two ZBDDs (MLF(Xi ) · MLF(Yj )). After that we counted the number of decision nodes“|ZBDD|(product)” and the number of the MLF
terms. We repeated this process for 100 times andshow the average time and space. The inferencetime shown here is the total time of ZBDD multiplication and traversing every decision node oncein the ZBDD for calculating probability. From theexperimental results, we can observe that the sizeof “|ZBDD|(product)” is dramatically smaller than“|ZBDDs|(total).” This indicates that we can avoid
calculating so many redundant terms of MLFs, byusing a product of local MLFs instead of the global
MLF.
In the last two columns, we referred the resultsof CNF-based method[2]. For some of examples,
our results are competitive or better than theirs.
Notice that we cannot directly compare to theirCompiling Bayesian Networks by Symbolic Probability Calculation Using Zero-suppressed BDDs

9

Table 2: Experimental results.
BN nameBN indi- paraoﬄine compile
infer. (ave. for 100 cases) CNF-based(*)
nodes cator meter|ZBDDs| |ZBDD|
time |ZBDD|
MLF
timecomp. inf.
vars. vars.
(total) (a node)(sec) (prod.)
terms
(sec)
time timealarm
37 105
187
34,2991,863
0.2
4,139 3.70 × 108
0.04
0.52 0.01
hailﬁnder
56 223835
294,605
4,427
3.0
9,799 1.00 × 1017
0.19
0.86 0.06
mildew
35 616 6,709 15,310,511 2,684,245 8019.4 593,469 6.60 × 1016 43.43 7,483.80 3.35
pathﬁnder(pf1) 109 448 1,839
16,808
155
20.1
337
667
0.01
20.36 0.07
pathﬁnder(pf23) 135 520 2,304
17,557
135
19.6
188
212
0.01
−
−
pigs
441 1,323 1,474
73,543237
2.9
993 3.27 × 107
0.01
17.84 1.60
water
32 116 3,578
25,629
611
6.1
974
6,295
0.02
4.83 0.21
diabetes
413 4,682 17,622−− (>36k)−−− 2,269.05 16.27
munin1
189 995 4,249−− (>36k)−−− 1,534.97 44.91
munin2
1,003 5,376 22,866 9,936,191
86,267 1,247.8−− (>360)
225.46 6.59
munin3
1,044 5,604 24,116 11,191,778 100,640 777.7−− (>360)
151.72 3.65
munin4
1,041 5,648 24,242 5,724,468
46,989 4,951.1−− (>360)
677.92 7.70(*) [2] uses a PC twice faster than ours.

results because (1) the experimental setting of online inference would be diﬀerent, (2) we may use adiﬀerent variable ordering since it is not shown in[2], and (3) for larger examples, they applied another technique called decomposition tree(dtree)[3],
to reduce the original network of CPTs
Currently, our simple variable ordering strategy
is that a variable appears at earlier stage of calculation will get a lower position (near to the leaf) in
ZBDDs. The ZBDD size is sometimes very sensitive to the variable ordering. For example, we haveobserved that the ZBDDs for “munin2” can easily
be reduced to a half by ad-hoc exchange of variable
ordering. We expect that a good variable ordering
will bring a signiﬁcant improvement to the current
results.
Our method is too time-consuming for larger examples, such as “diabetes” and “munin”s. This
would be because we have not applied the dtreebased CPT network reduction. This technique isindependent of our ZBDD-based data structure, so
we hope it will be eﬀective as well as for the CNFbased method.

6

Conclusion

We have presented a new method of compilingBNs, not using CNF encoding but directly calculate MLFs by using ZBDDs. Our method is
not necessary to generate MLFs for the whole networks, but we can extract MLFs for only selec-

tive BN nodes related to the query, to avoid unnecessary calculation of redundant terms of MLFs.
Our computation algorithm is quite simple and justbased on the mathematical deﬁnition of probability
calculation, and still eﬃciently calculates an exponential size of MLFs in a compact ZBDD representation. Our method will be improved more in
combining with state-of-the-art techniques developed in the history of BN processing.
In this paper, we have shown that the BN compilation process has a similarity to the symbolic
simulation of VLSI logic circuits. There have been
so many heuristic techniques on BDDs in VLSI
logic design area, and some of them would be useful for probabilistic inference on BNs or Markov
Decision Processes.

References[1] R. E. Bryant, “Graph-based algorithms for
Boolean function manipulation,” IEEE Trans.
Comput., C-35, 8 (1986), 677–691.
[2] M. Chavira and A. Darwiche, “Compiling
Bayesian Networks with Local Structure,” In
Proc. 19th International Joint Conference on
Artiﬁcial Intelligence (IJCAI-2005), pp. 1306–
1312, Aug. 2005.
[3] A. Darwiche, “Recursive conditioning,” Artiﬁcial Intelligence, vol. 126, No. 1–2, pp. 5–41,
2001.
[4] A. Darwiche, “A logical approach to factoring
belief networks,” In Proc. KR, pp. 409-420,
2002.

10

Shin-ichi Minato, Ken Satoh, and Taisuke Sato

[5] A. Darwiche, “A diﬀerential approach to inference in Bayesian networks,” JACM, Vol. 50,
No. 3, pp. 280–305, 2003.
[6] A. Darwiche, “New advances in compiling CNF to decomposable negational normal
form,” In Proc. European Conference on Artiﬁcial Intelligence (ECAI-2004), pp. 328–332,
2004.
[7] S. Minato, “Zero-suppressed BDDs for set
manipulation in combinatorial problems,” In
Proc. 30th Design Automation Conf. (DAC93), pp. 272–277, Jun. 1993.
[8] S. Minato, “Zero-Suppressed BDDs and Their
Applications,” International Journal on Software Tools for Technology Transfer, Vol. 3,
No. 2, pp. 156–170, Springer, May 2001.
[9] T. Nielsen, P. Wuillemin, F. Jensen, andU. Kjaerulﬀ, “Using ROBDDs for inferencein Bayesian networks with troubleshooting as
an example,” In Proc. the 16th Conference on
Uncertainty in Artiﬁcial Intelligence (UAI),
pages 426–435, 2000.
[10] S. Sanner and D. McAllester, “Aﬃne Algebraic Decision Diagrams (AADDs) and their
Application to Structured Probabilistic Inference,” In Proc. 19th International Joint
Conference on Artiﬁcial Intelligence (IJCAI2005), Aug. 2005.