A

Proof of SPNs as Mixture of Trees

Theorem 1. If T is an induced SPN from a complete and decomposable SPN S, then T is a tree thatis complete and decomposable.
Proof. Argue by contradiction that T is not a tree, then there must exist a node v 2 T such that v has
more than one parent in T . This means that there exist at least two paths R, p1 , . . . , v and R, q1 , . . . , v
that connect the root of S(T ), which we denote by R, and v. Let t be the last node in R, p1 , . . . , v
and R, q1 , . . . , v such that R, . . . , t are common prefix of these two paths. By construction we knowthat such t must exist since these two paths start from the same root node R (R will be one candidateof such t). Also, we claim that t 6= v otherwise these two paths overlap with each other, which
contradicts the assumption that v has multiple parents. This shows that these two paths can be
represented as R, . . . , t, p, . . . , v and R, . . . , t, q, . . . , v where R, . . . , t are the common prefix sharedby these two paths and p 6= q since t is the last common node. From the construction process definedin Def. 2, we know that both p and q are children of t in S. Recall that for each sum node in S, Def. 2
takes at most one child, hence we claim that t must be a product node, since both p and q are childrenof t. Then the paths that t ! p
v and t ! q
v indicate that scope(v) ✓ scope(p) ✓ scope(t)and scope(v) ✓ scope(q) ✓ scope(t), leading to ? 6= scope(v) ✓ scope(p) \ scope(q), which isa contradiction of the decomposability of the product node t. Hence as long as S is complete anddecomposable, T must be a tree.

The completeness of T is trivially satisfied because each sum node has only one child in T . It isalso straightforward to verify that T satisfies the decomposability as T is an induced subgraph of S,
which is decomposable.
⌅
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.
Proof. First, the scope of T is the same as the scope of S because the root of S is also the root of T .
This shows that for each Xi there is at least one indicator Ixi in the leaves otherwise the scope ofthe root node of T will be a strict subset of the scope of the root node of S. Furthermore, for eachvariable Xi there is at most one indicator Ixi in the leaves. This is observed by the fact that there
is at most one child collected from a sum node into T and if Ixi and Ix̄i appear simultaneously inthe leaves, then their least common ancestor must be a product node. Note that the least common
ancestor of Ixi and Ix̄i is guaranteed to exist because of the tree structure of T . However, this leads
to a contradiction of the fact that S is decomposable. As a result, there is exactly one indicator
QnIxi foreach variable Xi in T . Hence the multiplicative constant of the monomial admits the form i=1 Ixi ,which is a product of univariate distributions. More specifically, it is a product of indicator variablesin the case of Boolean input variables.
We have already shown that T is a tree and only product nodes in T can have multiple children. It follows that the functional form of fT (x) must be a monomial, and only edge weightsthat are in T contribute to the monomial. Combing all the above, we know that fT (x) =Q
QN⌅(vi ,vi )2TE wij
n=1 Ixn .
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.
Proof. We prove by induction on the height of S. If the height of S is 2, then depending on the typeof the root node, we have two cases:

1
1. If the root is a sum node with K children, then there are CK= K different subgraphs thatsatisfy Def. 2, which is exactly the value of the network by setting all the indicators andedge weights from the root to be 1.
2. If the root is a product node then there is only 1 subgraph which is the graph itself. Again,
this equals to the value of S by setting all indicators to be 1.

Assume the theorem is true for SPNs with height  h. Consider an SPN S with height h + 1. Again,
depending on the type of the root node, we need to discuss two cases:
101. If the root is a sum node with K children, where the kth sub-SPN has fSk (1|1)
unique induced trees, then by Def. 2 the total number of unique induced trees of S isPK
PK
k=1 fSk (1|1) =k=1 1 · fSk (1|1) = fS (1|1).
2. If the root is a product node with K children, then the total number of unique induced trees
QKof S can then be computed by k=1 fSk (1|1) = fS (1|1).

The second part of the theorem follows by using distributive law between multiplication and addition
to combine unique trees that share the same prefix in bottom-up order.
⌅B

MLE as Signomial Programming

Proposition 6. The MLE problem for SPNs is a signomial program.
Proof. 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
Iw 2T
fS (1|w)
(8)
w d t
t=1

subject towhich we claim is equivalent to:minimizew,zsubject tod=1

dw 2 RD
++
z

⌧
X
t=1

z

D
Y

Iw 2Tt

wd d

⌧ Y
N
D
X
Y
Iw 2T
I(t)
wd d t  0xn
l=1 n=1

d=1

w 2 RD++ , z > 0

(9)

d=1

It is easy to check that both the objective function and constraint function in (9) are signomials. To
see the equivalence of (8) and (9), let p⇤ be the optimal value of (8) achieved at w⇤ . Choose z = p⇤
and w = w⇤ in (9), then z is also the optimal solution of (9) otherwise we can find feasible (z 0 , w0 )in (9) which has z 0 < z , z 0 > z. Combined with the constraint function in (9), we have
0
)
⇤
⇤
⇤
p⇤ = z < z 0  ffSS (x|w(1|w0 ) , which contradicts the optimality of p . In the other direction, let z , w be
the solution that achieves optimal value of (9), then we claim that z ⇤ is also the optimal value of (8),⇤otherwise there exists a feasible w in (8) such that z , ffSS (x|w)(1|w) > z . Since (w, z) is also feasible in⇤⇤(9) with z < z , this contradicts the optimality of z .
⌅The transformation from (8) to (9) does not make the problem any easier to solve. Rather, it destroys
the structure of (8), i.e., the objective function of (8) is the ratio of two posynomials. However, theequivalent transformation does reveal some insights about the intrinsic complexity of the optimization
problem, which indicates that it is hard to solve (8) efficiently with the guarantee of achieving a
globally optimal solution.

C

Convergence of CCCP for SPNs

We discussed before that the sequence of function values {f (y(k) )} converges to a limiting point.
However, this fact alone does not necessarily indicate that {f (y(k) )} converges to f (y⇤ ) where y⇤ isa stationary point of f (·) nor does it imply that the sequence {y(k) } converges as k ! 1. Zangwill’s
global convergence theory [19] has been successfully applied to study the convergence propertiesof many iterative algorithms frequently used in machine learning, including EM [17], generalized
alternating minimization [8] and also CCCP [11]. Here we also apply Zangwill’s theory and combine
the analysis from [11] to show the following theorem:
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,(k)⇤⇤limk!1 f (y ) = f (y ), where y is some stationary point of (2).
11

Proof. We will use Zangwill’s global convergence theory for iterative algorithms [19] to show theconvergence in our case. Before showing the proof, we need to first introduce the notion of “point-toset mapping”, where the output of the mapping is defined to be a set. More formally, a point-to-set
map from a set X to Y is defined as : X 7! P(Y), where P(Y) is the power set of Y. Suppose
X and Y are equipped with the norm || · ||X and || · ||Y , respectively. A point-to-set map is said to⇤1⇤
be closed at x⇤ 2 X if xk 2 X , {xk }1
k=1 ! x and yk 2 Y, {yk }k=1 ! y , yk 2 (xk ) imply thaty ⇤ 2 (x⇤ ). A point-to-set map is said to be closed on S ✓ X if is closed at every point in S.
The concept of closedness in the point-to-set map setting reduces to continuity if we restrict that theoutput of to be a set of singleton for every possible input, i.e., when is a point-to-point mapping.
Theorem 8 (Global Convergence Theorem [19]). Let the sequence {xk }1
k=1 be generated by xk+1 2(xk ), where (·) is a point-to-set map from X to X . Let a solution set ✓ X be given, andsuppose that:
1. all points xk are contained in a compact set S ✓ X .
2. is closed over the complement of .
3. there is a continuous function ↵ on X such that:(a) if x 62 , ↵(x0 ) > ↵(x) for 8x0 2 (x).
(b) if x 2 , ↵(x0 ) ↵(x) for 8x0 2 (x).

Then all the limit points of {xk }1
k=1 are in the solution set↵(x⇤ ) for some x⇤ 2 .

and ↵(xk ) converges monotonically to(k 1)
Let w 2 RD
) = exp(arg maxy fˆ(y, y(k 1) )) and let ↵(w) = f (log w) = f (y) =+ . Let (wlog fS (x| exp(y)) log fS (1| exp(y)). Here we use w and y interchangeably as w = exp(y) or
each component is a one-to-one mapping. Note that since the arg maxy fˆ(y, y(k 1) ) given y(k 1)
is achievable, (·) is a well defined point-to-set map for w 2 RD+.

Specifically, in our case given w(k 1) , at each iteration of Eq. 7 we have(k 1)
wij fvj (1|w)) @fS (x|w(k 1) )(k 1) fvj (x|w
0
/ wij
wij
=P
(k
1)
fS (x|w) @fvi (x|w(k 1) )j wij fvj (1|w)

i.e., the point-to-set mapping is given by

(k 1)

ij (w

(k 1)

)= P

wij

(k

i

(k 1)

j0

1)

@fS (x|w)
fvj (x|w(k 1) ) @f
(k 1) )
v (x|w

wij 0

(k

1)

@fS (x|w)
fvj0 (x|w(k 1) ) @f
(k 1) )
v (x|wi

Let S = [0, 1] , the D dimensional hyper cube. Then the above update formula indicates that(w(k 1) ) 2 S. Furthermore, if we assume w(1) 2 S, which can be obtained by local normalization
D
before any update, we can guarantee that {wk }1
k=1 ✓ S, which is a compact set in R+ .
D

The solution to maxy fˆ(y, y(k 1) ) is not unique. In fact, there are infinitely many solutions to thisnonlinear equations. However, as we define above, (w(k 1) ) returns one solution to this convex
program in the D dimensional hyper cube. Hence in our case (·) reduces to a point-to-point map,
where the definition of closedness of a point-to-set map reduces to the notion of continuity of apoint-to-point map. Define = {w⇤ | w⇤ is a stationary point of ↵(·)}. Hence we only need toverify the continuity of (w) when w 2 S. To show this, we first characterize the functional form of@fS (x|w)@fS (x|w)@fvi (x|w) as it is used inside (·). We claim that for each node vi , @fvi (x|w) is again, a posynomial
function of w. A graphical illustration is given in Fig. 3 to explain the process. This can also bederived from the sum rules and product rules used during top-down differentiation. More specifically,
if vi is a product node, let vj , j = 1, . . . , J be its parents in the network, which are assumed to be sum
PJ @fS (x|w) @fvj (x|w)@fS (x|w)
nodes, the differentiation of fS with respect to fvi is given by @f= j=1 @f.
vi (x|w)
vj (x|w) @fvi (x|w)
We reachJ
X@fS (x|w)@fS (x|w)
=
wij
(10)
@fvi (x|w) j=1@fvj (x|w)
12

+
w1
⇥

⇥

vi

+

+

+

⇥

⇥

+

@fS (x|w)
Figure 3: Graphical illustration of @f. The partial derivative of fS with respect to fvi (invi (x|w)red) is a posynomial that is a product of edge weights lying on the path from root to vi and network
polynomials from nodes that are children of product nodes on the path (highlighted in blue).

Similarly, if vi is a sum node and its parents vj , j = 1, . . . , J are assumed to be product nodes, we
haveJX@fS (x|w)@fS (x|w) fvj (x|w)=@fvi (x|w)@fvj (x|w) fvi (x|w)
j=1

(11)

Since vj is a product node and vj is a parent of vi , so the last term in Eq. 11 can be equivalently
expressed as
fvj (x|w) Y=
fvh (x|w)
fvi (x|w)h6=iwhere the index is range from all the children of vj except vi . Combining the fact that the partial
differentiation of fS with respect to the root node is 1 and that each fv is a posynomial function, it@fS (x|w)
follows by induction in top-down order that @f
is also a posynomial function of w.
v (x|w)i

We have shown that both the numerator and the denominator of (·) are posynomial functionsof w. Because posynomial functions are continuous functions, in order to show that (·) is also
continuous on S\ , we need to guarantee that the denominator is not a degenerate posynomial
function, i.e., the denominator of (w) 6= 0 for all possible input vector x. Recall that={w⇤ | w⇤ is a stationary point of ↵(·)}, hence 8w 2 S\ , w 62 bd S, where bd S is the boundaryof the D dimensional hyper cube S. Hence we have 8w 2 S\ ) w 2 int S ) w > 0 for eachcomponent. This immediately leads to fv (x|w) > 0, 8v. As a result, (w) is continuous on S\
since it is the ratio of two strictly positive posynomial functions.
We now verify the third property in Zangwill’s global convergence theory. At each iteration of CCCP,
we have the following two cases to consider:
1. If w(k 1) 62 , i.e., w(k 1) is not a stationary point of ↵(w), then y(k 1)
arg maxy fˆ(y, y(k 1) ), so we have ↵(w(k) ) = f (y(k) )fˆ(y(k) , y(k 1) )fˆ(y(k 1) , y(k 1) ) = f (y(k 1) ) = ↵(w(k 1) ).
2. If w(k 1) 2
, i.e., w(k 1) is a stationary point of ↵(w), then y(k 1)(karg maxy fˆ(y, y 1) ), so we have ↵(w(k) ) = f (y(k) )fˆ(y(k) , y(k 1) )fˆ(y(k 1) , y(k 1) ) = f (y(k 1) ) = ↵(w(k 1) ).

62
>
2
=

By Zangwill’s global convergence theory, we now conclude that all the limit points of {wk }1
k=1 arein and ↵(wk ) converges monotonically to ↵(w⇤ ) for some stationary point w⇤ 2 .
⌅Remark 1. Technically we need to choose w0 2 int S to ensure the continuity of (·). This initialcondition combined with the fact that inside each iteration of CCCP the algorithm only applies
13

+
w1

w3

w2

⇥

⇥

⇥

+

+

2
3

1
3

X1

X̄1

2
3

X2

1
3

X̄2

Figure 4: A counterexample of SPN over two binary random variables where the weights w1 , w2 , w3
are symmetric and indistinguishable.
positive multiplicative update and renormalization, ensure that after any finite k steps, wk 2 intS.
Theoretically, only in the limit it is possible that some components of w1 may become 0. However
in practice, due to the numerical precision of float numbers on computers, it is possible that aftersome finite update steps some of the components in wk become 0. So in practical implementation
we recommend to use a small positive number ✏ to smooth out such 0 components in wk during theiterations of CCCP. Such smoothing may hurt the monotonic property of CCCP, but this can only
happens when wk is close to w⇤ and we can use early stopping to obtain a solution in the interior ofS.
1
Remark 2. Thm. 7 only implies that any limiting point of the sequence {wk }1
k=1 ({yk }k=1 ) must be
1
a stationary point of the log-likelihood function and {f (y)k }k=1 must converge to some f (y⇤ ) where1y⇤ is a stationary point. Thm. 7 does not imply that the sequence {wk }1
k=1 ({yk }k=1 ) is guaranteed
to converge. [11] studies the convergence property of general CCCP procedure. Under more strong
conditions, i.e., the strict concavity of the surrogate function or that () to be a contraction mapping,1
it is possible to show that the sequence {wk }1
k=1 ({yk }k=1 ) also converges. However, none of suchconditions hold in our case. In fact, in general there are infinitely many fixed points of (·), i.e., theequation (w) = w has infinitely many solutions in S. Also, for a fixed value t, if ↵(w) = t has atleast one solution, then there are infinitely many solutions. Such properties of SPNs make it generally
1very hard to guarantee the convergence of the sequence {wk }1
k=1 ({yk }k=1 ). We give a very simple
example below to illustrate the hardness in SPNs in Fig. 4. Consider applying the CCCP procedure tolearn the parameters on the SPN given in Fig. 4 with three instances {(0, 1), (1, 0), (1, 1)}. Then if
we choose the initial parameter w0 such that the weights over the indicator variables are set as shownin Fig. 4, then any assignment of (w1 , w2 , w3 ) in the probability simplex will be equally optimalin terms of likelihood on inputs. In this example, there are uncountably infinite equal solutions,which invalidates the finite solution set requirement given in [11] in order to show the convergence of1{wk }1k=1 . However, we emphasize that the convergence of the sequence {wk }k=1 is not as importantas the convergence of {↵(w)k }1
todesiredlocationsonthelog-likelihood
surface as in practice
k=1
any w⇤ with equally good log-likelihood may suffice for the inference/prediction task.
It is worth to point out that the above theorem does not imply the convergence of the sequence(k) 1{w(k) }1}k=1 , i.e., the limits of
k=1 . Thm. 7 only indicates that all the limiting points of {w(k) 1
subsequences of {w }k=1 , are stationary points of the DCP in (2). We also present a negative
example in Fig. 4 that invalidates the application of Zangwill’s global convergence theory on theanalysis in this case.
The convergence rate of general CCCP is still an open problem [11]. [16] studied the convergence
rate of unconstrained bound optimization algorithms with differentiable objective functions, of which
our problem is a special case. The conclusion is that depending on the curvature of f1 and f2 (which
are functions of the training data), CCCP will exhibit either a quasi-Newton behavior with superlinear
convergence or first-order convergence. We show in experiments that CCCP normally exhibits a fast,14

superlinear convergence rate compared with PGD, EG and SMA. Both CCCP and EM are special
cases of a more general framework known as Majorization-Maximization. We show that in the caseof SPNs these two algorithms coincide with each other, i.e., they lead to the same update formulas
despite the fact that they start from totally different perspectives.

D

Experiment Details

D.1

Methods

We will briefly review the current approach for training SPNs using projected gradient descent (PGD).
Another related approach is to use exponentiated gradient (EG) [10] to optimize (8). PGD optimizes
the log-likelihood by projecting the intermediate solution back to the positive orthant after each
gradient update. Since the constraint in (8) is an open set, we need to manually create a closed
set on which the projection operation can be well defined. One feasible choice is to project on toDRD✏, 8d} where ✏ > 0 is assumed to be very small. To avoid the projection,✏ , {w 2 R++ | wd
one direct solution is to use the exponentiated gradient (EG) method[10], which was first appliedin an online setting and latter successfully extended to batch settings when training with convex
models. EG admits a multiplicative update at each iteration and hence avoids the need for projectionin PGD. However, EG is mostly applied in convex setting and it is not clear whether the convergenceguarantee still holds or not in nonconvex setting.
D.2

Experimental Setup

The sizes of different SPNs produced by LearnSPN and ID-SPN are shown in Table 3.
Table 3: Sizes of SPNs produced by LearnSPN and ID-SPN.
Data set
LearnSPN
ID-SPN
NLTCS
13,733
24,690MSNBC
54,839579,364
KDD 2k
48,279 1,286,657
Plants132,959 2,063,708
Audio
739,525 2,643,948
Jester314,013 4,225,471
Netflix
161,655 7,958,088
Accidents
204,501 2,273,186
Retail
56,93160,961
Pumsb-star
140,339 1,751,092
DNA
108,021 3,228,616
Kosarak
203,321 1,272,981
MSWeb
68,853 1,886,777
Book
190,625 1,445,501
EachMovie
522,753 2,440,864
WebKB
1,439,751 2,605,141
Reuters-52
2,210,325 4,563,861
20 Newsgrp 14,561,965 3,485,029
BBC
1,879,921 2,426,602
Ad
4,133,421 2,087,253
We list here the detailed statistics of the 20 data sets used in the experiments in Table 4. Table 5shows the detailed running time of PGD, EG, SMA and CCCP on 20 data sets, measured in seconds.

15

Table 4: Statistics of data sets and models. N is the number of variables modeled by the network, |S|is the size of the network and D is the number of parameters to be estimated in the network. N ⇥V /Dmeans the ratio of training instances times the number of variables to the number parameters.
Data set
NLTCS
MSNBC
KDD 2kPlants
Audio
Jester
Netflix
Accidents
Retail
Pumsb-starDNA
Kosarak
MSWeb
Book
EachMovie
WebKB
Reuters-52
20 Newsgrp
BBC
Ad

N
16
17
64
69
100
100
100
111
135
163
180
190
294
500
500
839
889
910
1058
1556

|S|
13,73354,83948,279132,959
739,525
314,013
161,655
204,501
56,931
140,339
108,021203,32168,853
190,625
522,753
1,439,751
2,210,325
14,561,965
1,879,921
4,133,421

D
1,716
24,452
14,29258,853
196,103
180,750
51,60174,804
22,11363,17352,12153,204
20,346
41,122
188,387
879,893
1,453,390
8,295,407
1,222,536
1,380,676

Train
16,181
291,326
180,092
17,412
15,0009,000
15,00012,75822,041
12,262
1,600
33,37529,441
8,700
4,524
2,803
6,532
11,293
1,670
2,461

Valid
2,157
38,843
19,907
2,321
2,000
1,000
2,000
1,700
2,938
1,635
400
4,450
3,270
1,159
1,002
558
1,028
3,764
225
327

Test
3,236
58,26534,955
3,482
3,000
4,116
3,000
2,551
4,408
2,452
1,186
6,675
5,000
1,739
591
838
1,540
3,764
330
491

N ⇥ V /D
150.871202.541806.457
20.4147.649
4.979
29.06918.931134.560
31.6385.526
119.187425.423105.783
12.007
2.673
3.995
1.239
1.445
2.774

Table 5: Running time of 4 algorithms on 20 data sets, measured in seconds.
Data set
NLTCS
MSNBC
KDD 2kPlants
Audio
Jester
Netflix
Accidents
Retail
Pumsb-starDNA
Kosarak
MSWeb
Book
EachMovie
WebKB
Reuters-52
20 Newsgrp
BBC
Ad

PGD
438.352720.7346388.60
12595.60
19647.90
6099.4429573.10
14266.50
28669.50
3115.58599.93122204.00
136524.00
190398.00
30071.60
123088.00
13092.10
151243.00
20920.60
12246.40

EG
718.982917.7222154.10
10752.10
3430.696272.8027931.50
3431.827729.89
13872.80
199.63112273.00
13478.10
6487.8432793.60
50290.90
5438.35
96025.80
18065.00
2183.08

16

SMA
458.998078.41
27101.50
7604.09
12801.70
4082.6515080.50
5776.00
9866.944864.72727.5649120.50
65221.20
69730.50
17751.1044004.50
20603.70
173921.00
36952.20
12346.70

CCCP
206.102008.0729541.20
13049.80
14307.30
1931.41
8400.2020345.90
5200.202377.541380.3642809.30
45132.30
23076.40
60184.00
168142.00
1194.3111031.80
3440.37731.48