A Unified Approach for Learning the Parameters of
Sum-Product Networks
Han Zhao
Machine Learning Dept.
Carnegie Mellon University
han.zhao@cs.cmu.edu

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

Geoff Gordon
Machine Learning Dept.
Carnegie Mellon University
ggordon@cs.cmu.edu

Abstract
We present a unified approach for learning the parameters of Sum-Product networks(SPNs). We prove that any complete and decomposable SPN is equivalent to a
mixture of trees where each tree corresponds to a product of univariate distributions.
Based on the mixture model perspective, we characterize the objective function
when learning SPNs based on the maximum likelihood estimation (MLE) principle
and show that the optimization problem can be formulated as a signomial program.
We construct two parameter learning algorithms for SPNs by using sequential
monomial approximations (SMA) and the concave-convex procedure (CCCP),
respectively. The two proposed methods naturally admit multiplicative updates,
hence effectively avoiding the projection operation. With the help of the unified
framework, we also show that, in the case of SPNs, CCCP leads to the samealgorithm as Expectation Maximization (EM) despite the fact that they are different
in general.

1

Introduction

Sum-product networks (SPNs) are new deep graphical model architectures that admit exact probabilistic inference in linear time in the size of the network [14]. Similar to traditional graphicalmodels, there are two main problems when learning SPNs: structure learning and parameter learning.
Parameter learning is interesting even if we know the ground truth structure ahead of time; structure learning depends on parameter learning , so better parameter learning can often lead to better
structure learning. Poon and Domingos [14] and Gens and Domingos [6] proposed both generativeand discriminative learning algorithms for parameters in SPNs. At a high level, these approaches
view SPNs as deep architectures and apply projected gradient descent (PGD) to optimize the datalog-likelihood. There are several drawbacks associated with PGD. For example, the projection step in
PGD hurts the convergence of the algorithm and it will often lead to solutions on the boundary of thefeasible region. Also, PGD contains an additional arbitrary parameter, the projection margin, which
can be hard to set well in practice. In [14, 6], the authors also mentioned the possibility of applying
EM algorithms to train SPNs by viewing sum nodes in SPNs as hidden variables. They presented an
EM update formula without details. However, the update formula for EM given in [14, 6] is incorrect,
as first pointed out and corrected by [12].
In this paper we take a different perspective and present a unified framework, which treats [14, 6] as
special cases, for learning the parameters of SPNs. We prove that any complete and decomposable
SPN is equivalent to a mixture of trees where each tree corresponds to a product of univariate
distributions. Based on the mixture model perspective, we can precisely characterize the functional
form of the objective function based on the network structure. We show that the optimization problem
associated with learning the parameters of SPNs based on the MLE principle can be formulated
as a signomial program (SP), where both PGD and exponentiated gradient (EG) can be viewed as
first order approximations of the signomial program after suitable transformations of the objective
30th Conference on Neural Information Processing Systems (NIPS 2016), Barcelona, Spain.

function. We also show that the signomial program formulation can be equivalently transformed intoa difference of convex functions (DCP) formulation, where the objective function of the program
can be naturally expressed as a difference of two convex functions. The DCP formulation allows
us to develop two efficient optimization algorithms for learning the parameters of SPNs based onsequential monomial approximations (SMA) and the concave-convex procedure (CCCP), respectively.
Both proposed approaches naturally admit multiplicative updates, hence effectively deal with thepositivity constraints of the optimization. Furthermore, under our unified framework, we also showthat CCCP leads to the same algorithm as EM despite that these two approaches are different fromeach other in general. Although we mainly focus on MLE based parameter learning, the mixture
model interpretation of SPN also helps to develop a Bayesian learning method for SPNs [21].
PGD, EG, SMA and CCCP can all be viewed as different levels of convex relaxation of the original
SP. Hence the framework also provides an intuitive way to compare all four approaches. We conduct
extensive experiments on 20 benchmark data sets to compare the empirical performance of PGD, EG,
SMA and CCCP. Experimental results validate our theoretical analysis that CCCP is the best among
all 4 approaches, showing that it converges consistently faster and with more stability than the otherthree methods. Furthermore, we use CCCP to boost the performance of LearnSPN [7], showing thatit can achieve results comparable to state-of-the-art structure learning algorithms using SPNs withmuch smaller network sizes.

2

Background

2.1

Sum-Product Networks

To simplify the discussion of the main idea of our unified framework, we focus our attention on SPNs
over Boolean random variables. However, the framework presented here is general and can be easily
extended to other discrete and continuous random variables. We first define the notion of network
polynomial. We use Ix to denote an indicator variable that returns 1 when X = x and 0 otherwise.
Definition 1 (Network Polynomial [4]). Let f (·) 0 be an unnormalized probability distribution
over a Boolean random vector X1:N . The network polynomial of f (·) is a multilinear functionPQN
x f (x)n=1 Ixn of indicator variables, where the summation is over all possible instantiations of
the Boolean random vector X1:N .
A Sum-Product Network (SPN) over Boolean variables X1:N is a rooted DAG that computes the
network polynomial over X1:N . The leaves are univariate indicators of Boolean variables andinternal nodes are either sum or product. Each sum node computes a weighted sum of its children
and each product node computes the product of its children. The scope of a node in an SPN is
defined as the set of variables that have indicators among the node’s descendants. For any node v
in an SPN, ifSv is a terminal node, say, an indicator variable over X, then scope(v) = {X}, else
scope(v) = ṽ2Ch(v) scope(ṽ). An SPN is complete iff each sum node has children with the sameT
scope. An SPN is decomposable iff for every product node v, scope(vi ) scope(vj ) = ? where
vi , vj 2 Ch(v), i 6= j. The scope of the root node is {X1 , . . . , XN }.

In this paper, we focus on complete and decomposable SPNs. For a complete and decomposable
SPN S, each node v in S defines a network polynomial fv (·) which corresponds to the sub-SPN(subgraph) rooted at v. The network polynomial of S, denoted by fS , is the network polynomial
defined by the root of S, which can be computed recursively from its children. The probability
distribution induced by an SPN S is defined as PrS (x) , PfSf(x). The normalization constantx S (x)P
Px fS (x) can be computed in O(|S|) in SPNs by setting the values of all the leaf nodes to be 1, i.e.,
x fS (x) = fS (1) [14]. This leads to efficient joint/marginal/conditional inference in SPNs.
2.2

Signomial Programming (SP)Before introducing SP, we first introduce geometric programming (GP), which is a strict subclassof SP. A monomial is defined as a function h : Rn++ 7! R: h(x) = dxa1 1 xa2 2 · · · xann , where thedomain is restricted to be the positive orthant (Rn++ ), the coefficient d is positive and the exponentsPK
ai 2 R, 8i. A posynomial is a sum of monomials: g(x) = k=1 dk xa1 1k xa2 2k · · · xannk . One of the
key properties of posynomials is positivity, which allows us to transform any posynomial into the log
2domain. A GP in standard form is defined to be an optimization problem where both the objectivefunction and the inequality constraints are posynomials and the equality constraints are monomials.
There is also an implicit constraint that x 2 Rn++ .

A GP in its standard form is not a convex program since posynomials are not convex functions
in general. However, we can effectively transform it into a convex problem by using the logarithmic transformation trick on x, the multiplicative coefficients of each monomial and also eachobjective/constraint function [3, 1].
An SP has the same form as GP except that the multiplicative constant d inside each monomial is not
restricted to be positive, i.e., d can take any real value. Although the difference seems to be small,there is a huge difference between GP and SP from the computational perspective. The negative
multiplicative constant in monomials invalidates the logarithmic transformation trick frequently usedin GP. As a result, SPs cannot be reduced to convex programs and are believed to be hard to solve in
general [1].

3

Unified Approach for Learning

In this section we will show that the parameter learning problem of SPNs based on the MLE principle
can be formulated as an SP. We will use a sequence of optimal monomial approximations combinedwith backtracking line search and the concave-convex procedure to tackle the SP. Due to spaceconstraints, we refer interested readers to the supplementary material for all the proof details.
3.1

Sum-Product Networks as a Mixture of Trees

We introduce the notion of induced trees from SPNs and use it to show that every complete anddecomposable SPN can be interpreted as a mixture of induced trees, where each induced treecorresponds to a product of univariate distributions. From this perspective, an SPN can be understoodas a huge mixture model where the effective number of components in the mixture is determined by
its network structure. The method we describe here is not the first method for interpreting an SPN (orthe related arithmetic circuit) as a mixture distribution [20, 5, 2]; but, the new method can result in an
exponentially smaller mixture, see the end of this section for more details.
Definition 2 (Induced SPN). Given a complete and decomposable SPN S over X1:N , let T =(TV , TE ) be a subgraph of S. T is called an induced SPN from S if
1. Root(S) 2 TV .
2. If v 2 TV is a sum node, then exactly one child of v in S is in TV , and the correspondingedge is in TE .
3. If v 2 TV is a product node, then all the children of v in S are in TV , and the correspondingedges are in TE .

Theorem 1. If T is an induced SPN from a complete and decomposable SPN S, then T is a tree thatis complete and decomposable.
As a result of Thm. 1, we will use the terms induced SPNs and induced trees interchangeably. With
some abuse of notation, we use T (x) to mean the value of the network polynomial of T with input
vector x.
Q
QN
Theorem 2. If T is an induced tree from S over X1:N , then T (x) = (vi ,vj )2TE wij n=1 Ixn ,where wij is the edge weight of (vi , vj ) if vi is a sum node and wij = 1 if vi is a product node.
Remark. Although we focus our attention on Boolean random variables for the simplicity of
discussion and illustration, Thm. 2 can be extended to the case where the univariate distributions at
the leaf nodes are continuous or discrete distributions with countably infinitely many values, e.g.,
Gaussian distributions or Poisson distributions. We can simply replace the product of univariate
QN
QN
distributions term, n=1 Ixn , in Thm. 2 to be the general form n=1 pn (Xn ), where pn (Xn ) is a
univariate distribution over Xn . Also note that it is possible for two unique induced
trees to shareQ
the same product of univariate distributions, but in this case their weight terms (vi ,vi )2TE wij are
guaranteed to be different. As we will see shortly, Thm. 2 implies that the joint distribution over{Xn }Nn=1 represented by an SPN is essentially a mixture model with potentially exponentially many
components in the mixture.
3

Definition 3 (Network cardinality). The network cardinality ⌧S of an SPN S is the number of uniqueinduced trees.
Theorem 3. ⌧S = fS (1|1), where fS (1|1) is the value of the network polynomial of S with input
vector 1 and all edge weights set to be 1.
P⌧S
Theorem 4. S(x) = t=1
Tt (x), where Tt is the tth unique induced tree of S.

Remark. The above four theorems prove the fact that an SPN S is an ensemble or mixture of trees,
where each tree computes an unnormalized distribution over X1:N . The total number of unique trees
in S is the network cardinality ⌧S , which only depends on the structure of S. Each component is a
simple product of univariate distributions. We illustrate the theorems above with a simple example inFig. 1.
+

w1
⇥

X1

+

w3

w2
⇥

X1

⇥

X2

= w1

X2

+

+w2

⇥

X1

X2

+

+w3

⇥

X1

X2

⇥

X1

X2

Figure 1: A complete and decomposable SPN is a mixture of induced trees. Double circles indicate
univariate distributions over X1 and X2 . Different colors are used to highlight unique induced trees;
each induced tree is a product of univariate distributions over X1 and X2 .
Zhao et al. [20] show that every complete and decomposable SPN is equivalent to a bipartite Bayesian
network with a layer of hidden variables and a layer of observable random variables. The numberof hidden variables in the bipartite Bayesian network is equal to the number of sum nodes in S. A
naive expansion of such Bayesian network to a mixture model will lead to a huge mixture model with
2O(M ) components, where M is the number of sum nodes in S. Here we complement their theory
and show that each complete and decomposable SPN is essentially a mixture of trees and the effective
number of unique induced trees is given by ⌧S . Note that ⌧S = fS (1|1) depends only on the network
structure, and can often be much smaller than 2O(M ) . Without loss of generality, assuming that in S
layers of sum nodes are alternating with layers of product nodes, then fS (1|1) = ⌦(2h ), where h is
the height of S. However, the exponentially many trees are recursively merged and combined in S
such that the overall network size is still tractable.
3.2

Maximum Likelihood Estimation as SP

Let’s consider the likelihood function computed by an SPN S over N binary random variables
with model parameters w and input vector x 2 {0, 1}N . Here the model parameters in S are edge
weights from every sum node, and we collect them together into a long vector w 2 RD++ , where D
corresponds to the number of edges emanating from sum nodes in S. By definition, the probability
distribution induced by S can be computed by PrS (x|w) , PfSf(x|w)= ffSS (x|w)(1|w) .
S (x|w)x

N
Corollary 5. Let S be an SPN with weights w 2 RD++ over input vector x 2 {0, 1} , the netPfS (1|1) QN (t) QD
Iwd 2Tt
work polynomial fS (x|w) is a posynomial: fS (x|w) = t=1, wheren=1 Ixn
d=1 wdIwd 2Tt is the indicator variable whether wd is in the t-th induced tree Tt or not. Each monomial
corresponds exactly to a unique induced tree SPN from S.

The above statement is a direct corollary of Thm. 2, Thm. 3 and Thm. 4. From the definition of
network polynomial, we know that fS is a multilinear function of the indicator variables. Corollary 5
works as a complement to characterize the functional form of a network polynomial in terms of
w. It follows that the likelihood function LS (w) , PrS (x|w) can be expressed as the ratio of two
posynomial functions. We now show that the optimization problem based on MLE is an SP. Using
the definition of Pr(x|w) and Corollary 5, let ⌧ = fS (1|1), the MLE problem can be rewritten asP⌧ QN (t) QD
Iw 2T
Ix
wd d tfS (x|w)
maximizew= t=1P⌧n=1QDn d=1
Iwd 2Tt
fS (1|w)(1)
t=1
d=1 wdsubject tow 2 RD++4

Proposition 6. The MLE problem for SPNs is a signomial program.
Being nonconvex in general, SP is essentially hard to solve from a computational perspective [1, 3].
However, despite the hardness of SP in general, the objective function in the MLE formulation of
SPNs has a special structure, i.e., it is the ratio of two posynomials, which makes the design ofefficient optimization algorithms possible.
3.3

Difference of Convex Functions

Both PGD and EG are first-order methods and they can be viewed as approximating the SP after
applying a logarithmic transformation to the objective function only. Although (1) is a signomial
program, its objective function is expressed as the ratio of two posynomials. Hence, we can still
apply the logarithmic transformation trick used in geometric programming to its objective function
and to the variables to be optimized. More concretely, let wd = exp(yd ), 8d and take the log ofthe objective function; it becomes equivalent to maximize the following new objective without any
constraint on y:
0
!1
!!
⌧ (x)
D
⌧
D
X
X
X
X
@
A
maximize log
exp
yd Iyd 2Tt
log
exp
yd Iyd 2Tt
(2)
t=1

t=1

d=1

d=1

Note that in the first term of Eq. 2 the upper index ⌧ (x)  ⌧ , fS (1|1) depends on the current input
x. By transforming into the log-space, we naturally guarantee the positivity of the solution at each
iteration, hence transforming a constrained optimization problem into an unconstrained optimization
problem without any sacrifice. Both terms in Eq. 2 are convex functions in y after the transformation.
Hence, the transformed objective function is now expressed as the difference of two convex functions,which is called a DC function [9]. This helps us to design two efficient algorithms to solve theproblem based on the general idea of sequential convex approximations for nonlinear programming.
3.3.1

Sequential Monomial Approximation

Let’s consider the linearization of both terms in Eq. 2 in order to apply first-order methods in thetransformed space. To compute the gradient with respect to different components of y, we view eachnode of an SPN as an intermediate function of the network polynomial and apply the chain rule toback-propagate the gradient. The differentiation of fS (x|w) with respect to the root node of the
network is set to be 1. The differentiation of the network polynomial with respect to a partial function
at each node can then be computed in two passes of the network: the bottom-up pass evaluates thevalues of all partial functions given the current input x and the top-down pass differentiates the
network polynomial with respect to each partial function. Following the evaluation-differentiation
passes, the gradient of the objective function in (2) can be computed in O(|S|). Furthermore, although
the computation is conducted in y, the results are fully expressed in terms of w, which suggests thatin practice we do not need to explicitly construct y from w.
Let f (y) = log fS (x|exp(y)) log fS (1|exp(y)). It follows that approximating f (y) with the best
linear function is equivalent to using the best monomial approximation of the signomial program (1).
This leads to a sequential monomial approximations of the original SP formulation: at each iterationy(k) , we linearize both terms in Eq. 2 and form the optimal monomial function in terms of w(k) . The
additive update of y(k) leads to a multiplicative update of w(k) since w(k) = exp(y(k) ), and we use
a backtracking line search to determine the step size of the update in each iteration.
3.3.2

Concave-convex Procedure

Sequential monomial approximation fails to use the structure of the problem when learning SPNs.
Here we propose another approach based on the concave-convex procedure (CCCP) [18] to use thefact that the objective function is expressed as the difference of two convex functions. At a high level
CCCP solves a sequence of concave surrogate optimizations until convergence. In many cases, themaximum of a concave surrogate function can only be solved using other convex solvers and as aresult the efficiency of the CCCP highly depends on the choice of the convex solvers. However, weshow that by a suitable transformation of the network we can compute the maximum of the concave
surrogate in closed form in time that is linear in the network size, which leads to a very efficient5algorithm for learning the parameters of SPNs. We also prove the convergence properties of ouralgorithm.
Consider the objective function to be maximized in DCP: f (y) = log fS (x| exp(y))
log fS (1| exp(y)) , f1 (y) + f2 (y) where f1 (y) , log fS (x| exp(y)) is a convex function andf2 (y) , log fS (1| exp(y)) is a concave function. We can linearize only the convex part f1 (y) toobtain a surrogate functionfˆ(y, z) = f1 (z) + rz f1 (z)T (yz) + f2 (y)(3)

for 8y, z 2 R . Now fˆ(y, z) is a concave function in y. Due to the convexity of f1 (y) we have
f1 (y) f1 (z) + rz f1 (z)T (y z), 8y, z and as a result the following two properties always holdfor 8y, z: fˆ(y, z)  f (y) and fˆ(y, y) = f (y). CCCP updates y at each iteration k by solving
y(k) 2 arg maxy fˆ(y, y(k 1) ) unless we already have y(k 1) 2 arg maxy fˆ(y, y(k 1) ), in whichcase a generalized fixed point y(k 1) has been found and the algorithm stops.
D

It is easy to show that at each iteration of CCCP we always have f (y(k) ) f (y(k 1) ). Note alsothat f (y) is computing the log-likelihood of input x and therefore it is bounded above by 0. By themonotone convergence theorem, limk!1 f (y(k) ) exists and the sequence {f (y(k) )} converges.

We now discuss how to compute a closed form solution for the maximization of the concave surrogatefˆ(y, y(k 1) ). Since fˆ(y, y(k 1) ) is differentiable and concave for any fixed y(k 1) , a sufficient andnecessary condition to find its maximum isry fˆ(y, y(k 1) ) = ry(k 1) f1 (y(k 1) ) + ry f2 (y) = 0(4)

In the above equation, if we consider only the partial derivative with respect to yij (wij ), we obtain
(k 1)

wij

fS

fvj (x|w(k 1) ) @fS (x|w(k 1) )(x|w(k 1) )@fvi

(x|w(k 1) )=wij fvj (1|w) @fS (1|w)
fS (1|w) @fvi (1|w)(5)

Eq. 5 leads to a system of D nonlinear equations, which is hard to solve in closed form. However,
0
0
if
0 and
Pwe 0do a change of variable by considering locally normalized weights wij (i.e., wij
w
=
1
8i),
then
a
solutioncanbeeasilycomputed.
As
described
in
[13,
20],
any
SPN
can
be
j ij
transformed into an equivalent normal SPN with locally normalized weights in a bottom up pass asfollows:
wij fvj (1|w)
0
wij
=P
(6)
j wij fvj (1|w)

We can then replace wij fvj (1|w) in the above equation by the expression it is equal to in Eq. 5 toobtain a closed form solution:(k 1)) @fS (x|w(k 1) )(k 1) fvj (x|wfS (x|w(k 1) ) @fvi (x|w(k 1) )

0
wij
/ wij

(7)

Note that in the above derivation both fvi (1|w)/fS (1|w) and @fS (1|w)/@fvi (1|w) can be treated0
as constants and hence absorbed since wij, 8j are constrained to be locally normalized. In order toobtain a solution to Eq. 5, for each edge weight wij , the sufficient statistics include only three terms,(k 1)i.e, the evaluation value at vj , the differentiation value at vi and the previous edge weight wij,
all of which can be obtained in two passes of the network for each input x. Thus the computational
complexity to obtain a maximum of the concave surrogate is O(|S|). Interestingly, Eq. 7 leads tothe same update formula as in the EM algorithm [12] despite the fact that CCCP and EM start fromdifferent perspectives. We show that all the limit points of the sequence {w(k) }1
k=1 are guaranteed to
be stationary points of DCP in (2).
Theorem 7. Let {w(k) }1
k=1 be any sequence generated using Eq. 7 from any positive initial point,then all the limiting points of {w(k) }1
k=1 are stationary points of the DCP in (2). In addition,
limk!1 f (y(k) ) = f (y⇤ ), where y⇤ is some stationary point of (2).
We summarize all four algorithms and highlight their connections and differences in Table 1. Although
we mainly discuss the batch version of those algorithms, all of the four algorithms can be easily
adapted to work in stochastic and/or parallel settings.
6

Table 1: Summary of PGD, EG, SMA and CCCP. Var. means the optimization variables.
Algo

Var.

Update Type

PGD

w

Additive

EG
SMA
CCCP

w
log w
log w

Multiplicative
Multiplicative
Multiplicative

4

Experiments

4.1

Experimental Setting

Update Formula n
(k+1)

wd

(k+1)

(k)

PR✏++ wd + (rwd f1 (w(k) )(k)

rwd f2 (w(k) ))o

wd
wd exp{ (rwd f1 (w(k) ) rwd f2 (w(k) ))}
(k+1)
(k)
(k)
wd
wd exp{ wd ⇥ (rwd f1 (w(k) ) rwd f2 (w(k) ))}
(k+1)
(k)
wij
/ wij ⇥ rvi fS (w(k) ) ⇥ fvj (w(k) )We conduct experiments on 20 benchmark data sets from various domains to compare and evaluate
the convergence performance of the four algorithms: PGD, EG, SMA and CCCP (EM). These 20
data sets are widely used in [7, 15] to assess different SPNs for the task of density estimation. All thefeatures in the 20 data sets are binary features. All the SPNs that are used for comparisons of PGD,
EG, SMA and CCCP are trained using LearnSPN [7]. We discard the weights returned by LearnSPN
and use random weights as initial model parameters. The random weights are determined by thesame random seed in all four algorithms. Detailed information about these 20 datasets and the SPNs
used in the experiments are provided in the supplementary material.
4.2

Parameter Learning

We implement all four algorithms in C++. For each algorithm, we set the maximum number of
iterations to 50. If the absolute difference in the training log-likelihood at two consecutive steps isless than 0.001, the algorithms are stopped. For PGD, EG and SMA, we combine each of them withbacktracking line search and use a weight shrinking coefficient set at 0.8. The learning rates are
initialized to 1.0 for all three methods. For PGD, we set the projection margin ✏ to 0.01. There is nolearning rate and no backtracking line search in CCCP. We set the smoothing parameter to 0.001 in
CCCP to avoid numerical issues.
We show in Fig. 2 the average log-likelihood scores on 20 training data sets to evaluate the convergence
speed and stability of PGD, EG, SMA and CCCP. Clearly, CCCP wins by a large margin over
PGD, EG and SMA, both in convergence speed and solution quality. Furthermore, among the fouralgorithms, CCCP is the most stable one due to its guarantee that the log-likelihood (on training data)
will not decrease after each iteration. As shown in Fig. 2, the training curves of CCCP are moresmooth than the other three methods in almost all the cases. These 20 experiments also clearly showthat CCCP often converges in a few iterations. On the other hand, PGD, EG and SMA are on parwith each other since they are all first-order methods. SMA is more stable than PGD and EG andoften achieves better solutions than PGD and EG. On large data sets, SMA also converges faster than
PGD and EG. Surprisingly, EG performs worse than PGD in some cases and is quite unstable despite
the fact that it admits multiplicative updates. The “hook shape” curves of PGD in some data sets, e.g.
Kosarak and KDD, are due to the projection operations.
Table 2: Average log-likelihoods on test data. Highest log-likelihoods are highlighted in bold. "shows statistically better log-likelihoods than CCCP and # shows statistically worse log-likelihoods
than CCCP. The significance is measured based on the Wilcoxon signed-rank test.
Data set
NLTCS
MSNBC
KDD 2kPlants
Audio
Jester
Netflix
Accidents
Retail
Pumsb-star

CCCP-6.029-6.045-2.134-12.872-40.020-52.880-56.782-27.700-10.919-24.229

LearnSPN#-6.099#-6.113#-2.233#-12.955#-40.510#-53.454#-57.385#-29.907#-11.138#-24.577

ID-SPN#-6.050-6.048#-2.153"-12.554-39.824#-52.912"-56.554"-27.232-10.945"-22.552

Data set
DNA
Kosarak
MSWeb
Book
EachMovie
WebKB
Reuters-52
20 Newsgrp
BBC
Ad

7

CCCP
-84.921-10.880-9.970-35.009-52.557-157.492-84.628-153.205-248.602-27.202

LearnSPN#-85.237#-11.057#-10.269#-36.247#-52.816#-158.542#-85.979#-156.605#-249.794#-27.409

ID-SPN"-84.693-10.605-9.800"-34.436"-51.550"-153.293"-84.389"-151.666#-252.602#-40.012

Figure 2: Negative log-likelihood values versus number of iterations for PGD, EG, SMA and CCCP.
The computational complexity per update is O(|S|) in all four algorithms. CCCP often takes lesstime than the other three algorithms because it takes fewer iterations to converge. We list detailed
running time statistics for all four algorithms on the 20 data sets in the supplementary material.
4.3

Fine Tuning

We combine CCCP as a “fine tuning” procedure with the structure learning algorithm LearnSPN andcompare it to the state-of-the-art structure learning algorithm ID-SPN [15]. More concretely, we keep
the model parameters learned from LearnSPN and use them to initialize CCCP. We then update themodel parameters globally using CCCP as a fine tuning technique. This normally helps to obtaina better generative model since the original parameters are learned greedily and locally during thestructure learning algorithm. We use the validation set log-likelihood score to avoid overfitting. The
algorithm returns the set of parameters that achieve the best validation set log-likelihood score as
output. Experimental results are reported in Table. 2. As shown in Table 2, the use of CCCP after
LearnSPN always helps to improve the model performance. By optimizing model parameters onthese 20 data sets, we boost LearnSPN to achieve better results than state-of-the-art ID-SPN on 7
data sets, where the original LearnSPN only outperforms ID-SPN on 1 data set. Note that the sizesof the SPNs returned by LearnSPN are much smaller than those produced by ID-SPN. Hence, it isremarkable that by fine tuning the parameters with CCCP, we can achieve better performance despite
the fact that the models are smaller. For a fair comparison, we also list the size of the SPNs returned
by ID-SPN in the supplementary material.

5

Conclusion

We show that the network polynomial of an SPN is a posynomial function of the model parameters,
and that parameter learning yields a signomial program. We propose two convex relaxations to solve
the SP. We analyze the convergence properties of CCCP for learning SPNs. Extensive experiments are
conducted to evaluate the proposed approaches and current methods. We also recommend combining
CCCP with structure learning algorithms to boost the modeling accuracy.
Acknowledgments
HZ and GG gratefully acknowledge support from ONR contract N000141512365. HZ also thanks
Ryan Tibshirani for the helpful discussion about CCCP.
8

References[1] S. Boyd, S.-J. Kim, L. Vandenberghe, and A. Hassibi. A tutorial on geometric programming.
Optimization and Engineering, 8(1):67–127, 2007.
[2] H. Chan and A. Darwiche. On the robustness of most probable explanations. In In Proceedingsof the Twenty Second Conference on Uncertainty in Artificial Intelligence.
[3] M. Chiang. Geometric programming for communication systems. Now Publishers Inc, 2005.
[4] A. Darwiche. A differential approach to inference in Bayesian networks. Journal of the ACM(JACM), 50(3):280–305, 2003.
[5] A. Dennis and D. Ventura. Greedy structure search for sum-product networks. In International
Joint Conference on Artificial Intelligence, volume 24, 2015.
[6] R. Gens and P. Domingos. Discriminative learning of sum-product networks. In Advances in
Neural Information Processing Systems, pages 3248–3256, 2012.
[7] R. Gens and P. Domingos. Learning the structure of sum-product networks. In Proceedings of
The 30th International Conference on Machine Learning, pages 873–880, 2013.
[8] A. Gunawardana and W. Byrne. Convergence theorems for generalized alternating minimization
procedures. The Journal of Machine Learning Research, 6:2049–2073, 2005.
[9] P. Hartman et al. On functions representable as a difference of convex functions. Pacific J.
Math, 9(3):707–713, 1959.
[10] J. Kivinen and M. K. Warmuth. Exponentiated gradient versus gradient descent for linear
predictors. Information and Computation, 132(1):1–63, 1997.
[11] G. R. Lanckriet and B. K. Sriperumbudur. On the convergence of the concave-convex procedure.
pages 1759–1767, 2009.
[12] R. Peharz. Foundations of Sum-Product Networks for Probabilistic Modeling. PhD thesis, Graz
University of Technology, 2015.
[13] R. Peharz, S. Tschiatschek, F. Pernkopf, and P. Domingos. On theoretical properties of sumproduct networks. In AISTATS, 2015.
[14] H. Poon and P. Domingos. Sum-product networks: A new deep architecture. In Proc. 12th Conf.
on Uncertainty in Artificial Intelligence, pages 2551–2558, 2011.
[15] A. Rooshenas and D. Lowd. Learning sum-product networks with direct and indirect variableinteractions. In ICML, 2014.
[16] R. Salakhutdinov, S. Roweis, and Z. Ghahramani. On the convergence of bound optimization
algorithms. UAI, 2002.
[17] C. J. Wu. On the convergence properties of the EM algorithm. The Annals of Statistics, pages
95–103, 1983.
[18] A. L. Yuille, A. Rangarajan, and A. Yuille. The concave-convex procedure (CCCP). Advancesin Neural Information Processing Systems, 2:1033–1040, 2002.
[19] W. I. Zangwill. Nonlinear programming: a unified approach, volume 196. Prentice-Hall
Englewood Cliffs, NJ, 1969.
[20] H. Zhao, M. Melibari, and P. Poupart. On the Relationship between Sum-Product Networks andBayesian Networks. In ICML, 2015.
[21] H. Zhao, T. Adel, G. Gordon, and B. Amos. Collapsed variational inference for sum-productnetworks. In ICML, 2016.

9