Propositionalizing the EM algorithm by BDDs
Masakazu Ishihata1 , Yoshitaka Kameya1 , Taisuke Sato1 , and Shin-ichi Minato2
1

Graduate School of Information Science and Engineering,Tokyo institute of Technology{ishihata,kameya,sato}@mi.cs.titech.ac.jp
2
Graduate School of Information Science and Technology,
Hokkaido University
minato@ist.hokudai.ac.jp

Abstract. We propose an EM algorithm working on binary decision
diagrams (BDDs). It opens a way to applying BDDs to statistical inference in general and machine learning in particular. We also present thecomplexity analysis of noisy-OR models.

1Introduction

Binary decision diagrams (BDDs) have been popular as a basic tool for compactly representing boolean functions [1, 2]. In this paper3 we present yet another application of BDDs. We propose a new EM algorithm that works on
BDDs. Since the EM algorithm is a fundamental parameter learning algorithm
for maximum likelihood estimation in statistics [4], our proposal opens a way
to apply BDDs to statistical learning in general and to machine learning inparticular.

2The EM algorithm

We here describe our unsupervised learning setting and review the expectationmaximization (EM) algorithm [4]. First of all, we assume our problem domain ismodeled with k boolean random variables X1 , X2 , . . . , Xk , each taking 1 (true)and 0 (false) independently of each other. Let F be a boolean function composedof these k variables, and assume only the value of F is observable whereas thoseof the Xi ’s are not. Hereafter, to make notations simple, F is treated as a boolean
random variable as well that takes the value of (the function) F . We then call Fan observable variable, and the Xi ’s basic variables. The EM algorithm proposedin this paper aims to estimate the probabilities of basic variables being true fromthe observed values of F .
Let φ be an assignment of the set of basic variables X = {X1 , X2 , . . . , Xk }.
φ maps each variable X ∈ X to its value x ∈ {0, 1}. We assume X is partitioned
3

This is a shortened version of [3], which deals with zero-suppressed BDDs (ZBDDs)
as well as BDDs.

into S, sets of i.i.d. variables, and each partition s ∈ S has a parameter θs,x ,a common probability of X ∈ s taking x. We use Φ to stand for the set of
all assignments. Since the value F = f ∈ {0, 1} is uniquely determined by φ,F is a function F (φ) = f of assignments. Hence the set of assignments whichmake F = f is written as F −1 (f ) = {φ ∈ Φ | F (φ) = f }. We introduce
σs,x (φ) = |{X ∈ s | φ(X) = x}| to denote the total number of i.i.d. variables inthe partition s that takes a value x by φ. The EM algorithm we develop for thesetting described above consists of two steps, the expectation step (E-step) andthe maximization step (M-step), deﬁned as follows:– E-step: Compute the conditional expectation Eθ [σs,x (·) | F = f ] byηθx [s]/Pθ (F = f ), where:∑∏ ∏ηθx [s] =σs,x (φ)(θs0 ,x0 )σs0 ,x0 (φ)φ∈F −1 (f )Pθ (F = f ) =∑∏(1)

s0 ∈S x0 ∈{1,0}∏(θs,x )σs,x (φ) .

(2)

φ∈F −1 (f ) s∈S x∈{1,0}– M-step: Update θ to θ̂ by θ̂s,x ∝ Eθ [σs,x (·) | F = f ].

3BDDs and the EM algorithm

A BDD is a rooted directed acyclic graph representing a boolean function
as a disjunction of exclusive conjunctions. It has two terminal nodes, 1 (true)and 0 (false). Each nonterminal node n is labeled with a binary random variable denoted by Label (n), and has two outgoing edges called 1-edge and 0-edge,
indicating that Label (n) takes 1 and 0, respectively. Chx (n) stands for a childnode of n, connected by the x-edge (x ∈ {0, 1}).
A reduced ordered BDD (ROBDD) is a BDD which is a unique representationof the target boolean function. Fig. 1 illustrates some diﬀerent representationsof a boolean function F = (A ∨ B) ∧ C̄. Fig. 1 (a) is a truth table, in which arow corresponds to an assignment φ for X = {A, B, C}. One way to obtain theROBDD for F (Fig. 1 (d)) is to consider a binary decision tree (BDT) (b) andapply two reduction rules, the deletion rule and the merging rule, as many times
as possible to reach (d).
Consider a BDT like the one in Fig. 1 (b). In a BDT, there is a unique path
πφ from the root to a terminal for an assignment φ, in which every basic variableappears once as a node label. We rewrite Eq. 1 to Eq. 3 so that ηθx [s] is computed
on a BDD:∑∑∏(θ[Ln ] )φ(Ln ) (θ[Ln ] )1−φ(Ln ) (3)ηθx [s] =1φ(Ln0 )=x
πφ :φ∈F −1 (f ) n0 ∈πφ :Ln0 ∈sn∈πφHere n ∈ πφ says that the node n is on the path πφ . Ln is a shorthand for Label (n)and [Ln ] is the partition to which Ln belongs. 1φ(Ln0 )=x = 1 if φ(Ln0 ) = x istrue, and 0 otherwise.

      

        












Fig. 1. Examples of (a) a truth table, (b) a binary decision tree (BDT), (c) a BDD
which is ordered but is not reduced, (d) the ROBDD, for F = (A ∨ B) ∧ C̄.

4The BDD-EM algorithm

We here present the BDD-EM algorithm which is an EM algorithm working
on BDDs. There are four auxiliary procedures for the procedure BDD-EM(), i.e.
IterateEM(), GetBackward(), GetForward() and GetExpectation().
1: Procedure: BDD-EM()
2:
Initialize all parameters θ;3:repeat4:IterateEM();5:
until the parameters θ converge;
6: end1: Procedure: IterateEM()2:// E-step
3:
GetBackward();4:
GetForward();5:
GetExpectation();6:// M-step
7:
for each s ∈ S do
8:
θs,1 ∝ ηθ1 [s]/Pθf [F ];9:θs,0 ∝ ηθ0 [s]/Pθf [F ];10:end for
11: end

1: Procedure: GetBackward()
2:Bθ1 [ 1 ] = 1, Bθ1 [ 0 ] = 0;3:Bθ0 [ 1 ] = 0, Bθ0 [ 0 ] = 1;

4:
N = Par( 1 ) ∪ Par( 0 );5:// Par(n): the set of parents of n.
6:
while N 6= φ do
7:
n = argmaxn0 ∈N Ord (n0 )8:// Ord (n) is the index of Label (n)9:// in the variable order.
10:
X = Label (n);11:Bθ1 [n] = θ[X] Bθ1 [Ch1 (n)]12:+θ[X̄] Bθ1 [Ch0 (n)];13:Bθ0 [n] = θ[X] Bθ0 [Ch1 (n)]14:+θ[X̄] Bθ0 [Ch0 (n)];15:
N = N \{n} ∪ Par(n);16:
end while
17: endBackward and forward probabilities: We compute backward and forward
probabilities like those in hidden Markov models. The procedure GetBackward() calculates backward probabilities for each node in the BDD representing
F . A backward probability Bθ1 [n] (resp. Bθ0 [n]) is the sum of the probabilitiesof all paths from node n to 1 (resp. 0 ). We set Bθ1 [ 1 ] = 1 and Bθ0 [ 0 ] = 1
respectively. They are calculated from terminals to the root. Contrastingly theprocedure GetForward() calculates forward probabilities for each node fromthe root to terminals. A forward probability Fθ [n] is the sum of the probabilities

1: Procedure: GetForward()
2:InitializeF();
3:Fθ [root] = 1;
4:N = {root};5:
while N 6= φ do
6:n = argminn0 ∈N Ord (n0 );7:
X = Label (n);8:Fθ [Ch1 (n)] += Fθ [n]θ[X] ;9:Fθ [Ch0 (n)] += Fθ [n]θ[X̄] ;10:
N = N \{n} ∪ {Ch1 (n), Ch0 (n)};11:end while
12: end
1: Procedure: GetExpectation()
2:
InitializeEta();3:
for each n ∈ N do
4:
X = Label (n);5:e1n = Fθ [n]Bθf [Ch1 (n)]θ[X] ;6:e0n = Fθ [n]Bθf [Ch0 (n)]θ[X̄] ;
ˆ ˜
ˆ ˜
7:
ηθ1 [X] += e1n , kηθ0 [X] += e0n ;18:
for each
Y (n) doˆ ˜ Z ∈ Del119:ηθ ˆ[Z] ˜ += en θ[Z] ;10:ηθ0 [Z] += e1n θ[Z̄] ;11:
end for012:
for eachˆ ˜ Z ∈ Del Y (n) do
13:ηθ1 ˆ[Z]˜ += e0n θ[Z] ;14:
ηθ0 [Z] += e0n θ[Z̄] ;15:
end for16:
end for17: end

1: Procedure: GetExpectation*()2:
InitializeEta();3:
for each n ∈ N do
4:
X = Label (n);5:e1n = Fθ [n]Bθf [Ch1 (n)]θ[X]6:e0n = Fθ [n]Bθf [Ch0 (n)]θ[X̄]ˆ ˜7:ηθ1 ˆ[X]˜ += e1n ;08:ηθ [X] += e0n ;9:
X 0 : Ord (X 0 ) = Ord (X) + 1;
10:
ζ[X 0 ] += e1n + e0n ;11:
ζ[Label (Ch1 (n))] −= e1n ;12:ζ[Label (Ch0 (n))] −= e0n ;13:
end for
14:
X = X;
15:
X = argminX 0 ∈X Ord (X 0 );16:
z = ζ[X];17:
X = X \{X};18:while X 6= φ do
019:
X ˆ= argmin
X 0 ∈X Ord (X );˜120:ηθ ˆ[X]˜ += zθ[X] ;21:
ηθ0 [X] += zθ[X̄] ;22:z += ζ[X];23:
X = X \{X};24:
end while25: end
Fig. 2. Improved GetExpectation()of all paths from the root to node n. The procedure InitializeF() initializesFθ [n] = 0 for all n.
[ ]Conditional expectations: The procedure GetExpectation() updates ηθx [X]
which is deﬁned[ ]in Section 2 for each X ∈ X. The procedure InitializeEta()
sets each ηθx [X] = 0. In GetExpectation(), f ∈ {1, 0} is the observed valueof F , and N is the set of all nodes in the BDD.
Note that in order to compute probabilities properly, we need to recoverdeleted nodes. So, to denote the nodes deleted by the deletion rule, Del 1Y (n) and
Del 0Y (n) are introduced in GetExpectation(). Del xY (n) (x ∈ {1, 0}) stands
for the set of labels (i.e. variables) of deleted nodes between n and Chx (n). So
we have Del xY (n) = {X ∈ V(δY ) | Label (n) ≺ X ≺ Label (Chx (n))}. What
we actually use for the computation of conditional expectations is not GetExpectation() however, as it incurs some ineﬃciency, but GetExpectation*()shown in Fig. 2 which processes computation of the deleted nodes much more
eﬃciently (details omitted).

5Time complexities for noisy-OR models

The time complexity of building BDDs is NP-hard in general [5]. However,there are eﬃcient techniques to build BDDs using the Apply operation [2] andthose to ﬁnd good variable orderings, be they dynamic or static [5, 6]. So building
BDDs can be done eﬃciently in practice. In this section, we evaluate the timecomplexity of both building BDDs and running the BDD-EM algorithm fornoisy-OR models.4
A noisy-OR model represents a relation between multiple causes and aneﬀect. Let F be an observable variable representing an eﬀect, and C1 , C2 and C3
basic variables representing possible causes which make F true. While the logicalOR relation is represented as F ⇔ C1 ∨ C2 ∨ C3 , the noisy-OR relation allows fora situation where C1 is true but F is false. For this noisy-OR model, we introduce
inhibition variables, I1 ,I2 and I3 , which inhibit F to be true with probabilities
θ[I1 ] = P (F = 0 | C1 = 1, C2 = 0, C3 = 0), θ[I2 ] = P (F = 0 | C1 = 0, C2 = 1, C3 = 0)and θ[I3 ] = P (F = 0 | C1 = 0, C2 = 0, C3 = 1), respectively. An N -input noisy-OR
model between F and C1 , C2 , . . . , CN is described by:
F = (C1 ∧ I¯1 ) ∨ (C2 ∧ I¯2 ) ∨ · · · ∨ (CN ∧ I¯N ).
Fig. 3 shows a BDD representing F under the variable ordering Ord such thatCi ≺ Cj , Ii ≺ Ij (i < j) and Ci ≺ Ik (i ≤ k). We construct a BDD fromF using the Apply operation, denoted by Apply(δX , δY , hopi), that builds aBDD representing XhopiY where δX and δY represent the boolean functions
X and Y , respectively. Although the time complexity of Apply(δX , δY , hopi) isO(NX NY ) in general, where NX (resp. NY ) is the number of nodes in the BDD
representing X (resp. Y ), we can see an application of Apply(·) for an N -input
noisy-OR model takes just O(1). So the BDD is obtained by applying the Apply
operation N times, and the time complexity becomes O(N ) under Ord . Also thetime complexity of the E-step is O(N ) because |N| = 2N and |X| = 2N .





Fig. 3. A BDD representing the noisy-OR model.

4

We conﬁrmed the BDD-EM algorithm properly converges by numerical experiments.

6

Related work and concluding remarks

We have presented an EM algorithm that works on BDDs. Our work is considered as a succession to the previous work done by Minato et al. [7]. It shows
how to compile BNs into ZBDDs to compute probabilities but probability learning is left untouched. In [3], we supplemented a necessary algorithm to apply
ZBDDs to EM learning.
The introduction of BDDs solves a long-standing problem of PRISM [8],a logic-based language for generative modeling. It employs a propositionalized
data structure called explanation graphs similar to decomposed BDDs to represent boolean formulas in disjunctive normal form. The current PRISM howeverassumes the exclusiveness condition that the disjuncts are exclusive to makesum-product probability computation possible. Since the proposed algorithms
are applicable to explanation graphs as well, it allows PRISM to abolish theexclusiveness condition.
ProbLog is a recent logic-based formalism that computes probabilities viaBDDs [9]. A ProbLog program computes the probability of a query atom from adisjunction of conjunctions made up of independent probabilistic atoms by converting the disjunction to a BDD and applying the sum-product computation toit. 5 Since our BDD-EM algorithm works on BDDs, integrating it with ProbLogfor probability learning seems an interesting future research topic.

References1. Akers, S.B.: Binary decision diagrams. IEEE Trans. Computers 27(6) (1978) 509–516
2. Bryant, R.: Graph-based algorithms for boolean function manipulation. IEEE
Trans. Computers 35(8) (1986) 677–691
3. Ishihata, M., Kameya, Y., Sato, T., Minato, S.: Propositionalizing the EM algorithm
by BDDs. Technical Report TR08-0004, Dept. of Computer Science, Tokyo Instituteof Technology (2008)
4. Dempster, A., Laird, N., Rubin, D.: Maximum likelihood from incomplete data via
the EM algorithm. J. of the Royal Statistical Society B 39 (1977) 1–38
5. Drechsler, R., Sieling, D.: Binary decision diagrams in theory and practice. Int’l J.
on Software Tools for Technology Transfer 3 (2001) 112–136
6. Minato, S., Ishiura, N., Yajima, S.: Shared binary decision diagram with attributededges. Proc. ACM/IEEE Design Automation Conf. (1990) 52–57
7. Minato, S., Satoh, K., Sato, T.: Compiling Bayesian networks by symbolic probability calculation based on Zero-suppressed BDDs. In: Proc. of IJCAI’07. (2007)
2550–2555
8. Sato, T., Kameya, Y.: Parameter learning of logic programs for symbolic-statisticalmodeling. J. of Artiﬁcial Intelligence Research 15 (2001) 391–454
9. De Raedt, L., Angelika, K., Toivonen, H.: ProbLog: A probabilistic Prolog and its
application in link discoverry. In: Proc. of IJCAI’07. (2007) 2468–2473
5It should be noted that a special treatment is required for the computation of conditional expectations (see [3] for details).