Online and Distributed Bayesian Moment Matching for Parameter
Learning in Sum-Product Networks

Abdullah Rashwan
Computer Science
University of Waterloo
arashwan@uwaterloo.ca

Han Zhao
Machine Learning
Carnegie Mellon University
han.zhao@cs.cmu.edu

Abstract
Probabilistic graphical models provide a general and flexible framework for reasoning
about complex dependencies in noisy domains with many variables. Among the various types of probabilistic graphical models, sum-product networks (SPNs) have recently generated some interest because exact inference can always be done in linear
time with respect to the size of the network.
This is particularly attractive since it meansthat learning an SPN from data always yields
a tractable model for inference. However,existing parameter learning algorithms for
SPNs operate in batch mode and do not scale
easily to large datasets. In this work, we
explore online algorithms to ensure that parameter learning can also be done tractably
with respect to the amount of data. Morespecifically, we propose a new Bayesian moment matching (BMM) algorithm that operates naturally in an online fashion and thatcan be easily distributed. We demonstrate
the effectiveness and scalability of BMM incomparison to online extensions of gradientdescent, exponentiated gradient and expectation maximization on 20 classic benchmarks
and 4 large scale datasets.

1

Introduction

Sum-Product networks (SPNs) were first proposedby [Poon and Domingos, 2011] as a new type of
probabilistic graphical models. An SPN consists of an
Appearing in Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (AISTATS)
2016, Cadiz, Spain. JMLR: W&CP volume 51. Copyright2016 by the authors.

Pascal Poupart
Computer Science
University of Waterloo
ppoupart@uwaterloo.ca

acyclic directed graph of sums and products that computes a non-linear function of its inputs. SPNs can beviewed as deep neural networks where non-linearity
is achieved by products instead of sigmoid, softmax,
hyperbolic tangent or rectified linear operations. They
also have clear semantics in the sense that they encodea joint distribution over a set of leaf random variablesin the form of a hierarchical mixture model. To better
understand this distribution, SPNs can be converted
into equivalent traditional probabilistic graphicalmodels such as Bayesian networks (BNs) and Markov
networks (MNs) by treating sum nodes as hidden
variables [Zhao et al., 2015]. An important advantage
of SPNs over BNs and MNs is that inference can bedone without any approximation in linear time withrespect to the size of the network. Hence, SPNs are
gaining in popularity as a tractable class of probabilistic graphical models. SPNs have been used inimage completion tasks [Poon and Domingos, 2011],
activityrecognition[Amer and Todorovic, 2012,
Amer and Todorovic, 2015],
speechmodeling [Peharz et al., 2014b] and language modeling [Cheng et al., 2014].
A variety of algorithms have been proposed tolearn the structure [Rooshenas and Lowd, 2014,
Gens and Domingos, 2013]
andtheparameters [Poon and Domingos, 2011] of SPNs from
data. Since existing algorithms operate in a batchway, they do not scale to large datasets. In thiswork, we explore online algorithms that can process
a dataset in one sweep and can continuously refine
the parameters of an SPN with a fixed structure
based on streaming data. It is relatively easy toextend gradient descent (GD), exponentiated gradient and expectation maximization (EM) to theonline setting by restricting the algorithms to asingle iteration (i.e., single pass through the data)in which incremental updates to the parameters are
performed after processing each data point. Since
those algorithms maximize the likelihood of the data,
they are subject to overfitting and local optima (the1469Online and Distributed Bayesian Moment Matching for SPNs

optimization problem is non-convex). Furthermore,
restricting the algorithms to a single iteration meansthat some information is lost. We propose a new
Bayesian learning algorithm that does not frame theproblem as optimization and therefore does not sufferfrom local optima. Furthermore, Bayesian learning
is robust to overfitting and naturally operates in an
online, asynchronous and distributed fashion since
Bayes theorem allows us to incrementally update
the posterior after each data point and the updates
can be computed in any order and distributed on
different machines. The main issue with Bayesianlearning is that the posterior is often intractable,
which is the case for parameter learning in SPNs. To
that effect, we propose to approximate the posterior
after each update with a tractable distribution thatmatches some moments of the exact, but intractable
posterior. We call this algorithm online Bayesian
Moment Matching (oBMM). The approximation
introduced by moment matching yields a loss of
information, however we show that oBMM performs
better than online expectation maximization (oEM),
online Exponentiated Gradient (oEG), and Stochastic
gradient descent (SGD) on a suite of benchmarks
and some large language modeling problems. We also
demonstrate the scalability of oBMM by distributing
the computation on many machines.
The paper is structured as follows. Section 2 reviews
SPNs as well as parameter learning algorithms including gradient descent, exponentiated gradient and EM.
It also explains how to apply online versions of GD
and EM to parameter learning in SPNs. Section 3 describes oBMM to approximate Bayesian learning by
moment matching. Section 4 demonstrates the effectiveness and scalability of oBMM in comparison tooEG, oEM, and SGD on a set of benchmarks and fourlarge language modeling problems. Finally, Section 5
concludes and discusses future work.

2

Background

2.1

Sum-Product Networks (SPNs)

Consider a set of random variables X={X1 , X2 , ..., Xn }.
A sum-product network(SPN) [Poon and Domingos, 2011] is a probabilistic
graphical model that can be used to express a joint
distribution over those random variables. An SPN
consists of a rooted acyclic directed graph where theinterior nodes are sums or products and the leaves areindicator variables (e.g., IX=x ). There is one indicatorvariable per variable assignment that returns 1 when
the assignment is true and 0 otherwise. The edges
emanating from sum nodes are labeled with weights
wnm (where n is the source node, m is the destinationnode, and wnm > 0). An SPN can be viewed asa function of the indicator variables that can beevaluated in a bottom up pass. For a joint assignmente of the indicator variables, the value Vn (e) of a noden is computed recursively as follows:1
n is an indicator set to 1 in e
 0n is an indicator set to 0 in eQ
Vn (e) =Vm (e)
n is a product Pm∈children(n)wV(e)
n is a summ∈children(n) nm m
(1)

An SPN can be used to encode a joint distribution over
X, which is defined by the graphical structure and theweights. The probability of a joint assignment X = x
is proportional to the value at the root of the SPN
induced by setting the indicators according to the joint
assignment.
Pr(X = x) =Vroot (e(x))
Vroot (1)(2)

Here e(x) indicates that IXi =xi = 1 when xi ∈ x and0 otherwise. The normalization constant needed toobtain a probability is Vroot (1) where 1 is a vector of
all 1’s indicating that all the indicator variables are set
to 1. Intuitively, by setting all the indicator variables
to 1, the SPN will sum up the contributions of all the
joint assignments. Eq. 2 can also be used to computethe marginal probability of a partial assignment Y = y
as long as we define the indicator assignment e(y) insuch a way that IXi =xi = 1 when xi ∈ y or Xi 6∈ Y,
and 0 otherwise. This means that the indicators for thevariables outside of the partial assignment are all set to
1 since we need to sum out the variables outside of thepartial assignment. Conditional probabilities can also
be computed by evaluating two partial assignments:
Pr(Y = y, Z = z)
Pr(Z = z)
Vroot (e(y, z))=
Vroot (e(z))

Pr(Y = y|Z = z) =

(3)
(4)

Since joint, marginal and conditional queries can all beanswered by two network evaluations, exact inference
takes linear time with respect to the size of the network. This is a remarkable property since inference inBayesian and Markov networks may take exponential
time in the size of the network.
An SPN is said to be valid when it represents a distribution and Eq. 2 and 4 can be used to answer inference queries correctly [Poon and Domingos, 2011].
Decomposability and completeness are sufficient conditions that ensure validity. Below we define decomposability and completeness in terms of the scope of a
node.
1470

Abdullah Rashwan, Han Zhao, Pascal Poupart

Definition 1 (Scope) The scope of a node n is theset of all variables that appear in the leaf indicators of
the sub-SPN rooted at n.
We can compute the scope of each node in a bottom up pass as follows. If n is a leaf indicator
IXi =xi , then scope(n) = {Xi }, otherwise scope(n) =∪m∈children(n) scope(m).
Definition 2 (Decomposability) An SPN is decomposable when each product node has children withdisjoint scopes.
Definition 3 (Completeness) An SPN is complete
when each sum node has children with identical scope.
2.2

Learning SPNs

Severalalgorithms
have
been
proposed
to learn the parameters and the structure of an SPN [Dennis and Ventura, 2012,
Gens and Domingos, 2013,
Peharz et al., 2013,
Lee et al., 2013,
Rooshenas and Lowd, 2014,
Adel et al., 2015].
Parameter learning algorithms
estimate the weights of an SPN for a fixed structure.
Below, we review gradient descent (GD), and expectation maximization (EM) since they are the twomost popular parameter learning algorithms for SPNs
and they can be adapted easily to online learning.
We also briefly introduce exponentiated gradient(EG) [Kivinen and Warmuth, 1997], which has beenfrequently used in machine learning to train convex
models in the online setting.
2.2.1

Stochastic Gradient Descent (SGD)

Gradient
descent
has
been
proposedby [Poon and Domingos, 2011] to train SPNs inbatch mode. The basic idea is to treat an SPN as a
deep computational graph with probabilistic output,
so that gradient descent can be applied to maximize
the log-likelihood of the training data. Just as inother deep models, the gradient vector of model
parameters in SPNs can be computed using the chain
rule in a top-down fashion. Hence the computational
complexity of GD for each instance scales linearlyin the size of the network. Besides its conceptual
simplicity, another advantage of GD is that it canbe easily adapted to online learning by making
updates after each observation, which is known as thestochastic gradient descent (SGD) algorithm. SGD
is an off-the-shelf learning algorithm for many deepmodels. However, the model parameters need to be
projected back into the feasible region after each
iteration of SGD. Given a data instance x, the update

formula of SGD in SPNs can be expressed as follows
wk+1 ← wk − tk (∇w Vroot (e(x)) − ∇w Vroot (1)) (5)where tk is the step size in the kth iteration, [w] =max{, w} is the projection operator to −positive region (w ≥  > 0).
2.2.2

Exponentiated Gradient (oEG)

Explicit projection is required in SGD in order to keep
all the intermediate solutions in the feasible region. As
an alternative, exponentiated gradient (EG) was proposed by [Kivinen and Warmuth, 1997] to train linear separators in the online setting. After that, EG
has been widely applied in both online and batch
settings to train convex models, including log-linear
structured predictors [Globerson et al., 2007], conditional random fields and max-margin Markov networks [Collins et al., 2008], etc. EG has not been applied in training SPNs or other related nonconvex deeparchitectures. However, EG yields a natural training
paradigm that admits a multiplicative update in each
iteration so that there is no need to project intermediate gradients back to the feasible region. For thisreason, we also treat EG as a candidate online learning algorithm for SPNs.

2.2.3

Expectation Maximization (oEM)

SGD is widely applicable to any deep models with differentiable objective functions. However, it fails to
exploit the structure that the Vroot (e(x)) can be normalized to obtain a joint probability in SPNs. To utilize the generative nature of SPNs, EM has been proposed [Peharz, 2015] as another approach to learn theparameters of SPNs. The key observation here is that
we can treat sum nodes in SPNs as hidden variables
in a mixture model. More specifically, for each sum
node n in a SPN, n can be viewed as a multinomial
random variable, where the number of values taken byn corresponds to the number of edges emanating fromn. Such intuitive explanation will not affect the inference procedure for the observable variables in SPNs
because all the sum nodes are summed out in the inference phase. This perspective leads to the possibility of applying the EM algorithm to learn the model
parameters of SPNs. Again, EM can be extended toonline computation by making an incremental updateafter each observation [Liang and Klein, 2009]. We refer interested readers to [Peharz, 2015] for more details
about the EM algorithm in SPNs.
1471

Online and Distributed Bayesian Moment Matching for SPNs

3

Online Bayesian Moment Matching

We propose to use Bayesian learning to obtain a new online algorithm.
As pointed out
by [Broderick et al., 2013] Bayesian learning naturally
lends itself to online learning and distributed computation. In the case of an SPN, the weights are theparameters to be learned. Bayesian learning starts byexpressing a prior Pr(w) over the weights. Learning
corresponds to computing the posterior distribution
Pr(w|data) based on the data observed according toBayes’ theorem:
Pr(w|data) ∝ Pr(w) Pr(data|w)(6)

Since the data consists of a set of instances x1:N ={x1 , ..., xN } that is assumed to be sampled identicallyand independently from some underlying distribution,
we can rewrite Bayes’ theorem in a recursive way thatfacilitates incremental online learning:Pr(w|x1:n+1 ) ∝ Pr(w|x1:n ) Pr(xn+1 |w)(7)

The computation of the posterior in Bayes’ theorem
can also be distributed over several machines that eachprocess a subset of the data. For example, supposethat we have K machines and a dataset of KN instances, then each machine (indexed by k) can compute a posterior Pr(w|x(k−1)N +1:kN ) over N instances.
Those posteriors can be combined to obtain the posterior of the entire dataset as follows:
Pr(w|x1:KN ) = Pr(w)K
Y
Pr(w|x(k−1)N +1:kN )

k=1

Pr(w)

(8)

Hence, exact Bayesian learning can be performed naturally in an online and distributed fashion. Unfortunately, the computation of the posterior is often intractable. This is the case for parameter learning in
SPNs. Thus, we propose to approximate the posterior
obtained after each data instance with a tractable distribution by matching a set of moments. We first describe how to estimate the parameters of an SPN witha fixed structure by exact Bayesian learning. Then we
discuss the exponential complexity of this approachand how to circumvent this intractability by Bayesian
moment matching.
3.1

Exact Bayesian Learning

The parameters of an SPN consist of the weights associated with the edges emanating from each sum node.
The first step is to define a prior over the weights.
While the weights can be any non-negative number,any SPN can be transformed into an equivalent normal SPN with normalized weights (i.e., wij ≥ 0 andPj wij = 1 ∀i ∈ sumNodes) that correspond to local

distributions [Peharz et al., 2015, Zhao et al., 2015].
Without loss of generality, we will restrict ourselves
to normal SPNs since the likelihood of a data instance Pr(x) is obtained by a single network evaluation
Vroot (e(x)) (i.e., the normalization constant Vroot (1) isalways 1 in Eq. 2) and this allows us to use a Dirichlet for the prior over each local distribution associatedwith the weights of each sum node. We start with aprior that consists of a product of Dirichlets with respect to the weights wi· = {wij |j ∈ children(i)} ofeach sum node i:Y
Pr(w) =
Dir(wi· |αi· )(9)i∈sumNodes
The posterior is obtained by multiplying the prior by
the likelihood Vroot (x) of each data instance:
Pr(w|x1:n+1 ) ∝ Pr(w|x1:n )Vroot (xn+1 )(10)

Since a network evaluation consists of an alternationof sums and products, we can rewrite Vroot (x) as apolynomial with respect to the weights. Furthermore,this polynomial can always be re-written as a sum ofmonomials that each consists of a product of weights:
X
X
Y
Vroot (x) =monomialcx (w) =
wij
c

c

ij∈monomialcx(11)
Intuitively, if we distribute the sums over the products in the network evaluation, we obtain a large sumof small products of weights where each product ofweights is a monomial. The number of monomials is
exponential in the number of sum nodes. Note that
products of Dirichlets are conjugate priors with respect to monomial likelihood functions. This meansthat multiplying a monomial by a product of Dirichlets gives a distribution that is again a product ofDirichlets. However, since our likelihood function isa polynomial that consists of a sum of monomials, theposterior becomes a mixture of products of Dirichlets:
Pr(w|x)(12)
Y
X=
Dir(wi· |αi· )monomialcx (w) (13)ci∈sumNodes
XY=kc
Dir(wi· |αi· + δi·x,c )(14)
ci∈sumNodes
1 ij ∈ monomialcx
x,c(15)
where δij =0 ij 6∈ monomialcx
The nice thing about the above derivation is that theposterior has a closed form (mixture of products of
Dirichlets), however it is computationally intractable.
The number of mixture components is exponential in
the number of sum nodes after the first data instance(in the worst case). If we repeatedly update the posterior after each data instance according to Eq. 7, the1472Abdullah Rashwan, Han Zhao, Pascal Poupart

number of mixture components will grow exponentially with the amount of data and doubly exponentially with the number of sum nodes.
3.2

Moment Matching

Moment matching is a popular frequentist techniqueto estimate the parameters of a distribution basedon the empirical moments of a dataset. For instance, it has been used to estimate the parameters of mixture models, latent Dirichlet allocationand hidden Markov models while ensuring consistency [Anandkumar et al., 2012]. Moment matching
can also be used in a Bayesian setting to approximate an intractable posterior distribution. More precisely, by computing a subset of the moments of an
intractable distribution, another distribution from a
tractable family that matches those moments can beselected as a good approximation. Expectation propagation [Minka and Lafferty, 2002] is a good example
of such an approach. We describe how to use Bayesian
Moment Matching to approximate mixtures of products of Dirichlets obtained after processing each data
instance by a single product of Dirichlets.
Q
A Dirichlet Dir(wi· |αi· ) ∝ j (wij )αij −1 is defined byits hyper-parameters α. However it could also be defined by a set of moments. Consider the following firstand second order moments which are expectations of2
wij and wij:
1. MDir (wij ) =2
2. MDir (wij
)=

R

wij

R

wij

wij Dir(wi· |αi· )dwij
2
wij
Dir(wi· |αi· )dwij

We can express the hyperparameters αij in terms of
the above moments as follows:2
MDir (wij ) − MDir (wij)∀ij
2MDir (wij ) − (MDir (wij ))2(16)
When approximating a distribution P by a Dirichlet,
2
we can compute the moments MP (wij ) and MP (wij)
of P and then use Eq. 16 to set the hyperparameters of the Dirichlet so that it has the same first andsecond order moments. More generally, since we areinterested in approximating a joint distribution P (w)by a product of Dirichlets, we can compute the mo2
ments MP (wi· ) (wij ) and MP (wi· ) (wij
) of each marginal
P (wi· ) in order to set the hyperparameters αi· of each
Dirichlet in the product of Dirichlets. Hence, insteadof explicitly computing the intractable posterior after
each data instance, we compute the first and second order moments of the posterior which are sufficient to approximate the posterior by Bayesian moment matchingwith a product of Dirichlets. It turns out that we can

exploit the structure of SPNs to compute efficiently
the first and second order moments of the posterior.
Algorithm 1 describes how to compute a moment of
the posterior in one bottom-up pass. Since the number of moments is linear in the size of the network andcomputing each moment is also linear, the overall time
to approximate the posterior by a product of Dirichlets
is quadratic in the size of the network.
k(k
Algorithm 1 Compute marginal moment for wij
is an exponent indicating the order of the moment) in
the posterior obtained after observing x
1: if isLeaf (node) then2:
return Vnode (e(x))
3: else if isP
Qroduct(node) then4:
return child computeM oment(child)
5: else if isSum(node)and node == i thenPk6:
return child MDir (wijwi,child )×
7:
computeM oment(child)
8: elseP
9:
return child wnode,child computeM oment(child)
10: end if

In practice, many structure learning algorithms
produce SPNs that are trees (i.e., each node
has a single parent) [Dennis and Ventura, 2012,
Gens and Domingos, 2013,
Peharz et al., 2013,
Rooshenas and Lowd, 2014,
Peharz et al., 2014a,
Adel et al., 2015]. When an SPN is a tree, it ispossible to compute all the moments simultaneously
in time that is linear in the size of the network. The
key is to compute two coefficients coefi0 , coefi1 at eachnode i in a top-down pass of the network. Algorithm 2shows how those coefficients are computed. Once wehave the coefficients, we can compute each moment
as follows:

αij = MDir (wij )kMposterior (wij
)=

Z

wi·

k
wij
Dir(wi· |αi· )(coefi0+ coefi1X

wij 0 Vj 0 (e(x)))dwi·

(17)

j0

Here, coefi0 and coefi1 are additive and multiplicative
coefficients respectively that capture quantities in the
SPN above node i. We compute those coefficients in0
a top down fashion. At the root, coefroot
is initialized to 0 since there is nothing above the root to be1
added. Similarly, coefroot
is initialized to 1 since there
is nothing above the root to be multiplied. Then, as
we go down the SPN, the coefficients of the parent andnetwork values of the siblings of node i are combined
into coefi0 and coefi1 .
1473

Online and Distributed Bayesian Moment Matching for SPNs

Algorithm
Q 2 computeCoefficients(node) based on x
and prior i Dir(wi· |αi· )1: if isRoot(node) then02:
coefnode←01
3:
coefnode←1
4: else if isP roduct(parent(node)) then
005:
coefnode← coefparent
Q11
6:
coefnode ← coefparent
sibling Vsibling (e(x))
7: else if isSum(parent(node)) then
00
coefnode←P
coefparent
αparent,sibling8:+ sibling P
αparent,j Vsibling (e(x))
j

α

1
1
Pparent,nodecoefnode← coefparent
j αparent,j
10: end if
11: if isN otLeaf (node) then12:
computeCoefficients(child) ∀child
13: end if

9:4

Experiments

We evaluated oBMM on 2 sets of datasets; 20
small datasets and 4 large datasets.
The 20
datasets span diverse sets of domains, and thenumber of variables range from 16 to 1556 binary variables.
These datasets were used before for comparisons in [Gens and Domingos, 2013,
Rooshenas and Lowd, 2014]. The 4 large datasets arebag of words datasets and they are publicly available
online from the UCI machine learning repository. Eachdataset contains a collection of documents and thecorresponding word counts. The number of variables(dictionary size) ranges from 6906 to 102660 variables.
The variables are binarized by ignoring the word countand only used 0 or 1 for the absence or presence of aword in a document.
In order to evaluate the performance of oBMM, weevaluated it and compared it to three online algorithms: stochastic gradient descent (SGD), online exponentiated gradient (oEG) and online expectation
maximization (oEM). We measure both the quality of the three algorithms in terms of average loglikelihood scores on the held-out test data sets andtheir scalability in terms of running time. To test
the statistical significance of the results, we apply the
Wilcoxon signed rank test [Wilcoxon, 1950] to compute the p-value and report statistical significancewith p-value less than 0.05. The log-likelihood scoresfor the structural learning algorithm from LearnSPN[Gens and Domingos, 2013] are reported as a reference
for the comparison of the three online parameter learning algorithms. The online algorithms are not expected to beat a structural learning algorithm, but
we will show that online algorithms can outperform
LearnSPN for the large datasets in terms of running

time and accuracy.
Since we don’t do structural learning, a fixed structureis used to perform the experiments. We used a simple
structure generator which can take 2 hyperparameters(number of variables, and the depth of the SPN) andgenerate the SPN accordingly. The generator keeps
track of the scope at each node and it starts from asum node as the root node that has all variables inthe scope. Recursively, for each sum node, a numberof children product nodes are generated with the same
scope as the sum node, and for each product node, anumber of children sum nodes are generated while randomly factoring the scope among the children. Whenthe level at a product node is 2 or less, a number ofchildren sum nodes are generated such that each childhas only a single variable in its scope. Finally, a sum
node that contains a single variable in its scope, twoleaf nodes are generated corresponding to the indicators of the variables. For the small datasets, SPNs ofdepth 6 are used, while for the large datasets SPNs ofdepth 4 are used.
Online Bayesian Moment matching (oBMM) doesn’t
have any hyper-parameters to tune, except for theprior which we set randomly by selecting hyperparameters αij uniformly at random in [0, 1]. For the online
Distributed Bayesian Moment Matching (oDMM), thetraining set is partitioned into 10 smaller sets, and each
set is sent to a different machine to be processed. Oncethe machines finish, the output sum-product networks
are collected and combined into a single sum-productnetwork. For SGD and oEG, we use backtracking line
search to shrink the step size if the log-likelihood scoreson the training set decreases. The initial step size is
set to 1.0 for all data sets. oEM does not require alearning rate nor weight shrinking. To avoid possible
numeric underflow we use a smoothing constant equal
to 0.01 in all the experiments.
Table 1 shows the average log-likelihoods on thetest sets for various algorithms. oBMM outperforms the rest of the online algorithms in 19 outof the 20 datasets. The results show that oBMM
has significantly better log-likelihood on most of thedatasets. Surprisingly, oBMM matches the performance of LearnSPN in 11 datasets despite the fact thatthe structure used for oBMM is generated randomly.
The advantage of online algorithms over batch algorithms including LearnSPN appears when the dataset
size increases to the limit since it becomes hard to
fit it in memory. Tables 2 and 3 show the likelihoodscores and the running times of different methods onlarge datasets. Dashes are used to indicate that thealgorithm didn’t finish in a week or the training data
could not fit in memory. We were able to run LearnSPN only on the KOS dataset since the rest of the1474

Abdullah Rashwan, Han Zhao, Pascal Poupart

Table 1: Log-likelihood scores on 20 data sets. The best results among oBMM, SGD, oEM, and oEM arehighlighted in bold font. ↑ (↓) indicates that the method has significantly better (worse) log-likelihoods thanoBMM under Wilcoxon signed rank test with p value < 0.05.
DatasetVar# LearnSPN oBMM
SGD
oEM
oEG
NLTCS
16
-6.11
-6.07
↓-8.76↓-6.31↓-6.85
MSNBC
17
-6.11
-6.03
↓-6.81↓-6.64↓-6.74
KDD
64
-2.18
-2.14
↓-44.53↓-2.20↓-2.34
PLANTS69-12.98-15.14↓-21.50↓-17.68↓-33.47
AUDIO
100-40.50-40.7↓-49.35↓-42.55↓-46.31
JESTER100-53.48-53.86↓-63.89↓-54.26↓-59.48
NETFLIX
100-57.33-57.99↓-64.27↓-59.35↓-64.48
ACCIDENTS
111-30.04-42.66↓-53.69-43.54↓-45.59
RETAIL135-11.04-11.42↓-97.11↓-11.42↓-14.94
PUMSB-STAR 163-24.78-45.27↓-128.48 ↓-46.54↓-51.84DNA
180-82.52-99.61↓-100.70 ↓-100.10 ↓-105.25
KOSAREK
190-10.99-11.22↓-34.64↓-11.87↓-17.71MSWEB
294-10.25-11.33↓-59.63↓-11.36↓-20.69
BOOK
500-35.89-35.55↓-249.28 ↓-36.13↓-42.95
MOVIE
500-52.49-59.50↓-227.05 ↓-64.76↓-84.82
WEBKB
839-158.20-165.57 ↓-338.01 ↓-169.64 ↓-179.34
REUTERS889-85.07-108.01 ↓-407.96 -108.10↓-108.42
NEWSGROUP 910-155.93-158.01 ↓-312.12 ↓-160.41 ↓-167.89
BBC
1058-250.69-275.43↓-462.96 -274.82 ↓-276.97
AD
1556-19.73-63.81↓-638.43 ↓-63.83↓-64.11

Table 2: Log-lielihood scores on 4 large datasets. The best results are highlighted in bold font, and dashes ”-”
are used to indicate that an algorithm didn’t finish or couldn’t load the dataset into memory.
DatasetVar#
LearnSPN oBMM
oDMM
SGD
oEM
oEG
KOS
6906
-444.55-422.19-437.30-3492.9-538.21-657.13
NIPS
12419-1691.87 -1709.04 -7411.20-1756.06-3134.59
ENRON
28102
-518.842 -522.45-13961.40 -554.97-14193.90
NYTIMES 102660 -1503.65-1559.39 -43153.60 -1189.39 -6318.71

Table 3: Running time in minutes on 4 large datasets. The best running time is highlighted in bold font, anddashes ”-” are used to indicate that an algorithm didn’t finish or couldn’t load the dataset into memory.
DatasetVar#
LearnSPN oBMM oDMM
SGD
oEM
oEG
KOS
6906
1439.1189.40
8.66
162.9859.49
155.34NIPS
12419
139.509.43
180.2564.62
178.35
ENRON
28102
2018.05 580.63
876.18694.17883.12
NYTIMES 102660 12091.7 1643.60 5626.33 5540.40 6895.00

1475

Online and Distributed Bayesian Moment Matching for SPNs

datasets didn’t finish in a week or they were too big to
fit in memory. Both oBMM and oDMM outperform
LearnSPN, which runs 16 times slower than oBMM
and 166 times slower than oDMM. oBMM and oDMM
also outperform SGD by a large margin on the large
data sets. In terms of the running time, oDMM is significantly faster than the rest of the algorithms since
we are distributing the training data over multiple machines.

5

Conclusion

SPNs gained popularity for being able to provide exact
inference in linear time, however learning the parameters in a tractable way is still challenging. In this paper, we explored online algorithms for learning the parameters of an SPN tractably. We also proposed online
Bayesian Moment Matching as an online framework forparameters learning, and we showed how to distributethe algorithm over many machines. We showed howoBMM outperforms the rest of the algorithms, we also
showed that distributing the algorithm over multiple
machines is very effective when running time is thebottleneck.

References[Adel et al., 2015] Adel, T., Balduzzi, D., and Ghodsi,
A. (2015). Learning the structure of sum-productnetworks via an svd-based algorithm.
[Amer and Todorovic, 2015] Amer, M. and Todorovic, S. (2015). Sum product networks for activity
recognition.
[Amer and Todorovic, 2012] Amer, M. R. and Todorovic, S. (2012). Sum-product networks for modelingactivities with stochastic structure. In Computer
Vision and Pattern Recognition.
[Anandkumar et al., 2012] Anandkumar, A., Hsu, D.,
and Kakade, S. M. (2012). A method of moments for
mixture models and hidden markov models. Journalof Machine Learning Research - Proceedings Track,
23:33.1–33.34.

[Collins et al., 2008] Collins, M., Globerson, A., Koo,
T., Carreras, X., and Bartlett, P. L. (2008). Exponentiated gradient algorithms for conditional random fields and max-margin markov networks. The
Journal of Machine Learning Research, 9:1775–
1822.
[Dennis and Ventura, 2012] Dennis, A. and Ventura,
D. (2012). Learning the architecture of sum-productnetworks using clustering on variables. In Advancesin Neural Information Processing Systems.
[Gens and Domingos, 2013] Gens, R. and Domingos,
P. (2013). Learning the structure of sum-productnetworks. In Proceedings of The 30th International
Conference on Machine Learning, pages 873–880.
[Globerson et al., 2007] Globerson, A., Koo, T. Y.,
Carreras, X., and Collins, M. (2007). Exponentiatedgradient algorithms for log-linear structured prediction. In Proceedings of the 24th international conference on Machine learning, pages 305–312. ACM.
[Kivinen and Warmuth, 1997] Kivinen, J. and Warmuth, M. K. (1997). Exponentiated gradient versus
gradient descent for linear predictors. Information
and Computation, 132(1):1–63.
[Lee et al., 2013] Lee, S.-W., Heo, M.-O., and Zhang,
B.-T. (2013). Online incremental structure learningof sum–product networks. In Neural Information
Processing, pages 220–227. Springer.
[Liang and Klein, 2009] Liang, P. and Klein, D.
(2009). Online em for unsupervised models. In Proceedings of human language technologies: The 2009
annual conference of the North American chapter of
the association for computational linguistics, pages
611–619. Association for Computational Linguistics.
[Minka and Lafferty, 2002] Minka, T. and Lafferty, J.
(2002). Expectation-propagation for the generative aspect model. In Proceedings of the Eighteenth
conference on Uncertainty in artificial intelligence,
pages 352–359. Morgan Kaufmann Publishers Inc.
[Peharz, 2015] Peharz, D.-I. R. (2015). Foundationsof Sum-Product Networks for Probabilistic Modeling. PhD thesis, Aalborg University.

[Broderick et al., 2013] Broderick, T., Boyd, N.,
Wibisono, A., Wilson, A. C., and Jordan, M. I.
(2013). Streaming variational bayes. In Advancesin Neural Information Processing Systems, pages
1727–1735.

[Peharz et al., 2013] Peharz, R., Geiger, B. C., andPernkopf, F. (2013). Greedy part-wise learning of
sum-product networks. In Machine Learning andKnowledge Discovery in Databases, pages 612–627.
Springer.

[Cheng et al., 2014] Cheng, W.-C., Kok, S., Pham,
H. V., Chieu, H. L., and Chai, K. M. A. (2014).
Language modeling with sum-product networks. INTERSPEECH.

[Peharz et al., 2014a] Peharz, R., Gens, R., andDomingos, P. (2014a). Learning selective sumproduct networks. ICML Workshop on Learning
Tractable Probabilistic Models.
1476

Abdullah Rashwan, Han Zhao, Pascal Poupart[Peharz et al., 2014b] Peharz, R., Kapeller, G.,
Mowlaee, P., and Pernkopf, F. (2014b). Modelingspeech with sum-product networks: Application to
bandwidth extension. In Acoustics, Speech and Signal Processing (ICASSP), 2014 IEEE International
Conference on, pages 3699–3703. IEEE.
[Peharz et al., 2015] Peharz, R., Tschiatschek, S.,
Pernkopf, F., Domingos, P., and BioTechMed-Graz,
B. (2015). On theoretical properties of sum-productnetworks. In Proceedings of the Eighteenth International Conference on Artificial Intelligence andStatistics, pages 744–752.
[Poon and Domingos, 2011] Poon, H. and Domingos,
P. (2011). Sum-product networks: A new deep architecture. In Proc. 12th Conf. on Uncertainty in
Artificial Intelligence, pages 2551–2558.
[Rooshenas and Lowd, 2014] Rooshenas,
A. andLowd, D. (2014). Learning sum-product networks
with direct and indirect variable interactions. In
Proceedings of The 31st International Conference
on Machine Learning, pages 710–718.
[Wilcoxon, 1950] Wilcoxon, F. (1950). Some rapid approximate statistical procedures. Annals of the New
York Academy of Sciences, pages 808–814.
[Zhao et al., 2015] Zhao, H., Melibari, M., andPoupart, P. (2015). On the relationship between
sum-product networks and bayesian networks. In
Proceedings of The 32nd International Conference
on Machine Learning.

1477