Year: 2021

Abstract:
Probabilistic circuits (PCs) are a powerful modeling framework for representing tractable probability distributions over combinatorial spaces. In machine learning and probabilistic programming, one is often interested in understanding whether the distributions learned using PCs are close to the desired distribution. Thus, given two probabilistic circuits, a fundamental problem of interest is to determine whether their distributions are close to each other. The primary contribution of this paper is a closeness test for PCs with respect to the total variation distance metric. Our algorithm utilizes two common PC queries, counting and sampling. In particular, we provide a poly-time probabilistic algorithm to check the closeness of two PCs, when the PCs support tractable approximate counting and sampling. We demonstrate the practical efficiency of our algorithmic framework via a detailed experimental evaluation of a prototype implementation against a set of 475 PC benchmarks. We find that our test correctly decides the closeness of all 475 PCs within 3600 seconds.

heading: 1 Introduction
text: Probabilistic modeling is at the heart of modern computer science, with applications ranging from image recognition and image generation [29, 30] to weather forecasting [3]. Probabilistic models have a multitude of representations, such as probabilistic circuits (PCs) [9], graphical models [19], generative networks [16], and determinantal point processes [20]. Of particular interest to us are PCs, which are known to support guaranteed inference and thus have applications in safety-critical fields such as healthcare [2, 25]. In this work, we will focus on PCs that are fragments of the Negation Normal Form (NNF), specifically DNNFs, d-DNNFs, SDNNFs, and PIs [13]. We refer to the survey by Choi et al. [9] for more details regarding PCs.
Given two distributions P and Q, a fundamental problem is to determine whether they are close. Closeness between distributions is frequently quantified using the total variation (TV) distance, dTV (P,Q) = (1/2)‖P −Q‖1, where ‖ · ‖ is the `1 norm [21, 6]. Thus, stated formally, closeness testing is the problem of deciding whether dTV (P,Q) ≤ ε or dTV (P,Q) ≥ η for 0 ≤ ε < η ≤ 1. Determining the closeness of models has applications in AI planning [13], bioinformatics [31, 33, 35] and probabilistic program verification [15, 23].
Equivalence testing is a special case of closeness testing, where one tests if dTV (P,Q) = 0. Darwiche and Huang [13] initiated the study of equivalence testing of PCs by designing an equivalence test for d-DNNFs. An equivalence test is, however, of little use in contexts where the PCs under test ∗The accompanying tool, available open source, can be found at https://github.com/meelgroup/teq. The Appendix is available in the accompanying supplementary material. †The authors decided to forgo the old convention of alphabetical ordering of authors in favor of a randomized ordering, denoted by r©. The publicly verifiable record of the randomization is available at https://www.aeaweb.org/journals/policies/random-author-order/search with confirmation code: icoxrj0sNB2L. For citation of the work, authors request that the citation guidelines by AEA for random author ordering be followed.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
encode non-identical distributions that are nonetheless close enough for practical purposes. Such situations may arise due to the use of approximate PC compilation [10] and sampling-based learning of PCs [26, 27]. As a concrete example, consider PCs that are learned via approximate methods such as stochastic gradient descent [27]. In such a case, PCs are likely to converge to close but non-identical distributions. Given two such PCs, we would like to know whether they have converged to distributions close to each other. Thus, we raise the question: Does there exist an efficient algorithm to test the closeness of two PC distributions?
In this work, we design the first closeness test for PCs with respect to TV distance, called Teq. Assuming the tested PCs allow poly-time approximate weighted model counting and sampling, Teq runs in polynomial time. Formally, given two PC distributions P and Q, and three parameters (ε,η,δ), for closeness(ε), farness(η), and tolerance(δ), Teq returns Accept if dTV (P,Q) ≤ ε and Reject if dTV (P,Q) ≥ η with probability at least 1 − δ. Teq makes atmost O((η − ε)−2 log(δ−1)) calls to the sampler and exactly 2 calls to the counter.
Teq builds on a general distance estimation technique of Canonne and Rubinfeld [4] that estimates the distance between two distributions with a small number of samples. In the context of PCs, the algorithm requires access to an exact sampler and an exact counter. Since not all PCs support exact sampling and counting, we modify the technique presented in [4] to allow for approximate samples and counts. Furthermore, we implement and test Teq on a dataset of publicly available PCs arising from applications in circuit testing. Our results show that closeness testing can be accurate and scalable in practice.
For some NNF fragments, such as DNNF, no sampling algorithm is known, and for fragments such as PI, sampling is known to be NP-hard [32]. Since Teq requires access to approximate weighted counters and samplers to achieve tractability, the question of determining the closeness of the PCs mentioned above remains unanswered. Thus, we investigate further and characterize the complexity of closeness testing for a broad range of PCs. Our characterization reveals that PCs from the fragments d-DNNFs and SDNNFs can be tested for closeness in poly-time via Teq, owing to the algorithms of Darwiche [11] and Arenas et al. [1]. We show that the SDNNF approximate counting algorithm of Arenas et al. [1] can be extended to log-linear SDNNFs using chain formulas [8]. Then, using previously known results, we also find that there are no poly-time equivalence tests for PCs from PI and DNNF, conditional on widely believed complexity-theoretic conjectures. Our characterization also reveals some open questions regarding the complexity of closeness and equivalence testing of PCs.
The rest of the paper is organized in the following way. We define the notation and discuss related work in Section 2. We then present the main contribution of the paper, the closeness test Teq, and the associated proof of correctness in Section 3. We present our experimental findings in Section 4, and then discuss the complexity landscape of closeness testing in Section 5. We conclude the paper and discuss some open problems in Section 6. Due to space constraints, we defer some proofs to the supplementary Section A.

heading: 2 Background
text: Let ϕ : {0, 1}n → {0, 1} be a circuit over n Boolean variables. An assignment σ ∈ {0, 1}n to the variables of ϕ is a satisfying assignment if ϕ(σ) = 1. The set of all satisfying assignments of ϕ is Rϕ. If |Rϕ| > 0, then ϕ is said to be satisfiable and if |Rϕ| = 2n, then ϕ is said to be valid. We use |ϕ| to denote the size of circuit ϕ, where the size is the total number of vertices and edges in the circuit DAG.
The polynomial hierarchy (PH) contains the classes ΣP1 (NP) and Π P 1 (co-NP) along with generalizations of the form ΣPi and Π P i where Π P i+1 = co-NP ΠPi and ΣPi+1 = NP ΣPi [34]. The classes ΣPi and ΠPi are said to be at level i. If it is shown that two classes on the same or consecutive levels are equal, the hierarchy collapses to that level. Such a collapse is considered unlikely, and hence is used as the basic assumption for showing hardness results, including the ones we present in the paper.

heading: 2.1 Probability distributions
text: A weight function w : {0, 1}n → Q+ assigns a positive rational weight to each assignment σ. We extend the definition of w to also allow circuits as input: w(ϕ) = ∑ σ∈Rϕ w(σ). For weight function w and circuit ϕ, w(ϕ) is the weighted model count (WMC) of ϕ w.r.t. w.
In this paper, we focus on log-linear weight functions as they capture a wide class of distributions, including those arising from graphical models, conditional random fields, and skip-gram models [24]. Log-linear models are represented as literal-weighted functions, defined as: Definition 1. For a set X of n variables, a weight function w is called literal-weighted if there is a poly-time computable map w : X → Q ∩ (0, 1) such that for any assignment σ ∈ {0, 1}n :
w(σ) = ∏ x∈σ { w(x) if x = 1 1− w(x) if x = 0
For all circuits ϕ, and log-linear weight functions w, w(ϕ) can be represented in size polynomial in the input.
Probabilistic circuits: A probabilistic circuit is a satisfiable circuit ϕ along with a weight function w. ϕ and w together define a discrete probability distribution on the set {0, 1}n that is supported over
Rϕ. We denote the p.m.f. of this distribution as: P (ϕ, w)(σ) = { 0 ϕ(σ) = 0
w(σ)/w(ϕ) ϕ(σ) = 1
In this paper, we study circuits that are fragments of the Negation Normal Form (NNF). A circuit ϕ in NNF is a rooted, directed acyclic graph (DAG), where each leaf node is labeled with true, false, v or ¬v; and each internal node is labeled with a ∧ or ∨ and can have arbitrarily many children. We focus on four fragments of NNF, namely, Decomposable NNF(DNNF), deterministic-DNNF(d-DNNF), Structured DNNF(SDNNF), and Prime Implicates(PI). For further information regarding circuits in NNF, refer to the survey [14] and the paper [28].
The TV distance of two probability distributions P (ϕ1, w1) and P (ϕ2, w2) over {0, 1}n is defined as: dTV (P (ϕ1, w1), P (ϕ2, w2)) = 1 2 ∑ σ∈{0,1}n |P (ϕ1, w1)(σ)− P (ϕ2, w2)(σ)|.
P (ϕ1, w1) and P (ϕ2, w2) are said to be (1) equivalent if dTV (P (ϕ1, w1), P (ϕ2, w2)) = 0, (2) ε-close if dTV (P (ϕ1, w1), P (ϕ2, w2)) ≤ ε, and (3) η-far if dTV (P (ϕ1, w1), P (ϕ2, w2)) ≥ η. Our closeness testing algorithm Teq, assumes access to an approximate weighted counter Awct(α, β, ϕ, w), and an approximate weighted sampler Samp(α, β, ϕ, w). We define their behavior as follows: Definition 2. Awct(α, β, ϕ, w) takes a circuit ϕ, a weight function w, a tolerance parameter α > 0 and a confidence parameter β > 0 as input and returns the approximate weighted model count of ϕ w.r.t. w such that
Pr
[ w(ϕ)
1 + α ≤ Awct(α, β, ϕ, w) ≤ (1 + α)w(ϕ)
] ≥ 1− β
Tractable approximate counting algorithms for PCs are known as Fully Polynomial Randomised Approximation Schemes (FPRAS). The running time of an FPRAS is given by T (α, β, ϕ) = poly(α−1, log(β−1), |ϕ|). Definition 3. Samp(α, β, ϕ, w) takes a circuit ϕ, a weight function w, a tolerance parameter α > 0 and a confidence parameter β > 0 as input and returns either (1) a satisfying assignment σ sampled approximately w.r.t. weight function w with probability ≥ 1− β or (2) a symbol ⊥ indicating failure with probability < β. In other words, whenever Samp samples σ:
P (ϕ, w)(σ)
1 + α ≤ Pr[Samp(α, β, ϕ, w) = σ] ≤ (1 + α)P (ϕ, w)(σ)
Tractable approximate sampling algorithms for PCs are known as Fully Polynomial Almost Uniform Samplers (FPAUS). The running time of an FPAUS for a single sample is given by T (α, β, ϕ) = poly(α−1, log(β−1), |ϕ|).
In the rest of the paper [m] denotes the set {1, 2, . . .m}, 1(e) represents the indicator variable for event e, and E(v) represents the expectation of random variable v.

heading: 2.2 Related work
text: Closeness testing: Viewing circuit equivalence testing through the lens of distribution testing, we see that the d-DNNF equivalence test of Darwiche and Huang [13] can be interpreted as an equivalence test for uniform distribution on the satisfying assignments of d-DNNFs. This relationship between circuit equivalence testing and closeness testing lets us rule out the existence of distributional equivalence tests for all those circuits for which circuit equivalence is already known to be hard under complexity-theoretic assumptions. We will explore this further in Section 5.2.
Distribution testing: Discrete probability distributions are typically defined over an exponentially large number of points; hence a lot of recent algorithms research has focused on devising tests that require access to only a sublinear or even constant number of points in the distribution [5]. In this work, we work with distributions over {0, 1}n, and thus we aim to devise algorithms with running time at most polynomial in n. Previous work in testing distributions over Boolean functions has focused on the setting where the distributions offer pair-conditional sampling access [7, 22]. Using pair-conditional sampling access, Meel r© et al. [22] were able to test distributions for closeness using Õ(tilt(ϕ)2/(η − 6ε)3η) queries, where tilt is the ratio of the probabilities of the most and least probable element in the support.
3 Teq: a tractable algorithm for closeness testing
In this section, we present the main contribution of the paper: a closeness test for PCs, Teq. The pseudocode of Teq is given in Algorithm 1.
Given satisfiable circuits ϕ1, ϕ2 and weight functions w1, w2 along with parameters (ε, η, δ), Teq decides whether the TV distance between P (ϕ1, w1) and P (ϕ2, w2) is lesser than ε or greater than η with confidence at least 1 − δ. Teq assumes access to an approximate weighted counter Awct(α, β, ϕ, w), and an approximate weighted sampler Samp(α, β, ϕ, w). We define their behavior in the following two definitions.
The algorithm Teq starts by computing constants γ and m. Then it queries the Awct routine with circuit ϕ1 and weight function w1 to obtain a √ 1 + γ/4−1 approximation of w1(ϕ1) with confidence at least 1− δ/8. A similar query is made for ϕ2 and w2 to obtain an approximate value for w2(ϕ2). These values are stored in k1 and k2, respectively. Teq maintains a m-sized array Γ, to store the estimates for r(σi). Teq now iterates m times. In each iteration, it generates one sample σi through the Samp call on line 7. There is a small probability of at most δ/4m that this call fails and returns ⊥. Teq only samples from one of the two PCs.
The algorithm then proceeds to compute the weight of assignment σi w.r.t. the weight functions w1 and w2 and stores it in s1 and s2, respectively. Using the weights and approximate weighted counts stored in k1, k2 the algorithm computes the value r(σi) on line 10, where r(σi) is an approximation of the ratio of the probability of σi in the distribution P (ϕ2, w2) to its probability in P (ϕ1, w1). Since σi was sampled from P (ϕ1, w1), its probability in P (ϕ1, w1) cannot be 0, ensuring that there is no division by 0. If the ratio r(σi) is less than 1, then Γ[i] is updated with the value 1− r(σi) otherwise the value of Γ[i] remains 0. After the m iterations, Teq sums up the values in the array Γ. If the sum is found to be less than threshold m(ε+ γ), Teq returns Accept and otherwise returns Reject.
The following theorem asserts the correctness of Teq. Theorem 1. Given two satisfiable probabilistic circuits ϕ1, ϕ2 and weight functions w1, w2, along with parameters ε < η < 1 and δ < 1,
A. If dTV (P (ϕ1, w1), P (ϕ2, w2)) ≤ ε, then Teq(ϕ1, w1, ϕ2, w2, ε, η, δ) returns Accept with probability at least (1− δ).
B. If dTV (P (ϕ1, w1), P (ϕ2, w2)) ≥ η, then Teq(ϕ1, w1, ϕ2, w2, ε, η, δ) returns Reject with probability at least (1− δ).
The following theorem states the running time of the algorithm, Theorem 2. Let γ = η − ε, then the time complexity of Teq is in O ( TAwct(γ, δ,max(|ϕ1|, |ϕ2|)) + TSamp(γ, δ,max(|ϕ1|, |ϕ2|)) log(δ −1) γ2 ) . If the underlying
Algorithm 1 Teq(ϕ1, w1, ϕ2, w2, ε, η, δ) 1: γ ← (η − ε)/2 2: m← d2 log(4/δ)/γ2e 3: Γ← [0] ∗m 4: k1 ← Awct( √ 1 + γ/4− 1, δ/8, ϕ1, w1)
5: k2 ← Awct( √
1 + γ/4− 1, δ/8, ϕ2, w2) 6: for i ∈ {1, 2 . . . ,m} do 7: σi ← Samp(γ/(4η − 2γ), δ/4m,ϕ1, w1) 8: if σi 6=⊥ then 9: s1 ← w1(σi), s2 ← w2(σi)
10: r(σi)← s2k2 · k1 s1 11: if r(σi) < 1 then 12: Γ[i]← 1− r(σi) 13: if ∑ i∈[m] Γ[i] ≤ m(ε+ γ) then 14: Return Accept 15: else 16: Return Reject
PCs support approximate counting and sampling in polynomial time, then the running time of Teq is also polynomial in terms of γ, log(δ−1) and max(|ϕ1|, |ϕ2|).
To improve readability, we use P1 to refer to the distribution P (ϕ1, w1) and P2 to refer to P (ϕ2, w2).
3.1 Proving the correctness of Teq
In this subsection, we present the theoretical analysis of Teq, and the proof of Theorem 1(A). We will defer the proofs of Theorem 1(B) and Theorem 2 to the supplementary Section A.4.2 and Section A.4.3, respectively.
For the purpose of the proof, we will first define events Pass1, Pass2 and Good. Events Pass1, Pass2 are defined w.r.t. the function calls Awct( √ 1 + γ/4 − 1, δ/8, ϕ1, w1) and Awct( √ 1 + γ/4 − 1, δ/8, ϕ2, w2), respectively (as on lines 4, 5 of Algorithm 1). Pass1 and Pass2 represent the events that the two calls correctly return √ 1 + γ/4 approximations of the weighted model counts
of ϕ1 and ϕ2 i.e. w1(ϕ1)√ 1+γ/4
≤ Awct( √ 1 + γ/4 − 1, δ/8, ϕ1, w1) ≤ ( √
1 + γ/4)w1(ϕ1), and w2(ϕ2)√ 1+γ/4 ≤ Awct( √ 1 + γ/4− 1, δ/8, ϕ2, w2) ≤ ( √ 1 + γ/4)w2(ϕ2). From the definition of Awct, we have Pr[Pass1],Pr[Pass2] ≥ 1− δ/8. Let Faili denote the event that Samp (Algorithm 1, line 7) returns the symbol ⊥ in the ith iteration of the loop. By the definition of Samp we know that ∀i∈[m] Pr[Faili] < δ/4m. The analysis of Teq requires that all m Samp calls and both Awct calls return correctly. We denote this super-event as Good = ⋂ i∈[m] Faili ∩ Pass1 ∩ Pass2. Applying the union bound we see that the probability of all calls to Awct and Samp returning without error is at least 1− δ/2:
Pr[Good] = 1− Pr[ ⋃ i∈[m] Faili ∪ Pass1 ∪ Pass2] ≥ 1−m · δ/4m− 2 · δ/8 = 1− δ/2 (1)
We will now state a lemma, which we will prove in the supplementary Section A.4. Lemma 1. Good→ ∣∣∣r(σ)− P2(σ)P1(σ) ∣∣∣ ≤ γ/4 · P2(σ)P1(σ)
We now prove the lemma critical for our proof of correctness of Teq. Lemma 2. Assuming the event Good, let A = ∑ σ∈{0,1}n 1 (r(σ) < 1) (1− r(σ))P1(σ) , then
1. If dTV (P1, P2) ≤ ε , then A ≤ ε+ γ/4
2. If dTV (P1, P2) ≥ η , then A ≥ η − γ/4
Proof. If ∑ x (P1(x)− P2(x)) = 0, then 1 2 ∑ x |P1(x)−P2(x)| = ∑ x:P1(x)−P2(x)>0 (P1(x)−P2(x)). Using this fact we see that,
dTV (P1, P2) = ∑
σ:P2(σ)<P1(σ)
P1(σ)− P2(σ) = ∑
σ: P2(σ)
P1(σ) <1
( 1− P2(σ)
P1(σ)
) P1(σ)
= ∑
σ∈{0,1}n 1
( P2(σ)
P1(σ) < 1
)( 1− P2(σ)
P1(σ)
) P1(σ)
= A+ ∑
σ∈{0,1}n 1
( P2(σ)
P1(σ) < 1
)( 1− P2(σ)
P1(σ) ) P1(σ)−A︸ ︷︷ ︸
B
Thus we have that dTV (P1, P2)− A = B. We now divide the set of assignments σ ∈ {0, 1}n into three disjoint partition S1, S2 and S3 as following: S1 = {σ : 1(P2(σ)P1(σ) < 1) = 1(r(σ) < 1)}; S2 = {σ : 1(P2(σ)P1(σ) < 1) > 1(r(σ) < 1)}; S3 = {σ : 1( P2(σ) P1(σ)
< 1) < 1(r(σ) < 1)}. The definition implies that the indicator 1(r(σ) < 1) is 0 for all assignments in the set S2, and is 1 for all assignments in S3. Similarly 1(
P2(σ) P1(σ) < 1) takes value 1 and 0 for all elements in S2 and S3, respectively.
Now we bound the magnitude of B,
|B| = ∣∣∣∣∣∣ ∑
σ∈{0,1}n
[( 1− P2(σ)
P1(σ)
) 1 ( P2(σ)
P1(σ) < 1
) − (1− r(σ))1 (r(σ) < 1) ] P1(σ) ∣∣∣∣∣∣ For bj > 0, we have that | ∑ j ajbj | ≤ ∑ j |aj |bj , and thus:
|B| ≤ ∑
σ∈{0,1}n
∣∣∣∣[(1− P2(σ)P1(σ) ) 1 ( P2(σ) P1(σ) < 1 ) − (1− r(σ))1 (r(σ) < 1) ]∣∣∣∣P1(σ) We can split the summation into three terms based on the sets in which the assignments lie. Some summands take the value 0 in a particular set, so we don’t include them in the term.
|B| ≤ ∑ σ∈S1 1 ( P2(σ) P1(σ) < 1 ) ∣∣∣∣r(σ)− P2(σ)P1(σ) ∣∣∣∣P1(σ) + ∑ σ∈S2 1 ( P2(σ) P1(σ) < 1 )( 1− P2(σ) P1(σ) ) P1(σ)
+ ∑ σ∈S3 1 (r(σ) < 1) (1− r(σ))P1(σ)
Since we know that ∀σ ∈ S2, r(σ) > 1 and ∀σ ∈ S3, P2(σ)P1(σ) > 1, we can alter the second and third terms of the inequality in the following way:
|B| ≤ ∑ σ∈S1 1 ( P2(σ) P1(σ) < 1 ) ∣∣∣∣r(σ)− P2(σ)P1(σ) ∣∣∣∣P1(σ) + ∑ σ∈S2 1 ( P2(σ) P1(σ) < 1 ) ∣∣∣∣r(σ)− P2(σ)P1(σ) ∣∣∣∣P1(σ)
+ ∑ σ∈S3 1 (r(σ) < 1) ∣∣∣∣P2(σ)P1(σ) − r(σ) ∣∣∣∣P1(σ) ≤ ∑ σ∈S1∪S2∪S3 ∣∣∣∣r(σ)− P2(σ)P1(σ) ∣∣∣∣P1(σ)
Using our assumption of the event Good and Lemma 1, |B| ≤ ∑ σ∈{0,1}n γ/4 · P1(σ) ≤ γ/4 Since dTV (P1, P2) − A = B, we get |dTV (P1, P2) − A| ≤ γ/4. We can now deduce that if dTV (P1, P2) ≤ ε, then A ≤ ε+ γ/4 and if dTV (P1, P2) ≥ η, then A ≥ η − γ/4.
Using Teq to test PCs in general. Exact weighted model counting(WMC) is a commonly supported query on PCs. In the language of PC queries, a WMC query is known as the marginal (MAR) query. Conditional inference (CON) is another well studied PC query. Using CON and MAR, one can sample from the distribution encoded by a given PC. It is known that if a PC has the structural properties of smoothness and decomposability, then the CON and MAR queries can be computed tractably. For the definitions of the above terms and further details, please refer to the survey [9].

heading: 4 Evaluation
text: To evaluate the performance of Teq, we implemented a prototype in Python. The prototype uses WAPS3 [17] as a weighted sampler to sample over the input d-DNNF circuits. The primary objective of our experimental evaluation was to seek an answer to the following question: Is Teq able to determine the closeness of a pair of probabilistic circuits by returning Accept if the circuits are ε-close and Reject if they are η-far? We test our tool Teq in the following two settings:
A. The pair of PCs represent small randomly generated circuits and weight functions. B. The pair of PCs are from the set of publicly available benchmarks arising from sampling
and counting tasks.
Our experiments were conducted on a high performance compute cluster with Intel Xeon(R) E5-2690 v3@2.60GHz CPU cores. For each benchmark, we use a single core with a timeout of 7200 seconds.

heading: 4.1 Setting A - Synthetic benchmarks
text: Dataset Our dataset for experiments conducted in setting A consisted of randomly generated 3- CNFs and with random literal weights. Our dataset consisted of 3-CNFs with {14, 15, 16, 17, 18} variables. Since the circuits are small, we validate the results by computing the actual total variation distance using brute-force.
Results Our tests terminated with the correct result in less than 10 seconds on all the randomly generated PCs we experimented with. We present the empirical results in Table 1. The first column indicates the benchmark’s name, the second and third indicate the parameters ε and η on which we executed Teq. The fourth column indicates the actual dTV distance between the two benchmark PCs. The fifth column indicates the output of Teq, and the sixth indicates the expected result. The full detailed results are presented in the appendix Section B.

heading: 4.2 Setting B - Real-world benchmarks
text: Dataset We conducted experiments on a range of publicly available benchmarks arising from sampling and counting tasks4. Our dataset contained 100 d-DNNF circuits with weights. We have assigned random weights to literals wherever weights were not readily available. For the empirical evaluation of Teq, we needed pairs of weighted d-DNNFs with known dTV distance. To generate such a dataset, we first chose a circuit and a weight function, and then we synthesized new weight functions using the technique of one variable perturbation, described in the appendix Section B.1.
3https://github.com/meelgroup/WAPS 4https://zenodo.org/record/3793090
Results We set the closeness parameter ε, farness parameter η and confidence δ for Teq to be 0.01, 0.2 and 0.01, respectively. The chosen parameters imply that if the input pair of probabilistic circuits are ≤ 0.01 close in dTV , then Teq returns Accept with probability atleast 0.99, otherwise if the circuits are ≥ 0.2 far in dTV , the algorithm returns Reject with probability at least 0.99. The number of samples required for Teq (indicated by the variablem as on line 2 of Algorithm 1) depends only on ε, η, δ and for the values we have chosen, we find that we require m = 294 samples.
Our tests terminated with the correct result in less than 3600 seconds on all the PCs we experimented with. We present the empirical results in Table 2. The first column indicates the benchmark’s name, the second and third indicate the result and runtime of Teq when presented with a pair of ε-close PCs as input. Similarly, the fourth and fifth columns indicate the result and observed runtime of Teq when the input PCs are η-far . The full set of results are presented in the supplementary Section B.

heading: 5 A characterization of the complexity of testing
text: In this section, we characterize PCs according to the complexity of closeness and equivalence testing. We present the characterization in Table 3. The results presented in the table can be separated into (1) hardness results, and (2) upper bounds. The hardness results, presented in Section 5.2, are largely derived from known complexity-theoretic results. The upper bounds, presented in Section 5.1, are derived from a combination of established results, our algorithm Teq and the exact equivalence test of Darwiche and Huang [13](presented in supplementary Section A.1 for completeness).

heading: 5.1 Upper bounds
text: In Table 3 we label the pair of classes of PCs that admit a poly-time closeness and equivalence test with green symbols C and E respectively. Darwiche and Huang [13] provided an equivalence test for d-DNNF s. From Theorem 1, we know that PCs that supports the Awct and Samp queries in poly-time must also admit a poly-time approximate equivalence test. A weighted model counting algorithms for d-DNNFs was first provided by Darwiche [11], and a weighted sampler was provided by [17]. Arenas et al. [1] provided the first approximate counting and uniform sampling algorithm for SDNNFs. Using the following lemma, we show that with the use of chain formulas, the uniform sampling and counting algorithms extend to log-linear SDNNF distributions as well. Lemma 3. Given a SDNNF formula ϕ (with a v-tree T ), and a weight function w, Samp(ϕ, w) requires polynomial time in the size of ϕ.
The proof is provided in the supplementary Section A.5.

heading: 5.2 Hardness
text: In Table 3, we claim that the pairs of classes of PCs labeled with symbols C and E , cannot be tested in poly-time for closeness equivalence, respectively. Our claim assumes that the polynomial hierarchy (PH) does not collapse. To prove the hardness of testing the labeled pairs, we combine previously known facts about PCs and a few new arguments. Summarizing for brevity,
• We start off by observing that PC families are in a hierarchy, with CNF ⊆ NNF and DNF ⊆ SDNNF ⊆ DNNF [14].
• We then reduce the problem of satisfiability testing of CNFs (NP-hard) and validity testing of DNFs (co-NP-hard) into the problem of equivalence and closeness testing of PCs, in Propositions 1, 2 and 3. These propositions and their proofs can be found in the supplementary Section A.5.
• We then connect the existence of poly-time algorithms for equivalence to the collapse of PH via a complexity result due to Karp and Lipton [18].
The NP-hardness of deciding the equivalence of pairs of DNNFs and pairs of SDNNFs was first shown by Pipatsrisawat and Darwiche [28]. We recast their proofs in the language of distribution testing for the sake of completeness in the supplementary Section A.5.

heading: 6 Conclusion and future work
text: In this paper, we studied the problem of closeness testing of PCs. Before our work, poly-time algorithms were known only for the special case of equivalence testing of PCs; and, no poly-time closeness test was known for any PC. We provided the first such test, called Teq, that used ideas from the field of distribution testing to design a novel algorithm for testing the closeness of PCs. We then implemented a prototype for Teq, and tested it on publicly available benchmarks to determine the runtime performance. Experimental results demonstrate the effectiveness of Teq in practice.
We also characterized PCs with respect to the complexity of deciding equivalence and closeness. We combined known hardness results, reductions, and our proposed algorithm Teq to classify pairs of PCs according to closeness and equivalence testing complexity. Since the characterization is incomplete, as seen in Table 3, there are questions left open regarding the existence of tests for certain PCs, which we leave for future work.
Broader Impact
Recent advances in probabilistic modeling techniques have led to increased adoption of the said techniques in safety-critical domains, thus creating a need for appropriate verification and testing methodologies. This paper seeks to take a step in this direction and focuses on testing properties of probabilistic models likely to find use in safety-critical domains. Since our guarantees are probabilistic, practical adoption of such techniques still requires careful design to handle failures.
Acknowledgments and Disclosure of Funding
We are grateful to the anonymous reviewers of UAI 2021 and NeurIPS 2021 for their constructive feedback that greatly improved the paper. We would also like to thank Suwei Yang and Lawqueen Kanesh for their useful comments on the earlier drafts of the paper. This work was supported in part by National Research Foundation Singapore under its NRF Fellowship Programme[NRFNRFFAI1-2019-0004 ] and AI Singapore Programme [AISG-RP-2018-005], and NUS ODPRT Grant [R-252-000-685-13]. The computational work for this article was performed on resources of the National Supercomputing Centre, Singapore (https://www.nscc.sg).

Review summaries:
This paper presents a statistical closeness test for evaluating whether the total variation distance between the probability distributions encoded by two circuits is below a lower threshold or above an upper threshold with a given confidence in polynomial time. The authors introduce the setting, present the algorithm and give a sample of the analysis by proving parts of the main result. The results are evaluated on public datasets.

The contribution of this paper is a method for testing the closeness of the probability distributions encoded by two different probabalistic circuits (PCs). The closeness tester (called Teq), assumes access to an approximate weighted counter and an approximate weighted sampler. Teq is described (in words and pseudo-code) and the bulk of the paper is devoted to proving (PAC-style) correctness of Teq (ie Theorem 1) and characterising its time complexity (Theorem 2). Empirical results are given supporting the correctness of Teq and the stated time complexity theoretical results on Teq.