Characteristic Circuits
Authors: Zhongjie Yu
Martin Trapp
Kristian Kersting
Venue: NeurIPS 2023 oral (2023)
Keywords: Characteristic Circuit
Characteristic Function
Probabilistic Circuit
Heterogeneous Data
Density Estimation
TL;DR: Characteristic circuit is a deep probabilistic model over characteristic functions that enables a unified view for discrete and continuous random variables and allows to learn distributions that do not have closed form expressions for their density.

Abstract: In many real-world scenarios it is crucial to be able to reliably and efficiently reason under uncertainty while capturing complex relationships in data.
  Probabilistic circuits (PCs), a prominent family of tractable probabilistic models, offer a remedy to this challenge by composing simple, tractable distributions into a high-dimensional probability distribution. 
  However, learning PCs on heterogeneous data is challenging and densities of some parametric distributions are not available in closed form, limiting their potential use. 
  We introduce characteristic circuits (CCs), a family of tractable probabilistic models providing a unified formalization of distributions over heterogeneous data in the spectral domain.
  The one-to-one relationship between characteristic functions and probability measures enables us to learn high-dimensional distributions on heterogeneous data domains and facilitates efficient probabilistic inference even when no closed-form density function is available. 
  We show that the structure and parameters of CCs can be learned efficiently from the data and find that CCs outperform state-of-the-art density estimators for heterogeneous data domains on common benchmark data sets.

Characteristic Circuits
Zhongjie Yu TU Darmstadt
Martin Trapp Aalto University Espoo, Finland
Kristian Kersting
TU Darnstadd/Hesiann//DD AI/DFFI Darmstadt, Germany
Darmstadt, Germany
kesttnng htw.rriinnnnss.tt.treaeaaaeeeeee tu-darmstadt.do de, martin. to
Abstract
In many real-world scenarios, it is crucial to be able to reliably and efficiently reason under uncertainty while capturing complex relationships data. Proba- bilistic circuits (PCs), prominent family of tractable probabilistic models, offer remedy this challenge by composing simple, tractable distributions into a high- dimensional probability distribution. However, learning PCs on heterogeneous data is challenging and densities some parametric distributions are not available in closed form, limiting their potential use. We introduce characteristic circuits (CCs), a family of tractable probabilistic models providing unified formalization of distributions over heterogeneous data in the spectral domain. The one-to-one relationship between characteristic functions and probability measures enables to learn high- ligh-dimensional distributions facilitates efficient probabilistic inference even when no closed-form density func- tion is available. We show that the structure and parameters of CCs be learned efficiently from the data and find that CCs outperform state-of-the- art density estimators for heterogeneous data domains common benchmark data sets.
heterogencous data domains and
Introduction
Probabilistic circuits (PCs [Choi et al., 2020]) have gained increasing attention in the machine learning community as promising modelling family that ders many probabilistic inferences tractable with lit- tle compromise their expressivity. Their beneficial properties have prompted many successful applica- tions in density estimation [e.g., Peharz et al., 2020, Di Mauro et al., 2021, Dang et al., 2022, Correia et al., 2023] and in areas where probabilistic reasoning key, for example, neuro-symbolic reasoning [Ahmed al., 2022], certified fairness [Selvam et al., 2023], or causality [Zečević et al., 2021]. Moreover, re- cent works have explored ways of specifying PCs for more complex modelling scenarios, such time ries [Trapp et al., 2020, Yu et al., 2021b,a] or tractable representation of graphs [Wang et al., 2022].
churacteristic circuits
CF ip
mensures
unique relationship
integration
continuous dists.
discrete dists.
intractable
prulubilistic circuits
Figure 1: Characteristic circuits provide unified, tractable specification of joint contin- uous and discrete distributions in the spectral domain of probability measures.
However, while density estimation is at the very core of many machine learning techniques (e.g., approx- imate Bayesian inference [Murphy, 2012]) and fun- damental tool in statistics to identify characteristics of the data such 4tth order moments or multimodality [Silverman, 2018], even case of parametric families, densities are sometimes
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

not available in closed-form. For example, only special cases of a-stable distributions provide closed-form densities [Nolan, 2013]. Fortunately, there exists a one-to-one correspondence between probability measures and characteristic functions [Sasvári, 2013], which can be understood as the Courier-Stieltjes transform of the probability measures, enabling the characterisation of any probabil- ity measure through its characteristic function. Henceforth, the characteristic function of probability measures has found wide applicability in statistics, ranging from its use as a non- par-aaarameicc estimator through the empirical characteristic function [Feuerverger and Mureika, 1977] to estimate heavy- tailed data, e.g., through the family of a-stable distributions [Nolan, 2013]. However, even though the characteristic function has many beneficial properties, its application to encode nigh-dimensional data distributions and efficient computation of densities can be quite challenging [Nolan, 2013].
In this work, we bridge between the characteristic function of probability measures and PCs. We do so by examining PCs from a more general perspective, similar in spirit to their specifications as a summation over functions on commutative semiring [Friesen and Domingos, 2016] or as a convex combination of product measures on product probability spaces [Trapp et al., 2020]. Instead of defining the circuit over density functions, we propose to form the circuit over the characteristic function of the respective probability measures, illustrated in Fig. 1. The resulting characteristic circuits (CCs) are related to recent works, which define a circuit over probability generating polynomials to represent discrete probability distributions [Zhang et al., 2021], in that both approaches can be understood as transformation methods. The benefits of using the spectral domain are manifold: (i) characteristic functions as the base enable a unified view for discrete and continuous random variables, (ii) directly representing the characteristic function allows learning distributions that do not have closed-form expressions for their density, and (iii) the moment can be obtained efficiently by differentiating the circuit. When modelling heterogeneous data, standard PCs do not naturally lend themselves to a unified view of mixed data but treat discrete and continuous random variables (RVs) conceptually differently. The difference arises as PCs model heterogeneous data domains after integration w.r.t. the base measure which, in the case of mixed domains, differs between discrete and continuous RVs. RVs distributed according to a singular distribution can typically not be represented in PCs at all. This dependence on the base measure is subtly embedded within PCs, resulting in challenges when it comes to learning these models in heterogeneous domains. In contrast, CCs provide unified view compared to PCs by moving away from the dependence on the base measure, achieved by representing the distribution through its characteristic function, which is independent of the base measure.
In summary, contributions are: (1) We propose characteristic circuits, a novel deep probabilistic model class representing the joint of discrete and continuous random variables through a unifying view in the spectral domain. (2) We show that characteristic circuits retain the tractability of PCs despite the change of domain and enable efficient computation of densities, marginals, and conditionals. (3) We derive parameter and structure learning for characteristic circuits and find that characteristic circuits outperform SOTA density estimators in the majority of tested benchmarks.
We proceed follows. We start by discussing related work and review preliminaries on probabilistic circuits and characteristic functions. Consequently, we define our model characteristic circuits, discuss theoretical properties, and show how to learn the circuits' parameters and structure. We conclude by presenting an empirical evaluation and discussion of the new model class.
2 Related Work
Characteristic functions (CFs) were originally proposed as tool in the study of limit theorems and afterwards developed with independent mathematical interest [Lukacs, 1972]. The uniqueness between CFs and probability measures is recovered with Lévy's inversion theorem [Sasvári, 2013). A popular application of the CF is in statistical tests [e.g.. Eriksson and Koivunen, 2003, Su and White, 2007, Wang and Hong, 2018, Ke and Yin, 2019]. In practice, the CF of distribution is in most cases not easy to estimate, and in turn, the empirical characteristic function (ECF) is employed as an approximation to the CF [Feuerverger and Mureika, 1977]. The ECF has been successfully applied in sequential data analysis tasks [Knight and Yu, 2002, Yu, 2004, Davis et al., 2021]. When handling high dimensional data, multivariate CFs, and ECFs were proposed for modelling e.g. multivariate time series [Lee et al., 2022] and images [Ansaii et al., 2020]. Although a mass of work has been
Source code is available https: httpe:://ttttthhtteeee www/eoloeeeeeeeeeeeee hewaalrrreeerrchhaaaaaeeeee aww.aaacca/taaccttterseticteeeee

---

developed for the applications of CF, less attention has been paid to estimating the model quality of CF itself. Therefore, modelling the multivariate CF remains be challenging.
Probabilistic circuits (PCs) are a unifying framework for tractable probabilistic models [Choi et al., 2020] that recently show their power in e-g- probabilistic density estimation [Dang al., 2020, Di Mauro et al., 2021, Zhang et al., 2021], flexible inference [Shao et al., 2022], variational inference [Shih and Ermon, 2020], and sample generating [Peharz et al., 2020J. When it comes to data containing both discrete and continuous values, mixture of discrete and continuous random variables is employed in PCs. Molina al. [2018] propose to model mixed data based on the Hum-Product Network (SPN) structure, casting the randomized dependency coefficient [Lopez-Pazz al., 2013] for independence test for hybrid domains and piece-wise polynomial as leaf distributions. resulting in Mixed uun-Product Networks (MSPN). Furthermore, statistical data type and likelihood discovery have been made available with Automatic Bayesian Density Analysis (ABDA) [Vergari et al., 2019], which is a suitable tool for the analysis of mixed discrete and continuous tabular data. Moreover, Bayesian SPNs [Trapp et al., 2019] use well eeil-prieeepeed Bayesian framework for SPN structure learning, achieving competitive results in density estimation on heterogeneous data sets. The above-mentioned models try to handle the probability measure with either parametric density/mass functions or histograms, but yet could not offer unified view of heterogeneous data. PCs will also fail to model leaves with distributions that do not have closed-form density expressions.
3 Preliminaries on Probabilistic Circuits and Characteristic Functions
Before introducing characteristic circuits, we recap probabilistic circuits and characteristic functions.
3.1 Probabilistic Circuits (PCs)
PCs are tractable probabilistic models, structured as rooted directed acyclic graphs, where each leaf node represents probability distribution over univariate RV, each sum node models a mixture of its children, and each product node P models a product distribution (assuming independence) of their children. A PC over a set of RVs X can viewed as a computational graph 9 representing a tractable probability distribution over X, and the value obtained at the root node is the probability computed by the circuit. We refer to Choi et al. [2020] for more details.
Each node in G is associated with a subset of X called the scope of a node N and is denoted as (N). The scope of an inner node is the union of the scope of its children. Sum nodes compute weighted sum of their children S = Eeech(S) W, and product nodes compute the product of their children P [NEch(P) N, where ch(-) denotes the children of node. The weights ws, N generally assumed to be neg-negative and normalized (sum up one) each sum node. We also assume the PC to be smooth (complete) and decomposable [Darwiche, 2003], where smooth requires all children of sum node having the same scope, and decomposable means all children of product node having pairwise disjoint scopes.
3.2 Characteristic Functions (CFs)
Characteristic functions provide unified view for discrete and continuous random variables through the Fourier-Stieltjes transform of their probability measures. Let X be a d-dimensional random vector, the CF of X for t E Iad is given as:
x (t) = Elexp(it T X = JEERS exp(it x) pxxx)))
(1)
where μх the distribution/probabllty measure of X. CFs have certain useful properties. We will briefly review those that are relevant for the remaining discussion: (i) x0xxx0) = and I (t) [ < 1; (ii) for any two RVs X1, X2, both have the same distribution iff yx, xx (iii) if X has moments, then xpx is k-times differentiable; and (iv) two RVs X1, X2 are independent iff Xx,, (s. x, (s)xx, (t). We refer to Sasvári [2013] for more detailed discussion of CFs and their properties.
Theorem 3.1 (Lévy's ss inversion theorem [Sasvári, 2013]). Let X be real-valued random variable, μx its probability measure, and x IR + C its characteristic function. Then for any a, b R.
3

---

< b, we have that
T exp(-ita) - exp( -itb) lim T-200 2x J-T
ux + (1x +x((6)
(2)
il
and, hence, xx uniquely determines pxx-
Corollary. J2 (xx((t)dtt oc, then X has continuous probability density function fo given by
fx(x) 2 exp((itz))px(()dl
Note that not every probability measure admits analytical solution Eq. (3), e-g-, only special cases of the family of o-stable distributions have a closed-form density function [Nolan, 2013], and numerical integration might be needed.
Empirical Characteristic Function (ECF). In many cases, parametric form of the data distribution is not available and one needs to use non-parametric estimator. The ECF [Feuerverger and Mureika, 1977, Cramér, 1999] an unbiased and consistent non-paramen non-parametric estimator the population characteristic function. Given data { 1 the ECF is given
(t)
Σ exp(it" az).
Evaluation Metric. To measure the distance between two distributions represented by their char- acteristic functions, the squared characteristic function distance (CFD) can be employed. The CFD between two distributions P and Q is defined as:
/ ((t(())) ((t nt:
CFD (I,, Q
(5)
where w(t; is weighting function parameterized by and guarantees the integral in Eq. (5) converge. When ((t; 7) is probability density function, Eq. (5) can be rewritten as:
CFD (P. (tmw((tn))
[1pp(t) - (lox(t)))((t)?]
Actually, using the uniqueness theorem of CFs, we have CFD,, (IP, Q) O IP = Q [Sriperumbudur al., 2010]. Computing Eq. (6) is generally intractable, therefore, we use Monte-Carlo integration to approximate the expectation, resulting in CFD (I, Q) Σッ lgg - (t, where
nt; We refer to Ansari et al. [2020] for a detailed discussion.
Characteristic Circuits
Now we have everything hand to introduce characteristic circuits. We first give recursive definition of CC, followed by devising each type of node in CC. We then show CCs feature efficient computation of densities, and the end, introduce how to learn a CC from data.
Definition 4.1 (Characteristic Cireuit). Let X {XI,..., Xa) be set of random variables. A characteristic circuit denoted as C is a tuple consisting of a rooted directed acyclic graph G, scope function vo V(G) P(X). parameterized by set of graph parameters 0g. Nodes in G are either sum (S), product (P), or leaf (L) nodes. With this, characteristic circuit is defined recursively as follows:
1. a characteristic funcettoo for a scalar random variable is a characteristc circuit.
2. a product of characteristic circuits a characteristic circuit.
3. a convex combination of characteristic circuits is a characteristic circuit.
Let us now provide some more details. To this end, we denote with (t) the output of C computed the root of C, which represents the estimation of characteristic function given argument of the characteristic function & E Rdd, Further, we denote the number of RVs s in the scope of N PN

---

[u( and use (t) for the characteristic function of node. Throughout the paper, we assume the CC to be smooth and decomposable.
Product Nodes. A product node in a CC encodes the independence of its children. Let X and Y be two RVs. Following property (iv) of characteristic functions, the characteristic function of X, Y is given as (t,,y(t,s) s) x (t) (s). if and only if X and Y are independent. Therefore, by definition, the characteristic function of product nodes is given as:
(p)(1) = II INNCChPp (P
where UNEch(PP) (N()).
Sum Nodes. sum node in a CC encodes the mixture of children. Let the parameters be given as _NEck(S) WS,N 1 and ws,N 2 0, VS, N. Then the sum node in CC is given as: (ts(t)
f exp(it x)) |E Wss. AN "N (dz)) JEERU
-E
NEch(S)
WS.N
exp(it" ax) (N(()). (8)
WERPS
(t)
Leaf Nodes. A leaf node of CC models the characteristic function of a univariate RV. To handle various data types, we propose the following variants of leaf nodes.
ECF leaf. The most straightforward way for modelling the leaf node is to directly employ the empirical characteristic function for the local data at each leaf, defined as PPac (t) 1. > 2===1 (xp(itxx)) where n is the number of instances at the leaf L, and v is the jth instance. The ECF leaf is non-parametric and is determined by the instances I, the leaf.
Parametric leaf for continuous RVs. Motivated by existing SPN literature, we can assume that the RV at leaf node follows parametric continuous distribution egg. normal distribution. With this, the leaf node is equipped with the CF of normal distribution @L (t) exp(it 2 2))2)) where parameters fa and 6² are the mean and variance.
Parametric leaf for discrete RVs. For discrete RVs, if it is assumed to follow categorical distribution (P(X j) p2); then the CF at the leaf node can be defined LL (1) = Eiexp(i
Σj= P3 exp(itj). Other discrete distributions which are widely used in probabilistic circuits can also be employed as leaf nodes in CCs, e.g., Bernoulli, Poisson, and geometric distributions.
a-stable leaf. In the
of financial data data distributed with heavy tails, the a-stable distribution is frequently employed. a-stable distributions are more flexible in modelling e.g. data with skewed centered distributions. The characteristic function of a-stable distribu- tion is PL.-aant (1) = exp(il |ol| (1 - iB))n(()))), where sgn(() takes the sign of L and a 1 The parameters in a-stable distributions are the stability parame- ter a, the skewness parameter 8, the scale parameter c, and the location parameter μ.. Despite its modelling power, a-stable distribution is never employed in PCs, as it is represented analytically by its CF and in most cases does not have closed-form probability density function.
+ ( taan(Ta/2 (Ta/2) a
a
1-22/T log |t]
4.1 Theoretic Properties of Characteristic Circuits
With the CC defined above, we can now derive the densities, marginals, and moments from it.
4.1.1 Efficient computation of densities
Through their recursive nature, CCs enable efficient computation of densities in high-dimensional settings even if the density function not available in closed form. For this, we present an extension of Theorem 3.1 for CCs, formulated using the notion of induced trees T [Zhao et al., 2016]. A detailed definition of induced trees can be found in Appendix A.2.
Lemma 4.2 (Inversion). Let C = (G, 0g) be a characteristic circuit on RVs X = {X,] with univariate leave nodes. If (t)(d)
for every L V(G), then X has continuous
5

---

probability density function fa given by fx(
II WSSN II
exp(-itzr(())yLL dt,
(2T)²
(S.N)EE(T)) LEV(T)) B
and can be computed efficiently through analytic or numerical integration at the leaves.
Proof. Let C = (G, v. 0o) be characteristic circuit on RVs X = {X,}}=1 with univariate leave nodes and pN the number of RVs in the scope of N. In order to calculate the density function of need to integrate over the d-dimensional real space R2 iee.
fx(x)) (2T)a
exp(-it' x)) spe pc (t) Xa(de),
(10)
LER
fc())
where (t) denotes the CF defined by the root of the characteristic circuit and A is the Lebesque measure on (RR,, ((RR)). We can examine the computation of Eq. (10) recursively for every node.
Leaf Nodes. If N is leaf node L, we obtain fN(-) by calculating:
(x) 2 (xx)) / exp(-itz))xx(1)ml
(11)
which follows from Theorem 3.1.
Sum Nodes. If N is sum node S, then:
fs(x) exxp(-it x) ps()) Ap(dt) YEER
Σ
WSS.N
exp(-itt x)) (PN(() (dl).
(12)
TERSS
NEch(S)
fu(2))
Therefore, computing the inverse for S reduces to inversion at its children.
Product Nodes. a product node P, then:
fo(x) f eexp(-it) x)) (t((t) App (dt)
II
exp(-ix
-iis p(o(N)) (P((s) Apm (ds), (13)
JEER"
AERRN
NEch(P)
=fu(
where we used that Ape = @Nech(P) Apu is a product measure on a product space, applied Fubini's theorem [Fubini, 1907], and used the additivity property of exponential functions. Consequently, computing the inverse for reduces to inversion at its children.
Through the recursive application of Eq. (12) and Eq. (13), we obtain that Eq. (10) reduces to integration at the leaves and, therefore, can be solved either analytically or efficiently through one-dimensional numerical integration.
4.1.2 Efficient computation of marginals
Similar PCs over distribution functions, CCs allow efficient computation of arbitrary marginals. Given a CC on RVs Z X U Y, we can obtain the marginal CC of X as follows. Let n [X], m Yl and let the characteristic function of the circuit be given by
f)+m) = / exp(it" z)us(dz),
tn tn pe
(14)
*ERn+m
where μul denotes the distribution of the root. Then the marginal CC X given by setting L S + m. The proof of marginal computation is provided in Appendix B.

---

4.1.3 Efficiently computing moments via differentiation
Characteristic circuits also allow efficient computation of moments of distributions. Let & E N+ be such that the partial derivative efficiently through the derivative at the leaves
8dh aef---0t
exists, then the moment Mj exists and can be computed
M, = i- 8 PC())
d (P dt M(L)
dke
WSSN II II
(15)
Oth .....000 -. 61 1=00....
=va
1=1 (S.N)EB(T)) LEV(T))
detailed proof can be found in Appendix B.2.
4.2 Learning Characteristic Circuits from Data
To learn a characteristic circuit from data there are several options. The first option is parameter learning using random circuit structure. The random structure is initialized by recursively creating mixtures with random weights for sum nodes and randomly splitting the scopes for product nodes. leaf node is created with randomly initialized parameters when there is only one scope in node. Maximising the likelihood at the root of a CC requires one to apply the inversion theorem to the CC for each training data. When a leaf node does not have a closed-form density function, numerical integration could be used to obtain the density value given data, which makes the maximum likelihood estimation (MLE) at the root not guaranteed be tractable.
As discussed in prior works, see e.g. Yu [2004], minimising a distance function to the ECF is most related to moment-matoie matching approaches, but can result in more accurate fitting results. Therefore, minimising the CFD to the ECF can be beneficial if no tractable form of the likelihood exists but evaluating the characteristic function is tractable. In this case, instead of maximising the likelihood from CC, which is not guaranteed to be tractable, we take the ECF from data as an anchor and minimise the CFD between the CC and ECF:
Σ Σ
1=1 exp(it, x;) - vc((t)
(16)
Applying Sedrakyan's 's inequality [Sedrakyan, 1997] to Eq. (16), parameter learning can be operated batch-wise:
7hb
a exp(it]] mx) :pe(tt)
exp(it]] m:)) - sp((t) 2
78b
74b
where b is the number of batches and the batch size. This way, parameter learning of CC similar training neural network. Furthermore, two CCs are compatible, as similarly defined for PCs |Vergari et al., 2021], the CFD between the two CCs can be calculated analytically. see Appendix D for more details.
Algorithm CC Structure Learning
Variables
Inpul: truining data D. RV. X, m. Ag. kp
Outpot:
Function buildCF(D, X)
L return univeriate CF (t)
Function buildSunNode (D, X)
T Training data
if
then
5 buil (D, X)
else min_k
Partition D into X independent subscts Dy
$
| buildCF (D,, X,);
clse
Figure 2: Illustration of the recursive structure lcarning algorithm. Sum nodes are the result of clustering, having weighted children that are prod- uct nodes. Product nodes are the result of indepen- dence test, enforcing independence assumptions of their children. Leaf nodes are univariate char- acteristic functions modelling local data.
Partition into by clusters D.: Σ [P.
buildProdtiode (D,, X)
S
Function PdPrdddddad Partition D into Ap indopendent subscts D3 return 1 buildBunliode (D,, X,)
buildSunlidde X)
7

---

Table 1: Average test log-likelihoods from CC after parameter learning by minimising the CFD on synthetic data sets. The CC structure is either generated using Random Structure or learned using the Structure Learning algorithm.
Random Structure
Random Structure Parameter Learning
Structure Learning
Structure Learning & Parameter Learning
Structure Learning (random w)) & Parameter Learning
Data Set
MM
.4.93
-3.50 -4.12
-2.87 -3.27
-2.86 -3.27
-3.34
BN
-6.30
-3.93
However, relying on randomly initialized structures (e.g.. due to the fixed split of scopes) may also limit the performance of parameter learning of CC. To overcome this, we derive now a structure learning algorithm to learn the structure of the CC. Inspired by Gens and Domingos [2013], this structure learning recursively splits the data slice and creates sum and product nodes of the CC as summarized in Algorithm and depicted in Fig. 2. To create sum node S, clustering algorithms, e.g. K-means clustering, is employed to split data instances in the slice into kts subsets. The weights of the sum node are then determined by the portion of data instances in each subset. To create product node P. some independence tests eests-e.g., G-test of independence or random dependency coefficient (RDC) based splitting [Molina et al., 2018] are used to decide splitting the random variables in the data slice into hp sub- gub-group. The sum and product nodes are created recursively until any of the following conditions fulfils: (1) There is only one scope in the data slice, and then leaf node with the corresponding scope is created. (2) The number of data instances in the data slice is smaller than pre-defined threshold min_k. R. In the latter case, a naive factorization is applied to the scopes in the data slice to create a product node, and then create leaves for each scope as children for this product node. When creating leaf node, the leaf parameters are estimated by MLE if the closed-form density function is available. In the case of ECF leaves, the leaf nodes are created from local data following the definition of ECF Eq. (4). When there is no closed-form density at leaf, the parameters of an a-stable distribution are estimated using the algorithm in McCulloch [1986].
5 Experimental Evaluation
Our intention here is to evaluate the performance of characteristic circuit on synthetic data sets and UCI data sets, consisting of heterogeneous data. The likelihoods were computed based on the inversion theorem. For discrete and Gaus- sian leaves, the likelihoods were computed an- alytically. For a-stable leaves, the likelihoods were computed via numerical integration using the Gauss-Hermit quadrature of degree 50.
(0.3.
P(R2
(0.8.0.2)
Ps.
[1.0, oj
p(#s
0..9..11
0.3.
0.11..9
@
pis
I
p(as | (as,, ps)
10.98, 0.0g)
2
|0.55 0.96
p(=. Figure 3: The Bayesian network used for BN.
3.
Can characteristic circuits approximate known distributions well? We begin by de- scribing and evaluating the performance of CC on two synthetic data sets. The first data set consisted of data generated from a mixture of multivariate
distributions (denoted as MM): p(x) = Σ w,p(æ, I (4; of)p(x22 pt), where p(# μu, o²) is the univariate normal distribution with mean js and variance o², and p(æ: p) is the univariate categorical distribution with p the vector of probability of seeing each element. In our experiments we set K = and Wi- = 0.3, W2 = 0.7. For each univariate distribution we set μ4 = 0, of = 1, #12 = 5, oî = 1, Pi 0.6,, 0.4, 0.0] and P2- [0.1, 0.2, 0.7]. The second data set consisted of data generated from Bayesian network with 5 nodes (denoted as BN), to test the modelling power of characteristic circuits with more RVs and more complex correlations among each RV. The details of the BN are depicted in Fig. 3. Here, X,, X2, X3 and X; are binary random variables parameterized by p., and X, is a continuous random variable conditioned on X3. For both data sets MM and BN, 800 instances were generated for training and 800 for testing.
We first employed parameter learning and evaluated the log-likelihoods from the random structure and after parameter learning. detailed setting of parameter learning illustrated in Appendix C. The increase of log- likeeiisss after parameter learning (columns 2 and 3 in Table 1) implies that
8

---

-10-3
-10-2
8
1 argmax,
arg max,
CHD
CFD
0.5
2
0
+
5
22
4
log(n)
log(1))
Figure 4: Characteristic circuits approximate the true distributions better than the ECF by providing
smaller CFD. We visualize the CFD for CC with parametric leaves (CC-P =), ECF as leaves
(CC-E m). ). normal distribution as leaves (CC-N = and a single empirical characteristic function learned from synthetic heterogeneous data (Left: MM, Right: BN). Best viewed in color.
(ECF
minimising the CFD pushes CC to better approximate the true distribution of data. We then learnt CCs using structure learning with min_k k 100, and Kş kp 2. Various leaf types were evaluated: CC with ECF as leaves (CC-E), CC with normal distribution for continuous RVs and categorical distributions for discrete RVs, i.e., parametric leaves (CC-P), and CC with normal distribution for all leaf nodes (CC-N). The trained CCs were evaluated with the CFD between the CC and the ground truth CF. For data set BN, the ground truth CF was derived via the algorithm for generating arithmetic circuits that compute network polynomials [Darwiche, 2003]. Following Chwialkowski et al. [2015] and Ansari al. [2020], we illustrate both the CFD with varying scale r) in w(t: 7) and also optimising for the largest CFD, shown in Fig. 4. We report average CFD values and standard deviations obtained from five runs. It can be seen from Fig. 4 that both CC-E and CC-P have almost equally lower CFD values and also lower maximum CFD values compared to the ECF, which indicates the characteristic circuit structure better encodes the data distribution than the ECR The smaller standard deviation values from characteristic circuits compared with ECF also imply that characteristic circuits offer a more stable estimate of the characteristic function from data. For data set MM, the maximum CFD of CC-N is 0.0270 when log(o) 0.6735, which is far more than 0.0006 of CC-P, and thus not visualized in Fig. 4 (Left). This also happens to data set BN, as can be seen in Fig. 4 (Right) that CC-N gives higher CFD than CC-P and CC-E, which implies that assuming discrete RV as Normal distributed is not a suitable choice for CC. In addition, parameter learning on CCs from structure learning and structure learning with randomized parameters (last 2 columns in Table 1) provides higher log-likelihoods than random structures, which implies a well-initialized structure improves parameter learning. To conclude, CC estimates the data distribution better than ECF, which is justified by the smaller CFD from CC-E compared with ECF.
Can characteristic circuits be better density estimators heterogeneous data? Real-world tabular data usually contain both discrete and rallev elements, and thus are in most cases heterogeneous. Therefore, we also conducted density estimation experiments on real-world hetero- geneous data sets and compared to offte- probabilistic circuit methods, including Mixed SPNs (MSPN) [Molina al., 2018), Automatic Bayesian Density Analysis (ABDA) [Vergari et al., 2019] and Bayesian SPNs (BSPN) [Trapp et al., 2019]. We employed the heterogeneous data from the UCI data sets, see Molina et al. [2018] and Vergari al. [2019] for more details on the data sets. Similar to the setup in Trapp et al. [2019], a random variable was treated as categorical if less than 20 unique states of that RV were in the training set. All the rest RVs were modelled with either normal distributions (CC-P) or a-stable distributions (CC-A). Again, we first employed parameter learning with (fixed) random structure using a-stable distribution for continuous RVs and report the log- -ogliiklssoods (Parameter Learning in Table 2). Note that a-stable distributions can not be represented with closed-form densities, thus maximising the likelihood from can not be solved exactly and efficiently. As comparison, structure learning was also employed with min_k k = 100, for G-test based splitting (CC-P& & CC-A), and with min_k Ic 100, ks RDC based splitting (CC-ARDC), A detailed description of the experimental settings can be found in Appendix C.2. The test log-likelihoods are presented in Table 2. As one can see, parameter learning performs worse than CC-A but still outperforms some of the baselines. CC-P does not win on all the data sets but competitive with MSPN and ABDA on most of the data sets. CC-A outperforms the baselines on 8 out of 12 data sets, and CC-ARDC RDC outperforms all the other methods
kg kp
for

---

Table 2: Average test log- lieliiiks from CC and SOTA algorithms heterogeneous data.
Parameter Learning
Structure Learning
Data Set
MSPN
ABDA
BSPN
CC-P
CC-A
CC-A RTX.
Abalone
3.06
9.73
2.22
3.92
4.27
15.10
17.75
Adult
14.47
-4.077
-5.91
-4.62
-31.37
-7.76
-1.43
Australian
-5.59
-36.14
-16.44
-21.51
-30.29
-3.26
-2.94
Autism
-27.80
-39.20
-27.93
-0.47
-34.71
-17.52
-15.5
Breast
-20.39
-28.01
-25.48
-25.02
-54.75
-13.41
-12.66
Chess
-13.33
-13.01
-12.30
-11.54
-13.04
-13.04
-12.40
Crx
-6.82
-36.26
-12.82
-9933
-32.63
-4.72
-3.19
Dermatology
45,54
-27.71
-24.98
23.95
-30.34
-24.92
-23.58
Diabetes
-1.49
-31.22
-17.48
-21.21
-23.01
0.63
0.27
German
19.54
-26.05
-25.83
-26.76
227.29
-15.24
-15.02
Student
-33.13
-30.18
-28.73
-29.51
-31.59
22.922
-26.99
Wine
0.32
-0.13
-10.12
-8.62
-6.92
13.34
13.36
# best
0
0
1
9
on 9 out of 12 data sets. This implics that characteristic circuit, especially with structure learning, is a competitive density estimator compared with SOTA PCs. Actually, a-stable Ieaf distributions are more suitable choice for characteristic circuits on heterogencous tabular data.
Conclusion
We introduced characteristic circuits (CCs), novel circuit-based characteristic function estimator that leverages an arithmetic circuit with univariate characteristic function leaves for modelling the joint of heterogeneous data distributions. Compared to existing PCs, characteristic circuits model the characteristic function of data distribution in the continuous spectral domain, providing a unified view for discrete and continuous random variables, and further model distributions that do have closed-form probability density functions. We showed that both joint and marginal probability densities can be computed exactly and efficiently using characteristic eircuits. Finally, we empirically showed that characteristic circuits approximate the data distribution better than ECF, measured by the squared characteristic function distance, and that characteristic circuits can also be competitive density estimators as they win on 9 out of heterogeneous data sets compared to SOTA models.
There several avenues for future work. For instance, sampling from characteristic functions and, in turn, characteristic circuits is not straightforward. One should explore existing literature discussing sampling from CFs [Devroye, 1986, Ridout, 2009, Walker, 2017], and adapt them sampling from CCs. The circuit structure of characteristic circuits generated by structure learning has a high impact on the performance of the characteristic circuit, and therefore an inappropriate structure can limit the modelling power of characteristic circuits. Therefore, one should explore parameter learning of characteristic circuits on more advanced circuit structures [Peharz et al., 2020] and, in particular, using normalizing flows, resulting in what could be called characteristic flows.
Broader Impact. Our contributions broadly aimed at improving probabilistic modelling. CCs could be used to develop more scalable and more accurate probabilistic models, in particular over mixed domains as common economics, social science, medicine. Scaling even bigger mixed models can open even more potential applications, but also may require careful design to handle overconfidence and failures of CC.
Acknowledgments and Disclosure of Funding
This work was supported by the Federal Ministry of Education and Research (BMBF) Competence Center for AI and Labour ("K"mpAKI", FKZ 02L19C150), It benefited from Hessian Ministry of Higher Education, Research, Science and the Arts (HMWK; projects "The Third Wave of Al" and "The Adaptive Mind"), and the Hessian research priority program LOEWE within the project "WhiteBox". . MT acknowledges funding from the Academy of Finland (grant number 347279).
10

---

References
Kareem Ahmed, Stefano Teso, Kai-Wei Chang, Guy Van den Broeck, and Antonio Vergari. Semantic probabilistic layers for neuro-symbolic learning. In Advances in Neural Information Processing Systems (NeurIPS), volume 35, pages 11944-29955 2022.
Abdul Fatir Ansari, Jonathan Scarlett, and Harold Soh. characteristic function approach to deep implicit generative modeling. In IEEE/CVF Conference on Computer Vision and Puttern Recognition (CVPR), pages 7478-7487, 2020.
YooJung Choi, Antonio Vergari, and Guy Van den Broeck. Probabilistic circuits: A unifying framework for tractable probabilistic models. Technical report, UCLA, 2020.
Kacper Chwialkowski, Aaditya Ramdas, Dino Sejdinovic, and Arthur Gretton. Fast two-sample testing with analytic representations of probability measures. In Advances in Neural Information Processing Systems (NeurIPS), volume 28, 2015.
Alvaro HC Correia, Gennaro Gala, Erik Quaeghebeur, Cassio de Campos, and Robert Peharz. Con- tinuous mixtures tractable probabilistic models. In AAAI Conference on Artificial Intelligence, volume 37, pages 7244-7252, 2023.
Harald Cramér. Mathematical methods of statistics, volume 26. Princeton university press, 1999.
Meihua Dang, Antonio Vergari, and Guy Broeck. Strudel: Learning strucuued-decomposalae probabilistic circuits. In International Conference on Probabilistic Graphical Models (PGM), pages 137-148, 2020.
Meihua Dang, Antonio Vergari, and Guy Van den Broeck. Strudel: A fast and accurate learner of strucureeddeccompsabbe probabilistic eircuits. International Journal of Approximate Reasoning, 140:92-115, 2022.
Adnan Darwiche. A differential approach to inference in bayesian networks. Journal of the ACM (JACM), 5083):2800--2 305, 2003.
Richard A Davis, Thiago do Rêgo Sousa, and Claudia Klüppelberg. Indirect inference for time series using the empirical characteristic function and control variates. Journal of Time Series Analysis, (2(5-6):633-682 2021.
Luc Devroye. An automatic method for generating random variates with given characteristic function. SIAM journal on applied mathematics, 46(4))698-719 1986.
Nicola Di Mauro, Gennaro Gala, Marco lannotta, and Teresa MA Basile. Random probabilistic circuits. Uncertainty in Artificial Intelligence (UAI), pages 1682-1691, 2021.
Jan Eriksson and Visa Koivunen. Charactriisic-function-aaad independent component analysis. Signal Processing, 83(10)22155-2288 2003.
Andrey Feuerverger and Roman Mureika. The empirical characteristic function and its applications. The annals of Staristics, pages 88 88-97, 1977.
Abram Friesen and Pedro Domingos. The sum- uum-roduuct theorem: A foundation for learning tractable models. In International Conference on Machine Learning (ICML), pages 1919-1918,.. 2016.
Guido Fubini. Sugli integrali multipli. In Rendiconti, volume 16, pages 608-614, Accademia Nazionale dei Lincei, 1907.
Robert Gens and Pedro Domingos. Learning the structure of sum con-prrduct networks. In International Conference on Machine Learning (ICML), pages 873 773-880,20 2013.
Chenlu Ke and Xiangrong Yin. Expected conditional characteristic function- based measures for testing independence. Journal of the American Statistical Association, 2019.
John I. Knight and Jun Yu. Empirical characteristic function in time series estimation. Econometric
Theory, 18(3):691-21,, 2002.

---

Sangyeol Lee, Simos G Meintanis, and Charl Pretorius. Monitoring procedures for strict stationarity based on the multivariate characteristic function. Journal of Multivariate Analysis, 189:104892. 2022.
David Lopez-Paz, Philipp Hennig, and Bernhard Schölkopf. The randomized dependence coefficient. In Advances in Neural Information Processing Systems (NeurIPS), volume 26, 2013.
Eugene Lukacs. A survey of the theory of characteristic functions. Advances in Applied Probability, 4(1):1-37, 1972.
J Huston McCulloch. Simple consistent estimators of stable distribution parameters. Communications in statistics-simalation and computation, 15(4): 100:)1109-11666 1986.
Alejandro Molina, Antonio Vergari, Nicola Di Mauro, Sriraam Natarajan, Floriana Esposito, and Kristian Kersting. Mixed sum-product networks: A deep architecture for hybrid domains. In AAAI Conference on Artificial Intelligence, volume 32, 2018.
Kevin P Murphy. Machine learning: probabilistic perspective. MIT press, 2012.
John P Nolan. Multivariate elliptically contoured stable distributions: theory and estimation. Compu- tational statistics, 28:2067-2089, 2013.
Robert Peharz, Steven Lang, Antonio Vergari, Karl Stelzner, Alejandro Molina, Martin Trapp, Guy Van den Broeck. Kristian Kersting, and Zoubin Ghahramani. Einsum networks: Fast and scalable learning of tractable probabilistic circuits. In International Conference on Machine Learning (ICML), pages 7563-7574, 2020.
Martin S Ridout.
Generating random numbers from distribution specified by its laplace transform. Statistics and Computing, 19:439 2009.
Zoltán Sasvári. Multivariate characteristic and correlation functions, volume 50. Walter de Gruyter, 2013.
Nairi Sedrakyan. About the applications of one useful inequality. Kvant Journal, 97(2):42-44, 1997.
Nikil Roashan Selvam, Guy Van den Broeck, and YooJung Choi. Certifying fairness of probabilistic circuits. AAAI Conference on Artificial Intelligence, volume 37, pages 1-278-12284 2023.
Xiaoting Shao, Alejandro Molina, Antonio Vergari, Karl Stelzner, Robert Peharz, Thomas Liebig, and Kristian Kersting. Conditional sum functions. International Journal of Approximate Reasoning, 140:298-313, 2022.
sum- product networks: Modular probabilistic circuits via gate
Andy Shih and Stefano Ermon. Probabilistic circuits for variational inference in discrete graphical models. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, pages 4635 4646, 2020.
Bernard W Silverman. Density estimation for statistics and data analysis. Routledge, 2018.
Bharath K Sriperumbudur, Arthur Gretton, Kenji Fukumizu, Bernhard Schölkopf, and Gert RG Lanckriet. Hilbert space embeddings and metrics on probability measures. The Journal of Machine Learning Research, 11:1517-1561, 2010.
Liangjun Su and Halbert White. A consistent characteristic function-based test for conditional independence. Journal of Econometrics, 141(():807-82) 2007.
Martin Trapp, Robert Peharz, Hong Ge, Franz Pernkoff, and Zoubin Ghahramani. Bayesian learning of sum- sum-produu -rodduct networks. In Advances in Neural Information Processing Systems (NeurIPS), volume 32, 2019.
Martin Trapp, Robert Peharz, Franz Pernkopf, and Carl Edward Rasmussen. Deep structured mixtures of gaussian processes. International Conference on Artificial Intelligence and Statistics (AISTATS), pages 2251-2261, 2020.
12

---

Antonio Vergari, Alejandro Molina, Robert Peharz, Zoubin Ghahramani, Kristian Kersting, and Isabel Valera. Automatic bayesian density analysis. In AAAI Conference Artificial Intelligence, volume 33, pages 5207-5215, 2019.
Antonio Vergari, YooJung Choi, Anji Liu, Stefano Teso, and Guy Van den Broeck. A compositional atlas of tractable circuit operations for probabilistic inference. In Advances Neural Information Processing Systems (NeurIPS), volume 34, pages 15189-13201 2021.
Stephen G Walker. A laplace transform inversion method for probability distribution functions. Statistics and Computing, 27924449-444, 2017.
Benjie Wang, Matthew R Wicker, and Marta Kwiatkowska. Tractable uncertainty for structure
learning. International Conference Machine Learning (ICML), pages 23131-23150, 2022.
Xia Wang and Yongmiao Hong. Characteristic function based testing for conditional independence: A nonparametric regression approach. Econometric Theory, 34(4):815-849 2018.
Jun Yu. Empirical characteristic function estimation and its applications. Econometric reviews, 2004.
Zhongjie Yu, Fabrizio Ventola, and Kristian Kersting. Whittle networks: A deep likelihood model for time series. In International Conference on Machine Learning (ICML), pages 12177-12186,
2021a.
Zhongjie Yu, Mingye Zhu, Martin Trapp, Arseny Skryagin, and Kristian Kersting, Leveraging probabilistic circuits for nonparametric multi-output regression. In Uncertainty in Artificial 2021b.
Intelligence (UAI). pages
Matej Zečević, Devendra Singh Dhami, Athresh Karanam, Sriraam Natarajan, and Kristian Kersting. Interventional sum- num-product networks: Causal inference with tractable probabilistic models. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, pages 15019-15031, 2021.
Honghua Zhang, Brendan Juba, and Guy Van den Broeck. Probabilistic generating circuits. In International Conference on Machine Learning (ICML), pages 12447-12457, 2021.
Han Zhao, Tameem Adel, Geoff Gordon, and Brandon Amos. Collapsed variational inference for sum-product networks. In International Conference Machine Learning (ICMI., pages 1310-1318, 2016.
13


Reviews:
[{"review_id": "ZYVn1qgenB", "reviewer": "Reviewer_1MK1", "summary": "This paper studies the use of characteristic functions as probabilistic models for heterogeneous data and proposes characteristic circuits (CC) for their representations. The authors propose efficient algorithms for computing (marginal) densities with CCs and show that parameters of CCs can be learned by minimizing the CFD between CC and ECF. The authors also show that CCs achieve strong performance not only on synthetic data but also on some commonly used density estimation benchmarks. ", "questions": "In Section 4.2, the authors proposes to do parameter learning by minimizing the CFD between CC and ECF because the likelihood of CC is not guaranteed to be tractable. Yet I wonder if it is possible to discuss the relationship between CFD and likelihood.", "limitations": "The structure learning algorithm seems more of an adaptation of the existing structure learning algorithms for SPNs. This is not a major issue as structure learning of circuits has been a very challenging problem and probably not a main focus of this work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "To the best of my knowledge, the use of characteristic functions as a new language for probabilistic modeling, especially as a unified framework for heterogeneous data, is very novel. The empirical results is also very strong. I believe this work opens a brand new avenue for density estimation.", "weaknesses": "As a non-expert, I spent a lot of time on the background section; despite the uniqueness part in the inversion theorem, it is not completely intuitive how a probability measure is encoded as its characteristic function. It would be helpful if the authors could provide at least one simple example.\n\nAuthors use too many acronyms throughout the paper, especially in Section 5; it is not easy for me as a reader to distinguish between CC-N, RS, SL, CFD and etc. \n\nFor non-expert readers like me, more details on the empirical evaluations (in the main paper) could be helpful: e.g. how are the likelihoods measured for the heterogeneous datasets? are they computed via numerical integrations? etc.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the feedback and questions. \n\n> How is the probability measure encoded as a CF?\n\n - The characteristic function of a probability measure is its Fourier transform and, hence, can be obtained through the application of the Fourier transform. However, in our work, we do not start from the probability measure but directly model the characteristic function instead. This allows us to implicitly learn any probability measure by instead learning its spectral form. We refer to [Sasv&#225;ri, 2013] for a more detailed discussion. \n\n> Details on the empirical evaluations:\n\n - The likelihoods in the empirical evaluations are computed based on the inversion theorem. For discrete leaves and Gaussian leaves, the likelihoods can be computed analytically. While for $\\alpha$-stable leaves, the likelihoods are computed via numerical integration using quadrature. In general, it depends on the form of the characteristic function that is assumed at the leaf nodes. For example, one might relax the assumption that it is specified by a parametric family and could learn the characteristic functions directly. However, doing so is more involved as one has to ensure that the properties listed in Section 3.2. are still fulfilled. We believe this to be a promising future avenue. Once likelihoods at the leaves are computed, they are propagated bottom up following the inversion theorem in Section 4.1. We will improve the description in the updated manuscript.\n\n> Acronyms:\n\n - We will reduce the use of acronyms (RS, SL, etc.) in the updated manuscript for better readability and thank the reviewer for pointing this out. \n\n> Regarding the question on the relationship between CFD and likelihood:\n\n - Connections between maximum likelihood estimation (MLE) and minimizing a distance (e.g., the CFD) to the empirical characteristic function (ECF) is indeed an interesting question. Minimizing the CFD to the ECF can be beneficial if no tractable form of the likelihood exists but the characteristic function can be tractably evaluated. As discussed in prior works (e.g., [Yu, 2004]), minimizing a distance function to the ECF is most related to moment-matching approaches, but can result in more accurate fitting results. An interesting future direction could be a hybrid objective in which tractability of either the likelihood function or the characteristic function is exploited. We thank the reviewer and will add further detail and a discussion on the topic to the revised version. \n***\n[Sasv&#225;ri, 2013] Zolt&#225;n Sasv&#225;ri. \"*Multivariate characteristic and correlation functions.*\" volume 50. Walter de Gruyter, 2013.  \n[Yu, 2004] Jun Yu. \"*Empirical characteristic function estimation and its applications.*\" Econometric reviews, 2004.\n"}, {"review_id": "9dBhU7Hm2Q", "reviewer": "Reviewer_pe9b", "summary": "This manuscript proposes a framework for directly representing characteristic function of random variables by a probabilistic circuit-like structure. Unlike the ordinal probabilistic networks, the proposed framework, characteristic circuits, can treat distributions that do not have closed-form expressions for the density, or even marginals of discrete and continuous random variables. This is because the characteristic function provides a unified view for both discrete and continuous random variables. As a result, the characteristic circuit can treat broader class of distributions than the ordinal probabilistic circuits. Despite this, it is proved that the characteristic circuit keeps tractability of computing densities and marginals, which is an important query for probabilistic inference. Also, the parameter and circuit-structure learning algorithms for characteristic circuits are given. The experiments showed that the proposed characteristic circuits perform well for density estimation task on heterogeneous data sets, which includes both discrete and continuous variables.", "questions": "Within the queries that are tractable for the ordinal probabilistic circuits, are there any other tractable queries than marginal for characteristic circuits? Or, are there any queries that is proven to be hard (e.g., NP-complete) for characteristic circuits?", "limitations": "I think the authors adequately addressed the limitations.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "I think that representing a characteristic function by a circuit is a simple yet strong idea for representing broader class of distributions. Also, proposing an algorithm for computing marginals on characteristic circuits is really good, because it inherits the strengths of the original probabilistic circuits that some rich inference queries are tractable in time proportional to the size of the circuit; although it only proves the marginal query, I think this query is one of the most important one for probabilistic inference. The experimental results truly support the usefulness of characteristic circuits when applied to density estimation task where the evaluation metric is the test log-likelihood. Since the original probabilistic circuits also show their strengths in this task, I think the selection of tasks is appropriate.", "weaknesses": "It is not the first attempt to represent a generating function regarding random variables directly; the first one (as far as I know) is:\nProbabilistic Generating Functions https://arxiv.org/abs/2102.09768 (published in ICML 2021).\nThis represents the probability generating function directly, thus I think this framework is for discrete variables only. However, to clearly show the standing position of this paper, the comparison with this work should be clearly done in the main article.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback and the suggested related work. \n\n> Comparison to PGCs\n\n - Indeed, PGCs are related to CCs as both can be considered to represent the probability distribution using its generating function rather than its density function. We added a discussion and further details on how the two approaches relate to the updated manuscript. The key difference between PGCs and CCs is that, while PGCs can only represent discrete probability distributions that admit a probability generating function representation (finite countable), CCs can represent any probability distribution as every probability measure has an associated characteristic function. Interestingly, compared to directly modeling the density/mass function of a distribution, we can perform model fitting even in cases where a density w.r.t. the Lebesgue or counting measure does not exist or is not tractable to evaluate by minimizing the CFD to the empirical characteristic function. \n\n> Are there any other tractable queries for characteristic circuits? \n\n - Although not discussed in detail in the paper, the moments of any CCs can be computed tractably through differentiation. Even though the current work focuses on a unified view by moving to the spectral domain, we believe this to be a particularly useful property and added further details to the updated manuscript. \n - Sampling from a characteristic function is generally not straightforward. There has been literature discussing sampling from CFs [Devroye, 1986, Ridout, 2009, Walker, 2017] and we believe these sampling algorithms can be adapted to sampling from CCs in future works. We thank the reviewer for pointing this out and will add a discussion to the manuscript.\n***\n[Devroye, 1986] Luc Devroye, \"*An automatic method for generating random variates with a given characteristic function.*\" SIAM journal on applied mathematics, 1986.  \n[Ridout, 2009] Martin S Ridout,. \"*Generating random numbers from a distribution specified by its Laplace transform.*\" Statistics and Computing, 2009.  \n[Walker, 2017] Stephen G Walker. \"*A Laplace transform inversion method for probability distribution functions.*\" Statistics and Computing, 2017.\n"}, {"review_id": "d9QGejXPdf", "reviewer": "Reviewer_HuCd", "summary": "The paper introduces characteristic circuits (CCs), a new family of tractable probabilistic models (TPMs) that leverages univariate characteristic functions as leaves of probabilistic circuits (PCs) for modelling a tractable joint of heterogeneous data distributions (i.e. with both continuous and discrete variables).\nCCs model the characteristic function of the data distribution in the continuous spectral domain (cf. Equation 1), thus providing a unified framework for discrete and continuous random variables.\nAs a consequence, one of the main advantage of CCs is that they can model distributions that do not have closed-form probability density functions, such as $\\alpha$-stable distributions.\nImportantly, authors also show that CCs allow exact and efficient computation of joint and marginal probabilistic queries.\nCCs are evaluated on two synthetic datasets and 12 heterogeneous real-world tabular datasets.\n", "questions": "- Is sampling possible from CCs? If yes, can we know how CC samples compare with the ones of standard PCs? If not, what are the challenges?\n- Can you elaborate a bit more on what precisely you mean with \"unified view for discrete and continuous random variables\" (line 57)? While, to some extent, I understand what author mean, one may think \"but even standard PCs can handle heterogeneous data\". I think being more precise here can improve this major selling point of the paper.\n- Can you elaborate a bit more on lines 230-231-232? Why MLE is not tractable? How does Eq. 14 relate to MLE? (Also lines 248-249-250 are unclear to me)\n", "limitations": "Limitations are not explicitly addressed.\nIt looks like sampling can be one of these.\n\nMinors:\n- In Lemma 4.2, I think there's no explanation of what $\\tau$ and $E(\\mathcal{T}_i)$ represent. I know it's notation related to induced trees, but it is not introduced in the text.\n- In line 175, there's no $x$ occuring in the definition of $\\phi_{L_\\text{Normal}}(t)$, why?", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The research is definitely original as it proposes a new class of TPMs with many (novel) benefits\n- The model naturally lends itself to modelling heterogeneous data\n- The model allows to use distributions that do not have closed-form expressions, such as $\\alpha$-stable distributions, something that is not possible in current PCs\n- Despite having input units with no closed-form expressions, CCs can still deliver exact marginalisation \n\nOverall, a solid contribution.\n\n", "weaknesses": "- From experiments, it looks like inappropriate structure can limit the modelling power of CCs. This is can prevent using CCs when a good structure is not available.\n- It's unclear how reliable/precise numerical integration can be (lines 128-129-130)\n- Sampling it's an important inference routine of PCs yet it is not discussed at all, and it's unclear if CCs can provide it", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for pointing out both the strength and possible weakness of our work. \n\n> Inappropriate structure can limit the modelling power:\n\n - Similar to related modelling families (e.g., PCs, PGCs), the structure can have a high impact on the performance of the CC. To mitigate this issue, we proposed the first structure learning algorithm adapted from the well-known algorithm by [Gens and Pedro, 2013] for PCs. Note that structure learning of circuits (PCs, CCs alike) is a challenging and open task and further investigation is needed. However,  an approach similar to the one taken in Einsum networks [Peharz et al. 2020] combined with minimization of the CFD could be a promising future direction.   \n\n> Reliability of numerical integration:\n\n - We ran additional experiments with an increasing number of sample points to verify the reliability of the numerical integration through quadrature. The results indicate that a low number of sample points is sufficient as numerical integration is only required on the real line (1D). We thank the reviewer for pointing this out and will include the results into the Appendix and add further discussion on the reliability of the numerical integration. \n\n> Sampling:\n\n - Sampling from a characteristic function is generally not straightforward. There has been literature discussing sampling from CFs [Devroye, 1986, Ridout, 2009, Walker, 2017] and we believe these sampling algorithms can be adapted to sampling from CC in future works. Thanks for pointing this out, we will add this to the discussion of interesting future work.\n\n> Unified view:\n\n - PCs do not naturally provide a unified view and treat discrete and continuous RVs differently. For discrete RVs probabilities or mass values are computed w.r.t. the  counting measure, while for continuous RVs the reference measure is the Lebesgue measure. Moreover, RVs distributed according to a singular (continuous) distribution can typically not be represented at all. This dependence on the base measure is hidden in PCs and can result in challenges when it comes to learning these models in heterogeneous domains. For example, a model might focus only on maximizing the likelihood w.r.t. the Lebesgue measure during fitting. Consequently, prior works have suggested discretising the domain of continuous RV (see MSPNs), which introduces new challenges. Moving away from the dependence on the base measure by representing the distribution through its characteristic function, which is independent of the base measure, elevates this issue. Hence, CCs provide a truly unified view compared to PCs. We will clarify the “unified view” in the revised paper to better reflect our contribution.\n\n> MLE at the root and at a leaf node:\n\n - In parameter learning, maximizing the likelihood at the root of a CC needs to apply the inversion theorem to CC for each training data. When leaf nodes do not have a closed-form density function, numerical integration has to be employed to obtain the density value given data. This makes the MLE at the root not guaranteed to be tractable. \n - We thank the reviewer for raising this interesting question about the relationship between minimizing the distance and MLE, which is similar to the question from reviewer 1MK1. Connections between maximum likelihood estimation (MLE) and minimizing a distance (e.g., the CFD) to the empirical characteristic function (ECF) is indeed an interesting question. Minimizing the CFD to the ECF can be beneficial if no tractable form of the likelihood exists but the characteristic function can be tractably evaluated. As discussed in prior works (e.g., In [Yu, 2004]), minimizing a distance function to the ECF is most related to moment-matching approaches, but can result in more accurate fitting results. We will add further detail and a discussion on the topic to the revised version. \n - Creating leaf nodes in structure learning. Leaf nodes are created by fitting the estimated distribution to local data during structure learning. When closed-form density/mass function is available at a leaf, the leaf parameters can be estimated via MLE. In the case of ECF leaves, the leaf nodes are created from local data following the definition of ECF (in line 134). When there is no closed-form density, e.g. $\\alpha$-stable distributions, the algorithm in [McCulloch, 1986] is employed to estimate the parameters at the $\\alpha$-stable leaves. We apologise that we did not specify this detail in the manuscript and will add the above to lines 248-250 for better clarification.  \n\n> Minors:\n - Induced trees notation: Thanks for pointing this out, we will add one section in the Appendix to briefly introduce the notation of induced trees.\n - Indeed there is no x in the definition of the characteristic function at the leaf, because a characteristic function is a function of t, as illustrated in Eq (1).\n***\n[Gens and Pedro, 2013] Robert Gens and Domingos Pedro. \"*Learning the structure of sum-product networks.*\" In ICML, 2013.  \n[Peharz et al. 2020] Robert Peharz et al. \"*Einsum networks: Fast and scalable learning of tractable probabilistic circuits.*\" In ICML, 2020.  \n[Devroye, 1986] Luc Devroye, \"*An automatic method for generating random variates with a given characteristic function.*\" SIAM journal on applied mathematics, 1986.  \n[Ridout, 2009] Martin S Ridout. \"*Generating random numbers from a distribution specified by its Laplace transform.*\" Statistics and Computing, 2009.  \n[Walker, 2017] Stephen G Walker. \"*A Laplace transform inversion method for probability distribution functions.*\" Statistics and Computing, 2017.  \n[Yu, 2004] Jun Yu. \"*Empirical characteristic function estimation and its applications.*\" Econometric reviews, 2004.  \n[McCulloch, 1986] J. Huston McCulloch. \"*Simple consistent estimators of stable distribution parameters.*\" Communications in statistics-simulation and computation, 1986.\n\n"}, {"review_id": "pS79jWRDuM", "reviewer": "Reviewer_twZC", "summary": "This work proposes a new tractable probabilistic model called characteristic circuits or CC. The CC is defined in a similar way to probabilistic circuits (PCs) but with leave nodes defined as characteristic functions instead of the distributions as in PCs. The authors further show the computation of marginals and the learning algorithms for CC. Empirical evaluations on both synthetic datasets and UCI datasets are presented.", "questions": "- Can the authors elaborate on the motivation for CCs, that is, when one would prefer CC over PC?\n- Can the authors provide some discussions on the expressiveness and tractable queries of CC?\n- For the empirical results on UCI datasets, I wonder if the improvements are from CC itself or from the alpha-stable distributions. What would happen if the continuous leaves in MSPN are defined as alpha-stable distributions? Such an ablation study might make the results more convincing.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "- This paper is generally well-written, with sufficient backgrounds provided to help readers understand the proposed new model.\n- The authors show that CC shares the same efficient marginal computations as in PCs.\n- CC provides a unified view for mixed continuous and discrete distributions. Also, the \\alpha-stable distributions are less explored in the previous literature of tractable probabilistic models to my knowledge and the use of these seems help deliver good performance in the UCI experiments.", "weaknesses": "- From what is presented, it seems that the authors simply rewrite the distribution nodes and computations of PCs into their characteristic function duals. It is unclear what are the key differences between CC and PCs and when would one prefer one over the other. I don't think the unified view of the discrete and continuous distributions serves as a strong motivation since mixed SPN can also handle the mixed distributions.\n- To further illustrate the previous point, one would expect to see investigations on expressiveness, such as are there any distributions that can be tractably represented by CCs but not PCs, or investigations on tractable operations, such as what probabilistic queries would be intractable for PC but tractable for CC, while none of these are discussed in this work.\n- A proof for the validity of the marginal computations seems to be missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the feedback and questions.\n\n> Key difference between CCs and PCs:\n - PCs do not naturally lend themselves to a unified view over heterogeneous data domains, while CCs more naturally provide a framework to model high-dimensional mixed data distributions. To highlight this, recall that PCs are formulated over density/mass functions which is the Radon–Nikodym derivative w.r.t. some base measure. In heterogeneous domains, the relationship to the base measure becomes involved as dimensions might have a density w.r.t. different base measures. This fact is typically hidden in PCs and results in challenges when learning such models over heterogeneous data domains as, for example, gradient-based parameter learning will now depend on different base measures depending on the dimensions considered. This can result in undesirable behaviour and is elevated, for example, in MSPNs by discretizing the continuous domain, hence, ensuring the same base measure for all dimensions. However, discretization introduces challenges going beyond this rebuttal. CCs, on the other hand, evaluate this problem in a more principled way by instead modelling the Fourier transform of the probability measure directly. This makes the learning and modelling process independent of the base measure and provides a truly unified view compared to PCs. We hope that this expose better explains the conceptual difference between CCs and PCs.\n\n> Expressiveness and tractable queries:\n - We agree that investigating the expressive efficiency and tractability of CCs is an interesting avenue. Although not discussed in detail in the paper, the moments of any CC can be computed tractably through differentiation given that the leaf nodes allow tractable differentiation. Even though the current work focuses on a unified view by moving to the spectral domain, we believe this to be a particularly useful property and added further details to the updated manuscript. We leave a theoretical analysis of the expressive efficiency of CCs for future work.\n\n> Proof of marginal computation:\n - A proof sketch of marginalization is given in lines 221 to 225 and we will add a more detailed proof in the appendix. \n - Proof sketch: \nFollowing lines 216 to 225, we have assumed that the circuit decomposes all dimensions into univariate leaves, RVs $Z = X \\cup Y$, $t = t_X \\cup t_Y$, and we aim to compute $\\varphi_X(t_X)$.  \nThen for any leaf node, we have \n$\\varphi_L(t_j) =  1$ if $ t_j = 0$, and  $\\varphi_L(t_j)$ otherwise, by definition of CFs.    \nLet $P$ be a product node that splits at least one $Y_j$ from its scope into a single child and let this child be denoted as $N_j$, then   \n$\\varphi_P(t \\cup 0) = \\varphi_{N_j}(0) \\prod_{N \\in ch(P)\\setminus{N_j}} \\varphi_{N}(t_{\\psi(N)}) = \\varphi_{P\\setminus{N_j}}(t)$,  \nwhere $\\varphi_{N_j}(0)=1$.\nBy the assumption that sum nodes are convex combinations (weights sum up to one) and recursive application of the above, one can show that any marginal distribution can be obtained tractably in CCs.\n\n> Choice of CC over PC:\n\n - There are various tasks in which CCs are preferable over PCs. In particular, as outlined before, CCs provide a more principled and natural representation in the case of heterogeneous data domains. Moreover, CCs enable the modeling and learning of distributions that do not have an analytical density function. Lastly, CCs provide an efficient representation of moments even in case densities are not available in closed form as CCs circumvent the challenge of integration in this case and instead only require differentiation of the model.\n\n> $\\alpha$-stable distribution leaves and MSPNs:\n\n - We agree that studying the combinations of MSPNs and CCs is an interesting direction. Henceforth, we will provide additional results using MSPNs as a construction algorithm for the CC structure. However, we want to stress that MSPNs and CCs are conceptually very different as MSPNs aim to model heterogeneous domains non-parametrically through discretization, while CCs directly model the characteristic function of the mixed distribution. Therefore, CCs provide a more flexible framework and allow for meaningful parameter learning that is more suited to mixed data domains. Moreover, we want to note that we empirically observed improvements by fitting CCs (work in the spectral domain) also in the case $\\alpha$-stable distribution has not been employed, see results CC-P in Tab. 2, indicating that CCs are a promising modeling family even if tractable densities exist.\n\n\n\n\n\n\n"}, {"review_id": "DextnnbkKA", "reviewer": "Reviewer_6Se4", "summary": "I am not qualified to review this paper.", "questions": "I am not qualified to review this paper.", "limitations": "I am not qualified to review this paper.", "rating": 10, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "I am not qualified to review this paper.", "weaknesses": "I am not qualified to review this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}]

Author rebuttal:

Meta-review: This paper proposes a great new member of the probabilistic circuit family, representing characteristic polynomials. It might turn out to be a seminal paper in modeling tractable distributions.
Decision: Accept (oral)