A Compositional Atlas of Tractable Circuit Operations for Probabilistic Inference
Authors: antonio vergari
YooJung Choi
Anji Liu
Stefano Teso
Guy Van den Broeck
Venue: NeurIPS 2021 Oral (2021)
Keywords: probabilistic reasoning
tractable inference
probabilistic circuits
sum-product networks

Abstract: Circuit representations are becoming the lingua franca to express and reason about tractable generative and discriminative models. In this paper, we show how complex inference scenarios for these models that commonly arise in machine learning---from  computing the expectations of decision tree ensembles to information-theoretic divergences of sum-product networks---can be represented in terms of tractable modular operations over circuits. Specifically, we characterize the tractability of simple transformations---sums, products, quotients, powers, logarithms, and exponentials---in terms of sufficient structural constraints of the circuits they operate on, and present novel hardness results for the cases in which these properties are not satisfied. Building on these operations, we derive a unified framework for reasoning about tractable models that generalizes several results in the literature and opens up novel tractable inference scenarios.

A Compositional Atlas of Tractable Circuit Operations for Probabilistic Inference
Antonio Vergari' School of Informatics University of Edinburgh avergari @ed ac.uk
YooJung Choi CS Department UCLA
Anji Liu CS Department UCLA liuanj jicas ucla. acla.edu
yj www.i@c..cla..eeeec......e...c.e ucla.edu
Stefano Teso CS Department University of Trento, Italy stefano. teso@unitn.
Guy Van den Broeck
CS Department UCLA guyvdbêcs ucla. edu
Abstract
Circuit representations are becoming the lingua franca to express and reason about tractable generative and discriminative models. In this paper, we show how complex inference scenarios for these models that commonly arise in ma- chine leamiig-frrot from computing the expectations of decision tree ensembles information- -heorretcc divergences of sum- sum-product networks can represented in terms of tractable modular operations over circuits. Specifically, character- products, quotients, powers,
ize the tractability of simple transformationss-sune logarithms, and exponentials-in terms of sufficient structural constraints of the circuits they operate on, and present novel hardness results for the cases in which these properties are satisfied. Building on these operations, derive unified framework for reasoning about tractable models that generalizes several results in the literature and opens up novel tractable inference scenarios.
Introduction
Many core computational tasks machine learning (ML) and Al involve solving complex integrals, such expectations appearing in training losses in information-theoredt quantities including entropies or divergences. A fundamental question naturally arises: under which conditions do these quantities admit tractable computation? Or equivalently, when efficiently without resorting to approximations or heuristics? If we are able to find model classes tractably compute these quantities of interest-henceffrtt called queries-we can then design efficient algorithms with important applications in learning, approximate inference
compute them reliably and
44 model
compression 28 explainable AI 24 47 52
and algorithmic bias detection 23
This "quest" for tracing the tractability different queries has been carried out several times, often independently for different model classes in MI and AI and crucially, for each query in isolation. For example, the computation the Kullback-Leible divergence (KLD) is known to have a closed form for Gaussians, but only recently has exact algorithm been derived for more complex tractable model class such as probabilistic sentential decision diagrams (PSDDs) [28]. On the other hand, tractable computation of the entropy, despite being sub-routine for the KLD, has only been derived for a different tractable model
sum-product networks (SPNs) [36]-by Shih and
Ermon 44 In the current paradigm, if were trace the tractability of query that has
This work done while AV the CS Department UCLA.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

function kid <p q)
function zent
quotient (p. (r)
log(4) (4)
product (p. 2)
product (p.
raturn eintagrate
retura intograto
und
end
Figure I: Computational pipelines of the KLD (left) and cross entropy (right) over two distributions p and encoded as circuits, with the intermediate computations (r, 8 and f) also represented as circuits. Their corresponding implementations in few lines of Julia code are shown their right.
yet been investigated but still involves the same "building blocks" such as logarithms, integrals and products over distributions, for instance Rényi's alpha divergence [40], they would need to derive a novel custom algorithm for each model class and prove its tractability from scratch.
In this paper, we take a different path and introduce a general framework under which the tractability of complex queries can be traced in unified and effortless manner model classes and query classes. To abstract from the different model formalisms, we carry our analysis over circuit representations [8]
they subsume many tractable generative models cise--probbbbiittie circuits such as Chow-Liu trees (9)
hidden Markov models (HMMs) (39, sum- cum-product networks (SPNs) (38], and other deep mixture
models-as well discriminative ones, including decision trees [25 10 and deep regressors (23
thus enabling a unified treatment across model classes.
To generalize our analysis across queries, we propose to represent single query circuit pipeline: a computational graph whose intermediate operations transform and combine the input circuits into other circuits. We can first build a set of simple tractable circuit transformations- sums, products, powers, logarithms, and exponentials- and then i) analyze the tractability of a single query by propagating the sufficient conditions for tractability of the intermediate operators in the pipeline; and ii) automatically distill a tractable inference algorithm by composing the operators used. For instance. [Fi. shows the pipeline for computing the KLD of p and q. two distributions encoded by circuits. We can identify a general class of models that supports its tractable computation: by tracing the conditions for tractable quotient, logarithm, and product over circuits such that the output circuit (i.e., !) admits tractable integration, we can derive a set of sufficient conditions for the input circuits. Moreover,
reuse the logarithm and product operations in the KLD pipeline to reason about the tractability of cross entropy, in the very same way we can reuse the corresponding subroutines we provide in Julia to quickly implement algorithms for the two queries in couple lines of code as shown in Fig. I This compositionality greatly speeds up the design of novel tractable algorithms.
We make the following contributions: (1) systematic way to compositionally answer many complex queries using simple circuit transformations (Sec. 3), proving sufficient conditions for their tractability and computational hardness when these conditions
unmet (Tab. ID: (2) unification and gener- alization of many inference algorithms proposed in the literature so far for specific representations (Sec. 4); (3) novel tractability and hardness results of complex information-theorett queries including several widely used entropies and divergences ( (Tab. 2); and (4) a publicly available implementation of these operators in the Juice circuit library [12]. We now start by introducing the circuit language.
2 Circuit Representations
Circuits represent functions as parameterized computational graphs. By imposing certain structural constraints on these graphs, we guarantee the tractability of certain operations over the encoded functions. Moreover, these constraints help understand how circuits unify several classicul tractable model classes, such as mixture models, founded-treewinng probabilistic graphical models (PGMs), decision trees, and compact logical function representations g 51). As such, circuits provide a language for building and reasoning about tractable representations, and it follows that all our results in the following sections automatically translate to these model classes.
We introduce the basic rules of this language by distinguishing between general circuits and those encoding probability distributions, as some operators Sece may restricted the latter. Then, we will review the structural constraints we need to characterize different inference scenarios, also known as classes of queries. We denote random variables by uppercase letters (X) and their assignments by lowercase ones (zr). Sets of variables and their assignments are denoted by bold uppercase (X) and bold lowercase (x) letters, respectively, and the set of all their values as val(X).

---

(a) Decomposable
(b) prructured-decompose
(c) Omni-compatible
Figure 2: Examples of circuits with different structural properties. The feedforward order is from left
to right; input units labeled by their scopes; and sum parameters are omitted for visual clarity. Product units of the rearranged onni-compatible circuits encoding p(X1) p(X2) p(Xs) are shown in (c) and color-coded with those of matching scope in (a) and (b).
Definition 2.1 (Circuit). A circuit p over variables X is a parameterized computational graph encoding a function pXX) and comprising three kinds of computational units: imput, product, and sum. Each inner unit n (i.e., product or sum unit) receives inputs from other units, denoted in(n). If n is an input unit, it encodes parameterized function (a((())) over variables Φ(n) S X, also called its scope. Instead, if n a sum unit, it encodes Exein(n) (.Pe(o(c)) where 0g E R are the sum parameters; while it is product unit, it encodes Ieεin(n)) Pe (p(c)). The scope of an inner unit is the union of the scopes of its inputs: Φ(n) Ucgin(n) ((c). The output unit of the circuit is the last unit (i.e., with out-degree 0) in the graph, encoding p(X). The support of p is the set of all complete states for X for which the output of is non-zero: supp(p) = {ær E val (X) p(x) # 0}.
Circuits can be understood as compact representations of polynomials with exponentially many terms, whose indeterminates are the functions encoded by the input units. These functions are assumed be simple enough to allow tractable computations of the operations discussed in this paper. Fig. 2 shows some examples of circuits. probabilistic circuit (PC) S represents a (possibly unnormalized) probability distribution by encoding its probability mass, density, combination thereof.
Definition 2.2 (Probabilistic circuit). A PC over variables a circuit encoding function p that non-negative for all values of X; i.e., Vz val(X)) p(x) 2 O.
From here on, we will assume that PC has positive sum parameters and input units that model valid (unnormalized) distributions, which is a sufficient condition to satisfy the above definition. Moreover, w.l.o.g. we will assume that each layer of circuit alternates between sum and product units and that every product unit n receives only two inputs C1, C22 i.e., Pa. (X) Pe, (X) Peg (X). These conditions can easily be enforced on circuit in exchange for only a polynomial increase in size 49 50
Computing (functions of) p(X), or in other words performing inference, can be done by evaluating its computational graph. Hence, the computational cost of inference on circuit is function of its size, defined as the number of edges in it and denoted as [p]. For instance, querying the value of p for complete assignment x: equals feedforward evaluation-inpue inputs before outputs- and therefore is linear in ipl. Other common inference scenarios such as function integration-ww wwhch translate to marginal inference the context of probability distributions be tackled in linear time with circuits that exhibit certain structural properties, as discussed next.
Structural Properties of Circuits. Structural constraints the computational graph of circuit in terms of its scope or support provide sufficient and/or necessary conditions for certain queries to be tractably computed. We define the structural properties needed for the query classes that this work will focus on, referring to Choi et al. g for more details.
Definition 2.3 (Smoothness). A circuit is smooth if for every sum unit n, its inputs depend on the same variables: C1, C2 E in(n), ((()) = ((02).
Smooth PCs generalize shallow mixture models 30 to deep and hierarchical models. For instance, Gaussian mixture model (GMM) can be represented as a smooth PC with a single sum unit over as many input units as mixture components, each encoding (multivariate) Gaussian density.
Definition 2.4 (Decomposability). A circuit is decomposable if the inputs of every product unit depend on disjoint sets of variables: in(n) {ci, o2), σ(c1) n d(c2)) = 0.

---

Decomposable product units encode local factorizations. That is, a decomposable product unit over variables X encodes Pr. (X) = pi (X)) P2 (2(X2) where X, and X₂ form a partition of X. Taken together, decomposability and smoothness are sufficient and necessary condition for performing tractable integration over arbitrary sets of variables in single feedforward pass, as they enable larger integrals to be efficiently decomposed into smaller ones [5] 8]. Next proposition formalizes it.
Proposition 2.1 (Tractable integration, Choi et al. () Let p be a smooth and decomposable circuit over X with input functions that can be tractably integrated. Then for any variables Y X and their assignment y, the integral Jzeval(z) ply, 2 2)Z can be computed exactly in ([pl)) time, where Z denotes X Y.
As the complex queries we focus on in this work involve integration as the last step, it is therefore needed that any intermediate operation preserves least decomposability; smoothness is less of an issue, as it can be enforced in polytime 45. A key additional constraint over scope decompositions is compatibility Intuitively, two decomposable circuits are compatible if they can be rearranged in polynomial time such that their respective product units, once matched by scope, decompose in the same way. We formalize this with the following inductive definition.
Definition 2.5 (Compatibility). Two circuits and over variables X are compatible if (1) they are smooth and decomposable and (2) any pair of product units n E and m E q with the same scope can be rearranged into binary products that are mutually compatible and decompose in the same way: (d(n) = ((m)) = (ő(n,) = (m,,) n, and m, are compatible) for some rearrangement of the inputs of (resp. m) into 1 n22 (resp. my, m2).
We can derive from compatibility the following properties pertaining to a single circuit, which will be useful in our analysis later.
Definition 2.6 (Special types of compatibility). A circuit pruuctureddeecomposatbe if it is com- patible with itself. A decomposable circuit p over X is omni-compatible if it is compatible with any smooth and decomposable circuit over X.
Not all decomposable circuits structured-deccompssabb (see Figs. 2a and 2b but some can be rearranged to be compatible with any decomposable circuit. For instance, in Fig. g 2c
the fully
(X2) Pa( (Xa)) and (2(22) (pi (X1) (Xxs) to match the yellow and pink products in Fig. 2a We can casily see that omni-compatible circuits must assume the form of mixtures of fully-factorized models; i.e. Σ, 0; II, Pt,5(X)) For example, an additive ensemble of decision trees over variables X can be represented as an omni-compatible circuit (see Σx. D.I in the Appendix). Also note that if two circuits are compatible and neither is omni-compatible, then both must be structured decomposable.
factorized product unit p (X) = P1 (X1) ( (X2) P3 PP((X,, (X3) be rearranged into P1
(p2(X2)
Definition 2.7 (Determinism). A circuit is deterministic if the inputs of every sum unit have disjoint supports: Vii, 02 E in(n).c1 7 02 = supp(ci) O supp(e2) 0.
Analogously to decomposability. determinism induces a recursive partitioning. but this time over the support of circuit. For a deterministic sum unit n, the partitioning of its support can be made explicit by introducing an indicator function per each of its inputs, i.e., Eegin(a) (xpx(x) Exgi((n) [x) u E supp(p=)]] Determinism allows for tractable maximization of circuits [13
While we do not consider maximization queries in this work, determinism will still play a crucial role in the next sections. Moreover. bounded-treewidde PGMs, such as Chow-Liu trees [9] and thin junction trees [I] can efficiently be represented as smooth, deterministic, and decomposable PCs via compilation [3 III. Probabilistic sentential decision diagrams (PSDDs) (26] are deterministic and dtroctuee PCs that can be efficiently learned from data
3 From Simple Circuit Transformations...
This section aims to build an atlas of simple operations over circuits which can then be composed into more complex queries via circuit cepelines-commuatiiinnn graphs whose units are tractable operators over circuits. To compose two operators, we would need that the output circuits of one satisfy the structural properties required for the inputs of the other. As such, for each these operations we are interested in characterizing (1) its tractability in terms of the structural properties of its input circuits,
By changing the order in which n-ary product units turned into series of binary product units.

---

Table 1: Tractability and hardness of simple circuit operations. Tractable properties inputs translate to properties on outputs. E.g.. for the quotient p/q. q. if p and are compatible (Cmp) and q is deterministic (Det), then the output decomposable (Dec); also (+) deterministic if p is deterministic; and -erucuureddeecomppabbee (SD) if both p and are. Hardness results are for representing the output as smooth (Sm) and decomposable circuit without some input condition.
Tractability
Operation
Hardness
Input properties
Ouput properties
Time Complexity
0 1 0gg
(=Cmp)
(+SD)
O[pl [e))
NP-hard Det output
PRODUCT
p-gg
Cmpp (+Det, +SD)
Dee (+Der, +SD)
T B000
#P-hard wlo Cmp
Thm
3
POWER
p0.0
p".
SD (+Det)
Dec. Det (+SD)
SD (+Det)
Sm. Dec, (+SD)
O1pp"")
[[[p])
#P-hard wlo SD
4P-hard Det
B.1
QUOTENNT
2//
Cmp: Det (+p Det,+SD)
Dec (+D))r+SD))
([[p]]])
0000 15.1
#P-hard wlo Det
LOG
logtp)
Sm, Dec. Det
Sm, Doe
O1(p))
#P-hard wlo Det
EXP
exp(p)
lineur
O1(p))
4P-hard
and (2) its closure w.r.t. these properties, i.c. whether they are preserved in the output circuit, in order to compose many operations together in pipeline, while (3) providing an efficient algorithmic implementation for it. As we are interested in pipelines for queries involving integration, we would expect the output circuits to least retain decomposability (see (sep.Prop. 2.1). For pipeline in which all operators can be computed tractably, a simple tractable algorithm can be then distilled for it. Furthermore, our analysis will highlight if one needs to resort approximations, by tracing the hardness of representing the output of an operator as a decomposable circuit when some property of its inputs unmet. Tab. summarizes all our results. For space constraints, discuss the main theorems next and report their complete statements and proofs in the Appendix.
Sum of Circuits. The operation of summing two circuits pZZ) and q(Y) is defined as s(X) 81 p(Z) + f2 gYY for X = Z U Y and two real parameters 01, 02 E R. This operation, which is at the core of additive ensembles of tractable representations sum unit that takes as input p and q. Summation applies to any input circuits, regardless of structural assumptions, and it preserves several properties (see Prrop. B.I in the Appendix). In particular, if p and q are decomposable then 8 is also decomposable; moreover, if they are compatible then s is seccuuredddecomooabbele as well as compatible with p and q. However, representing a sum deterministic circuit is known to be NP-hard [4). even for compatible and deterministic inputs.
I can be realized by introducing single
properties
Product of Circuits. The product of two circuits p(Z) and (Y) can be expressed as m(X) p(Z) (22))((Y)) ()) for variables X = ZUY. Z and Y are disjoint, the product m is already decomposable. Otherwise, Shen et al. [43 proved that representing the product of two decomposable circuits as decomposable circuit is NP-hard, even if they are deterministic. We prove a novel result: it is even ha-d to multiply two deuctured-decomposatee and deterministic circuits.
Theorem 3.1 (Hardness of product). If and are two gructtree-ddcoomposse and deterministic circuits, then computing their product decomposable circuit is #P-hard.
Shen et al. 43 also introduced an efficient algorithm for the product of two structured and deterministic PCs that compatible (namely PSDDs). We generalize this result by proving that compatibility alone is sufficient for the tractable product computation of any two circuits.
Theorem 3.2 (Tractable product). If p and q are two compatible circuits, then computing their product as decomposable circuit that is compatible with them can be done in O(pl (4] time.
The proof is by construction and leads to Alg. 3 in the Appendix. In the following, we provide a sketch of the algorithm for the case X- 2 Y. Intuitively, the idea is to "break down" the construction of the product circuit in a recursive manner by exploiting compatibility. The base case is where p and q are input units with simple parametric forms. Their product can be represented as a single input unit as long as we can find simple parametric form for it, as the case for products of exponential families such as (multivariate) Gaussians. Next, we consider the inductive steps where p and q are two sum or product units. If p and q are compatible product units, they decompose X the same way for some ordering of inputs; i.e., p(X)= = Pı (xx))2(XX (X2) and (X) qı (X, )22 (X2). Then, their product m as decomposable eircuit can be constructed recursively from the products of their inputs: m(X) = (p1q) (X.) (p242) (X2). On the other hand, if and are smooth sum units, written as p XX) E, 0.p. () and q (X) Σ, 0/ (X), we can obtain their product m recursively
If p and g are PCs, then is a PC encoding monotonic mixture model if 01, O2 > 0 and 01 + 02 1.
5

---

by distributing product over sum. In other words, m(X) input circuits are also deterministic, is also deterministic since ( n supp(g,) are disjoint for different i, j. Combining these, the algorithm will recursively compute the product of each pair of units in p and q with matching scopes. Assuming efficient products for input units, the overall complexity is Olpl [g]), which yields a compact circuit m of size (1pl [g]) This upper bound is loose and in practice product circuits will be much smaller our experiments show (Sec. 5). especially if inputs are deterministic as products of units with disjoint supports will be "pruned" away.
= E., (p:i)))))) Note that if both
Powers of a Circuit. The a-power of PC p(X) for an a R is denoted as p² and is an operation needed to compute generalizations of the entropy of a PC and related divergences (Sec. 4). Let us first consider natural powers (a N) which can be computed even for general circuits.
Theorem 3.3 (Natural powers). If is structured decomposable circuit, then for any a E N. its power can be represented as a prructureddeecompon only smooth and decomposable, then computing (X) as a decomposable circuit is #P-hard.
circuit in (1ppl)) time. Otherwise, if is
The proof for tractability easily follows by directly applying the product operation repeatedly. However, the exponential dependence on a is unavoidable unless P=NP as we demonstrate in Thm. B.I in the Appendix, thus rendering the operation intractable for large a.
Turning our attention to non-natural a E R. and restricting our attention PCs, structured- decomposability is not sufficient to tractably compute a-powers, which we will show in the next theorem for 1. First, zero raised to negative power is undefined, we instead consider the restricted a-power of PC, denoted as (**))aupp()) and equal to (p(x)) if æ E supp(p) and O otherwise. Note that this is equivalent to the a-power if a 2 0. Abusing notation, we will also denote this by p" [z>[ E supp(p)] where [-] stands for indicator functions.
Theorem 3.4 (Hardness of reciprocals). I is structured- decooppsale circuit over variables X. then computing (X) supp(p) as decomposable circuit is #P-hard.
The key property that enables efficient computation of power circuits is determinism. More interest- ingly, we do not require structured- structured-decomppsabbee decomposabiiliyy but only smoothness and decomposability.
Theorem 3.5 (Tractable real powers). p is a smooth, decomposable, and deterministic PC, then for any E I. its restricted power can be represented smooth, decomposable, and deterministic circuit that is compatible with in (1p)) time.
Again, the proof is done by construction and detailed in Sec. B.3 The key insight is that restricted powers "break down" over a smooth and deterministic sum unit p. That is, supp(r:)]- This follows from
(E, [<> supp(p:)])* [ar supp(p)]
Σ, (f)) the fact that for any x, at most one indicator [ E supp(p;)] evaluates to 1. As such, when multiply- ing deterministic sum unit with itself, each input will only have overlapping support with itself, thus effectively matching product units only with themselves. This is why decomposability suffices. In conclusion, this recursive decomposition of the power of a eircuit will result in the power circuit having the same structure as the original circuit, with input functions and sum parameters replaced by their a-powers. The space and time complexity of the algorithm ((p)) for smooth, deterministic, and decomposable PCs, even for natural powers. This will be key insight to compactly multiply circuits with the same support structure, such as when computing logarithms and entropies (Sec. 4).
We can already see an example of how simple operators can be composed to derive other tractable ones. Consider the quotient of two circuits p(X) and q(X) (X), denoted as ((X)) () (X)), and restricted to supp(q). The quotient, appearing in queries such as KLD or Itakura-Saite Saito divergence (Sec. 4). can be computed by first taking the reciprocal circuit (i.c., the (-1) (-1)-power) of q. followed by its product with p. Thus, if is deterministic and compatible with p. we can take its chiprocal-whieee will have the same structure as q and multiply with p to obtain the quotient as decomposable circuit as we show in Thm. B.3 in the Appendix. There, Thmm B.2 B.2Iinsted proves that the quotient between p and a non non-determimistic q is #P-hard even if they are compatible.
Logarithms of a PC. The logarithm of PC p(X), denoted log p( X), is fundamental in computing
quantities such as entropies and divergences between distributions (Sec. 4). Since the log is undefined for 0 we will again consider the restricted logarithm, denoted as log pl (x)) supp(n) and equal to log p( if x E supp(p) and 0 otherwise.

---

Theorem 3.6 (Logarithms), If p is smooth, deterministic and decomposable PC, then its restricted logarithm log ((X) lmppp(p) can be represented as a decomposable circuit in O(Ip)) time. Otherwise, if p is only smooth and decomposable, or even strucured-decomposahle computing restricted logarithm as decomposable circuit is #P-hard.
Note that while the input of the logarithm operator must be PC, its output can be a general circuit. Moreover, if p is structured decomposable, then so is its logarithm. The tractability proof again by construction and is detailed in [Sec. B.5 in the Appendix. We point out that determinism again allows the restricted log to decompose over the support of the PC, but this time the output circuit is not deterministic, as more than one of its inputs can yield a non-zero output at time. Nevertheless, the inputs of the newly introduced sum units can be clearly partitioned into groups sharing the same support of the corresponding product units in p. This acts as relaxed form of determinism when at most three inputs can be non-zero at once, and it implies that whenever we multiply a deterministic circuit and its logarithmic circuit- for instance to compute its Shannon entropy (Sec. 4) we can leverage the sparsifying effect of oveelleplap supports and perform only a linear number of products (ef. product and power operators). We confirm this empirically in [Sec.. 5 when evaluating the size of the intermediate circuits for computing entropy pipelines over real-world distributions.
Exponentials of Circuit. The exponential of a circuit p(X), denoted (xp(p(X)) is the inverse operation of the logarithm and is a fundamental operation when representing distributions such as log-linear models (27]. Similarly to the logarithm, building decomposable circuit that encodes an exponential of circuit is hard in general.
Theorem 3.7 (Hardness of exponentials). If is a smooth and decomposable circuit, then, computing its exponential decomposable circuit #P-hard, even if p is structureddeccompsssttee
Unlike the logarithm however, restricting the operation to deterministic circuits does not help with tractability, since the issue comes from product units: the exponential of a product is neither sum nor product of exponentials. Nevertheless, it is casy to see that if p encodes linear sum over its variables, i.e., p(X) = Σ; 8,X;, we could easily represent its exponential as a circuit comprising a single decomposable product unit, hence tractably.
Proposition 3.1 (Tractable exponential of a linear eircuit). If p is a linear circuit. then its exponential can be represented as an omni onni-compatible circuit in ((p)) time.
Note that if we were to add an additional deterministic sum unit over many omni-compatible circuits built in this way, we would retrieve mixture of truncated exponentials 32 55). This is the largest
class of tractable exponentials we know so far, and enlarging its boundaries is an open problem.
More operators? Our compositional atlas is now complete. In fact, if we were to add additional circuit operator to the atlas, it would have to take the form of the already discussed operators. First, we require from any functional to be applied to circuit p(X) yield smooth and decomposable circuit (x(()) in order to admit tractable integration and to be added to our atlas. To that end, as usual can assume to apply to the input units of p and obtain tractable representations for the new input units; this is generally the case for simple parametric input functions. Next, we would require f decompose over products and over sums. In other words, we first need that f [(p (X1) P2(2 (X2)) can be broken down to either a product [((i (X1)) ))- (f2((x2) or sum f(p (X, )) [p2 X2)). Furthermore, we want / to similarly decompose over sum units; that is, [(P {x) + P2 (X2)) also yields a product or sum of [(p (X,)) and (((2(X2)). As the next lemma states, non-linear function ff that satisfies either of the above two conditions must be a power, logarithmic, or exponential function.
Lemma 3.8. Lei I be continuous function. If R. - IR satisfies f(x +))= [1x) + f(w) then is a linear function 3 x; i RR_ - R4 satisfies J(x . y) = f(x). f(y), then it takes the form 99; if instead f R2 + R satisfies f(x 3) =f(x)= fly), then it takes the form 3 log()); and if
f: R + R2 satisfies that f(x + y) = f(x) f() then it is of the form exp(3 x), for certain
3 BED R.
4 ... to Complex Compositional Queries
In this section, we show how our atlas of simple tractable operators can be effectively used to systematically find tractable model class for any advanced query that comprises these operators.
7

---

Table 2: Tractability and hardness of informatiiontheeorticc queries over circuits. Tractability given some conditions over the input circuits; computational hardness when some of these are unmet.
Query
Tract. Conditions
Hardness
Reference
CROSS ENTROPY
ppaa log ((r) dX
Cmp. Det Sm, Dec, Det
AP hard wlo Det
Thm. C.1
SHANNON ENTROPY
mn log
coNP-hard w/o
RĀNYI ENTROPY
(1 log [1" aX, a e N
SD
AP hard wlo SD
Tum.
(1 a) log (p"(a) dX, R
Sm, Dec. Det
#P-hard w/o Det
Tim. C.6
MUTCAL INFORMATION
[p(a. logip(ar, (1(((())))
Sm, SD, Det
coNP hard w/o SD
Tim.
KULLBACK-LEIDLLA DIV.
(pta)) log(p(x)//q(a))xx
Cmp. Det
#P-hard w/o Det
Tim. C4
RÉNYI'S ALPHA DIV.
0) log /og/p((ell (=()) dX. a
lug (2r(g" "(x) dX.
Cmp. Det
Cmp. Det
aP-lard Det
#P-hard wio Det
Tim 4.10
N.1
ITAKURA-SAITO DIV.
(ppla//(aaa - lop(p(a))/((a))) - I]d X
Cmp. Det
#P-hard w/o Det
Thm. C.M
CAUCHY-SCHWARZ DIV.
lox V/ (0000 Tomox
Ixleiglan
Cmp
#P-hard wlo Cmp
Thm. C.9
SQUARED LOSS
[(p(e) - (
Cmp
#P-hard w/o Cmp
Tam. C.10
We will show its practical utility by quickly coming up with tractability proofs as well distilling efficient algorithms for several entropy and divergence queries that are largely used in ML. We will then discuss how our discovered tractable circuit classes subsume some previously known results in the literature and prove novel hardness results for when the structural properties of these circuits are unmet. Tab.2 summarizes our results.
We now showcase how a short tractability proof can be easily distilled, using Rényi's a- divergence" 400 as example. Note that no tractable algorithm was available for it yet. A proof can be built by inferring the sufficient conditions to tractably compute each operator in the pipeline- starting from the last before the integral and proceeding backwards according to Tab. !
Theorem 4.1 (Tractable alpha divergence). The Rényi's o-divergence between two distributions p and q, defined as (1 a) a- log (x)) dX. can be computed exactly in (lp) [q]) time for a E N, a > p and q are compatible and q is deterministic, or in O(pl (g)) time for a E I, a + if p and q are both deterministic and compatible.
Proof. A circuit pipeline for Rényi's q-divergence involves first computing pd and ga-a then = r 8 and finally integrate it Therefore we require t to be a smooth and decomposable circuit (Prop. 2.1). which in turn requires r and to be compatible Thm. 3.2) To conclude the proof, we need to compute two compatible circuits r and s in polytime, which can be done according to Thm. 3.5 or Thm. 3.3 depending be compatible with and respectively, with sizes ((pl") and (((g) for a natural power a or (Ip)) and (lgg) for a real-valued a. As such, could be computed in O(p)] [q]) time for E N or O(p) ([ppppl) [gl)) for a E TR (Thm. 3.2
the value of a. As these theorems state, pd and q'-a will
We leave the formal theorems and proofs for the other queries listed in Tab. 2 to Sec. C in the Appendix for space constraints. We remark again that our technique be used beyond this query list and can be applied to any complex query that involves a pipeline comprising the operations we discussed in Sec. and culminating in an integration.
Shannon entropy Smooth, decomposable and deterministic PCs enable the exact computation of Shannon entropy (Thm. C.2) and this tractability result translates to bounded-treewidth PGMs such as Chow- -iu trees and polytrees as they are special cases (Sec. 2). Our framework provides a more succinct tractability proof for the computation of Shannon entropy derived by Shih and Ermon [44), which we complete by demonstrating in Thm. C.2 that it is coNP-hard for non-deterministic PCs.
Rényi entropy For non-deterministic PCs we can employ the tractable computation of Rényi entropy of order a E N (40, which recovers Shannon Entropy for a -> 1. As the logarithm taken after integration of the power circuit, the tractability and hardness follow directly from those of the power operation Thm. 3.3 and 3.5).
"Several alternative formulations of a-divergences be found in the literature such Amari's B1 and Tsallis's [44] divergences. However, as they share the same core operations real powers and products of circuits-our our results easily extend to them as well.
Note that all the operations outside integration are tractable, therefore can skip them.
8

---

Table 3: Efficient algorithms for several query classes quickly distilled using our compositional atlas. Times in seconds to compute the Shannon entropy (ENT), gross-entropp (XENT), Kullback- Leibler divergence (KI.D, Alpha divergence (AlphaDiv) for a = 1.5, Rényi entropy (RényiEnt), and Cauchy-Schwarz divergence (CSDiv) over the circuits learned from 7 real-world datasets (complete results for 10 datasets in Tab. 5) by using algorithms distilled by our pipelines and comparing them to the highly-optimized implementations of the ENT [44] and KLD [28] algorithms available in Juice.jl
[2]. No tractable implementation was available for XENT, AlphaDiv, RényiEnt, and CSDiv.
DATASET
ENT
KLD
XENT
ALPHADIV OURS
RONYIENT
CSDIV
OURS
JUICE
OURS
JUICE
OURS
JUICE
JUICE
OURS
JUICE
OURS
JuICE
KDD
0.157
0.001
3.154
0.790
2,180
0.885
0.016
1.136
PLANTS
0.679
0.005
3,983
3.909
3.739
1.160
0.088
1.572
AUDIO
0.406
0.003
2.736
1.681
1.873
0.537
0.029
0.771
JESTER
0.764
0.003
1.019
0.432
0.805
0.351
0.024
0.476
NETELIX
0.106
0.002
0.352
0.175
0.264
0.100
0.017
0.201
DNA
4.365
0.027
64.664
220.377
52.997
15.609
0.255
22.901
AD
0.193
0.007
0.346
0.046
0.281
0.151
0.031
0.207
Cross entropy As hinted by the presence of a logarithm, the cross entropy is #P-hard to compute without determinism, even for compatible PCs (Thm. C.Ip. Nevertheless, given our atlas the cross entropy can be tractably computed in ((pl lql) if p and q are deterministic and compatible.
Mutual information Let joint distribution pXX, Y) and its marginals pXX) and pYY be repre- sented as PCs. Then the mutual information (MI) over these three PCs can be computed via a pipeline involving product, quotient, and log operators and it is tractable if all circuits compatible and deterministic. On the other hand, if the marginal distributions cannot be represented as compact deterministic PCs, we prove to be coNP-hard (Thm. C.3).
Divergences Liang and Van den Broeck 28 proposed an efficient algorithm to compute the KI.D tailored for PSDDs. This has been the only tractable divergence available for PCs so far. We greatly extend this panorama with our atlas by introducing Rényi's a-divergences which generalize several other divergences such as the KLD when - 1. Hellinger's squared divergence when a = 2-1, and the divddvereence when a x= 2 [T].. As Thm. 4. states, they are tractable for compatible and deterministic PCs, as is the Itakura-Saito divergence [53] (Thm. C.8). For non-deteriinistic PCs, we characterize the tractability of the squared loss and the Cauchy-Schwarz divergence [19]. The latter has applications in mixture models for approximate inference [46] and has been derived in closed-form only for mixtures of simple parametric forms like Gaussians [22). Weibull and Rayligh
distributions
33
Our results generalize them to deep mixture models 38
Expectation queries Among other complex queries that can be abstracted into the general form of an expectation of circuit f w.r.t. a PC p, i.e., Ex--()) [f(x), there are the moments of distributions, such as means and variances. They can be efficiently computed for any smooth and decomposable PC, as f is an omni-compatille circuit (Prop. D.I. This result generalizes the moment computation for simple models such as GMMs and HMMs as they can be encoded as smooth and decomposable PCs (See. 2}. If f is the indicator function of logical formula, the expectation computes its probability w.r.t. the distribution p. Choi et al. [4] proposed an algorithm tailored to formulas f over binary variables, encoded SDDs [14] w.r.t. distributions that PSDDs. We generalize this result mixed continuous-discrete distributions encoded as pructtred-decomposatle
PCs that are not necessarily deterministic and to logical formulas in the language of satisfiability modulo theories (2 over linear arithmetics with univariate literals (Prop. D.2). Lastly, if f encodes constraints over the output distribution of a deep network we retrieve the semantic loss (54). If f encodes a classifier or a regressor, then [f] refers to computing its expected predictions w.r.t. p [24). Our results generalize the results reported in Van den Broeck al. 47 such as computing the expectations of decision trees
and their ensembles [25] (cf. Prop. D.3) as well as those of deep regression circuits 23
5 Experiments
We prototyped the tractable operators defined in Sec. 3 as subroutines in Julia in the Juice,jl frame- work [2] to showcase how our modular atlas can practically and quickly help implement tractable
'Despite the name, regression circuits do not conform to our definition of circuits in Def. 2.1 Nevertheless. we translate them our format in polytime we illustrate in Alg. 8 the Appendix.

---

algorithms for novel query classes. _ To this extent, we distilled algorithms for the Shannon, Rényi, and cross entropies and for the KL, Alpha, and Cauchy-Schward divergences. We then ran them on deterministic and sunctured-decmpooseee
circuits learned as in Dang et al. [ from 20 publicly available real-world benchmark datasets [29] 48).
Tab. 3 shows the time taken to build and execute the pipelines on a subset of the datasets, while Tab. and Tab. Si Sec.. E in the Appendix report all the intermediate circuit sizes in their respective pipelines and times for all datasets. First, the intermediate circuits created in the pipeline do not blow up in size: as predicted by our theoretical analysis, the size of the logarithm circuit grows by a linear factor (~3-4x). Moreover, the size of the product circuit p q is only slightly larger than max(Ipl. (g) when p and q are deterministic, much smaller than the theoretical bound of O(p) Iq]).
In terms of execution time, our algorithms run in less than a second for most circuits and peak at slightly more than one minute compute a pipeline of the KLDD, whose output circuit has more than 3 million edges on the DNA dataset (Tab. 4). A custom and highly optimized implementation of the KLD for PSDDs by Liang and Van den Broeck (28) runs up to ten times faster on smaller circuits but surprisingly takes ~220 seconds for DNA, highlighting that our compositional atlas is a promising way distill tractable algorithms. We emphasize that the aim of these experiments is not distill the fastest al algorithm for a query class, but to demonstrate that our compositional framework empowers practitioners to quickly distill new tractable algorithms for queries that were not available before, such as the Rényi entropy and a and Cauchy- -chhaar divergences.
6 Discussion and Conclusions
This work introduced a unified framework to reason about tractable model classes for complex queries composed of simpler operations. This rich atlas of operators can be used to solve many queries common in probabilistic ML and Al as well as novel inference scenarios.
Darwiche and Marquis 15 is the work most closely related to ours: they define operators over logical circuits, encoding Boolean functions computational graphs with AND and OR gates, for which structural properties analogous to those discussed in [Sec. 2|can be defined. Our results generalize their work on logical tractable operators such as disjunctions and conjunctions-the analogous to our (deterministic) sums and products-whid also extending it to powers, logarithms and exponentials as well complex queries such as divergences. which have no direct counterpart in the logical domain. Algorithms to tractably multiply two probabilistic models have been proposed for probabilistic decision graphs (PDGs) first [17 and PSDDs later [43. Despite the different syntax, both model classes can be encoded as structured-decomppsse decomposable and deterministic circuits in our language [8) Historically, algorithms for the tractable product of PDGs and PSDDs relied on a special case of compatibility, when two structuee-deccmpponn scope partitioning in terms of special graphical representations such as pseudo forests [17 18 and vtrees [37]. They also implicitly entangle compatibility with determinism. As we showed in Thm. 3.2 compatibility is sufficient for tractable multiplication, which interestingly, has been noted in the context of logical circuits 37 As discussed in the previous section, many algorithms tailored for PSDDs
models exactly share the same hierarchical
23 can therefore be generalized to non-deterministc distributions in our framework.
Our property-drine driven analysis closes many open questions about the tractability and hardness of queries for several model classes that are special cases of circuits. At the same time, our hardness results might limit its general applicability by restricting tractable inference of some query classes to only certain inputs (Sec. 3p. However, we see this as an opportunity: now that we can analyze which operators in a pipeline are tractable or not, we could substitute the latter by an approximate inference algorithm distilled from the pipeline. Lastly, we plan to extend our analysis to other queries involving not only integration but also maximization that is, understanding what are the operators that make MAP inference over probabilistic circuits or optimization over general circuits tractable.
Acknowledgements AV would like to thank Yujia Shen and Arthur Choi for insightful discussions about the product algorithm for PSDDs and Zhe Zeng for proofreading an initial version of this #CCF-1837129, work. This work is partially supported by NSF grants #1IS-1943641, #IIS- a Sloan Fellowship. and gifts from Intel and Facebook Research. The research of ST was partially supported by TAILOR, a project funded by EU Horizon 2020 research and innovation programme under GA No 952215.
"Code publicly available at
10

---

References
[1] Francis Bach and Michael Jordan. Thin junetion trees. NIPS, volume 14, pages 569-576, 2001.
[2] Clark Barrett and Cesare Tinelli, Satisfiability modulo theories. In Handbook of Model Checking. pages 305-343. Springer, 2018.
[3] Arthur Choi, Doga Kisa, and Adnan Darwiche. Compiling probabilistic graphical models using sentential decision diagrams. In European Conference on Symbolic and Quantitative Approaches Reasoning and Uncertainty, pages 121-132. Springer, 2013.
[4] Arthur Choi, Guy Van den Broeck, and Adnan Darwiche. Tractable learning for structured probability spaces: A case study in learning preference distributions. In Proceedings of 24th International Joint Conference Artificial Intelligence (IJCAI), volume 2015, pages 2861- 2868, 2015.
[5] YooJung Choi, Adnan Darwiche, and Guy Van den Broeck. Optimal feature selection for decision robustness in bayesian networks. In IJCAI, pages 1554-1560, 2017.
[6] YooJung Choi, Meihua Dang, and Guy Van den Broeck. Group faireess by probabilistic modeling with latent fair decisions. arXiv preprint arXiv:2009.0903// 2020.
[7] YooJung Choi, Golnoosh Farnadi, Behrouz Babaki, and Guy Van den Broeck. Learning fair naive bayes classifiers by discovering and eliminating discrimination patterns. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 10077-10084, 2020.
[8] YooJung Choi, Antonio Vergari, and Guy Van den Broeck. Probabilistic circuits: A unifying framework for tractable probabilistic modeling. 2020.
[9] C Chow and Cong Liu. Approximating discrete probability distributions with dependence trees. IEEE transactions Information Theory, 14(3):462 467, 1968.
[10] Alvaro H. C. Correia, Robert Peharz, and Cassio P. de Campos. Joints in random forests. In NeurlPS, 2020.
[11] Meihua Dang, Antonio Vergari, and Guy Van den Broeck. Strudel: Learning structured- decomposable probabilistic circuits. In PGM, Proceedings of Machine Learning Research, 2020.
[12] Meihua Dang, Pasha Khosravi, Yitao Liang, Antonio Vergari, and Guy Van den Broeck. Juice: A julia package for logic and probabilistic circuits. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (Demo Track), Feb 2021.
[13] Adnan Darwiche. Modeling and reasoning with Bayesian networks. Cambridge university press, 2009.
[14] Adnan Darwiche. Sdd: A new canonical representation of propositional knowledge bases. In Twenty-Second International Joint Conference Artificial Intelligence, 2011.
[15) Adnan Darwiche and Pierre Marquis. A knowledge compilation map. Journal of Artificial Intelligence Research, 17:229 264, 2002.
[16] Alison Gibbs and Francis Edward Su. On choosing and bounding probability metrics. International statistical review, 70(3):419-435, 2002.
[17] Manfred Jaeger. Probabilistic decision combbiing verification and ai techniques for probabilistic inference. International Journal of Uncertainty, Fuzziness and Knowledge-Basee Systems, 12(sup01)):1944 2004.
[18] Manfred Jacger, Jens D Nielsen, and Tomi Silander. Learning probabilistic decision graphs. International Journal of Approximate Reasoning, 42(1-2):84 100, 2006.
[19] Robert Jenssen, Jose C Principe, Deniz Erdogmus, and Torbjørn Eltoft. The cauchy-schwarz divergence and parzen windowing: Connections to graph theory and mereer kernels. Journalof the Franklin Institute, 343(6))614-629, 2006.

---

[20] Mark Jerrum and Alistair Sinclair. folynomial-time approximation algorithms for the ising model. SIAM Journal on computing, 2285::007--1166, 1993.
[21] Wolfgang B Jurkat. On cauchy's 's functional equation. Proceedings of the Americun Mathemati- cal Society, 16(4))683-686, 1965.
[22] Kittipat Kampa, Erion Hasanbelliu, and Jose C Principe. Closed-form cauchy-schwarz pdf divergence for mixture of gaussians. In The 201 International Joint Conference on Neural Networks, pages 2578-2588 7788. IEEE, 2011.
[23] Pasha Khosravi, YooJung Choi, Yitao Liang, Antonio Vergari, and Guy Van den Broeck. On tractable computation of expected predictions. In Advances in Neural Information Processing Systems, pages 11169-11800 2019.
[24] Pasha Khosravi, Yitao Liang, YooJung Choi, and Guy Van den Broeck. What to expect of classifiers? reasoning about logistic regression with missing features. In IJCAI, pages 2716-2724, 2019.
[25] Pasha Khosravi, Antonio Vergari, YooJung Choi, Yitao Liang, and Guy Van den Broeck. Handling missing data in decision trees: A probabilistic approach. In Proceedings of The Art of Learning with Missing Values, Workshop at ICML, 2020.
[26] Doga Kisa, Guy Van den Broeck. Arthur Choi, and Adnan Darwiche. Probabilistic sentential decision diagrams. In Proceedings of the 14th international conference on principles of knowledge representation and reasoning (KR), pages 1-10, 2014.
[27] Daphne Koller and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.
[28] Yitao Liang and Guy Van den Broeck. Towards compact interpretable models: Shrinking of learned probabilistic sentential decision diagrams. In IJCAI 2017 Workshop on Explainable Artificial Intelligence (XAI), August 2017.
[29] Daniel Lowd and Jesse Davis. Learning markov network structure with decision trees. In 2010 IEEE International Conference on Data Mining, pages 334-343. IEEE, 2010.
[30] Geoffrey J McLachlan, Sharon Lee, and Suren I Rathnayake. Finite mixture models, Annual review of statistics and its application, 6:355-371 378,, 2019.
[31] Thomas P. Minka. Expectation propagation for approximate bayesian inference. In UAI, pages 362-369. Morgan Kaufmann, 2001.
[32] Serafín Moral, Rafael Rumí, and Antonio Salmerón. Mixtures of truncated exponentials in hybrid bayesian networks. In ECSOARU, volume 2143 of Lecture Notes in Computer Science, pages 156-167. Springer, 2001.
[33] Frank Nielsen. Closed-form information-theorrtic divergences for statistical mixtures. In Proceedings of the 21 International Conference on Pattern Recognition (ICPR2012), pages 1723-1726 IEEE, 2012.
[34] Manfred Opper, Ole Winther, and Michael J Jordan. Expectation consistent approximate inference. Journal of Machine Learning Research, 6(12), 2005.
[35] Umut Oztok, Arthur Choi, and Adnan Darwiche. Solving ppmP-complete problems using knowledge compilation. In Proceedings of the 15th International Conference on Principles of Knowledge Representation and Reasoning (KR), pages 943, 2016.
[36] Robert Peharz, Robert Gens, and Pedro Domingos. Learning selective sum sum-product networks.
In LTPM workshop, volume 32, 2014.
[37] Knot Pipatsrisawat and Adnan Darwiche. New compilation languages based on structured decomposability. In AAAI, volume 8, pages 517-522, 2008
12

---

[38] Hoifung Poon and Pedro Domingos. Sum-prue cum-product networks: A new deep architecture. In
2011 IEEE International Conference on Computer Vision Workshops (ICCV Workshops), pages 689-690. IEFE, 2011.
[39] Lawrence Rabiner and Biinghwang Juang. An introduction to hidden markov models. ieee assp magazine, (1):4416,, 1986.
[40] Alfréd Rényi et al. On measures of entropy and information. In Proceedings of the Fourth Berkeley Symposium Mathematical Statistics and Probability, Volume I: Contributions to the Theory of Statistics. The Regents of the University of California, 1961.
[41] Amirmohammad Rooshenas and Daniel Lowd. Learning sum-product networks with direct and indirect variable interactions. In International Conference on Machine Learning, pages 710-718. PMLR, 2014.
[42] Prasanna K Sahoo and Palaniappan Kannappan. Introduction to functional equations. CRC Press, 2011.
[43] Yujia Shen, Arthur Choi, and Adnan Darwiche. Tractable operations for arithmetic circuits of probabilistic models. In Advances in Neural Information Processing Systems, pages 3936-3944, 2016.
[44] Andy Shih and Stefano Ermon. Probabilistic circuits for variational inference in discrete graphical models. In NeurlPS, 2020.
[45] Andy Shih, Guy Van den Broeck, Paul Beame, and Antoine Amarilli. Smoothing structured decomposable circuits. In NeurlPS, pages 11412-11422, 2019.
[46] Linh Tran, Maja Pantic, and Marc Peter Deisenroth. Cauchy-schwarz regularized autoencoder. arXiv preprint arXiv:2101.02/111 2021.
[47] Guy Van den Broeck, Anton Lykov, Maximilian Schleich, and Dan Suciu. On the tractability of shap explanations. In Proceedings of the 35th Conference on Artificial Intelligence (AAAI), 2021.
[48] Jan Van Haaren and Jesse Davis. Markov network structure learning: A randomized feature gen- eration approach. In Proceedings of the AAAI Conference Artificial Intelligence, volume 26, 2012.
[49] Antonio Vergari, Nicola Di Mauro, and Floriana Esposito. Simplifying, regularizing and strengthening sum-product network structure learning. Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 343-358. Springer, 2015.
[50] Antonio Vergari, Nicola Di Mauro, and Floriana Esposito. Visualizing and understanding sun-product networks. Machine Learning, 108(4):551-573 2019.
[51] Antonio Vergari, Nicola Di Mauro, and Guy Van den Broeck. Tractable probabilistic models: Representations, algorithms, learning, and applications. Tutorial at UAI, 2019.
[52] Eric Wang, Pasha Khosravi, and Guy Van den Broeck. Probabilistic sufficient explanations. arXiv preprint arXi::2105.10118, 2021.
[53] Bo Wei and Jerry D Gibson. Comparison of distance measures in discrete spectral modeling. Master's thesis, Citeseer, 2001.
[54] Jingyi Xu, Zilu Zhang, Tal Friedman, Yitao Liang, and Guy Van den Broeck. A semantic loss function for deep learning with symbolic knowledge. In ICML, volume 80 of Proceedings of Machine Learning Research, pages 5498-5507. PMLR, 2018.
[55] Zhe Zeng, Paolo Morettin, Fanqi Yan, Antonio Vergari, and Guy Van den Broeck. Scaling up hybrid probabilistic inference with logical and arithmetic constraints via message passing. In ICML, volume 119 of Proceedings of Machine Learning Research, pages 10990-11000. PMLR, 2020.
13


Reviews:
[{"review_id": "tJgFug5TlY", "reviewer": "Reviewer_gLaG", "summary": "This paper introduces a general framework to trace the tractability of complex queries involving circuit representations in a unified manner over model classes and query classes, and to automatically distill tractable inference functions. Using the framework, the paper unifies and generalizes existing inference algorithms in the literature, and presents new tractability and hardness results of many information-theoretic queries.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The proposed framework is novel, and can be very useful for understanding the tractability of complex queries involving circuit representations, as well as deriving tractable inference algorithms. I did not check all the details in the proofs, but the paper seems technically sound, and is clearly written and well organized. The empirical results showing the practicality of the framework is a nice addition.\n\nSome questions to the authors/that need more clarifications:\n1. Is there any redundancy involved in the automatically derived inference algorithms? In other words, are there still advantages in some of the manually derived inference algorithms, even through they are essentially calculating the same thing? What are some sources of this redundancy? There are some brief discussions in L370-377 but it would be informative to include a brief discussion on how the distilled inference algorithm and the highly optimized implementation differ.\n2. It looks like most of the results give sufficient conditions. To what extent are these conditions also necessary? In other words, to what extent is the framework complete? And what are some cases that are not covered by the framework?\n\n=================================\n\nUpdate after rebuttal: I thank the authors for the clarifications. I still think this is a good paper and would recommend acceptance.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "futu4DFPbwV", "reviewer": "Reviewer_fFgc", "summary": "A general framework for developing tractable models using circuits. The main contributions are defining the building blocks for tractable models such that queries can be expressed as compositions of these blocks and also open-source software for building these models quickly with tractable guarantees.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper proposes a general framework for tractable queries based on a circuit representation. The main contribution is to abstract out a set of operations and new queries that can be composed using these abstractions are provably tractable. Thus, new tractable algorithms can be easily developed by composing the operations. Tractability conditions and hardness results are proved for operations. The results are applied to prove hardness or tractability results for several common queries. The main takeaway is that these proofs are quite easy since they build upon the basic operations. It is shown that some information theoretic queries for which tractable algorithms were not available before can be tractably computed using the proposed framework. Experiments are performed as part of an open source package to demonstrate the practical implementation of tractable algorithms.\n\nThe paper is very well written and clear in terms of contributions. While it does cover a lot of material given the page limit, the organization seems very nice with details in the appendix. In terms of overall significance, having the abstraction for tractable models is a valuable contribution along with an open source software package that one can use to quickly implement tractable models. This could potentially have impact in various important sub-fields such as XAI and Fairness in AI. \n\nOverall, I did not see many weaknesses in this paper. One aspect that could be improved is if algorithms may not fit into the proposed tractable framework through the defined operations, some comments on how they could be approximated in the pipeline may also be useful for practical relevance.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "It is hard to see any potential negative societal impact with this work since it seems quite foundational in nature.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "c8eh9Zs1nl2", "reviewer": "Reviewer_FfYX", "summary": "This work suggests a general framework for deriving complex information-theoretic queries using probabilistic circuits (PCs). This framework represents a complex query as a pipeline of operations. The manuscript also provides algorithms for applying these operations to PCs as well.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This work is original in its unifying characteristic. The contributions presented here provide a simple and helpful tool for tractability analysis of common queries in Machine Learning (ML) and related fields.\n\nThe manuscript has an excellent technical quality. The theoretical contributions are non-trivial. Moreover, the work discusses different cases, such as deterministic and non-deterministic PCs. Derived theoretical results are sound, to the best of my knowledge.\n\nThis paper is well-written, and it has a clear presentation. For instance, Table 1 summarizes sufficient conditions for the tractability of typical circuit operations.\n\nThis work is relevant to a broader audience besides the PC community. Indeed, the manuscript summarizes in Table 2 tractability results for various commonly used machine learning functions.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper does not explicitly discuss the limitations of the general framework. It would be interesting to see possible assumptions required for adopting this unifying perspective using PCs.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "1qOVseEsR9w", "reviewer": "Reviewer_cgs4", "summary": "This paper investigate the tractability of arithmetic operations on circuits for probabilistic inference.  There is considerable similar work when it comes to operators on logical circuits, and this paper generalises this to operators such as powers, logarithm and exponentials. The paper also considers these operations in a computational graph, which means that the results of this paper can be used to prove tractability conditions for many queries, in particular divergences and entropy calculations. The paper discusses various examples of such tractability results.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written, and despite its technical nature, is quite easy to follow. The main ideas are discussed in the paper, and sometimes intuitive ideas behind proofs are explained. I thought the general ideas were clear. \n\nThe key concept that seems to be introduced in this paper is compatibility, which turns out to be important to prove many of the tractability results. As far as I can see, this idea is novel and certainly non-trivial. In my estimation, this is a major step forward in this research area. I would expect that this will have significant impact in designing new methods that rely on tractable computations of information-theoretic queries. \n\nAs far as I can see, the paper is technically sound. The experimental results are obviously limited for this type of paper. Some preliminary observations are made from experiments, which I think is sufficient at this point.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Societal impact is not relevant for this paper. The authors do address various hardness results, which are limitations for probabilistic inference in general. This is fine.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Very interesting solid work with potential impact. Please take all comments in consideration.
Decision: Accept (Oral)