The PC shown in Fig. 1 is structured-decomposable because for all three groups of product units
with the same scope (grouped by their colors), their children divide the variable scope in the same
way. For example, the children of both orange units decompose the scope {X1, X2, X3, X4} into
{X1, X2} and {X3, X4}.
As a key sub-routine in the proposed algorithm, we describe how to compute marginal queries given a
smooth and (structured-)decomposable PC in O(|p|) time. First, we assign probabilities to every input
unit: for an input unit n deﬁned on variable X, if evidence is provided for X in the query (e.g., X = x
or X < x), we assign to n the corresponding probability (e.g., p(X = x), p(X < x)) according to fn
in Eq. (2); if evidence of X is not given, probability 1 is assigned to n. Next, we do a feedforward
(children before parents) traverse of inner PC units and compute their probabilities following Eq. (2).
LOSSLESS COMPRESSION WITH PROBABILISTIC CIRCUITS