A Compositional Atlas of Tractable Circuit Operations for Probabilistic Inference
Year: 2021

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.

heading: 1 Introduction
text: Many core computational tasks in machine learning (ML) and AI involve solving complex integrals, such as expectations appearing in training losses or in information-theoretic quantities including entropies or divergences. A fundamental question naturally arises: under which conditions do these quantities admit tractable computation? Or equivalently, when can we compute them reliably and efficiently without resorting to approximations or heuristics? If we are able to find model classes to tractably compute these quantities of interest—henceforth called queries—we can then design efficient algorithms with important applications in learning, approximate inference [44], model compression [28], explainable AI [24, 47, 52] and algorithmic bias detection [23, 7, 6].
This “quest” for tracing the tractability of different queries has been carried out several times, often independently for different model classes in ML and AI and crucially, for each query in isolation. For example, the computation of the Kullback-Leibler divergence (KLD) is known to have a closed form for Gaussians, but only recently has an exact algorithm been derived for a more complex tractable model class such as probabilistic sentential decision diagrams (PSDDs) [28]. On the other hand, tractable computation of the entropy, despite being a sub-routine for the KLD, has only been derived for a different tractable model class—selective sum-product networks (SPNs) [36]—by Shih and Ermon [44]. In the current paradigm, if one were to trace the tractability of a query that has not
∗This work was done while AV was at the CS Department at UCLA.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
p q / r log s
× t
∫ function kld(p, q)
r = quotient(p, q) s = log(r) t = product(p, s) return integrate(t)
end
function xent(p, q)
r = log(q)
s = product(p, r)
return -integrate(s)
end
1
p
q
log
r
× s
∫
function kld(p, q) r = quotient(p, q) s = log(r) t = product(p, s) return integrate(t) end
function xent(p, q) r = log(q) s = product(p, r) return -integrate(s) end
1
Figure 1: Computational pipelines of the KLD (left) and cross entropy (right) over two distributions p and q encoded as circuits, with the intermediate computations (r, s and t) also represented as circuits. Their corresponding implementations i a few lin s of Julia code are shown on 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 a unified and effortless manner over model classes and query classes. To abstract from the different model formalisms, we carry our analysis over circuit representations [8] as they subsume many tractable generative models—probabilistic circuits such as Chow-Liu trees [9], hidden Markov models (HMMs) [39], sum-product networks (SPNs) [38], and other deep mixture models—as well as 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 a single query as a 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, Fig. 1 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., t) admits tractable integration, we can derive a set of sufficient conditions for the input circuits. Moreover, we can 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 a couple lines of code as shown in Fig. 1. This compositionality greatly speeds up the design of novel tractable algorithms.
We make the following contributions: (1) a 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 are unmet (Tab. 1); (2) a unification and generalization of many inference algorithms proposed in the literature so far for specific representations (Sec. 4); (3) novel tractability and hardness results of complex information-theoretic 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.

heading: 2 Circuit Representations
text: Circuits represent functions as parameterized computational graphs. By imposing certain structural constraints on these graphs, we can guarantee the tractability of certain operations over the encoded functions. Moreover, these constraints help understand how circuits unify several classical tractable model classes, such as mixture models, bounded-treewidth probabilistic graphical models (PGMs), decision trees, and compact logical function representations [8, 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 in Sec. 3 may be restricted to 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 (x). 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).
Definition 2.1 (Circuit). A circuit p over variables X is a parameterized computational graph encoding a function p(X) and comprising three kinds of computational units: input, 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 a parameterized function pn(φ(n)) over variables φ(n) ⊆ X, also called its scope. Instead, if n is a sum unit, it encodes ∑ c∈in(n) θcpc(φ(c)) where θc ∈ R are the sum
parameters; while if it is a product unit, it encodes ∏ c∈in(n) pc(φ(c)). The scope of an inner unit is
the union of the scopes of its inputs: φ(n) = ⋃ c∈in(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 p is non-zero: supp(p) = {x ∈ val(X) | p(x) 6= 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 to be simple enough to allow tractable computations of the operations discussed in this paper. Fig. 2 shows some examples of circuits. A probabilistic circuit (PC) [8] represents a (possibly unnormalized) probability distribution by encoding its probability mass, density, or a combination thereof.
Definition 2.2 (Probabilistic circuit). A PC over variables X is a circuit encoding a function p that is non-negative for all values of X; i.e., ∀x ∈ val(X) : p(x) ≥ 0.
From here on, we will assume that a 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 a circuit alternates between sum and product units and that every product unit n receives only two inputs c1, c2, i.e., pn(X) = pc1(X) ·pc2(X). These conditions can easily be enforced on a circuit in exchange for only a polynomial increase in its 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 a circuit is a function of its size, defined as the number of edges in it and denoted as |p|. For instance, querying the value of p for a complete assignment x equals its feedforward evaluation—inputs before outputs—and therefore is linear in |p|. Other common inference scenarios such as function integration—which translate to marginal inference in the context of probability distributions—can be tackled in linear time with circuits that exhibit certain structural properties, as discussed next.
Structural Properties of Circuits. Structural constraints on the computational graph of a circuit in terms of its scope or support provide sufficient and/or necessary conditions for certain queries to be tractably computed. We now define the structural properties needed for the query classes that this work will focus on, referring to Choi et al. [8] 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 ∈ in(n), φ(c1) = φ(c2).
Smooth PCs generalize shallow mixture models [30] to deep and hierarchical models. For instance, a 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 a (multivariate) Gaussian density.
Definition 2.4 (Decomposability). A circuit is decomposable if the inputs of every product unit n depend on disjoint sets of variables: in(n) = {c1, c2}, φ(c1) ∩ φ(c2) = ∅.
Decomposable product units encode local factorizations. That is, a decomposable product unit n over variables X encodes pn(X) = p1(X1) · p2(X2) where X1 and X2 form a partition of X. Taken together, decomposability and smoothness are a sufficient and necessary condition for performing tractable integration over arbitrary sets of variables in a single feedforward pass, as they enable larger integrals to be efficiently decomposed into smaller ones [15, 8]. Next proposition formalizes it. Proposition 2.1 (Tractable integration, Choi et al. [8]). 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 ∫ z∈val(Z) p(y, z)dZ can be computed exactly in Θ(|p|) 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 at 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 time2 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 p and q over variables X are compatible if (1) they are smooth and decomposable and (2) any pair of product units n∈ p and m∈ q with the same scope can be rearranged into binary products that are mutually compatible and decompose in the same way: (φ(n) =φ(m)) =⇒ (φ(ni) =φ(mi), ni and mi are compatible) for some rearrangement of the inputs of n (resp. m) into n1, n2 (resp. m1,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 is structured-decomposable if it is compatible 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 are structured-decomposable (see Figs. 2a and 2b), but some can be rearranged to be compatible with any decomposable circuit. For instance, in Fig. 2c, the fully factorized product unit p(X) = p1(X1) · p2(X2) · p3(X3) can be rearranged into p1(X1) · (p2(X2) · p3(X3)) and p2(X2) · (p1(X1) · p3(X3)) to match the yellow and pink products in Fig. 2a. We can easily see that omni-compatible circuits must assume the form of mixtures of fully-factorized models; i.e., ∑ i θi ∏ j pi,j(Xj). For example, an additive ensemble of decision trees over variables X can be represented as an omni-compatible circuit (see Ex. D.1 in the Appendix). Also note that if two circuits are compatible and neither is omni-compatible, then both must be structured decomposable. Definition 2.7 (Determinism). A circuit is deterministic if the inputs of every sum unit n have disjoint supports: ∀ c1, c2 ∈ in(n), c1 6= c2 =⇒ supp(c1) ∩ supp(c2) = ∅.
Analogously to decomposability, determinism induces a recursive partitioning, but this time over the support of a 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.,
∑ c∈in(n) θcpc(x) =∑
c∈in(n) θcpc(x)Jx ∈ supp(pc)K. Determinism allows for tractable maximization of circuits [13, 8]. While we do not consider maximization queries in this work, determinism will still play a crucial role in the next sections. Moreover, bounded-treewidth PGMs, such as Chow-Liu trees [9] and thin junction trees [1], can efficiently be represented as smooth, deterministic, and decomposable PCs via compilation [13, 11]. Probabilistic sentential decision diagrams (PSDDs) [26] are deterministic and structured-decomposable PCs that can be efficiently learned from data [11].

heading: 3 From Simple Circuit Transformations. . .
text: This section aims to build an atlas of simple operations over circuits which can then be composed into more complex queries via circuit pipelines—computational 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 of these operations we are interested in characterizing (1) its tractability in terms of the structural properties of its input circuits,
2By changing the order in which n-ary product units are turned into a series of binary product units.
and (2) its closure w.r.t. these properties, i.e. whether they are preserved in the output circuit, in order to compose many operations together in a 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 at least retain decomposability (see Prop. 2.1). For a 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 to approximations, by tracing the hardness of representing the output of an operator as a decomposable circuit when some property of its inputs is unmet. Tab. 1 summarizes all our results. For space constraints, we discuss the main theorems next and report their complete statements and proofs in the Appendix.
Sum of Circuits. The operation of summing two circuits p(Z) and q(Y) is defined as s(X) = θ1 · p(Z) + θ2 · q(Y) for X = Z ∪Y and two real parameters θ1, θ2 ∈ R. This operation, which is at the core of additive ensembles of tractable representations,3 can be realized by introducing a single 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 Prop. B.1 in the Appendix). In particular, if p and q are decomposable then s is also decomposable; moreover, if they are compatible then s is structured-decomposable as well as compatible with p and q. However, representing a sum as a deterministic circuit is known to be NP-hard [43], even for compatible and deterministic inputs.
Product of Circuits. The product of two circuits p(Z) and q(Y) can be expressed as m(X) = p(Z) ·q(Y) for variables X = Z∪Y. If Z and Y are disjoint, the productm is already decomposable. Otherwise, Shen et al. [43] proved that representing the product of two decomposable circuits as a decomposable circuit is NP-hard, even if they are deterministic. We prove a novel result: it is even #P-hard to multiply two structured-decomposable and deterministic circuits. Theorem 3.1 (Hardness of product). If p and q are two structured-decomposable and deterministic circuits, then computing their product as a decomposable circuit is #P-hard.
Shen et al. [43] also introduced an efficient algorithm for the product of two structured-decomposable and deterministic PCs that are 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 a decomposable circuit that is compatible with them can be done in O(|p| |q|) 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 = Z = 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 a simple parametric form for it, as is 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)=p1(X1)p2(X2) and q(X)=q1(X1)q2(X2). Then, their product m as a decomposable circuit can be constructed recursively from the products of their inputs: m(X) = (p1q1)(X1) · (p2q2)(X2). On the other hand, if p and q are smooth sum units, written as p(X)= ∑ i θipi(X) and q(X)= ∑ j θ ′ jqj(X), we can obtain their product m recursively
3If p and q are PCs, then s is a PC encoding a monotonic mixture model if θ1, θ2 > 0 and θ1 + θ2 = 1.
by distributing product over sum. In other words, m(X) = ∑ i,j θiθ ′ j(piqj)(X). Note that if both input circuits are also deterministic, m is also deterministic since supp(piqj)=supp(pi) ∩ supp(qj) 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 O(|p| |q|), which yields a compact circuit m of size O(|p| |q|). This upper bound is loose and in practice product circuits will be much smaller as our experiments show (Sec. 5), especially if inputs are deterministic as products of units with disjoint supports will be “pruned” away.
Powers of a Circuit. The α-power of a PC p(X) for an α ∈ R is denoted as pα(X) 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 (α ∈ N) which can be computed even for general circuits. Theorem 3.3 (Natural powers). If p is a structured-decomposable circuit, then for any α ∈ N, its power can be represented as a structured-decomposable circuit in O(|p|α) time. Otherwise, if p is only smooth and decomposable, then computing pα(X) as a decomposable circuit is #P-hard.
The proof for tractability easily follows by directly applying the product operation repeatedly. However, the exponential dependence on α is unavoidable unless P=NP as we demonstrate in Thm. B.1 in the Appendix, thus rendering the operation intractable for large α.
Turning our attention to non-natural α ∈ R, and restricting our attention to PCs, structureddecomposability is not sufficient to tractably compute α-powers, which we will show in the next theorem for α = −1. First, as zero raised to a negative power is undefined, we instead consider the restricted α-power of a PC, denoted as pα(x)|supp(p) and equal to (p(x))α if x ∈ supp(p) and 0 otherwise. Note that this is equivalent to the α-power if α ≥ 0. Abusing notation, we will also denote this by pα(x)Jx ∈ supp(p)K, where J·K stands for indicator functions. Theorem 3.4 (Hardness of reciprocals). If p is a structured-decomposable circuit over variables X, then computing p−1(X) ∣∣ supp(p) as a decomposable circuit is #P-hard.
The key property that enables efficient computation of power circuits is determinism. More interestingly, we do not require structured-decomposability, but only smoothness and decomposability.
Theorem 3.5 (Tractable real powers). If p is a smooth, decomposable, and deterministic PC, then for any α ∈ R, its restricted power can be represented as a smooth, decomposable, and deterministic circuit that is compatible with p in O(|p|) 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, ( ∑ i θipi(x)Jx ∈ supp(pi)K)α Jx ∈ supp(p)K = ∑ i θ α i p α i (x)Jx ∈ supp(pi)K. This follows from the fact that for any x, at most one indicator Jx ∈ supp(pi)K evaluates to 1. As such, when multiplying a 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 circuit will result in the power circuit having the same structure as the original circuit, with input functions and sum parameters replaced by their α-powers. The space and time complexity of the algorithm is O(|p|) for smooth, deterministic, and decomposable PCs, even for natural powers. This will be a 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), denoted as p(X)/q(X), and restricted to supp(q). The quotient, appearing in queries such as KLD or Itakura-Saito divergence (Sec. 4), can be computed by first taking the reciprocal circuit (i.e., the (−1)-power) of q, followed by its product with p. Thus, if q is deterministic and compatible with p, we can take its reciprocal—which will have the same structure as q—and multiply with p to obtain the quotient as a decomposable circuit as we show in Thm. B.3 in the Appendix. There, Thm. B.2 instead proves that the quotient between p and a non-deterministic q is #P-hard even if they are compatible.
Logarithms of a PC. The logarithm of a 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 p(x)|supp(p) and equal to log p(x) if x ∈ supp(p) and 0 otherwise.
Theorem 3.6 (Logarithms). If p is a smooth, deterministic and decomposable PC, then its restricted logarithm log p(X)|supp(p) can be represented as a decomposable circuit in O(|p|) time. Otherwise, if p is only smooth and decomposable, or even structured-decomposable, computing its restricted logarithm as a decomposable circuit is #P-hard.
Note that while the input of the logarithm operator must be a PC, its output can be a general circuit. Moreover, if p is structured decomposable, then so is its logarithm. The tractability proof is 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 a 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 a 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 non-overlapping supports and perform only a linear number of products (cf. 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 a Circuit. The exponential of a circuit p(X), denoted exp(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 a decomposable circuit that encodes an exponential of a circuit is hard in general. Theorem 3.7 (Hardness of exponentials). If p is a smooth and decomposable circuit, then, computing its exponential as a decomposable circuit is #P-hard, even if p is structured-decomposable.
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 a sum nor product of exponentials. Nevertheless, it is easy to see that if p encodes a linear sum over its variables, i.e., p(X) = ∑ i θiXi, 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 circuit). If p is a linear circuit, then its exponential can be represented as an omni-compatible circuit in O(|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 a 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 an additional circuit operator to the atlas, it would have to take the form of the already discussed operators. First, we require from any functional f to be applied to a circuit p(X) to yield a smooth and decomposable circuit f(p(X)) in order to admit tractable integration and to be added to our atlas. To that end, as usual we can assume to apply f 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 to decompose over products and over sums. In other words, we first need that f(p1(X1) · p2(X2)) can be broken down to either a product f(p1(X1)) · f(p2(X2)) or sum f(p1(X1)) + f(p2(X2)). Furthermore, we want f to similarly decompose over sum units; that is, f(p1(X1) + p2(X2)) also yields a product or sum of f(p1(X1)) and f(p2(X2)). As the next lemma states, a non-linear function f that satisfies either of the above two conditions must be a power, logarithmic, or exponential function. Lemma 3.8. Let f be a continuous function. If f : R→ R satisfies f(x+ y) = f(x) + f(y) then it is a linear function β · x; if f : R+ → R+ satisfies f(x · y) = f(x) · f(y), then it takes the form xβ; if instead f : R+ → R satisfies f(x · y) = f(x) + f(y), then it takes the form β log(x); and if f : R → R+ satisfies that f(x + y) = f(x) · f(y) then it is of the form exp(β · x), for a certain β ∈ R.

heading: 4 . . . to Complex Compositional Queries
text: In this section, we show how our atlas of simple tractable operators can be effectively used to systematically find a tractable model class for any advanced query that comprises these operators.
We will show its practical utility by quickly coming up with tractability proofs as well as 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 αdivergence4 [40] as an 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. 1.
Theorem 4.1 (Tractable alpha divergence). The Rényi’s α-divergence between two distributions p and q, defined as (1−α)−1 log ∫ pα(x)q1−α(x)dX, can be computed exactly inO(|p|α |q|) time for α ∈ N, α > 1 if p and q are compatible and q is deterministic, or in O(|p| |q|) time for α ∈ R, α 6= 1 if p and q are both deterministic and compatible.
Proof. A circuit pipeline for Rényi’s α-divergence involves first computing r = pα and s = q1−α, then t = r · s and finally integrate it.5 Therefore we require t to be a smooth and decomposable circuit (Prop. 2.1), which in turn requires r and s 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 on the value of α. As these theorems state, pα and q1−α will be compatible with p and q , respectively, with sizes O(|p|α) and O(|q|) for a natural power α or O(|p|) and O(|q|) for a real-valued α. As such, t could be computed in O(|p|α |q|) time for α ∈ N or O(|p| |q|) for α ∈ R (Thm. 3.2).
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 can 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. 3 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-Liu 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 α ∈ N [40], which recovers Shannon Entropy for α → 1. As the logarithm is 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).
4Several alternative formulations of α-divergences can be found in the literature such as Amari’s [31] and Tsallis’s [34] divergences. However, as they share the same core operations—real powers and products of circuits—our results easily extend to them as well.
5Note that all the operations outside integration are tractable, therefore we can skip them.
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.1). Nevertheless, given our atlas the cross entropy can be tractably computed in O(|p| |q|) if p and q are deterministic and compatible. Mutual information Let a joint distribution p(X,Y) and its marginals p(X) and p(Y) be represented 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 are compatible and deterministic. On the other hand, if the marginal distributions cannot be represented as compact deterministic PCs, we prove it to be coNP-hard (Thm. C.3).
Divergences Liang and Van den Broeck [28] proposed an efficient algorithm to compute the KLD 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 α-divergences which generalize several other divergences such as the KLD when α→ 1, Hellinger’s squared divergence when α = 2−1, and the X 2-divergence when α=2 [16]. As Thm. 4.1 states, they are tractable for compatible and deterministic PCs, as is the Itakura-Saito divergence [53] (Thm. C.8). For non-deterministic 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 a circuit f w.r.t. a PC p, i.e., Ex∼p(X) [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-compatible circuit (Prop. D.1). This result generalizes the moment computation for simple models such as GMMs and HMMs as they can be encoded as smooth and decomposable PCs (Sec. 2). If f is the indicator function of a 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 as SDDs [14] w.r.t. distributions that are PSDDs. We generalize this result to mixed continuous-discrete distributions encoded as structured-decomposable 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 Ep[f ] refers to computing its expected predictions w.r.t. p [24]. Our results generalize the results reported in Van den Broeck et 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].6

heading: 5 Experiments
text: We prototyped the tractable operators defined in Sec. 3 as subroutines in Julia in the Juice.jl framework [12] to showcase how our modular atlas can practically and quickly help implement tractable
6Despite the name, regression circuits do not conform to our definition of circuits in Def. 2.1. Nevertheless, we can translate them to our format in polytime as we illustrate in Alg. 8 in the Appendix.
algorithms for novel query classes. 7 To this extent, we distilled algorithms for the Shannon, Rényi, and cross entropies and for the KL, Alpha, and Cauchy-Schwarz divergences. We then ran them on deterministic and structured-decomposable circuits learned as in Dang et al. [11] 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. 4 and Tab. 5 in 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(|p| , |q|) when p and q are deterministic, much smaller than the theoretical bound of O(|p| |q|). In terms of execution time, our algorithms run in less than a second for most circuits and peak at slightly more than one minute to compute a pipeline of the KLD, 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 to distill tractable algorithms. We emphasize that the aim of these experiments is not to distill the fastest 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 α and Cauchy-Schwarz divergences.

heading: 6 Discussion and Conclusions
text: 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 AI 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 as 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—while also extending it to powers, logarithms and exponentials as well as 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-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 structured-decomposable models exactly share the same hierarchical 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 [4, 43, 23] can therefore be generalized to non-deterministic distributions in our framework.
Our property-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. 3). 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.
Io so. Ma non ho le prove. Pierpaolo Pasolini. 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 work. This work is partially supported by NSF grants #IIS-1943641, #IIS-1956441, #CCF-1837129, 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.
7Code publicly available at https://github.com/UCLA-StarAI/circuit-ops-atlas.

Review summaries:
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.

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.